シラバス
| 授業科目名 | 年度 | 学期 | 開講曜日・時限 | 学部・研究科など | 担当教員 | 教員カナ氏名 | 配当年次 | 単位数 |
|---|---|---|---|---|---|---|---|---|
| 計算基礎理論 | 2025 | 前期 | 火3 | 理工学研究科博士課程前期課程 | 今井 桂子 | イマイ ケイコ | 1年次配当 | 2 |
科目ナンバー
SG-IG5-8C11
履修条件・関連科目等
基礎となる数学的概念、基本的なデータ構造やアルゴリズムに関する知識を持っていること．
授業で使用する言語
日本語
授業で使用する言語（その他の言語）
授業の概要
計算量理論の基礎的な事について講義を行なう．
基礎となる概念を習得し，NP完全やNP困難を正しく理解する．
科目目的
実社会における最適化問題の多くは，NP困難と呼ばれる難しい問題である．計算量理論の基礎を学び，NP困難な問題であるかどうかを正しく判断できるようにする．
到達目標
計算量の基本的概念を理解する．
授業計画と内容
第1回 計算量とは
第2回 NP完全の理論１：決定問題
第3回 NP完全の理論２：クラスPとNP
第4回 NP完全の理論３：多項式時間還元
第5回 SATの難しさ
第6回 代表的なNP完全問題（3SAT）
第7回 代表的なNP完全問題（3次元マッチング）
第8回 代表的なNP完全問題（頂点被覆）
第9回 代表的なNP完全問題（ハミルトン閉路）
第10回 代表的なNP完全問題（分割問題）
第11回 NP完全問題のまとめ
第12回 ＮＰ困難問題
第13回 近似アルゴリズム
第14回 難しい問題の例（プレゼンテーション）
授業時間外の学修の内容
その他
授業時間外の学修の内容（その他の内容等）
概念や証明の詳細を理解するために，各回の内容を次の回までに復習しておくこと．
NP完全問題の例を各自が調べ，最終回に発表を行うので，準備をしておくこと．
授業時間外の学修に必要な時間数／週
・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。
成績評価の方法・基準
| 種別 | 割合（％） | 評価基準 |
|---|---|---|
| レポート | 60 | 計算量理論の基本的概念を理解し、論理的に正しく証明を構成することができている。 |
| 平常点 | 40 | 授業における参加や貢献度も評価に加える。プレゼンテーションにおいて、問題をよく理解し，他者に分かるように説明ができている。他の学生の発表に対して適切なコメントをすることができている。 |
成績評価の方法・基準（備考）
課題や試験のフィードバック方法
授業時間内で講評・解説の時間を設ける
課題や試験のフィードバック方法（その他の内容等）
アクティブ・ラーニングの実施内容
プレゼンテーション
アクティブ・ラーニングの実施内容（その他の内容等）
授業におけるICTの活用方法
その他
授業におけるICTの活用方法（その他の内容等）
必要に応じて，Webexミーティング，Googleドライブ等を用いて双方向型の学び及び自主学習支援を実施する．具体的にはその都度指示する．
実務経験のある教員による授業
いいえ
【実務経験有の場合】実務経験の内容
【実務経験有の場合】実務経験に関連する授業内容
テキスト・参考文献等
M. R. Garey and D. S. Johnson: Computers and Intractability
- A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.