情報システム科学I

お知らせ

• Thu Sep 23 2010: 授業ページを作りました。開講日は2010年10月8日(金)です。

資料

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

講義情報

目標:

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

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

授業形式:

講義を中心とする

講義計画:

• (4週)オートマトン・正規言語・非決定性オートマトン・チューリング機械・セルラオートマトン
• (4週)関数型プログラミング言語Objective Caml・ラムダ計算
• (4週)論理プログラミング言語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

成績評価:

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