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