理学类情报数理学精选PPT.ppt

《理学类情报数理学精选PPT.ppt》由会员分享，可在线阅读，更多相关《理学类情报数理学精选PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、理学类情报数理学第1页，此课件共42页哦2履修2007年度大学院奇数（前期）開講K336大学院棟D（次回）教室：時限：火曜日時限（12:5014:20）担当草苅良至第2页，此课件共42页哦3講義予定計算機理論計算限界問題難現実問題計算言語理論計算量理論論第3页，此课件共42页哦4参考書M.R.Garey and D.S.Johnson,Computers And Intractability:A guide to the Theoryof NP-Completeness,Freeman,1979,ISBN:0-7167-1045-5岩間一雄、理論入門昭晃堂、2001、ISBN：4-7856-3

2、125-2、言語理論計算論 I,II社、1984,ISBN:4-7819-0374-6,4-7819-0432-7M.Sipser著、計算理論基礎、共立出版、1997,ISBN:4-320-02948-8岩間一雄、言語計算理論社、2003、ISBN：4-339-01821-XV.V.著、浅野孝夫訳、近似、東京、ISBN:4-431-70991-6第4页，此课件共42页哦5正規表現第5页，此课件共42页哦611有限、答計算機考。101110入力自動機械入力”一度“走査、点灯消灯。自動機械(有限）。第6页，此课件共42页哦7有限制御部01有限概略入力書文字定要素有限制御部内部状態初期状態状態変化受

3、理判断第7页，此课件共42页哦8有限数学的定義有限、項組与。、有限集合、状態表。有限集合、入力記号集合表。写像（）、状態遷移表。状態遷移関数。、初期状態表。受理状態集合表。第8页，此课件共42页哦9有限図式表現（状態遷移図）有限、状態遷移図表現。例0011形式的定義（数学的定義）、次状態遷移表定義。第9页，此课件共42页哦10練習次数学的表現与。011001第10页，此课件共42页哦1112言語計算機扱対象、0,1表数考。、0,1並一種言語。任意有限集合。要素文字。任意列文字列。文字列集合、（上）言語。、計算機扱対象再考。以下、言語数学的定義与。第11页，此课件共42页哦12言語例1例：上文字

4、列例：bookaaaab上言語例：第12页，此课件共42页哦13言語例2例：上文字列例：000001100010001111110111上言語例：第13页，此课件共42页哦14言語関諸概念、文字列関諸概念定義与。文字列w含文字数、文字列w長、文字列長：記号表。空列：長0文字列空列、記号 表。連結：文字列 後文字列 繋文字列 連結次記号表。第14页，此课件共42页哦15例上文字列考。、次式成立。文字列連結演算、交換不可第15页，此课件共42页哦16言語関諸概念、言語関諸概念定義与。言語連結（連結演算）：言語閉包(演算）：言語和集合(和集合演算）：言語。第16页，此课件共42页哦17例上言語考。、

5、次式成立。第17页，此课件共42页哦18要素無言語空列言語要素無言語空列言語異。、。第18页，此课件共42页哦19言語受理入力集合、入力記号 上言語。例0011 受理言語 書。例、。第19页，此课件共42页哦20練習次言語受理 作成。、状態遷移図、形式的定義両方示事。第20页，此课件共42页哦2113非決定性(有限）、入力記号、状態遷移一意定。制限緩和計算機考。非決定性、同入力対複数遷移”。対、同入力対、一遷移”決定性。第21页，此课件共42页哦22略記決定性、英語、Deterministic Finite Automaton、DFA略記。非決定性、英語、Non-determinisc Fin

6、ite Automaton、NFA略記。第22页，此课件共42页哦23NFA形式的定義非決定性有限、項組与。、有限集合、状態表。有限集合、入力記号集合表。写像 、状態遷移表。状態遷移関数。、初期状態表。受理状態集合表。第23页，此课件共42页哦24NFA状態遷移図0,110,10,1形式的定義（数学的定義）、次状態遷移表定義。第24页，此课件共42页哦25 受理言語 、。実、非決定性受理言語同言語受理決定性常存在。自体能力差。、証明。第25页，此课件共42页哦26言語受理DFA 示。0110001111111000第26页，此课件共42页哦27練習言語受理非決定性決定性示。上第27页，此课件共

7、42页哦28 例、DFANFA状態遷移調。DFANFA状態遷移入力：。入力第28页，此课件共42页哦29受理NFA受理、入力系列受理遷移系列存在。受理系列第29页，此课件共42页哦30 対、入力1011状態遷移木示、受理不受理確認。練習第30页，此课件共42页哦311正規表現(正則表現）DFA受理言語対、正規表現呼別表現法知。上正規表現、下記帰納的定義。、表集合、空集合。、表集合、。各元 対、正規表現、表集合、。言語 言語 表正規表現 、正規表現、表。正規表現形式的定義第31页，此课件共42页哦32正規演算優先順位正規表現演算記号優先順位、括弧省略。通常、上優先順位考、不必要括弧省略。第32页

8、，此课件共42页哦33例 上正規表現考。第33页，此课件共42页哦34練習、次正規表現表言語含文字列示、直感的意味述。（）（）（）（）（）第34页，此课件共42页哦35正規表現応用UNIX、正規表現引数指定。、UNIX正規表現、UNIX独特注意。：任意文字列表。：一文字以上文字列。：文字：文字第35页，此课件共42页哦36例$ls*.caverage.chello.csort.csum.c$ls ab*averageaverage.c$ls h-s*.chello.c sort.csum.c$*.c.c終文字列。（拡張子区別、特定種類指定。）ab*ab始文字列。（長名一括扱。）h-s*.chs

9、文字始、.c終文字列。（組合絞込。）第36页，此课件共42页哦371拡張NFADFA、NFA共、入力記号文字対、遷移行。制限緩和計算機考。拡張NFA、遷移正規表現許NFA。拡張NFA：Generalized Non-deterministic finite Automaton GNFA略。第37页，此课件共42页哦38GNFA形式的定義GNFA、項組与。、有限集合、状態表。有限集合、入力記号集合表。3.写像 、状態遷移表。状態遷移関数。、上正規表現集合（上正規言語）表。、初期状態表。受理状態表。第38页，此课件共42页哦39GNFA状態遷移図1形式的定義（数学的定義）、次状態遷移表定義。第39页，此课件共42页哦401GNFA関注意初期状態、他状態遷移。受理状態、他状態遷移。入矢印（）無。出行（）無。初期状態、受理状態。特、受理状態注意。第40页，此课件共42页哦41練習言語上受理状態拡張NFA状態遷移図、形式的定義両方示。第41页，此课件共42页哦更多资源初一语文初一英语初一数学初一政治初一历史初一地理初一生物第42页，此课件共42页哦