cheader

シラバス詳細照会

シラバス詳細照会

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

main start

授業情報

開講年度 2019年度 開講箇所 教育学部
科目名
応用数学4

担当教員 横森 貴
学期曜日時限 秋学期  月3時限
科目区分 数学科 配当年次 2年以上 単位数 2
使用教室 14-717A数学演習室(1) キャンパス 早稲田
科目キー 150600000F 科目クラスコード 01
授業で使用する言語 日本語
  コース・コード MATX254L
大分野名称 数学
中分野名称 数学
小分野名称 応用数学
レベル 中級レベル(発展・応用) 授業形態 講義

シラバス情報

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

授業概要  コンピュータの歴史はほんの半世紀であるにも関わらず現代人の生活に不可欠であり,その発展ぶりも目を見張るものがあるが,また同時にその現実的な限界も認識されつつある。この能力の限界を正しく理解し,それを克服し改良していくためには,理論的な基礎知識・背景となる関連知識の習得が必要となる。本講では,離散数学的素養を基盤に計算機のための数学として,「オートマトンと言語理論」に関する以下の項目を講述する。
授業の到達目標 本講では,離散数学的素養(特に、計算機のための情報数学)を基礎として,種々の計算モデルとそれらの能力の限界を正しく理解する。
授業計画 [第 1回]正則言語と表現定理
[第 2回]局所的言語と正則言語
[第 3回]文脈自由言語に対するチョムスキー・スタンレーの表現定理
[第 4回]句構造文法とチョムスキー階層
[第 5回]句構造言語とチューリング機械
[第 6回]チューリング機械とその変形
[第 7回]アルゴリズムとチューリング機械
[第 8回]文脈依存文法と単純文法
[第 9回]文脈依存言語と線形有界オートマトン
[第10回]万能チューリング機械
[第11回]計算可能性
[第12回]アルゴリズムと決定問題
[第13回]チューリング機械の停止問題
[第14回ポスト対応問題
[第15回]総復習(試験を含む)

教科書 オートマトン・言語理論:第2版(富田他著:森北出版)
参考文献 オートマトン言語理論 計算論I,II (野崎他訳:サイエンス社)
基礎 情報数学(横森・小林:サイエンス社)
計算量理論 I ~アルゴリズムの数学的定義から P≠NP 予想まで~(守屋:サイエンス社)電子版
成績評価方法
割合 評価基準
試験: 100% 15回目の授業時間内に試験を行う。(試験問題の解説も同時間内で行う。)
その他: 授業中に適時だす演習問題への回答、授業における受講態度の積極性も、加点の評価対象となる。
備考・関連URL 与えられた学習内容から,それを包括するより一般的な学問体系をかいま見る努力をしてほしい。

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

ページの先頭へ戻る

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

read