コンピュータ科学特論Ⅲ

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

授業計画
1	１．ガイダンス・配列と整列
2	２．基本的なデータ構造（スタック・キュー）
3	３．探索
4	４．最小全域木１　クラスカルのアルゴリズム
5	５．最小全域木２　プリムのアルゴリズム
6	６．最短路探索１　ダイクストラのアルゴリズム
7	７．最短経路探索２　ベルマンフォードのアルゴリズムとワーシャルフロイドのアルゴリズム
8	８．分割統治法
9	９．動的計画法（１）
10	１０．動的計画法（２）
11	１１．計算可能性
12	１２．計算量・計算複雑性
13	１３．充足可能性問題
14	１４．課題学習
15	１５．クックの定理・まとめ

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