授業科目一覧
プログラム
メニューここまで

コンピューティング('15)-原理とその展開-

※印刷用にはシラバスPDF版新規ウィンドウ をご利用ください
主任講師
川合 慧 (放送大学名誉教授)
萩谷 昌己 (東京大学教授)
放送メディア
ラジオ
放送時間(平成29年度)
第1学期:(日曜)14時30分~15時15分
第2学期:(金曜)0時45分~1時30分

講義概要

情報に関する学問は極めて幅広いが、その基本的な部分は計算という概念で把握することができる。本科目では、この計算について、その原理的な定義、表現の方法、数理的な性質等々を、基礎的な部分から実際の計算機械及び実用的な計算システムまでを扱う。その際、計算のためのモデルとしていくつかを取り上げ、その基本的な理解のみならず相互的な比較を理論面と実用面の両面から行い、計算について全体的に理解する。
※詳しくはシラバス

開設年度
平成27年度
科目区分
情報学プログラム
自然環境科学プログラム
科目コード
8970084
単位数
2単位
単位認定試験
試験日・時限
平成29年度 第1学期:平成29年7月21日(金曜)6時限(15時35分~16時25分)
平成29年度 第2学期:平成30年1月20日(土曜)7時限(16時45分~17時35分)
単位認定試験
平均点
(平成28年度 第1学期)55.4点
(平成28年度 第2学期)59.6点
備考
 
このページのトップへ本文ここまで

授業の目標

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

履修上の留意点

「計算論('16)」,学部科目の「計算事始め('13)」などが強く関連する科目である。

シラバス

テーマ 内容 執筆担当講師名
(所属・職名)
放送担当講師名
(所属・職名)
1 コンピューティングと状態遷移 本科目の全体的な内容と構成とを紹介した後、状態の考え方を使って問題をモデル化することによって、変化や振舞の理論的な解析が可能であることを学ぶ。以降で取り上げるオートマトンやチューリング機械、命令型計算モデルの基礎となる。

【キーワード】
問題解決、計算、状態、状態遷移
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
2 オートマトン 状態と状態遷移のシステムを明確化したオートマトンの振舞の様子や理論的性質を考え、オートマトンが受理する言語の定義を見た後、言語の階層について学ぶ。次回のチューリング機械への導入と、DNA分子に触発された計算モデルを紹介する。

【キーワード】
オートマトン、受理、形式言語、DNA
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
3 チューリング機械 入出力を無限長のテープを使って行ない、テープ上に与えられた問題の計算結果を再びテープに書き出すチューリング機械について、その構成方法や性質、実行できる計算とその能力、及び他のチューリング機械をシミュレートする万能チューリング機械、さらに計算可能性と不可能性について学ぶ。

【キーワード】
チューリング機械、テープ、万能チューリング機械、計算可能性
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
4 計算と論理 計算と論理とは相互に密接に関係しているので、計算のとくに理論的側面の理解のためには論理における様々な扱いが適用できる。ここではその様子を、演繹体系やペアノ算術、ゲーデルの不完全性定理、及びゲンツェンの無矛盾性証明などを通じて学ぶ。

【キーワード】
演繹体系、ペアノ算術、不完全性定理、無矛盾性証明
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
5 命令型計算モデル 読み書きできる部分が変数の集合である命令型の計算モデルを見る。変数は、直接にアクセスできるセルの集合体上に確保され、その値が書き変えてゆくことで計算が進行する。現実のコンピュータとの対応にも触れ、実際の計算機構において重要なメモリとCPUの様々な構成方法も学ぶ。

【キーワード】
変数、制御構造、ボトルネック、スループット、キャッシュ
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
6 ホーア論理 命令型計算モデル上のプログラムにおける、連接、選択、反復などが満たす論理的性質を表現するホーア論理について、その概略と実際のプログラム構築との関係を学ぶとともに、現実のシステムにおけるホーア論理の発展的な応用を学ぶ。

【キーワード】
ループ不変条件、ループ変動式、プログラム導出、分離論理
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
7 並列・分散計算 現代では、理論的にも実際的にも並列に動作する複数の計算機構を扱う。ここではその原理的な事項として、マルチプロセッサとマルチプロセス、排他制御と同期、分散計算の問題点、分散計算用プロトコル等を学び、最後に分散システムに関わる共有知識について考える。

【キーワード】
並列処理、分数処理、排他制御、同期、通信、共有知識
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
8 ラムダ計算 関数プログラミングの基礎にある関数型計算モデルの代表格であるラムダ計算について学び、ラムダ計算とチューリング機械が、互いに他をシミュレートすることによって同一の関数族を計算できるという意味で等価であることを理解する。また、高階関数を利用したステージ化計算の考え方も見る。

【キーワード】
ラムダ項、簡約、高階関数、カリー化、継続、ステージ化計算
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
9 関数プログラミング 関数プログラミングについて、宣言的記述、ソフトウェア高品質化、並列計算などの優れた点について概観した後、その要因となっている参照透明性、高階関数、遅延評価などの特徴について学ぶ。型の概念にも触れる。またMapReduce と呼ばれる超並列計算のフレームワークについても見る。

【キーワード】
参照透明性、高階関数、遅延評価、MapReduce
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
10 計算の複雑さ 計算にともなう手間を抽象化した概念である計算量について、その定義、実際の様々なアルゴリズムでの導出方法などを学ぶ。小さな計算量から大きな計算量までの実際に触れるとともに、大きな計算量を必要とする計算の例としてゲームプログラミングを見る。

【キーワード】
時間計算量、空間計算量、計算量のオーダ、ゲーム情報学
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
11 計算量の理論 実際的な問題についての計算量のいろいろとその階層性について学ぶ。理論的な話題として、多項式計算量を必要とする問題の集合(P)と非決定的多項式計算量を必要とする問題の集合(NP)について見る。大きな計算量を必要とする実用計算である線形計画法についても学ぶ。

【キーワード】
多項式オーダ、指数オーダ、PとNP、線形計画法
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
12 いろいろな計算機構 現実のコンピュータはそのほとんどが電気信号の処理をその基本としているが、その他にも自然現象に含まれる種々の計算要素を利用した計算モデルについての研究が活発に行なわれている。ここではその具体化状況を、分子計算と量子計算を例にとって学ぶ。

【キーワード】
自然計算、分子計算、量子計算
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
13 数値の計算 現実世界の量をモデル化すると、物理世界や人間の経済活動などについての計算を行なうことができる。ここではモデルとしての数値の世界と、そのコンピュータによる処理の概略を見た後、実際の問題に適用されている大規模な計算とその有用性、及び留意するべき諸点を学ぶ。

【キーワード】
浮動小数点、精度、桁落ち、IEEE754、スーパーコンピュータ
川合 慧
(放送大学名誉教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
14 現代のソフトウェア開発 現代のソフトウェア開発では、計算に関する様々な理論を具体化することによって、人間に優しく、かつ生産性が向上する支援システムが使用されている。ここでは実際の場面で利用されているこの種のシステムの機能の概略を見る。

【キーワード】
言語処理系、エディタ、コンパイラ、統合開発環境
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
15 コンピューティングの未来 現実世界では様々な方式による種々の計算がいろいろな仕組みといろいろな環境で実行されており、その目的もさまざまである。そのいくつかの項目について学び、実際の計算の様子やその応用のされ方、さらには近未来の社会における計算の役割について考える。

【キーワード】
ユビキタス、サイバーフィジカル、シンギュラリティ
萩谷 昌己
(東京大学教授)
川合 慧
(放送大学名誉教授)
萩谷 昌己
(東京大学教授)
このページのトップへ本文ここまで
授業科目案内 大学院 放送大学