计算の理论I-数学的概念と记法-.ppt

計算理論 I 数学的概念記法,月曜校時 大月 美佳,集合 (1.2節 pp. 68),集合(set) 対象（重複）集 元(member) 集対象,集合,元,部分集合、真部分集合,AB部分集合AB含 := A元B元 真部分集合 AB := ABAB A元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 集合 (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 : 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) 正(可算)示命題P P正(可算)仮定 仮定例導出 2例P満示,1対1写像f(2i)=i,証明例 (p. 8),S1(整数全体)S2 (実数全体)1対1対応仮定 例次数考 各i=1, 2, 3, 、第i番目実数（1対応正整数i対応実数）小数点以下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) 定義域値域同集合S場合関係 aRb := (a, b)関係R属,1R3 2R2 2R3,関係性質,反射的 (reflexive) 非反射的 (irreflexive) 推移的 (transitive) 対称的 (symmetric) 非対称的 (asymmetric),反射的,反射的 (reflexive) := S各元aaRa,R,1R1 2R2 3R3,非反射的,非反射的 (irreflexive) := S各元aaRa成立,R,1R1 2R2 3R3,推移的,推移的 (transitive) := aRbbRc常aRc,R,1R2 2R3 1R3,対称的,対称的 (symmetric) := aRb常bRa,R,1R22R1 1R33R1,非対称的,非対称的 (asymmetric) := aRbbRa決成立,R,1R22R1 1R33R1,非対称的関係常非反射的,関係性質例 (例1.3 p. 9),整数上大小関係 推移的 abbcac 非対称的 abba決 非反射的,同値関係,同値関係 (equivalence relation) := 反射的、対称的、推移的関係,R,1R12R23R3,2R33R2,反射的,対称的,推移的,同値類,同値類 (equivalence class) := 次性質持部分集合Si Si, ijSiSj Si各元a, b対aRb ijSi各元aSj各元b対aRb成立 SSi和Si表,同値関係例 (例1.4 pp. 910),法m関合同 (congruence module m) := i-jm割切 := im j ij mod m 反射的： 任意aa-am割切 推移的： am bbm c、am c a=mx+b, b= my+c a=m（x+y)+c 対称的： am bbm a a-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+元,123 13,反射的推移的閉包,R反射的推移的閉包:R* = R+ (a, a)|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, 5 E=(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, 4 2 2, 5,有向,有向 (directed graph, digraph) G G=(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, father?) : 前者 子 (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(|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 （) 空集合、無限個記