cheader

シラバス詳細照会

シラバス詳細照会

  • 講義要項やWebシラバスの記載内容は、登録された受講生の人数や理解度に応じて、授業開始後に変更となる可能性があります。

main start

授業情報

開講年度 2019年度 開講箇所 教育学部
科目名
数学演習1 L

担当教員 横森 貴
学期曜日時限 通年  月4時限
科目区分 数学科 配当年次 3年以上 単位数 4
使用教室 14-708数学演習室(5) キャンパス 早稲田
科目キー 150600000U 科目クラスコード 12
授業で使用する言語 日本語
  コース・コード MATX303S
大分野名称 数学
中分野名称 数学
小分野名称 数学
レベル 上級レベル 授業形態 演習/ゼミ

シラバス情報

最終更新日時:2019/03/01 16:07:34

授業概要  「計算の理論」に関する基礎的な事柄を学習する。
 ここでいう“計算”とは「コンピュータで行う計算」のことである。現在の高度情報化社会の中枢を担うデジタルコンピュータの計算メカニズムに関して,その基礎となる数学的計算モデルを学習し,“計算可能性とは?”」という素朴な疑問について考察する。
オートマトン,形式言語,形式文法,計算可能性,アルゴリズムなどの話題を含む。
パソコンなどのコンピュータやプログラミングの知識は前提としない。
授業の到達目標 デジタルコンピュータの計算メカニズムに関して,その基礎となる種々の数学的計算モデルを学習し,“計算可能性”についての理解を深める。
授業計画 [第 1回]概念と記法(準備)正則集合の性質
[第 2回]記号列と集合(言語)
[第 3回]有限オートマトンと正則集合
[第 4回]非決定性有限オートマトン
[第 5回]部分集合構成法
[第 6回]正則表現と有限オートマトン
[第 7回]正則集合の性質
[第 8回]演算と閉包性
[第 9回]最小化アルゴリズム
[第10回]文脈自由文法とその言語
[第11回]文脈自由言語の性質
[第12回]文脈自由文法とプッシュダウンオートマトン
[第13回]文脈自由文法と決定問題
[第14回]構文解析アルゴリズム
[第15回]前期総復習(試験などを含む)

[第16回]チューリングマシン入門
[第17回]計算可能性と限界
[第18回]チューリングマシンあれこれ
[第19回]アルゴリズムと形式システム
[第20回]帰納的可算言語と計算
[第21回]決定問題と計算可能性
[第22回]チューリングマシンの停止問題
[第23回]決定不能問題
[第24回]ポスト対応問題
[第25回]ライスの定理
[第26回]クラスPとクラスNP
[第27回]NP完全問題
[第28回]他の計算量的言語クラス
[第29回]確率アルゴリズム
[第30回]後期総復習(試験などを含む)

教科書 Introduction to the Theory of Computation, Course Technology Inc., 2005 (by
Michael Sipser)
成績評価方法
割合 評価基準
平常点評価: 100% 出席だけでなく,授業中に適時だす質問・問題への回答,授業における受講態度の積極性も、評価対象となる。
備考・関連URL 与えられた学習内容から,それを包括するより一 般的な学問体系をかいま見る努力をしてほしい。

関連URL:
(横森研)http://www.edu.waseda.ac.jp/~yokomori/index.html

ページの先頭へ戻る

Copyright © Media Network Center,Waseda University 2006-2019.All rights reserved.

read