講義コード
授業番号
授業科目名計算論
科目名(英題)
講義題目
授業科目区分コア科目(計算機)
開講年度2009
開講学期前期
曜日時限
必修選択選択
単位数2.0
担当教員竹田正幸
対象学部等システム情報科学府・情報学専攻
対象学年修士1年
開講地区伊都地区
履修条件履修条件は特に定めない.
授業概要まず,計算理論の基礎をなすオートマトン論と言語理論について講義し,計算機の基礎理論と情報の表現法を理解し,同時に,計算機科学の様々な面で必要となる抽象化と理論化の基本的な素養を身に付けさせる.次に,計算のモデルとしてTuring機械を導入し,このモデルによる計算可能性を議論する.さらに,計算量理論に関する基礎的な事項についても講義する.
全体の教育目標情報学,特に,計算機科学の理論的基礎である計算論の要点を体系的に修得させる。具体的には、(1)オートマトン論と言語理論、(2)計算可能性理論、(3)計算量理論、の基礎的事項について修得させる。
個別の学習目標授業計画を参照のこと.
授業計画【オートマトン論と言語理論】
1.正規言語と有限オートマトン
2.正規言語と正規表現      
3.文脈自由言語
4.プッシュダウンオートマトン
5.非文脈自由言語
              
【計算可能性理論】
6.Turing機械
7.Turing機械の変型
8.判定可能な言語
9.停止問題
10.帰着可能性

 【計算量理論】
11.時間の複雑さ(1)
12.時間の複雑さ(2)
13. 領域の複雑さ(1)
14.領域の複雑さ(2)
15.問題の扱いにくさ
キーワードオートマトン理論・言語理論,計算可能性理論,計算量理論
授業の進め方配布資料を中心に授業を行います.課題を提示し,レポートの提出を求めます.
テキストMichael Sipser著(渡辺治,太田和夫訳)「計算の理論」(共立出版)
参考書
学習相談教員室(場所は授業中に提示する)で学習相談を行います.希望する者は,事前に電子メールで相談希望日時,相談内容を連絡し,予約して下さい.
試験/成績評価の方法等適宜レポートを課し、その内容と定期試験の結果をもとに総合的に評価する.
その他特になし.