コンピュータ科学特論Ⅱ

授業テーマ	アルゴリズムとデータ構造再入門及び計算複雑性理論入門
授業のねらい・到達目標	効率の良いプログラムを作るには，良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では，データ構造とアルゴリズム設計の基本を，実際にプログラミングをしながら学ぶ．後半では，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
授業の方法	前半は，プログラミングコンテストに出題された問題を題材に，講義と演習を織り交ぜながら進める．後半は，講義形式で行う．
事前学修・事後学修，授業計画コメント	事前・事後とも，演習に取り組むこと．

授業計画
1	ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）・配列と整列
2	基本的なデータ構造（スタック・キュー）
3	探索
4	最小全域木１　クラスカルのアルゴリズム
5	最小全域木２　プリムのアルゴリズム
6	最短路探索１　ダイクストラのアルゴリズム
7	最短経路探索２　ベルマンフォードのアルゴリズムとワーシャルフロイドのアルゴリズム
8	分割統治法
9	動的計画法（１）概念・一般論
10	動的計画法（２）応用
11	計算可能性
12	計算量・計算複雑性
13	充足可能性問題（１）前半
14	充足可能性問題（２）後半
15	クックの定理・まとめ（これまでの復習・解説を行い授業の理解を深める）

その他
教科書	講義時に資料を配布する．
参考書	J. Kleinberg, E. Tardos 著『アルゴリズムデザイン』共立出版 2008年秋葉拓哉・岩田陽一・北川宜稔著『プログラミングコンテストチャレンジブック第２版』毎日コミュニケーションズ 2014年第2版
成績評価の方法及び基準	授業内テスト(20%)、授業参画度(80%)
オフィスアワー	月曜18時〜19時