シラバス表示
シラバスの詳細な内容を表示します。
→ 閉じる（シラバスの一覧にもどる）
科目の基本情報
| 開講年度 | 2022 年度 | |
|---|---|---|
| 開講区分 | 工学研究科(博士前期課程)情報工学専攻 | |
| 領域 | 主領域 : C | |
| 受講対象学生 |
大学院(修士課程・博士前期課程・専門職学位課程) : 1年次, 2年次 |
|
| 選択・必修 | ||
| 授業科目名 | 計算モデル特論 | |
| けいさんもでるとくろん | ||
| Models of Computation | ||
| 単位数 | 2 単位 | |
| ナンバリングコード | EN-CMPS-5
|
|
| 開放科目 | 非開放科目 | |
| 開講学期 |
前期 |
|
| 開講時間 |
|
|
| 授業形態 |
対面授業 * 状況により変更される可能性があるので定期的に確認して下さい
「オンライン授業」・・・オンライン会議ツール等を利用して実施する同時双方向型の授業 |
|
| 開講場所 | 工学部指定教室 | |
| 担当教員 | 山田俊行（工学研究科情報工学専攻） | |
| YAMADA, Toshiyuki | ||
| SDGsの目標 |
|
|
| 連絡事項 | * 状況により変更される可能性があるので定期的に確認して下さい |
|
学修の目的と方法
| 授業の概要 | 計算の本質について理解することが，本講義の目的である．異なる計算モデル（手続き型プログラム，帰納関数，チューリング機械，等）を通して，複数の視点から計算の原理を理解する． (Course description) The aim of this course is to understand the essentials of computation. By comparing different computation models (precedual programs, recursive programs, Turing machines, etc.), we understand the principles of computation from multiple perspectives. |
|---|---|
| 学修の目的 | |
| 学修の到達目標 | 各種の計算モデルの計算能力の等価性を議論できるようになる．具体的な問題の計算可能性を判定できるようになる． (Attainment targets) aquiring ability to discuss the equivalence of the computational power of different computation models. aquiring skills to judge computability of concrete computational problems. |
| ディプロマ・ポリシー |
|
| 成績評価方法と基準 | 中間報告4割，期末試験6割 (Grading policy) report 40%, exam 60% |
| 授業の方法 | 講義 演習 |
| 授業の特徴 |
Moodleを活用する授業 |
| 授業改善の工夫 | 報告書等に講義への意見も書いてもらい，講義の進め方を改善する．ウェブを活用して演習の情報や資料を見られるようにする．Moodleで成績等を通知できるようにする． (Ideas for improving classes) Opinions from students will be used to improve the lectures. Information of the course and handouts can be obtained from the Web page. Results of the report and exam will be notified by using Moodle. |
| 教科書 | なし（資料を配布） (Textbooks) None (handouts will be distributed) |
| 参考書 | 『コンピュータと数学』，高橋正子 著，朝倉書店，2016 (Reference materials) "Introduction to the Theory of Computation", 3rd edition, Michael Sipser, Cengage Lerning, 2013 |
| オフィスアワー | 水曜日7〜8時限 (14:40-16:10)，情報棟5階 山田講師室 (Office hour) 14:40-16:10 on Wednesdays, Yamada's office, 5th floor, Information Engineering Building |
| 受講要件 | 論理（論理式，証明法）と集合論（集合，関係，順序，写像）に習熟していること． (Prerequisites) Student must be acquainted with logic (logical formulas and proof methods) and naive set theory (set, relation, ordering, mapping). |
| 予め履修が望ましい科目 | 離散数学と数理論理学 (情報工学科で開講) (Courses encouraged to take in advance) Discrete Mathematics and Mathematical Logic (courses at the Department of Information Engineering) |
| 発展科目 | |
| その他 |
英語対応授業である。 授業のホームページ homepage of the course http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compmodel/ This course is English-supported. |
授業計画
| MoodleのコースURL |
|---|
| キーワード | 手続き型プログラム，帰納関数，チューリング機械，計算可能性，決定可能性 |
|---|---|
| Key Word(s) | procedual programs, recursive functions, Turing machines, computability, decidability |
| 学修内容 | (Course contents) ●第１回 計算モデル入門，手続き型プログラム 1 Lecture 1: Introduction to Computation Models, Procedual Programs 1 計算モデル入門（授業内容，計算モデル，関数の分類） 流れ図プログラム（流れ図プログラムとは，プログラムが表す関数） ●第２回 手続き型プログラム 2 Lecture 2: Procedual Programs 2 構造化プログラム（構造化プログラムとは，流れ図プログラムとの相互変換） ●第３回 原始帰納関数 1 Lecture 3: Primitive Recursive Functions 1 原始帰納関数（原始帰納関数とは，拡張された構成法，原始帰納関数による四則） ●第４回 原始帰納関数 2 Lecture 4: Primitive Recursive Functions 2 原始帰納述語（原始帰納述語とは，限定最小化） ●第５回 原始帰納関数 3 Lecture 5: Primitive Recursive Functions 3 原始帰納関数の計算能力（流れ図プログラムへの変換，原始帰納関数の特徴，原始帰納的でない関数の存在） ●第６回 帰納関数 1 Lecture 6: Recursive Functions 1 帰納関数（帰納関数とは，流れ図プログラムへの変換の概要） ●第７回 帰納関数 2 Lecture 7: Recursive Functions 2 帰納関数の計算能力（固定長数列の符号化と復号，流れ図プログラムへの変換の証明） ●第８回 チューリング機械 1 Lecture 8: Turing Machines 1 帰納関数の計算能力（流れ図プログラムへの変換の例，手続きモデルと関数モデルの計算能力の比較） チューリング機械（チューリング機械とは，チューリング機械が計算する関数） ●第９回 チューリング機械 2 Lecture 9: Turing Machines 2 チューリング機械の計算能力（帰納関数への変換の概要，可変長数列の符号化と復号） 計算可能性（チャーチ・チューリングの提唱） ●第10回 計算不能関数 1 Lecture 10: Uncomputable Functions 1 万能関数（プログラムの符号化，万能関数とは） ●第11回 計算不能関数 2 Lecture 11: Uncomputable Functions 2 計算不能関数（対角線論法，帰納的述語，停止性判定問題の決定不能性） ●第12回 計算不能関数 3 Lecture 12: Uncomputable Functions 3 計算不能関数（全域性判定問題の決定不能性，非帰納的関数の例，Rice の定理） ●第13回 計算不能関数 4 Lecture 13: Uncomputable Functions 4 計算不能関数（Rice の定理の応用，Rice の定理の証明） ●第14回 決定可能集合と枚挙可能集合 1 Lecture 14: Decidable Sets and Recursively Enumerable Sets 1. 計算不能関数（Rice の定理の証明，決定不能問題の例） ●第15回 決定可能集合と枚挙可能集合 2 Lecture 15: Decidable Sets and Recursively Enumerable Sets 2. 枚挙可能集合（決定可能集合とは，枚挙可能集合とは，枚挙可能集合と枚挙不能集合の例） ●期末試験 |
| 事前・事後学修の内容 | 授業前に配布資料や参考書を読み，疑問点を整理しておく．講義で指定された演習問題を解き，理解度を確認する． |
| 事前学修の時間:120分/回 事後学修の時間:120分/回 |