計算量理論概論
 Computational Theory
 担当教員:内澤 啓(UCHIZAWA Kei)
 担当教員の所属:大学院理工学研究科(工学系)情報・エレクトロニクス専攻
 担当教員の実務経験の有無:
 開講学年:2年  開講学期:前期  単位数:2単位  開講形態:講義
 開講対象:情報・エレクトロニクス専攻  科目区分:選択 
【授業の目的】
計算量理論の基本的な考え方を習得する。さらに、プログラムによる記述と関連付けて、アルゴリズムの設計手法を理解するとともに、アルゴリズムの時間計算量と領域計算量に基づいて、問題の難しさについて説明することができる。

【授業の到達目標】
(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室

59100183-2025-15-56663