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]

形式言語理論 (2014年度)

概要

• 担当教員: 蓮尾 一郎，理学部情報科学科 講師
• 冬学期 金曜4限 14:50 - 16:20
• 駒場キャンパス 5号館 532教室
• 理学部情報科学科 2年生 第4学期科目．時間割コード: 理0510002
• 講義は日本語で行う．

講義の内容

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

講義の方法

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

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

教科書・ハンドアウト

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

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

評価・試験・レポート

• 期末試験とレポートによる．
• レポートについて
• 出席確認を兼ねる．
• 毎週，講義開始前に直接提出．講義開始後は一切受け取らない．
• A4用紙に手書きか，出力したものを提出．
• レポート課題は，ハンドアウトの中で指定．
• 期末試験
• 講義最終回に実施．
• 期末試験問題
• 配点と解答
• 評価
• 期末試験 7 ∼ 8, レポート 2 ∼ 3
• レポートを出さなくても，試験がきちんとできれば，単位は来る．ただし，
  • レポート課題は予習／復習のためにあるものだし，
  • ぼくもがんばってわかりやすく講義するつもりであるし，
  • 必修をあまり欠席していると心配されて学科長呼び出しがかかるので，
  出席することが推奨される(いや，マジで)．
• 単位がギリギリのときに，レポート点のおかげで助かることは十分ありえる．
• 追試
• 期末試験の結果単位がとれそうにない人には，追試を行います．
• 追試の日程・場所: 2015/3/30 (月)，10:30-12:00，理学部７号館102教室 （予定）
• 問題は簡単で，基本がしっかりできているか見ます．なので，かなりの部分できないと単位はきびしい（8割が目安）．
• NEW!! 追試の前に補講（質問セッション）をやります．期末試験が出来なかった人は根本的な誤解をしている人が多かったです（特に3年生）． 基本的なことをもう一度インタラクティブに説明しますので， ぜひ出席してください．
  • 2015/2/27（金），13:00-，理学部7号館102教室 ==> 日程を変更しました．2015/2/26（木），13:00-，理学部7号館102教室
  • 当日は入試のため入構制限があります．学生証を忘れずに
• 次の番号はいい感じですね．3/30 に予定入れても大丈夫．

  00240400F
  00240627E
  00240800H
  00240868H
  00241052F
  00340016D
  00340038B
  00340044A
  00340072H
  00340082I
  00340137B
  00340205F
  00340288C
  00340399J
  00340441D
  00340455G
  00340490F
  00340551H
  00340577H
  00340610D
  00340626C
  00340640G
  00340727I
  00340734A
  00340747A
  00340763A
  00340769I
  00340775H
  00340823J
  00340844E
  00340866C
  00340867F
  00340871I
  00340901E
  00340914E
  00340917D
  00340970I
  00341015B
  00341063A
  00341065G
  00341069I
  00341086B
  00341090E
  00341096C
  00341122G
  00341129H
  00341185B
  00250408C
  00350006F
  00350010I
  00350030A
  00350076C
  00350152B
  00350294E
  00350439J
  00350476E
  8141036
  8142014
  8142016
  8142021
  8142024
       

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

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

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

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

スケジュール

• 2014.10.10 (Fri) イントロ，定理1.1の証明の終わりまで．初回なのでゆっくりやりました． 次回は定理1.1の「対角線ぽい絵」から．
  ハンドアウト レポート解答
• 2014.10.17 (Fri) 定義2.1 まで．今回レポートの問2はスキップしてください．（講義の進みがイマイチだったので） ハンドアウト レポート解答
• 2014.10.24 (Fri) 教科書25ページ，定理2.3 （Pumping Lemma）の証明の概略まで． ハンドアウト レポート解答
• 2014.10.31 (Fri) 教科書31ページ，定理2.7 の証明の途中まで．
  （対角線論法や，syntax と semantics の分離について話していたら 進みがイマイチでした．あとハロウィンなのに仮装していくのを忘れました．無念）
  ハンドアウト レポート解答
• 2014.11.7 (Fri) 教科書45ページ， 2.9節の最後まで． ハンドアウト レポート解答
• 2014.11.14 (Fri) 教科書 48 ページ，定理 2.16 の証明まで．年々講義に慣れていくと，説明を親切にしようと思ってついつい進みが遅れていってしまいます． ハンドアウト レポート解答
• 2014.11.28 (Fri) 教科書53ページのアルゴリズムのアイデアの解説まで．次回はアルゴリズムの適用例からはじめます． ハンドアウト レポート解答
• 2014.12.5 (Fri) 教科書 67 ページ，3.1節の終わりまで．次回は p. 60 の問題5と，（念のため）CFG における曖昧さの定義から始めます． ハンドアウト
• 2014.12.12 (Fri) 教科書76ページ，3.4 節の終わりまで． ハンドアウト
  Pushdown automaton 資料:
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 2014.12.19 (Fri) Pushdown automaton についてやりました．次回は PDA <-> CFG の構成の説明からはじめます．
  Happy holidays! ハンドアウト レポート解答
• 2015.1.9 (Fri) Turing machine について，Section 4.1 まで終わりました．次回はその続きと，質問セッションにします． ハンドアウト
• 2014.1.23 (Fri) Turing machine, Church's thesis についてと，質問セッション．
  質問にぼくの代わりに答えてくれる学生さんたちがいて，講師冥利につきます．
• 2015.1.27 (Tue) 期末試験
• 2015.2.26 (Thu)，13:00-，理学部7号館102教室 質問セッション．基本的なことをもう一度説明します．当日は入試のため入構制限があります．学生証を忘れずに．
• 2015.3.30 (Mon), 10:30-12:00，理学部７号館102教室 追試