【授業の目的】
計算量理論の基本的な考え方を習得する。さらに、プログラムによる記述と関連付けて、アルゴリズムの設計手法を理解するとともに、アルゴリズムの時間計算量と領域計算量に基づいて、問題の難しさについて説明することができる。
【授業の到達目標】
(1) アルゴリズムの時間計算量と領域計算量を解析できる
(2) 計算量理論の考え方に基づいて、問題の難しさについて説明できる
【授業概要（キーワード）】
アルゴリズム、計算量理論、時間計算量、領域計算量
【科目の位置付け】
この授業は，知識情報科学，情報メディア科学の技術分野に関わる深い知識を修得し，情報科学の先端的分野に自在に応用できる能力を養うものである（情報科学専攻の学習・教育目標（A)）
【SDGs（持続可能な開発目標）】
04.質の高い教育をみんなに
09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
講義形式で行う。初めに本講義で取り扱う計算モデルと、その計算量について述べる。その後、具体的な決定問題や探索問題に対して、アルゴリズムを与えるとともに、そのアルゴリズムの計算量について議論する。
・日程
第1回: イントロダクション
第2回: 計算モデル
第3回: 計算量の評価
第4回: 計算量解析の具体例
第5回: アルゴリズム解析の基礎１
第6回: アルゴリズム解析の基礎２
第7回: アルゴリズムの最適性
第8回: グラフアルゴリズムの基礎１
第9回: グラフアルゴリズムの基礎２
第10回: アルゴリズムの設計手法１
第11回: アルゴリズムの設計手法２
第12回: グラフアルゴリズムの設計
第13回: グラフアルゴリズムの高速化１
第14回: グラフアルゴリズムの高速化２
第15回: 講義のまとめ
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
講義後に行う小テストによって，理解できていない部分を把握し，復習に努めること．
・授業時間外学習（予習・復習）のアドバイス
講義中の理解が正しいかを確認するため，講義資料などを参考に復習すること．
【成績の評価】
・基準
提示されたアルゴリズムの動作や、その計算量の解析について，本質的な誤解なく理解していることを合格の基準とする．
・方法
講義後に実施する小テスト（20点），期末レポート（80点）を合計し，100点満点で判定する．60点以上を合格とする．
【テキスト・参考書】
担当教員が作成するスライド，プリントなどを授業で資料として配布する。
【その他】
・学生へのメッセージ
講義資料をもとに，繰り返し復習を行うと良い．特に，アルゴリズムの動作と，計算量の解析について，自分が理解できているかを確認しながら学習を進めるとよい．
・オフィス・アワー
曜日：金曜日
時間：16:00-17:00
場所：8号館2階 225室
|