シラバスの詳細な内容を表示します。
→ 閉じる（シラバスの一覧にもどる）
| 開講年度 | 2018 年度 | |
|---|---|---|
| 開講区分 | 工学研究科(博士前期課程)情報工学専攻 | |
| 領域 | 主領域 : C | |
| 受講対象学生 |
大学院(修士課程・博士前期課程・専門職学位課程) : 1年次, 2年次 |
|
| 選択・必修 | ||
| 授業科目名 | 計算モデル特論 | |
| けいさんもでるとくろん | ||
| Computation Models | ||
| 単位数 | 2 単位 | |
| 他学部・他研究科からの受講 |
他専攻の学生の受講可 |
|
| 市民開放授業 | 市民開放授業ではない | |
| 開講学期 |
前期 |
|
| 開講時間 |
|
|
| 開講場所 | 工学部指定教室 | |
| 担当教員 | 山田俊行（工学研究科情報工学専攻） | |
| YAMADA, Toshiyuki | ||
| 授業の概要 | 計算の本質について理解することが，本講義の目的である．異なる計算モデル（手続き型プログラム，帰納関数，チューリング機械，等）を通して，複数の視点から計算の原理を理解する． |
|---|---|
| 学習の目的 | |
| 学習の到達目標 | 各種の計算モデルの計算能力の等価性を議論できるようになる．具体的な問題の計算可能性を判定できるようになる． |
| ディプロマ・ポリシー |
|
| 授業の方法 | 講義 演習 |
| 授業の特徴 | Moodle |
| 教科書 | なし（資料を配布） |
| 参考書 | 『コンピュータと数学』，高橋正子 著，朝倉書店，2016 |
| 成績評価方法と基準 | 中間報告４割，期末試験６割 |
| オフィスアワー | 水曜日7〜8時限 (14:40-16:10)，情報棟5階 山田講師室 |
| 受講要件 | 論理（論理式，証明法）と集合論（集合，関係，順序，写像）に習熟していること． |
| 予め履修が望ましい科目 | 離散数学と数理論理学 (情報工学科で開講) |
| 発展科目 | |
| 授業改善への工夫 | 報告書等に講義への意見も書いてもらい，講義の進め方を改善する．ウェブを活用して演習の情報や資料を見られるようにする．Moodleで成績等を通知できるようにする． |
| その他 |
授業のホームページ（メールによる連絡先等も掲載） http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compmodel/ |
| キーワード | 手続き型プログラム，帰納関数，チューリング機械，計算可能性，決定可能性 |
|---|---|
| Key Word(s) | |
| 学習内容 | ●第１回 計算モデル入門，手続き型プログラム 1 計算モデル入門（授業内容，計算モデル，関数の分類） 流れ図プログラム（流れ図プログラムとは，プログラムが表す関数） ●第２回 手続き型プログラム 2 構造化プログラム（構造化プログラムとは，流れ図プログラムとの相互変換） ●第３回 原始帰納関数 1 原始帰納関数（原始帰納関数とは，拡張された構成法，原始帰納関数による四則） ●第４回 原始帰納関数 2 原始帰納述語（原始帰納述語とは，限定最小化） ●第５回 原始帰納関数 3 原始帰納関数の計算能力（流れ図プログラムへの変換，原始帰納関数の特徴，原始帰納的でない関数の存在） ●第６回 帰納関数 1 帰納関数（帰納関数とは，流れ図プログラムへの変換の概要） ●第７回 帰納関数 2 帰納関数の計算能力（固定長数列の符号化と復号，流れ図プログラムへの変換の証明） ●第８回 チューリング機械 1 帰納関数の計算能力（流れ図プログラムへの変換の例，手続きモデルと関数モデルの計算能力の比較） チューリング機械（チューリング機械とは，チューリング機械が計算する関数） ●第９回 チューリング機械 2 チューリング機械の計算能力（帰納関数への変換の概要，可変長数列の符号化と復号） 計算可能性（チャーチ・チューリングの提唱） ●第10回 計算不能関数 1 万能関数（プログラムの符号化，万能関数とは） ●第11回 計算不能関数 2 計算不能関数（対角線論法，帰納的述語，停止性判定問題の決定不能性） ●第12回 計算不能関数 3 計算不能関数（全域性判定問題の決定不能性，非帰納的関数の例，Rice の定理） ●第13回 計算不能関数 4 計算不能関数（Rice の定理の応用，Rice の定理の証明） ●第14回 決定可能集合と枚挙可能集合 1 計算不能関数（Rice の定理の証明，決定不能問題の例） ●第15回 決定可能集合と枚挙可能集合 2 枚挙可能集合（決定可能集合とは，枚挙可能集合とは，枚挙可能集合と枚挙不能集合の例） |
| 事前・事後学修の内容 | 授業前に配布資料や参考書を読み，疑問点を整理しておく．講義で指定された演習問題を解き，理解度を確認する． |
| ナンバリングコード(試行) |
|---|
※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 ナンバリングコード一覧表はこちら