计算理论导引与算法复杂性初步.pptVIP

* 计算理论导引与算法复杂性 Introduction to the Theory of Computation and Algorithm Complexities 主讲：刘国华 （学院楼①205室，ghliu@dhu.edu.cn） 助教：张君宝 CHANGES(蝶变) CHAPTER 1 FUNDATION MATHEMATICAL NOTIONS AND TERMINOLOGY DEFINITIONS,THEOREMS,AND PROOFS TYPES OF PROOFS MATHEMATICAL NOTIONS AND TERMINOLOGY 1 SETS 1)SET:a set is a group of objects represented as a unit. 2)Ways to describe a set elements or members (membership?,? ) CHAPTER 1 FUNDATION (1)Listing EXAMPLE1.1 {1,2,3,4} (2)Rules EXAMPLE1.2 {n|n=m for some m?N } 2 (3)Venn diagram EXAMPLE1.3 A B 3)Subset(A?B) and proper subset (A?B) 4)Multiset 5) Cardinality(|A|) 6)Infinite set (|A|=?) 7)Empty set (|A|=0) 8)Union(A?B) 9)Intersection(A?B) 10)Difference(A-B) 11)Complement(A) CHAPTER 1 FUNDATION EXAMPLE1.4 {57,7,7,7,21 } EXAMPLE1.5 |{57,7,7,7,21 }|=5 EXAMPLE1.6 {57,7,21 }? {8,9} ={21,57,7, 8,9} EXAMPLE1.7 {57,7,21 }?{7,9} ={7} EXAMPLE1.8 {57,7,21 }-{7,9} ={57,21} EXAMPLE1.9 Universe is {57,7,21 }, A={7} A={57,21} 12)Power set(2 or P(A)) 13)Cartesian product(A×B) A CHAPTER 1 FUNDATION EXAMPLE1.10 A={57,7,21 }, P(A)={?,{57},{21},{7},{57,7}, {57,21},{7,21},{57,7,21}}, |P(A)|=? EXAMPLE1.11 A={57,7,21 }, B={7,9} A×B={(57,7),(57,9),(7,7),(7,9),(21,7),(21,9)} CONSIDER A×A×A×A=? 4 A×A×A×A=A ={(57,57,57,57), (57,57,57,7), (57,57,57,21),? } |A| 2 2 SEQUENCES AND TUPLES 1)Sequence:a sequence of objects is a list of these objects in some order. 2)Tuple:a finite sequence. 3)k-tuple:a sequence with k elements. 4)pair:2-tuple. 3 FUNCTIONS AND RELATIONS 1)Function(mapping):a function is an object that sets up an input-output relationship. CHAPTER 1 FUNDATION (2,1,1,5,5) (2,1) 2)Domain:the set of possible inputs to a function. 3)Range:the set from whom the outputs of a function come. f:D?R 4)Ways to describe a specific function (1)Procedure (2)Listing 5)K-ary function: a function f whose domain is A1 ×? ×Ak, the input is a k-tuple