Syllabus data
|
Teacher name ： 戸田 貴久
|
開講年度
2025Year
開講学期
First Semester
科目名
Computational Mathematics
授業種別
Lecture
科目名（英語）
Computational Mathematics
授業情報(授業コード・クラス・授業形態)
A1100230 Computational Mathematics
担当教員
null
単位数
2.0Credits
曜日時限
Thu.5Period
キャンパス
Shinjuku Campus
教室
A-0815教室
学位授与の方針
1 基礎知識の修得 10 ％
2 専門分野の知識・専門技術の修得 70 ％ 3 汎用的問題解決力の修得 10 ％ 4 道徳的態度と社会性の修得 10 ％ 具体的な到達目標
有限オートマトン・プッシュダウンオートマトンの概念・対応する言語・文法との等価性を理解すること。具体的な例題について、オートマトンや文法を設計することができること。
受講にあたっての前提条件
授業のねらいを把握し、それを習得する意志がある。
授業の方法とねらい
本科目では、オートマトン・形式言語といった様々な計算モデルにふれることにより、計算とは何か・計算機でできることは何かを学びます。
AL・ICT活用
Support for self-learning using ICT
第1回
授業形態
授業情報欄記載の通り
事前学習
参考書1. 1〜4講を読んでおく。
3時間
授業内容
１ 計算とは何か
本授業の目的、歴史的な経緯や位置付けを示し、集合論・論理・グラフ理論などの以降で必要となる準備的な内容を解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 5〜7講を読んでおく。 3時間
第2回
授業形態
授業情報欄記載の通り
授業内容
２ 有限オートマトンと言語
有限オートマトンの定義を示し、有限オートマトンが受理する言語について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 8講を読んでおく。 2時間
第3回
授業形態
授業情報欄記載の通り
授業内容
３ 非決定性有限オートマトン
非決定性有限オートマトンについて解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 9講を読んでおく。 2時間
第4回
授業形態
授業情報欄記載の通り
授業内容
４ DFAとNFAの等価性
決定性有限オートマトンと非決定性有限オートマトンとの等価性について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 10講を読んでおく。 2時間
第5回
授業形態
授業情報欄記載の通り
授業内容
5 正規表現
正規表現の定義を示し、正規表現が表す言語について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 11講を読んでおく。 2時間
第6回
授業形態
授業情報欄記載の通り
授業内容
６ 正規表現の持つ性質
有限オートマトンと正規言語との等価性について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 12講を読んでおく。 2時間
第7回
授業形態
授業情報欄記載の通り
授業内容
７ 有限オートマトンの受理能力
有限オートマトンの受理能力の限界について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：前回までの総復習を行っておく。 2時間
第8回
授業形態
授業情報欄記載の通り
授業内容
８ 総合演習
これまでの授業の内容について振り返り、演習をする。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 14〜15講を読んでおく。 2時間
第9回
授業形態
授業情報欄記載の通り
授業内容
９ 文脈自由文法と言語生成能力
文脈自由文法の定義と、文法の生成能力の階層について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 16〜17講を読んでおく。 2時間
第10回
授業形態
授業情報欄記載の通り
授業内容
１０ 文脈自由文法の設計
文脈自由言語が与えられたとき、それを生成する文脈自由文法を設計する手法について解説する。 またチョムスキーの標準形についても解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 18講を読んでおく。 2時間
第11回
授業形態
授業情報欄記載の通り
授業内容
１１ 文脈自由文法の言語生成能力の限界
文脈自由言語でない言語の例と、ある言語が文脈自由言語でないことを証明する手法について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 19講を読んでおく。 2時間
第12回
授業形態
授業情報欄記載の通り
授業内容
１２ プッシュダウンオートマトン
プッシュダウンオートマトンの定義を示し、プッシュダウンオートマトンが受理する言語について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：参考書1. 20-21講を読んでおく。 2時間
第13回
授業形態
授業情報欄記載の通り
授業内容
１３ プッシュダウンオートマトンの性質
プッシュダウンオートマトンと文脈自由言語の等価性について解説する。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
事前学習：前回までの総復習を行っておく。 3時間
第14回
授業形態
授業情報欄記載の通り
授業内容
１４ 総合演習
これまでの授業の内容について振り返り、演習をする。 事後学習・事前学習
事後学習：授業中に出題した課題に取り組む。
1時間
第15回
授業形態
授業情報欄記載の通り
授業内容
１５ 総合演習の解説など
主に総合演習の解説をして、これまでの授業内容のまとめも行う。 事後学習
事後学習：授業中に出題した課題に取り組む。
1時間
成績評価の方法
授業ごとに演習問題を出題し、次回の授業までのレポート課題とする。
また、総合演習の授業では、その回までの総合的な内容を問う演習問題を出題して、通常回よりも長く設定した期日までにレポートを提出する。 これらのレポートの結果を総合して成績評価をつける。 受講生へのフィードバック方法
課題の解答を提出締め切り後に公開する。
授業内でも解説する。 教科書
丸岡 章 著 「やさしい計算理論—有限オートマトンからチューリング機械まで」 サイエンス社
参考書
Michael Sipser著 「計算理論の基礎 原著第2版 1 オートマトンと言語」 共立出版
オフィスアワー
電子メールで随時受け付ける。
受講生へのメッセージ
本授業は、コンピュータ・サイエンスの標準的なカリキュラムとして確立している内容です。
コンピュータに付き合う上での、基礎的な頭の体操という側面も持っており、パズルを解くようなおもしろさもありますが、数学や論理を使った深い内容の一端にも触れることもできますので、積極的に取り組んでほしいと思います。 実務家担当科目
Not applicable
実務経験の内容
教職課程認定該当学科
Department of Computer Science
その他の資格・認定プログラムとの関連
関連する科目でない
教育課程コード
Ⅲ3b
教育課程コードの見方【例】 Ⅰ2a（Ⅰ…Ⅰ群、2…2年配当、a…必修） ※ a : 必修 b : 選択必修 c : 選択 ※複数コードが表示されている場合には入学年度・所属学科の学生便覧を参照のこと
|
