計算論

科目基礎情報

学校 岐阜工業高等専門学校 開講年度 平成28年度 (2016年度)
授業科目 計算論
科目番号 0020 科目区分 専門 / 選択
授業形態 講義 単位の種別と単位数 学修単位: 2
開設学科 電子システム工学専攻 対象学年 専2
開設期 後期 週時間数 2
教科書/教材 計算論入門(渡辺治,米崎直樹・日本評論社)
担当教員 出口 利憲

目的・到達目標

計算の原理,計算のモデルをさまざまな角度から学び,計算の本質に対する理解を深める。
(1) チューリング機械と S プログラムを理解する。
(2) チューリング機械と S プログラムの計 算方法を理解する。
(3) 計算の異なる表現の仕方を理解する。
(4) 計算の異なる表現の計算方法を理解する。
(5) データのコード化を理解する。
(6) 計算の限界について理解する。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
評価項目1チューリング機械および S プロ グラムに関する問題を正確 (80%) に解ける。チューリング機械および S プロ グラムに関する問題をほぼ正確 (60%) に解ける。チューリング機械および S プログ ラムに関する問題が解けない。
評価項目2チューリング機械および S プロ グラムの計算に関する問題を正確 (80%) に解ける。チューリング機械および S プログ ラムの計算に関する問題をほぼ正 確 (60%) に解ける。チューリング機械および S プログ ラムの計算に関する問題が解けな い。
評価項目3帰納的関数およびラムダ計算に関 する問題を正確 (80%) に解ける。帰納的関数およびラムダ計算に関 する問題をほぼ正確 (60%) に解 ける。帰納的関数およびラムダ計算に関 する問題が解けない。
帰納的関数およびラムダ計算に おける計算に関する問題を正確 (80%) に解ける。帰納的関数およびラムダ計算にお ける計算に関する問題をほぼ正確 (60%) に解ける。帰納的関数およびラムダ計算に おける計算に関する問題が解けな い。
2 進コード化,ゲーデル数および 自然数を表すラムダ式に関する問 題を正確 (80%) に解ける。2 進コード化,ゲーデル数および 自然数を表すラムダ式に関する問 題をほぼ正確 (60%) に解ける。2 進コード化,ゲーデル数および 自然数を表すラムダ式に関する問 題が解けない。
計算不可能性に関する問題を正確 (80%) に解ける。計算不可能性に関する問題をほぼ 正確 (60%) に解ける。計算不可能性にに関する問題が解 けない。

学科の到達目標項目との関係

教育方法等

概要:
授業の進め方と授業内容・方法:
教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。
注意点:

授業計画

授業内容・方法 週ごとの到達目標
後期
3rdQ
1週 チューリング機械入門
2週 チューリング機械によ
る計算とデータのコード化
3週 多テープチューリング
機械
4週 チューリング機械計算
可能性
5週 S プログラムと S プロ グラム計算可能性
6週 帰納的関数入門
7週 原始帰納的関数
8週 ゲーデル数
4thQ
9週 帰納的関数とチューリ
ング機械
10週 原始帰納的関数と帰
納的関数の関係
11週 帰納的関数とSプロ グラム
12週 ラムダ計算入門
13週 自然数のコード化
14週 ラムダ計算による計
算可能性
15週 for-times プログラム
16週

評価割合

試験レポート合計
総合評価割合8020100
基特tん8020100