筑波大学教育課程編成支援システム

GB21802 プログラミングチャレンジ

2.0 単位, 3・4 年次, 春AB 火3,4
アランニャ, クラウス, 櫻井鉄也

授業概要

競技プログラミングの課題を用いて様々なアルゴリズムについて勉強する。プログラミング実装に集中される講義。内容:動的プログラミング、グラフ、データ構造、文字列操作、計算幾何、等。

備考

授業形態

演習

学位プログラム・コンピテンスとの関係

・汎用コンピテンス
2. 批判的・創造的思考力
4. 広い視野と国際性
・専門コンピテンス
2. ソフトウエアサイエンス分野の専門能力
6. 実践的技術力と問題解決能力
7. 情報専門技術者としての倫理

授業の到達目標(学修成果)

本講義では、様々な問題に対して適切なアルゴリズムを選び、そのアルゴリズムを正しく実装することを目標とする。これまでに学習したアルゴリズムとプログラミング技術の具体的な使い方を学ぶ。

The goal of this course is to learn how to identify the necessary algorithm to solve a given program, and how to correctly implement it. This course aims at giving a practical view of previously learned algorithms and programming techniques.

キーワード

アルゴリズム, プログラミング, 問題解決, プログラミングコンテスト

授業計画

第1回	講義概要・プログラミングコンテストとは?・アドホック問 Course Introduction - What are programming contests? - Introductory Problems
第2回	データ構造:1Dベクトル・2Dベクトル・セット・木構造・UFDS Data Structures:1D Vector, 2D Vector, Sets, Tree Structures, UFDS
第3回	探索方:完全探索・2分探索・グリーディ−方 Search Methods: Full Search, Binary Search, Greedy Search
第4回	動的プログラミング:グリード探索、MaxSum、LIS、MaxSum、TSP Dynamic Programming: Grid Search, MaxSum, LIS, MaxSum, TSP
第5回	グラフI:グラフ構造、BFS、DFS、フルードフィール、TopoSort、Spanning Tree Graph I:Graph Structure, BFS, DFS, Flood Fill, TopoSort, Spanning Tree
第6回	グラフ II:最短経路、フロー Graph II:Shortest Paths, Flow
第7回	数学:数論・組合せ問題 Mathematics: Number Theory, Combinatoric Problems
第8回	幾何:線・角度・円・三角・ポリゴン Geometry: Lines, Angles, Circles, Triangles, Polygons
第9回	文字列:文字列探索・エディット距離・Suffix Array Strings: String Matching, Edit Distance, Suffix Array
第10回	ファイナルリミックス:今まで勉強したアルゴリズムを複数使われる問題 Final Remix: Problems using multiple of the algorithms studies in this course.

履修条件

基本的なプログラミングの知識(コンパイル、ループ、if-then-elseなど)[C,C++ or Java]
Basic programming concepts (Compiling, loops, if-then-else operators, etc.) [C, C++ or Java]

成績評価方法

この講義は期末試験を実施しない。毎週プログラミング課題の提出によって評価。

This course does not implement a final examination. The evaluation is based on weekly programming assignments.

学修時間の割り当て及び授業外における学修方法

学生が少なくとも毎週プログラミング課題2問を提出する必要があります。「A」成績を達成するため、少なくとも毎週課題4問を提出する必要があります。

The student must submit at least 2 programming exercises per week. To achieve an "A" grade, the student must submit at least 4 programming exercises per week.

教材・参考文献・配付資料等

1. Steven Halim, Felix Halim,"Competitive Programming", 3rd edition.
2. Steven S. Skiena, Miguel A. Revilla,"Programming Challenges", Springer, 2003
3. 秋葉拓哉、岩田陽一、北川宜稔,『プログラミングコンテストチャレンジブック』

MANABAでレクチャースライドを配布します。

We will distribute lecture notes on Manaba.

オフィスアワー等(連絡先含む)

アランニャ, クラウス火・木 9:00~11:30
SB1012 (Advanced Research Building B / 総合研究棟B) 029-853-6574 23051014 http://conclave.cs.tsukuba.ac.jp/

その他(受講生にのぞむことや受講上の注意点等)

授業が日本語で行います。配布資料は英語です。課題提出や教員とのやり取りはどちらでも可。
Lectures are held in Japanese. Class materials are in English. Reports and communication with the professor can be in either language.

シラバス参照