一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ 一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ 一般的な情報 担当: 宮野 英次 (MIYANO, Eiji) 計算基礎論 講義ガイダンス 所属: システム創成情報工学研究系 Email: [email protected] . Phone: 7721 宮野 英次 Room: W619 号室 . [email protected] . 講義時間: 月曜日，1404 号室，14:40 - 16:10 URL: 2009 年 http://theory.ces.kyutech.ac.jp/˜miyano/Classes/KITtcs/ ログイン名: tcs09 一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ 一般的な情報 パスワード: tcs@SDI 講義概要 講義内容と位置付け オートマトン・計算可能性・計算複雑さ 講義項目 オートマトンと言語 講義概要: 問題解決のためのアルゴリズムを実装するときに不 可欠な計算可能性に関する基本的性質，効率的なア ルゴリズムを構築するための計算複雑さの理論，効 率化や概念の把握に役立つオートマトン論的考え方 について議論を行う． 授業位置付け: 「離散数学 (1 年後期)」で教育される集合，関係， 写像，帰納的関数に関する知識， 「データ構造とアル ゴリズム (2 年前期)」「プログラム設計 (2 年後期)」 で教育される基本データ構造と様々な計算パラダイ ムに関する知識を踏まえて，計算可能性と計算困難 性に関する教育を行う 有限オートマトン，正規言語，両者の等価性 文脈自由文法 文脈自由文法，プッシュダウン・オートマトン，両者の等価性 Church-Turing の提唱 Turing 機械，アルゴリズムの定義 判定可能性 帰着可能性 時間の複雑さ 計算量クラス，クラス P，クラス NP，NP 完全性 領域の複雑さ クラス PSPACE，PSPACE 完全，クラス L，クラス NP 計算複雑さの理論における先進的な話題，暗号系 一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ 一般的な情報 講義概要 講義資料 講義の進め方と評価方法 講義の進め方 資料 スライドを用いた講義 Web よりダウンロード 演習，小テスト テキスト レポート M. Sipser 著 (渡辺，太田監訳)，計算理論の基礎，共立 評価方法 参考書 一般的な情報 オートマトン・計算可能性・計算複雑さ 岩間一雄，アルゴリズム理論入門，昭晃堂 出席 (毎回)，10 回以上が最低条件 岩間一雄，オートマトン・言語と計算理論，コロナ社 演習，小テスト (10 - 20 %) H.R. Lewis & C.H. Papadimitoriou, Elements of the Theory of Computation, Prentice Hall 中間テストまたはそれに準ずるレポート (30 - 40 %) 講義概要 オートマトン・計算可能性・計算複雑さ 評価基準 オートマトン理論の概要，および正規言語の等価性について 理解している 文脈自由文法とプッシュダウン・オートマトンの等価性につ いて知っている Turing 機械について知っている 計算可能性に関する基本性質について理解している 判定可能性，帰着可能性の証明について理解をし，証明法を 活用することができる 計算複雑さに関する基本性質を理解している 時間の複雑さによるクラス階層，領域の複雑さによるクラス 階層について理解している 与えられた NP 完全問題の NP 完全性を証明することがで きる 期末テストまたはそれに準ずるレポート (40 - 50 %) 一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ オートマトン，計算可能性，複雑さ 計算機の本質的な能力とその限界は何か? A. Turing (1930 年代) 計算機械が「できること」と「できないこと」の境界を明 確化 N. Chomsky (1950 年代) 形式的な「文法」の研究．オートマトンと密接な関係 コンパイラーの一部の基礎として役立っている S. Cook (1969 年) 「コンピュータで効率良く解ける問題集合」と「非常に時間 がかかり，小規模な場合にしかコンピュータが役に立たない 問題集合」の分離 一般的な情報 講義概要 オートマトン・計算可能性・計算複雑さ 一般的な情報 講義概要 オートマトン理論 計算可能性の理論 計算可能性の理論 オートマトン理論 抽象的な計算装置， 「機械」の研究のこと コンピュータにはどのような特徴があるのか ? . アルゴリズムの定義とは ? 計算のさまざまな数学的モデルが定義され，その性質を議論 どんな問題でもコンピュータで解けるのか ? . . . 計算モデルの例: 有限オートマトン: テキスト処理，コンパイラ，ハードウェア設 . 計で用いられる 20 世紀前半，Kurt Gödel，Alan Turing，Alonzo Church などの数学者が，ある種の基本的な問題が計算機では解けな いことを発見 文脈自由文法: プログラム言語や人工知能で用いられる 数学における命題の真偽を決定するという問題など . .. 計算機の厳密な定義 一般的な情報 講義概要 計算可能な問題 vs 計算不可能な問題 オートマトン・計算可能性・計算複雑さ 計算複雑さの理論 計算複雑さの理論 何が，問題の難しさ・やさしさを決めているのだろうか? . 最大値問題と整列問題はどっちが難しいか? . オイラー閉路問題とハミルトン閉路問題はどっちが難しいか? 計算複雑さ 問題が本質的に持っている難しさ 暗号システム . 例: 難しい問題の利用 オートマトン・計算可能性・計算複雑さ
© Copyright 2024 ExpyDoc
