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]

形式言語理論 (2016年度)

概要

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

講義の内容

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

講義の方法

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

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

教科書・ハンドアウト

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

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

評価・試験・レポート

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

  3153008
  3160441
  45166016
  48166106
  00440021A
  00440055F
  00540014J
  00540023H
  00540027J
  00540042G
  00540056J
  00540067D
  00540076B
  00540084G
  00540087F
  00540090F
  00540105E
  00540322D
  00540351D
  00540373B
  00540420A
  00540499E
  00540510C
  00540602A
  00540621J
  00540623F
  00540639E
  00540645D
  00540662G
  00540695I
  00540724B
  00540839A
  00540872D
  00540925A
  00540926D
  00541007I
  00541025E
  00541027A
  00541033J
  00541062J
  00541184A
  00550003I
  00550040D
  00550172F
  00550239F
  00550280D
  00550310J
  00550464J
  00550527H
  00560001F
  7P169360
  	   

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

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

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

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

スケジュール

• 2016.9.30 (Fri) イントロ，命題 1.1 の証明の最初まで．新しい教室でロジスティカルに苦戦してしまいました :-( 次回は証明の詳細からやります．
  ハンドアウト
  板書（ホワイトボードが多かったですが，念のため）
• 2016.10.7 (Fri) 定義2.1 まで．今回レポートの問2はスキップしてください．（講義の進みがイマイチだったので） ハンドアウト
• 2016.10.14 (Fri) 教科書25ページ，Section 2.4 の終わりまで．次回はお楽しみ，pumping lemma から．
  今回レポートの問2はスキップしてください．（講義の進みがイマイチだったので）
  ハンドアウト
• 2016.10.21 (Fri) 教科書29ページ，命題2.5 までやったことにします．次回は練習問題2.5 から． ハンドアウト
• 2016.10.28 (Fri) 定理2.7まで．次回は定理2.8から． ハンドアウト
• 2016.11.4 (Fri) 教科書定理2.10の主張まで．次回はその証明から． ハンドアウト
• 2016.11.11 (Fri) 教科書 2.8 節を定理 2.12 までやったあと，残りと 2.9節はスキップ．2.12 節をやって，その後 2.10 節の 定義 2.13 まで． ハンドアウト
• 2016.12.2 (Fri) 教科書48ページ，系2.3 まで． ハンドアウト
• 2016.12.9 (Fri) 文脈自由文法のイントロまで．次回は文脈自由文法の定義から． ハンドアウト
  Pushdown automaton 資料:
  [Keynote | pdf (プレゼン用，アニメ付き) | pdf (印刷用, 4-up)]
• 2016.12.16 (Fri) 文脈自由文法の pumping lemma のイントロまで．次回はその statement と証明から． ハンドアウト
• 2016.12.23 (Fri, Holiday) 文脈自由文法の pumping lemma についてやったあと，所属性判定アルゴリズムのアイデア（V_ij とは何か？）まで． ハンドアウト
• 2017.1.6 (Fri) PDA について説明しました．1/20 の補講は ** やりません **． ハンドアウト
• 2017.1.12 (Thu) ハンドアウト
• 2017.1.20 (Fri) 補講は**やりません**．
• 2017.2.3 (Fri) 期末試験，14:55-16:40. K211 教室．
• 2017.3.6 (月)，14:55-，本郷キャンパス 理学部7号館102教室 追試対策補講 開催予定． 基本的なことをもう一度説明します．
• 2017.3.27 (月), 10:25-12:10，本郷キャンパス 理学部７号館102教室 追試予定