シラバスの詳細な内容を表示します。
→ 閉じる（シラバスの一覧にもどる）
| 開講年度 | 2017 年度 | |
|---|---|---|
| 開講区分 | 工学部情報工学科 ・専門教育 | |
| 受講対象学生 |
学部(学士課程) : 3年次 |
|
| 選択・必修 | 選択 選択科目 |
|
| 授業科目名 | 計算理論 | |
| けいさんりろん | ||
| Theory of Computation | ||
| 単位数 | 2 単位 | |
| 他学部・他研究科からの受講 |
|
|
| 市民開放授業 | 市民開放授業ではない | |
| 開講学期 |
前期 |
|
| 開講時間 |
金曜日 5, 6, 7, 8時限 開講日は掲示等で指定 |
|
| 開講場所 | ||
| 担当教員 | 笠井琢美 | |
| KASAI, Takumi | ||
| 授業の概要 | 本講義では、計算の理論および最近発展が著しい計算量の理論を講義する。計算の理論は、帰納的関数の理論とも呼ばれることもあるが、計算(アルゴリズム)を直接対象とした理論である。ここでは、そもそも計算とは何か、計算できないとは何を意味するのかを解説する。また、可算、帰納的可算などの基本概念や、万能関数の存在などについて解説し、具体的な計算できない問題について述べる。計算について議論するには、計算を実行する媒体である計算機モデルが必要である。本講義では、現在の計算機の忠実なモデルであるランダム･アクセス機械とそのプログラミング言語である whileプログラムを計算機モデルとして用いる。しかし、計算不能な問題は、これらの計算モデルには依存しないことも議論する。 計算の理論では、単にアルゴリズムが存在するかどうかを議論するだけで、そのアルゴリズムの効率については考慮しない。これに対し、計算量の理論では、計算に必要な時間や領域を理論の対象とする。ここでは、非決定性アルゴリズムや、多項式時間計算可能性といった基本的な事項に付いて解説する。また、NP完全問題についても述べる。さらに、現在なぜNP完全問題が実際的な時間では計算できないと見なされているかについて議論する。 |
|---|---|
| 学習の目的 | |
| 学習の到達目標 | |
| ディプロマ・ポリシー |
|
| 授業の方法 | 講義 |
| 授業の特徴 | |
| 教科書 | 特になし |
| 参考書 | 参考書：計算の理論（笠井琢美、戸田誠之助著、共立出版） |
| 成績評価方法と基準 | 基本的に定期試験で評価する。しかし、2講義に1回程度、演習問題を解いてもらったり、小テストを行っている。定期試験の成績不振者にはこの小テストの点を加味している。 |
| オフィスアワー | 電子メールによる受け付け可。 |
| 受講要件 | |
| 予め履修が望ましい科目 | オートマトン･形式言語理論。講義では、計算機科学一般で必要とされるごく基本的な概念や、離散数学の基本概念を用いるが、講義の中で基本概念はすべて解説するので、この講義のための前知識は何も仮定していない。 |
| 発展科目 | |
| 授業改善への工夫 | 従来の計算の理論は、Turing機械と呼ばれる計算モデルを基礎にしており、この機械を習得するのに、授業の大半の時間を必要とした。この講義で用いるwhile プログラムは、現実のプログラミング言語とほとんど同じもので、習得にほとんど時間を要しない。また、講義の間にたびたび学生諸君に演習問題を解く時間を設けている。 |
| その他 |
| キーワード | |
|---|---|
| Key Word(s) | |
| 学習内容 | 第１回 while プログラム 第２回 基本プログラミング：基本的な関数、条件文、手続きの処理 第３回 対象の算術化(コード化)、配列の処理 第４回 チャーチの定立 第５回 ランダム・アクセス機械 第６回 万能プログラムと万能関数 第７回 計算可能性の基本定理 第８回 可算と帰納的可算 第９回 計算不能性 第10回 計算不能な具体的な問題：語の問題 第11回 実際的計算可能性: (多項式時間計算可能性) 第12回 非決定性アルゴリズム 第13回 NP完全問題とは 第14回 具体的なNP完全問題 第15回 まとめ 第16回 定期試験 |
| 学習課題(予習・復習) |
| ナンバリングコード(試行) | EN-CMPS-3 |
|---|
※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら