《计算の理论I-数学的概念と记法.ppt》由会员分享，可在线阅读，更多相关《计算の理论I-数学的概念と记法.ppt（49页珍藏版）》请在三一办公上搜索。
1、計算理論 I数学的概念記法,月曜校時大月 美佳,集合(1.2節 pp.68),集合(set)対象（重複）集元(member)集対象,集合,元,部分集合、真部分集合,AB部分集合AB含:=A元B元真部分集合 AB:=ABABA元B含A元B元ABAB=AB,A,B,A,B,集合記述法,元列挙 0,1 dog,cat 元満条件記述 x|P(x):=P(x)真x集合元所属集合書 xA|P(x):=P(x)真A元x集合=x|P(x)xA,集合演算（一部）,和(union):AB共通部分(intersection):AB差(difference):AB直積(Cartesian product):AB集合(
2、power set):,和(union),AB=x|xAB元 例A=1,2 B=2,3 AB=1,2,3,共通部分(intersection),AB=x|xA元B元 例A=1,2 B=2,3 AB=2,差(difference),AB=x|xA元B元 例A=1,2 B=2,3 AB=1,直積(Cartesian product),AB=(x,y)|xA元yB元 例A=1,2 B=2,3 AB=(1,2),(1,3),(2,2),(2,3)An個Bm個、ABnm個,集合(power set),=B|BA 例A=1,2=,1,2,1,2 An個、個,写像(projection?),線形代数写像f:
3、f(x)=y,f(U)=V,x,y,A,B,f,f,U,V,濃度(cardinality),等濃度:=集合S1S2、S1S2上1対1写像有限集合S1S2異濃度無限集合S1S2等濃度場合,真部分集合無限集合（等濃度）,例S1:偶数全体S2:整数全体,1対1写像f(2i)=i,真部分集合無限集合（異濃度）,例S1:整数全体S2:実数全体証明対角線論法(diagonalization)正(可算)示命題PP正(可算)仮定仮定例導出2例P満示,1対1写像f(2i)=i,証明例(p.8),S1(整数全体)S2(実数全体)1対1対応仮定例次数考 各i=1,2,3,、第i番目実数（1対応正整数i対応実数）小数
4、点以下i桁目数字、法105加数字、小数点以下i桁目実数1満,対角線,yi=xii、法105加数字(0i)例：83,50,16,対角線,y 各位数字xi各位数字同有(yixii5),可算無限,可算無限(countably many)=加算(countable):=正整数1対1対応集合例 有理数集合 空上（有限長）記号列集合*集合 整数 0,1 関数集合,実数集合同濃度持,関係,(2項)関係(binary relation):=順序対集合順序対（順序対(pair,組)）(1,2)(2,1),RAB,A,B,定義域(domain),値域(range),S上関係,S上関係(relation on S)
5、定義域値域同集合S場合関係aRb:=(a,b)関係R属,1R32R22R3,関係性質,反射的(reflexive)非反射的(irreflexive)推移的(transitive)対称的(symmetric)非対称的(asymmetric),反射的,反射的(reflexive):=S各元aaRa,R,1R12R23R3,非反射的,非反射的(irreflexive):=S各元aaRa成立,R,1R12R23R3,推移的,推移的(transitive):=aRbbRc常aRc,R,1R22R31R3,対称的,対称的(symmetric):=aRb常bRa,R,1R22R11R33R1,非対称的,非対
6、称的(asymmetric):=aRbbRa決成立,R,1R22R11R33R1,非対称的関係常非反射的,関係性質例(例1.3 p.9),整数上大小関係推移的abbcac非対称的abba決非反射的,同値関係,同値関係(equivalence relation):=反射的、対称的、推移的関係,R,1R12R23R3,2R33R2,反射的,対称的,推移的,同値類,同値類(equivalence class):=次性質持部分集合SiSi,ijSiSjSi各元a,b対aRbijSi各元aSj各元b対aRb成立SSi和Si表,同値関係例(例1.4 pp.910),法m関合同(congruence mod
7、ule m):=i-jm割切:=im j ij mod m反射的：任意aa-am割切推移的：am bbm c、am ca=mx+b,b=my+c a=m（x+y)+c対称的：am bbm aa-b=mx b-a=m（-x),整数全体m同値類,m個,関係閉包,R G 閉包(G-closure)G：関係関性質集関係R部分集合含、G性質有最小関係R,R,R,推移的閉包,推移的閉包(transitive closure)R含最小推移関係R+(a,b)R元、(a,b)R+元(a,b)R+元(b,c)R元(a,c)R+元12示以外R+元,12313,反射的推移的閉包,R反射的推移的閉包:R*=R+(a,a
8、)|aS,R+,R,R*,最後,時間：15分終了後横交換、解答採点提出帰次回、言語履修出帰,開始,（1.2節 pp.25）,使？状態遷移図文法木各種構造他,定義,G=(V,E)V:有限個頂点(vertex,node)集合E:頂点対(v1,v2)表記)示辺(edge)集合例（図1.1 p.3）V=1,2,3,4,5E=(n,m)|n+m=4、n+m=7,道,道(path)、路頂点列 v1,v2,vk(k1)道、(v1,v2),(v2,v3),(vk-1,vk)辺閉路(cycle):vi=vk道例（図1.1 p.3）1,3,422,5,有向,有向(directed graph,digraph)GG
9、=(V,E)E要素有向辺(arc)vw:vw向有向辺例(図1.2 p.3)(1,2,3,4,ij|ij),前者(predecessor),後者(successor),有向道,有向道(path):=vivi+1(1ik)有向辺頂点列 v1,v2,vk(、k1)例(図1.2 p.3)1234:14道,木,木(tree,ordered directed tree)次性質持有効前者持、各頂点道必存在根(root)呼頂点一持根以外頂点一前者持各頂点後者左右一列順序,木書方,根上、各有向辺下向書有向辺矢印書必要頂点（）順序従左右書,有向辺(arc),根(root),木特有用語,親(parent,fathe
10、r?):前者子(child,son?):後者葉(leaf):子持頂点内部(interior)頂点:葉頂点先祖(ancestor)子孫(descendant)頂点v1v2道(v1:先祖、v2:子孫)各頂点自分自身先祖子孫,葉,親,子,内部頂点,構文木(例1.3 p.4),英単語葉,品詞名内部頂点,The quick brown fox jumped over the lazy dog,記号記号列,記号:=定義（例）a,b,c,1,2,記号列(string)語(word):=記号有限個並列（例）abc,cba,a1,2c|w|:=記号列w長(length)（例）abcb長|abcb|4空列:=長0
11、(|0)記号列,接頭語接尾語,接頭語(prefix):=記号列(w)先頭文字列（長0|w|）（例）abc接頭語,a,ab,abc接尾語(postfix):=記号列(w)末尾文字列（長0|w|）（例）abc接尾語,c,bc,abc,真（proper)接頭語接尾語,記号列連接,連接(concatenation):=記号列演算（例）doghouse連接doghouse演算記号記号列wx連接wx単位元w=w=w,言語,(alphabet):=空記号有限集合（例）q,z,1 0（)空集合、無限個記号集合言語(language,formal language)属記号列集合（例）空集合、,言語,0,1上回文(palindrome)要素無限個,0,1,00,11,010,11011,無限個記号上有限個回文（記号有限）上 上全記号列集合*=a、*=,a,aa,aaa,=0,1、*=,0,1,00,01,10,11,000,
