コンピューティング(’15)

主任講師: 川合 慧、萩谷 昌己

計算という概念及びその数理的な性質を把握するとともに、計算の理論的な振舞と実際的な動きについて理解する。計算を記述し解析するためには計算をモデル化する必要があるが、主要な計算モデルのうち、状態遷移モデル、命令型計算モデル、関数型計算モデル、チューリング機械、ラムダ計算について理解する。現実世界での計算および計算システムの役割についても理解を深める。 検討中リストに追加

各回のテーマと放送内容

※テーマをクリックすると授業内容が表示されます。

第1回 コンピューティングと状態遷移
本科目の全体的な内容と構成とを紹介した後、状態の考え方を使って問題をモデル化することによって、変化や振舞の理論的な解析が可能であることを学ぶ。以降で取り上げるオートマトンやチューリング機械、命令型計算モデルの基礎となる。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第2回 オートマトン
状態と状態遷移のシステムを明確化したオートマトンの振舞の様子や理論的性質を考え、オートマトンが受理する言語の定義を見た後、言語の階層について学ぶ。次回のチューリング機械への導入と、DNA分子に触発された計算モデルを紹介する。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第3回 チューリング機械
入出力を無限長のテープを使って行ない、テープ上に与えられた問題の計算結果を再びテープに書き出すチューリング機械について、その構成方法や性質、実行できる計算とその能力、及び他のチューリング機械をシミュレートする万能チューリング機械、さらに計算可能性と不可能性について学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第4回 計算と論理
計算と論理とは相互に密接に関係しているので、計算のとくに理論的側面の理解のためには論理における様々な扱いが適用できる。ここではその様子を、演繹体系やペアノ算術、ゲーデルの不完全性定理、及びゲンツェンの無矛盾性証明などを通じて学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第5回 命令型計算モデル
読み書きできる部分が変数の集合である命令型の計算モデルを見る。変数は、直接にアクセスできるセルの集合体上に確保され、その値が書き変えてゆくことで計算が進行する。現実のコンピュータとの対応にも触れ、実際の計算機構において重要なメモリとCPUの様々な構成方法も学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第6回 ホーア論理
命令型計算モデル上のプログラムにおける、連接、選択、反復などが満たす論理的性質を表現するホーア論理について、その概略と実際のプログラム構築との関係を学ぶとともに、現実のシステムにおけるホーア論理の発展的な応用を学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第7回 並列・分散計算
現代では、理論的にも実際的にも並列に動作する複数の計算機構を扱う。ここではその原理的な事項として、マルチプロセッサとマルチプロセス、排他制御と同期、分散計算の問題点、分散計算用プロトコル等を学び、最後に分散システムに関わる共有知識について考える。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第8回 ラムダ計算
関数プログラミングの基礎にある関数型計算モデルの代表格であるラムダ計算について学び、ラムダ計算とチューリング機械が、互いに他をシミュレートすることによって同一の関数族を計算できるという意味で等価であることを理解する。また、高階関数を利用したステージ化計算の考え方も見る。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第9回 関数プログラミング
関数プログラミングについて、宣言的記述、ソフトウェア高品質化、並列計算などの優れた点について概観した後、その要因となっている参照透明性、高階関数、遅延評価などの特徴について学ぶ。型の概念にも触れる。またMapReduce と呼ばれる超並列計算のフレームワークについても見る。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第10回 計算の複雑さ
計算にともなう手間を抽象化した概念である計算量について、その定義、実際の様々なアルゴリズムでの導出方法などを学ぶ。小さな計算量から大きな計算量までの実際に触れるとともに、大きな計算量を必要とする計算の例としてゲームプログラミングを見る。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第11回 計算量の理論
実際的な問題についての計算量のいろいろとその階層性について学ぶ。理論的な話題として、多項式計算量を必要とする問題の集合(P)と非決定的多項式計算量を必要とする問題の集合(NP)について見る。大きな計算量を必要とする実用計算である線形計画法についても学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第12回 いろいろな計算機構
現実のコンピュータはそのほとんどが電気信号の処理をその基本としているが、その他にも自然現象に含まれる種々の計算要素を利用した計算モデルについての研究が活発に行なわれている。ここではその具体化状況を、分子計算と量子計算を例にとって学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第13回 数値の計算
現実世界の量をモデル化すると、物理世界や人間の経済活動などについての計算を行なうことができる。ここではモデルとしての数値の世界と、そのコンピュータによる処理の概略を見た後、実際の問題に適用されている大規模な計算とその有用性、及び留意するべき諸点を学ぶ。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第14回 現代のソフトウェア開発
現代のソフトウェア開発では、計算に関する様々な理論を具体化することによって、人間に優しく、かつ生産性が向上する支援システムが使用されている。ここでは実際の場面で利用されているこの種のシステムの機能の概略を見る。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)
第15回 コンピューティングの未来
現実世界では様々な方式による種々の計算がいろいろな仕組みといろいろな環境で実行されており、その目的もさまざまである。そのいくつかの項目について学び、実際の計算の様子やその応用のされ方、さらには近未来の社会における計算の役割について考える。
担当講師: 川合 慧 (放送大学名誉教授) 萩谷 昌己 (東京大学教授)

放送メディア:

ラジオ

放送時間:


2017年度 [第1学期] (日曜)
14時30分〜15時15分
2017年度 [第2学期] (金曜)
0時45分〜1時30分

単位認定試験 試験日・時限:

2017年度 [第1学期]
2017年7月21日 (金曜)
6時限 (15時35分~16時25分)

単位認定試験 試験日・時限:

2017年度 [第2学期]
2018年1月20日 (土曜)
7時限 (16時45分~17時35分)

開設年度:

2015年度

科目区分:

大学院科目

科目コード:

8970084

単位数:

2単位
このページの先頭へ