科目名 : アルゴリズム論

科目コード 90551
配当学年 3年
開講期 後期
曜時限 木曜・1時限
講義室 2号館101
単位数 2
履修者制限
講義形態 講義
言語
担当教員 岩間一雄

講義概要

時間と記憶量を考慮できる計算のモデルを導入し,計算量理論の基礎を解説する.

評価方法

2回のレポートと最終試験

最終目標

講義計画

項目 回数 内容説明
言語・オートマトン理論の復習 1
チューリング機械とその能力 4 標準的計算モデルであるチューリング機械の能力を様々な面から観察する.非常に単純な同等機械の存在や,我々が通常使用している「計算機」とも同等であることを示す.
計算可能性 4 問題の形式的定義を行なった後,それが「可解」であるものと「非可解」であるものに分類できることを示す.非可解な問題の例を与える.
計算量理論の基礎 6 問題が可解であっても,計算時間がかかり過ぎて「手に負えない」ものと比較的短い時間で解けるものに分類できることを示す.手に負えない問題の例を与える.

教科書

岩間,アルゴリズム理論入門,昭晃堂,2001.

参考書

予備知識

言語・オートマトンを既習していることが望ましい.そうでない場合は,上記教科書の最初の部分を自習しておくこと.

授業URL

その他