2025年 大学院理工学研究科 シラバス - 数学専攻
設置情報
| 科目名 | 計算数学特論Ｂ | ||
|---|---|---|---|
| 設置学科 | 数学専攻 | 学年 | 1年 |
| 担当者 | 平石 秀史 | 履修期 | 後期 |
| 単位 | 2 | 曜日時限 | 木曜3 |
| 校舎 | 駿河台 | 時間割CD | N43A |
| クラス | |||
概要
| 学修到達目標 | アルゴリズム設計の典型的なパラダイムを学び、様々な視点からアルゴリズム設計ができるようになることを目標とする。 |
|---|---|
| 授業形態及び 授業方法 |
講義は対面授業で、主に板書で行う。適宜レポート課題を出題する。 |
|
準備学習（予習・ 復習等）の内容・ 受講のための 予備知識 |
グラフや文字列のアルゴリズムについて基礎知識があると望ましい。 |
授業計画
| 第1回 | 計算理論の概要 【事前学習】グラフや文字列のアルゴリズムについて調べる（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
|---|---|---|---|
| 第2回 | 計算量の評価について 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第3回 | 分割統治法 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第4回 | 局所探索法 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第5回 | 動的計画法 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第6回 | 様々な計算量クラス：クラスP,NP 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第7回 | 様々な計算量クラス：還元とNP完全 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第8回 | 乱拓アルゴリズムの基礎 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第9回 | 乱拓アルゴリズムと計算量クラス 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第10回 | 乱拓アルゴリズムと脱乱拓化 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第11回 | 近似アルゴリズムの基礎 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第12回 | 計算困難問題と近似アルゴリズム 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第13回 | 近似アルゴリズムの計算量クラス 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第14回 | 計算困難問題とパラメータ化計算量 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
| 第15回 | これまでのまとめ 【事前学習】前回の講義の内容を確認する（3時間） 【事後学習】講義の内容を復習する（3時間） | 【事前学修】グラフや文字列のアルゴリズムについて調べる 【事後学修】講義でふれたトピックについて調べる | 【事前学修】３時間 【事後学修】３時間 |
その他
| 教科書 | |
|---|---|
| 参考資料コメント 及び 資料（技術論文等） |
|
| 成績評価の方法 及び基準 |
課題提出による。課題の解説は講義中に行う |
| 質問への対応 | 質問は随時受け付ける |
| 研究室又は 連絡先 |
授業中に指示する |
| オフィスアワー |
水曜 駿河台 17:30 ～ 18:30
|
| 学生への メッセージ |