ソフトウェア基礎論
Foundations of Software Science

講義内容

ソフトウェアシステムを設計する際に大切なことは， まず対象を簡潔にモデ ル化し， 次に， 対象の性質を明らかにするための方法論をもつことである。 このような観点に立ち，本講義前半では，データベース理論を取り上げ，重要 な概念と方法論を紹介する。後半では，計算複雑さ理論の基礎について開設す る。
  1. データベース理論
    データベースにおける質問言語に関する理論的な事柄を説明する。
    1. 関係代数， 関係論理
    2. 一階述語質問
    3. 再帰質問
    4. 否定を含む再帰質問
  2. 計算複雑さ
    「計算機出問題を解くときの，問題の難しさをはかる尺度はあるのだろうか」 といった疑問に答えていく。
    1. 計算複雑さの定義と諸性質
    2. NP完全性（Cook の定理，還元による証明法）
    3. 他のクラスの完全性（PSPACE完全性など）
    4. 他の話題(多項式時間階層，確率アルゴリズムなど）

    教科書

    （２）の教科書
    J.ホップクロフト・J.ウルマン著，野崎・高橋・町田・山崎訳：オートマトン 言語理論 計算論II，サイエンス社，1986.

    参考書

    授業中に紹介する

    前提とする知識(必ずしも先修条件ではない)