情報システム科学I

お知らせ

• Fri Oct 7: 授業ページを作りました。開講日は2011年10月12日(水)です。

資料

• オートマトンシミュレータのダウンロードと説明
• Conwayのライフゲーム情報
• ラムダ計算インタプリタ
• Prologの使い方

講義情報

目標:

計算機が行う「計算」を理想化した計算モデルをいくつか見て、「計算」の本質、計算機との関係、計算モデル間との関係を知る。具体的には、以下の2つの代表的な計算モデルを紹介する。

• 機械モデル
• 関数モデル
• 論理モデル

授業形式:

講義を中心とする

講義計画:

• (6週)オートマトン・正規言語・非決定性オートマトン・チューリング機械・セルラオートマトン
• (6週)関数型プログラミング言語Objective Caml・ラムダ計算
• (0週)論理プログラミング言語Prolog・論理計算モデル

教科書・参考書:

• 機械モデル: Michael Sipser, Introduction to the Theory of Computation, Course Technology, 2005 ISBN 0619217642
• 関数モデル:
  • 五十嵐淳,「Objective Caml 入門」
  • 木村泉, 米澤明憲,「算法表現論」岩波書店, 1982, ISBN 4-00-010162-5
• 論理モデル: 井田哲雄, 「計算モデルの基礎理論」岩波書店, 1991, ISBN4-00-010352-0 C3355

成績評価:

レポートまたは期末試験による。

連絡先:

masuhara+iss1@lecture.ecc.u-tokyo.ac.[ここに日本のドメイン名を補って下さい]