[前へ戻る]
   

 授業科目
 Course Title
数理論理特論
Mathematical Logic
 担当者
 Instructor
教授   阿部 吉弘  後学期 月曜日5時限
 単 位
 Credit
2

到達目標 Target to be Reached
次の項目を最低限の到達目標とする。
(1)ブール代数の演算と、ブール式の標準形への変換・簡約ができる。
(2)オートマトンの動作を理解し、与えられた言語を受理するオートマトンを設計できる。
(3)形式文法になじみ、簡単な文のコンパイルを行える。
(4)関数の再帰(帰納)的構成を理解し、計算を実行できる。
(5)チューリング計算機の動作を追跡できる。
(6)簡単な関数を計算するチューリング計算機を設計できる。


 
授業内容 Course Content
 計算機科学の数理論理学と関連する基礎事項を概観する。
具体的には、次の事項を取り上げる。
  1.ブール代数
  2.オートマトン
  3.形式文法
  4.再帰(帰納)的関数
  5.チューリング計算機
どの項目も初歩段階に限定しており、さらに勉強するための基礎となることを主眼としている。

 
授業計画 Course Planning
 テキストの輪読を行う。進度は履修者の理解度に左右されるが、概ね次の予定で進む。各回のキーワードを()内に記す。
   1.順序集合と束(極大・極小元、上界・下界、束の公理)
   2.ブール代数の公理(分配束、補元、双対原理)
   3.ブール関数と組み合わせ回路(ブール変数、AND・OR・否定回路)
   4.ブール関数の論理式表現と簡約(主選言・主連言標準形、カルノー図)
   5.有限ブール代数の表現定理(アトム、冪集合、同型)
   6.オートマトンの状態遷移(アルファベット、状態遷移関数、初期状態、受理状態)
   7.オートマトンの受理言語(状態遷移図、オートマトンの解析・合成)
   8.形式文法とオートマトン(1)(正規文法、文脈自由文法、文脈依存文法)
   9.形式文法とオートマトン(2)(有限オートマトン、非決定性オートマトン、ポンプ原理)
  10.再帰的関数の定義(原始再帰的関数、正則性条件)
  11.再帰的関数の計算(2重帰納法)
  12.チューリング計算機(動作関数、時点表示、計算ステップ数)
  13.チューリング計算機の運転(停止、発散、計算結果)
  14.基本的なチューリング計算機(合成、ダイヤグラム)
  15.計算量のクラス(チューリング計算可能関数、時間計算量、多項式時間、PとNP)

 
授業運営 Course Management
 当番の学生がテキストの内容を説明する。
担当教員は適宜質問をして、学生の理解を確かめる。当番以外の学生も質問をして、理解を深めあう状況を目指す。
 
評価方法 Evaluation Method
 輪読当番の際の様子と、レポートで評価する。
 
オフィスアワー Office Hour (s)
 月曜日の13:00~13:30
 
使用書 Textbook (s)
田中尚夫『計算論理入門』第5版[裳華房]2008年


 
 
 
[前へ戻る]