2020年秋学期 - 情報数学 / MATHEMATICS FOR INFORMATION SCIENCE
|
B6144 情報数学 MATHEMATICS FOR INFORMATION SCIENCE |
基盤科目-共通科目 Fundamental Subjects - Interdisciplinary Subjects 2 単位 |
| 実施形態 | 完全オンライン |
| 開催日程 | 秋学期 火曜日１時限 |
| 担当教員 | 萩野 達也（ハギノ タツヤ） |
| 関連科目 |
前提科目（推奨）: B6117 |
| 開講場所 | SFC |
| 授業形態 | 講義 |
| 履修者制限 |
履修人数を制限する Only the selected students can take this course. |
| 履修条件 | |
| 使用言語 | 日本語 |
| 連絡先 | hagino@sfc.keio.ac.jp |
| 授業ホームページ | https://web.sfc.keio.ac.jp/~hagino/mi20/ |
| 同一科目 | |
| 学生が利用する予定機材/ソフト等 | |
| 設置学部・研究科 | 総合政策・環境情報学部 |
| 大学院プロジェクト名 | |
| 大学院プロジェクトサブメンバー | |
| ゲストスピーカーの人数 | 0 |
| 履修選抜・課題タイプ=テキスト登録可 | false |
| 履修選抜・選抜課題タイプ=ファイル登録可 | false |
| GIGAサティフィケート対象 | |
| 最終更新日 | 2020/07/13 16:27:03 |
科目概要
コンピュータプログラムは入力をもらって出力を出すという意味では数学の関数とみなすことができるが、単純な集合間の関数とみなすと矛盾することになる。プログラムは全関数ではなく半関数である。プログラムの動作を理解するためには位相の一種である完全半順序集合を用いいる必要がある。この講義ではプログラムの意味の基礎となっている領域理論を中心に、λ計算、完全半順序、カテゴリー理論などについて解説する。
A programs can be seen as a mathematical function which calculate output value for a given input. However, it is not a simple mathematical function. It is not a total function, but a partial one. In order to understand the property of programs, it is necessary to introduce topology of complete partial order. In this lecture, we will study lambda calculus, domain theory, category theory and so on which are base for mathematical theory of programs.
授業シラバス
主題と目標／授業の手法など
プログラムは入力から出力を計算する数学的な関数とみなすことができる．この授業では．プログラムに対応する関数がどのような性質を持つかについて考える．
最初に，プログラムによる計算を理解するために，プログラムの3つのモデルを比較する：帰納的関数，チューリング機械，ラムダ計算．これらの3つもモデルが同値であることを示す．
次に，ラムダ計算の意味を与える半順序について学ぶ．
最後に，プログラムのデータ型に関係する数学の基礎理論であるカテゴリ理論について取り扱う．
A programs can be seen as a mathematical function which calculate output value for a given input. In this lecture, we will look into the property of functions which correspond to programs.
Firstly, in order to understand what we can calculate using programs, we compare three models of programs: recursive functions, turing machines and lambda calculi. We will show that three models are equivalent.
Secondly, we will study complete partial order which gives the model of lambda calculi and programs.
Thirdly, in order to understand data types of programs, we will look into category theory which is the abstraction of functions and can show the beauty behind data types.
教材・参考文献
授業でスライドのコピーを配る． Handouts will be distributed in each class.
提出課題・試験・成績評価の方法など
期末試験と，演習によって評価する．
Evaluated by final examination and exercises.
履修上の注意
授業計画
第1回 Whileプログラム
[While Program]
プログラムによる計算について定義する．
Define computation by a program.
第2回 原始帰納的関数
[Primitive Recursive Function]
原始帰納的関数について定義し，四則演算などを原始帰納的関数として定義する．
Define primitive recursive functions and define some well known arithmetic functions.
第3回 帰納的関数
[Recursive Function]
原始帰納的関数を拡張し，帰納的関数を定義する．計算可能な関数が，原始帰納的関数と一致することを示す．
Extend primitive recursive functions to general recursive functions.Show computable functions are equivalent with recursive functions.
第4回 演習(1)
[Exercise(1)]
帰納的関数に関する演習問題を解く．
Some exercises for recursive functions.
第5回 チューリング機械
[Turing Machine]
計算機のモデルとしてチューリング機械を定義する．
Define Turing machine which is a model of computation.
第6回 チューリング機械と計算可能性
[Turing Machine and Computability]
チューリング機械と計算可能性が一致することを示す．
Show equivalence of Turing machine and computability.
第7回 演習（2）
[Exercise(2) ]
チューリング機械に関する演習問題を解く．
Some exercises for Turing machine
第8回 ラムダ計算
[Lambda Calculus]
ラムダ式の定義を行い，αおよびβ変換について説明する．
Define lambda calculus and introduce alpha. beta and eta conversions.
第9回 ラムダ計算と計算可能性
[Lambda Calculus and Computabilty]
ラムダ式による計算と計算可能性が一致することを示す．
Show equivalence of lambda calculus and computability.
第10回 演習（3）
[Exercise(3)]
ラムダ計算に関する演習問題を解く．
Some exercises for lambda calculus.
第11回 完全半順序
[Complete Partial Order Set]
情報の集合を表すために完全半順序を導入する．また，完全半順序おける積・和・関数空間によるデータ型の構築について説明する．
Introduce complete partial order set which represents set of information. Construction of complete partial order sets are also instoduced: cartesian product, disjoint sum, function space.
第12回 連続関数
[Continuous Function]
プログラムは完全半順序集合間の連続関数であることを示す．
Show programs can be modeled as continuous functions.
第13回 演習（4）
[Exercise(4)]
完全半順序に関する演習問題を解く．
Some exercises for CPOs.
第14回 カテゴリー理論入門
[Introduction to Category Theory]
カテゴリー理論について説明する。カテゴリー、射、対象、関手などについて定義する。
Introduce category theory which can give alternative foundation of mathematics. It is much more intuitive than set theory and is easier to see hidden relationships between objects.
第15回 カテゴリー理論とデータ型
[Category Theory and Data Type]
プログラミング言語におけるデータ型をカテゴリー理論を用いて説明する．
Understand the connection between category theory and data type in programs.
15回目に相当するその他の授業計画