| 授業方針・テーマ |
計算量の考え方について理解することを目的とする。コンピュータで処理される様々な問題をその処理に要する時間やメモリ量に基づいて分類する方法を説明する。 |
習得できる知識・能力や授業の
目的・到達目標 |
・アルゴリズムを計算量に基づいてクラス分け又はそれを証明することができる。（専門分野の知識・理解、論理的思考能力）
・アルゴリズムの設計並びに漸近的解析ができる。（専門分野の知識・理解、アルゴリズム設計能力・解析能力、論理的思考能力）
・アルゴリズムの数学的性質について証明することができる。（専門分野の知識・理解、論理的思考能力） |
授業計画・内容
授業方法 |
第１回 計算理論
第２回 複雑さの測定
第３回 クラスP
第４回 クラスNP
第５回 NP 完全性
第６回 他の NP 完全問題
第７回 領域の複雑さ
第８回 クラス PSPACE
第９回 PSPACE完全性
第１０回 クラス L とクラス NL
第１１回 NL完全性
第１２回 階層定理
第１３回 相対化
第１４回 回路の複雑さ
第１５回 ランダム化アルゴリズムとオラクル、まとめ
|
| 授業外学習 |
複数回の演習問題を課す。宿題を出した場合、次回の授業までに解答を用意しておくこと。 |
| テキスト・参考書等 |
教科書
・Michael Sipster，計算理論の基礎 [原著第3版] 3.複雑さの理論. 共立出版（2023）
参考書
・Cormen他，「アルゴリズムイントロダクション第3版 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム」，近代科学社（2012）
|
| 成績評価方法 |
期末試験60％、小テスト複数回40％、平常点（授業態度や積極性の状況等）により加点・減点する。
試験については記述式の問題を課し、専門知識を理解した上で論理的な説明ができるか確認する。（アルゴリズムの基本的な知識・理解、アルゴリズム設計能力及び解析能力、論理的思考）
小テストについては選択式の問題を課し、専門知識を理解した上で適切にアルゴリズムの解析ができるか確認する。（アルゴリズムの基本的な知識・理解、アルゴリズム解析能力） |
質問受付方法
(オフィスアワー等) |
オフィスアワーについては、原則として毎週火曜日13時30分〜14時30分、毎週水曜日12時10分〜12時40分とする。これ以外の時間帯に担当教員に会いたい場合は、事前にメールでアポイントメントを取ること。また質問は Kibaco 又はメールにて受け付ける。 |
特記事項
(他の授業科目との関連性) |
関連科目：
データ構造とアルゴリズムI，データ構造とアルゴリズムII，データ構造とアルゴリズム演習，離散数学，計算理論，暗号理論
|
| 備考 |
|
シラバス照会