|
授業の目標
|
|
計算機はある種の問題解決に非常に有効な道具である。多様化した現代社会の問題を計算機を用いて解決するためには、問題の本質を数理的に理解しなければならない。問題の数理的理解と定式化ができるようになり、計算機を用いた問題解決ができるようなる。
一方、計算機を用いても解決が困難な問題も知られている。計算機の理論モデルとそのモデル上での問題解決の仕組みを学び、計算機の限界を理解する。
|
|
|
|
到達目標
|
|
(1) 正規言語を理解し、オートマトンの設計ができる。
(2) 文脈自由文法を理解し、プッシュダウンオートマトンの設計ができる。
(3) チューリングマシンの設計ができる。
(4) 問題の難しさの階層およびNP完全問題について理解する。
|
|
|
|
身につく能力
|
|
＜全学ディプロマ・ポリシー＞
○(1)各研究科・専攻の専門分野に応じた高度な専門知識
○(2)各研究科・専攻の専門分野に応じた研究開発能力
(3)高い水準の幅広い教養と倫理観
(4)高度な専門知識・研究開発能力・倫理観・幅広い教養を統合し、問題を発見し解決する能力
(5)高度な専門知識・研究開発能力・倫理観・幅広い教養を統合し、グローカルな視野をもって社会的・経済的価値を創出する力
|
|
|
授業の概要
|
|
|
計算機および問題の数理的な取り扱い方を講義する。オートマトン理論、言語理論から初めて、計算量理論、アルゴリズム論を講義する。特に、計算機科学の中で重要な概念となっている「ＮＰ完全問題」や「ＮＰ困難問題」を中心にその周辺を講義する。
|
|
|
|
授業の計画
|
|
第１週. オートマトンと正規言語
第２週.オートマトンと正規言語の等価生
第３周. プッシュダウンオートマトンと文脈自由文法
第４週.プッシュダウンオートマトンと文脈自由文法の等価生
第5周チューリングマシンと計算
第６周. チューリングマシンの符号化と計算不可能生
第７週.時間限定チューリングマシンとクラスＰ
第8周.非決定性チューリングマシンとクラスＮＰ
第９周.多項式時間帰着
第１０週.ＮＰ完全問題とＮＰ困難問題
第１１週.クラスＮＰとクラスＰの境界
第１２週.計算困難な問題への挑戦１（動的計画法と擬多項式時間アルゴリズム）
第１３週. 計算困難な問題への挑戦２（数理計画法）
第14周.計算困難な問題への挑戦３（分枝限定法）
第15周.計算困難な問題への挑戦４（近似アルゴリズム）
|
|
|
|
授業時間外学修の指示
|
|
参考書を熟読し、演習問題を行うと理解が深まる。
レポートにより成績評価を行うので、そのレポート作成を行う必要がある。
|
|
|
|
成績評価の方法
|
|
・レポート、受講態度等を考慮して、総合的に判断して評価する。
・正規言語、文脈自由言語、チューリングマシン、ＮＰ完全問題に関する理解度により判定する
|
|
|
|
テキスト・参考書等
|
|
参考書：岩間一雄著、「オートマトン・言語と計算理論」、コロナ社、￥3,000＋税（１～４回対応）
岩間一雄著、「アルゴリズム理論入門」、昭晃堂、￥3,300＋税（5～11対応）
マイケルシプサ著、渡辺治、太田和夫訳「計算理論の基礎」、共立出版、￥7,500＋税
川添愛著、「白と黒のとびら: オートマトンと形式言語をめぐる冒険」、東京大学出版会、￥3080＋税
|
|
|
|
履修上の留意点
|
|
|
【manabaの利用法】課題提出と資料配布に用いる
|
|
|
|
資料
|
|
|
|
|
備考
|
|
|