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]

形式言語理論 (2015年度)

概要

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

講義の内容

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

講義の方法

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

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

教科書・ハンドアウト

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

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

評価・試験・レポート

• 期末試験とレポートによる．
• レポートについて
• 出席確認を兼ねる．
• 毎週，講義開始前に直接提出．講義開始後は一切受け取らない．
• A4用紙に手書きか，出力したものを提出．
• レポート課題は，ハンドアウトの中で指定．
• 期末試験
• 講義最終回に実施．詳細は下参照．
• 期末試験問題
• 配点と解答
• 評価
• 期末試験8, レポート 2，くらい．
• レポートを出さなくても，試験がきちんとできれば，単位はもちろん優や優上も来る．ただし，
  • レポート課題は予習／復習のためにあるものだし，
  • ぼくもがんばってわかりやすく講義するつもりであるし，
  • 必修をあまり欠席していると心配されて学科長呼び出しがかかるので，
  出席することが推奨される(いや，マジで)．
• 単位がギリギリのときに，レポート点のおかげで助かることは十分ありえる．
• 追試
• 期末試験の結果単位がとれそうにない人には，追試を行います．
• 追試の日程・場所: 下記スケジュール参考
• 問題は簡単で，基本がしっかりできているか見ます．なので，かなりの部分できないと単位はきびしい（8割が目安）．
• 追試の前に補講（質問セッション）をやります．（予定）
• 次の番号はいい感じですね．3/25 に予定入れても大丈夫．

  1150081
  5150512
  5151026
  31156861
  00340556C
  00341072I
  00350390F
  00350542C
  00440009C
  00440016E
  00440022D
  00440034A
  00440035D
  00440041C
  00440052G
  00440070C
  00440074E
  00440075H
  00440081G
  00440086B
  00440175A
  00440322C
  00440349F
  00440386A
  00440418C
  00440442H
  00440502G
  00440504C
  00440515G
  00440552B
  00440571A
  00440591C
  00440605I
  00440608H
  00440687C
  00440698G
  00440826J
  00440827C
  00440857F
  00440868J
  00440890I
  00440897J
  00440908G
  00440950H
  00440956F
  00440973I
  00441019E
  00441032F
  00441051E
  00441082A
  00441111D
  00441133B
  00441186F
  00441199F
  00450218J
  00450316G
  00450338E
  00450411E
  00450428G
  00450453E
       

• 不正行為には厳正に対処します．(たとえば法学部ならば一発退学) 「不正行為」の定義について，小林直樹先生のページから抜粋:

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

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

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

スケジュール

• 2015.9.18 (Fri) イントロ，定理1.1の証明の終わりまで．初回なのでゆっくりやりました． ハンドアウト レポート解答
• 2015.9.25 (Fri) 定義2.3 まで．今回レポートの問2はスキップしてください．（講義の進みがイマイチだったので） 次回は定義2.3の用語の注意から． ハンドアウト レポート解答
• 2015.10.2 (Fri) 教科書25ページ，定理2.3 （Pumping Lemma）の証明の概略まで． ハンドアウト レポート解答
• 2015.10.9 (Fri) 教科書29ページ，練習問題 2.5 まで． ハンドアウト レポート解答
• 2015.10.16 (Fri) 2.8節の終わりまで．2.9節はスキップして，次回は2.10節から始めます． ハンドアウト レポート解答
• 2015.10.23 (Fri) 教科書 48 ページ，定理 2.16 の証明まで．年々講義に慣れていくと，説明を親切にしようと思ってついつい進みが遅れていってしまいます． ハンドアウト レポート解答
• 2015.10.30 (Fri) 教科書57ページまで．次回は 2.12節から． ハンドアウト レポート解答
• 2015.11.6 (Fri) 教科書62ページ，CFG における導出についてまで．次回は 1) 文字列の導出（terminal のみを考える）と，2) 練習問題 3.2 からやります． ハンドアウト レポート解答
• 2015.11.13 (Fri) 教科書74ページ，定理3.9.1 まで．次回は定理3.9.1 の復習から． ハンドアウト レポート解答
  Pushdown automaton 資料:
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 2015.11.24 (Tue) （午後は金曜の授業の日） Pushdown automaton についてやりました．次回は PDA の正確な定式化から．
  ハンドアウト レポート解答
• 2015.11.27 (Fri) ハンドアウト
• 2015.12.4 (Fri) 休講！
• 2015.12.11 (Fri) ハンドアウト
• 2016.1.8 (Fri) 期末試験．14:55～16:40， 駒場 1322教室．
• 2015.3.4 (Fri)，10:30-，本郷キャンパス 理学部7号館102教室 質問セッション（開催予定）．
• 2016.3.25 (Fri), 14:55-16:40，本郷キャンパス 理学部７号館007教室 追試