Ichiro Hasuo

• Department of Computer Science
• University of Tokyo
• ichiro [at] is.s.u-tokyo.ac.jp

• English
• Japanese
• Dutch
• Chinese

• Home
• Contact
• Research
• Cv
• Papers
• Talks
• Teaching

[Back to Teaching]

形式言語理論 (2018年度)

概要

• 担当教員: 蓮尾 一郎，国立情報学研究所 准教授
• Aセメスター 金曜4限 14:55-16:40
• 駒場キャンパス 5号館 511教室
• 理学部情報科学科 2年生 第4学期科目．時間割コード: 0510002
• 講義は日本語で行う．

講義の内容

キーワード: オートマトン，正則言語，形式文法，文脈自由文法，理論計算機科学

講義の方法

配布の教科書に基づき，板書で行う．

• 教科書は，2011年度まで担当の宮野悟先生のご厚意により，そのまま使わせていただきます．
• 各回の内容は，前回の講義時に配布するハンドアウトの中で予告する．予習が推奨される．(ぜひ，少なくとも，電車の中でざっと眺めてきてください)
• 毎回のレポート課題(下参照)は，復習問題と予習問題からなる．

教科書・ハンドアウト

このページで配布する資料は，毎回のハンドアウトを除いて学内のみからアクセス可能．

• 教科書: pdf． 希望者には，教科書を印刷したものを配布する．
• Pushdown automaton 講義資料：
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 毎回のハンドアウト: 下の「スケジュール」の項を参照．

評価・試験・レポート

• 期末試験とレポートによる．
• レポートについて
• 出席確認を兼ねる．
• 毎週，講義開始前に直接提出．講義開始後は一切受け取らない．
• A4用紙に手書きか，出力したものを提出．
• レポート課題は，ハンドアウトの中で指定．
• 期末試験
• 講義最終回に実施．詳細は下参照．
• 期末試験問題
• 解答例
• ところで，次の番号は良い感じでした．3/29 に予定を入れても大丈夫ですね．

  5180515
  5181021
  8182024
  7Q189368
  7Q189369
  J4170016
  J4170039
  J4170045
  J4170050
  J4170052
  J4170062
  J4170095
  J4170135
  J4170171
  J4170258
  J4170300
  J4170321
  J4170342
  J4170448
  J4170460
  J4170473
  J4170499
  J4170601
  J4170641
  J4170653
  J4170659
  J4170669
  J4170679
  J4170748
  J4170749
  J4170766
  J4170791
  J4170803
  J4170812
  J4170818
  J4170863
  J4170883
  J4170913
  J4170952
  J4170956
  J4171012
  J4171018
  J4171082
  J4171122
  J4171138
  J5170038
  J5170063
  J5170319
  J5170369
  J5170420
  J5170442
  	   

• 評価
• 期末試験8, レポート 2，くらい．
• レポートを出さなくても，試験がきちんとできれば，単位はもちろん優や優上も来る．ただし，
  • レポート課題は予習／復習のためにあるものだし，
  • ぼくもがんばってわかりやすく講義するつもりであるし，
  • 必修をあまり欠席していると心配されて学科長呼び出しがかかるので，
  出席することが推奨される(いや，マジで)．
• 単位がギリギリのときに，レポート点のおかげで助かることは十分ありえる．
• 追試
• 期末試験の結果単位がとれそうにない人には，追試を行います．
• 追試の日程・場所: 下記スケジュール参考
• 問題は簡単で，基本がしっかりできているか見ます．なので，かなりの部分できないと単位はきびしい（8割が目安）．
• 追試の前に補講（質問セッション）をやります．（予定）
• 不正行為には厳正に対処します．(たとえば法学部ならば一発退学) 「不正行為」の定義について，小林直樹先生のページから抜粋:

  レポートは，自分で考えたこと，調べたことを，自分の言葉でまとめること．レポートをまとめるにあたって，参考にした文献があれば，レポート中の各個所について参考文献へのレファレンスを挿入するとともに，レポートの最後に参考文献リストをつけること．また，文献の一部をそのまま引用する場合には，引用部分を明確にするために引用符とレファレンスをつけること（レポートの最後に参考文献として載せるだけでは不十分）．参考文献から図や写真，プログラム等を引用する場合も同様．

  以上が守られない場合には，提出されたレポートは盗作と判断され，深刻な結果に至る可能性があります．

  なお，何をもって盗作と判断されるかを知る上で，例えばインディアナ大学のこちらのページ に目を通すことをお勧めします．理解を確認するためのクイズを解くことができます．

スケジュール

• 2018.9.28 (Fri) 講義のイントロ．教科書命題1.1まで．「復習問題」の範囲をカバーできませんでしたが，レポート課題に変更はありません．
  ハンドアウト
• 2018.10.5 (Fri) 有限状態オートマトンの定義の直前まで． ハンドアウト
• 2018.10.12 (Fri) 定理2.1，直感的説明まで． ハンドアウト
• 2018.10.19 (Fri) Section 2.6，正規表現の構文論的定義と，意味論まで． ハンドアウト
• 2018.10.26 (Fri) 定理 2.9 のイントロまで．DFA から regular expression の説明のなかで，最終的にほしい物の説明を忘れました．次回． ハンドアウト
• 2018.11.2 (Fri) 教科書 定義 2.12，同値関係の定義まで． ハンドアウト
• 2018.11.9 (Tue) 定理 2.16 の証明，3 -> 1 を示して，1 -> 2 のヒントを言いました．オートマトン最小化に関する練習問題も配布しました．
  レポート問題を追加しました． ハンドアウト
• 2018.11.30 (Fri) 教科書 2.10節の終わりまで．次回は教科書 2.12節から．レポート課題はキャンセルしました． ハンドアウト
• 2018.12.7 (Fri) 教科書 2.12 節．次回は3章から． ハンドアウト
• 2018.12.14 (Fri) Chomsky 標準形まで．次回は pumping lemma から． ハンドアウト
  Pushdown automaton 資料:
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 2018.12.21 (Fri) CFG の membership problem まで．次回は線形文法，pushdown automata． 注： 今日出題のレポート課題，締めきりは 2019/01/11 です．（来週クリスマスではない）
  ハンドアウト
• 2018.12.25 (Tue) ハンドアウト
• 2019.1.11 (Fri) ハンドアウト
• 2019.2.1 (金) 4限 期末試験．場所はいつもの教室と同じ（511）．
• 2019.3.14 (Thu) 午後 追試対策質問セッション
  日時： 2019/03/14 13:00-14:30
  場所： ERATO 蓮尾プロジェクト 竹橋オフィス
  地下鉄東西線 竹橋駅直結，アクセス
  玄関のドアホンを鳴らして，形式言語理論の受講者であることを告げてください
  対象者： 追試該当者を含む全ての受講者
  
• 2019.3.29 (Fri) 10:25-12:10 追試
  本郷キャンパス 理学部７号館102教室