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]

形式言語理論 (2017年度)

概要

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

講義の内容

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

講義の方法

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

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

教科書・ハンドアウト

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

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

評価・試験・レポート

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

  540535
  540870
  550423
  640016
  640024
  640029
  640051
  640059
  640091
  640112
  640115
  640133
  640140
  640152
  640234
  640239
  640259
  640300
  640358
  640511
  640514
  640533
  640547
  640548
  640568
  640578
  640590
  640614
  640659
  640672
  640692
  640711
  640726
  640761
  640771
  640815
  640823
  640845
  640865
  640892
  640903
  640978
  640981
  641004
  641040
  641069
  641079
  641094
  650347
  650363
  5161030
  5170503
  8171085
  8172015
  	   

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

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

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

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

スケジュール

• 2017.9.29 (Fri) イントロ．（要回収伏線： 理論を構築することで inclusion check がするりと解ける） 命題1.1の statement まで．次は練習として証明を一度やってみます．
  ハンドアウト
• 2017.10.6 (Fri) 教科書第1章の終わりまで．regularity の定義と，直感的説明はやりました． ハンドアウト
• 2017.10.13 (Fri) 教科書25ページ，Section 2.4 の終わりまで．次回はお楽しみ，pumping lemma から．
  今回レポートの問2はスキップしてください．（講義の進みがイマイチだったので）
  ハンドアウト
• 2017.10.20 (Fri) 教科書28ページ，命題2.4 まで． ハンドアウト
• 2017.10.27 (Fri) 定理 2.9.4 まで． ハンドアウト
• 2017.11.10 (Fri) 教科書例 2.15 まで． ハンドアウト
• 2017.11.14 (Tue) （熱発のため休講．申し訳ありません）
• 2017.12.1 (Fri) 定理 2.16, 1) => 2) まで． ハンドアウト
• 2017.12.8 (Fri) ハンドアウト
• 2017.12.15 (Fri) 文脈自由文法の簡素化まで． ハンドアウト
• 2017.12.22 (Fri) 文脈自由文法の pumping lemma についてやったあと，所属性判定アルゴリズムの まで．次回は所属性判定アルゴリズムの実際と，PDA について． ハンドアウト Pushdown automaton 資料:
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 2017.12.26 (Tue) ハンドアウト
• 2018.1.5 (Thu) ハンドアウト
• 2018.2.2 (金) 期末試験（予定）
• 2018.3.19 (Mon) 質問セッション
  日時： 2018/03/19 13:00-14:30
  場所： ERATO 蓮尾プロジェクト 竹橋オフィス
  地下鉄東西線 竹橋駅直結，アクセス
  玄関のドアホンを鳴らして，形式言語理論の受講者であることを告げてください
  対象者： 追試該当者を含む全ての受講者
  
• 2018.3.29 (木), 10:25-12:10，本郷キャンパス 理学部７号館102教室 追試