※代数学特論Ⅲ(学部:代数学3)
計算論入門―
143-F-813

担 当 者 単 位 数 配当年次 学 期 曜 日 時 限
中野 伸 教授 2 D/M 第1学期 2

授業概要

計算およびアルゴリズムという概念が数学的にどのように捉えられてきたのかを講義する。記数法、代数記号に関する歴史的な話から始め、論理関数、チューリング機械、原始帰納的関数などの古典理論を解説し、余裕があれば不定方程式論への応用についても紹介したい。

到達目標

計算やアルゴリズムの概念がどのように生まれてきたのかを理解できる。
計算やアルゴリズムに階層があることを理解し、応用できるようになる。
計算の理論がコンピュータの基本設計やプログラミングに役立てることができる。

授業計画

1 序論、記数法・代数記法の歴史
2 計算機械の発展
3 計算機のしくみと数学モデル
4 論理関数
5 チューリング機械の定義
6 チューリング機械の実例
7 万能チューリング機械
8 アルゴリズムの数学的基礎付け
9 原始帰納的関数と原始帰納的述語
10 算術化
11 帰納的関数、帰納的述語
12 自然数論の形式化
13 不定方程式論への応用
14 まとめと展望
15 理解度の確認

授業方法

講義形式。

準備学習

毎回の授業においては、前回までの内容を理解しておくこと(30分以上)。
指示に従って、予習をしておくこと(30分以上)。

成績評価の方法

レポート:90%(何度かに分けてレポートを課す)
平常点(クラス参加、グループ作業の成果等):10%

教科書

教科書用いない。レジュメを配布する予定。

参考文献

講義中に適宜、紹介する。

履修上の注意

第1回目の授業に必ず出席のこと。