授業科目名 : アルゴリズム論

科目コード 90551
配当学年 3年
開講年度・開講期 平成30年度・後期
曜時限 木曜・2時限
講義室 総合研究7号館情報1
単位数 2
履修者制限
授業形態 講義
使用言語 日本語
担当教員    所属・職名・氏名 情報学研究科・教授・湊真一

授業の概要・目的

時間と記憶量を考慮できる計算のモデルを導入し,計算可能性や計算の困難さに関する計算量理論の基礎を解説する.

成績評価の方法・観点及び達成度

演習(小テスト)と定期試験の成績を総合して評価する.

到達目標

計算可能性や計算の困難さに関する基礎理論を学び,情報学的視点および数理的な視点の両方から理解する.

授業計画と内容

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

教科書

教科書は指定しないが,講義の進展に合わせて下記の参考書の少なくとも一つを入手し熟読することを望む.

参考書等

Hopcroft, Motowani, Ullman: Introduction to Automata Theory,Languages, and Computation -3rd Edition- Peason, 2007
ホップクロフト, モトワニ, ウルマン: オートマトン言語理論 計算論 [第2版] I および II (上記の第2版の邦訳) , サイエンス社, 2003
岩間,アルゴリズム理論入門,昭晃堂,2001

履修要件

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

授業外学習(予習・復習)等

講義スライド資料は講義前にwebページで提供する.各回に簡単な演習問題(小テスト)を解く時間を設け,履修者の理解度を見る.各自の復習のため,演習問題の解答は講義後に提供する.

授業URL

その他(オフィスアワー等)