计算理论导引与算法复杂性

计算理论导引与算法复杂性IntroductiontotheTheoryofComputationandAlgorithmComplexities主讲：刘国华（学院楼①205室，[e-mail]）助教：张君宝CHANGES(蝶变)CHAPTER1FUNDATION•MATHEMATICALNOTIONSANDTERMINOLOGY•DEFINITIONS,THEOREMS,ANDPROOFS•TYPESOFPROOFS•MATHEMATICALNOTIONSANDTERMINOLOGY1SETS1)SET:asetisagroupofobjectsrepresentedasaunit.2)Waystodescribeasetelementsormembers(membership,)CHAPTER1FUNDATION(1)ListingEXAMPLE1.1{1,2,3,4}(2)RulesEXAMPLE1.2{n|n=mforsomemN}2(3)VenndiagramEXAMPLE1.3AB3)Subset(AB)andpropersubset(AB)4)Multiset5)Cardinality(|A|)6)Infiniteset(|A|=)7)Emptyset(|A|=0)8)Union(AB)9)Intersection(AB)10)Difference(A-B)11)Complement(A)CHAPTER1FUNDATIONEXAMPLE1.4{57,7,7,7,21}EXAMPLE1.5|{57,7,7,7,21}|=5EXAMPLE1.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.9Universeis{57,7,21},A={7}A={57,21}12)Powerset(2orP(A))13)Cartesianproduct(A×B)ACHAPTER1FUNDATIONEXAMPLE1.10A={57,7,21},P(A)={,{57},{21},{7},{57,7},{57,21},{7,21},{57,7,21}},|P(A)|=?EXAMPLE1.11A={57,7,21},B={7,9}A×B={(57,7),(57,9),(7,7),(7,9),(21,7),(21,9)}CONSIDERA×A×A×A=?4A×A×A×A=A={(57,57,57,57),(57,57,57,7),(57,57,57,21),}|A|22SEQUENCESANDTUPLES1)Sequence:asequenceofobjectsisalistoftheseobjectsinsomeorder.2)Tuple:afinitesequence.3)k-tuple:asequencewithkelements.4)pair:2-tuple.3FUNCTIONSANDRELATIONS1)Function(mapping):afunctionisanobjectthatsetsupaninput-outputrelationship.CHAPTER1FUNDATION(2,1,1,5,5)(2,1)2)Domain:thesetofpossibleinputstoafunction.3)Range:thesetfromwhomtheoutputsofafunctioncome.f:DR4)Waystodescribeaspecificfunction(1)Procedure(2)Listing5)K-aryfunction:afunctionfwhosedomainisA1××Ak,theinputisak-tuple(a1,a2,,ak),andaiiscalledtheargumentstof,kiscalledtheary.CHAPTER1FUNDATIONx=y+1nf(n)01123440f:{0,1,2,3,4}{0,1,2,3,4}7)Predicateorproperty:isafunctionwhoserangeis{TRUE,FALSE}.8)Relation:apropertywhosedomainisasetofk-tuplesA××A.aRbR(a1,,ak)9)Equivalencerelation:abinaryrelationRisanequivalencerelationifRsatisfiesthreeconditions:(1)Risreflexiveifforeveryx,xRx;(2)Rissymmetricifforeveryxandy,xRyimpliesyRx;andCHAPTER1FUNDATION(3)Ristransitiveifforeveryxandy,xRyandyRzimpliesxRz.EXAMPLE1.12A={57,7,21}R={(57,57),(7,7),(21,21),(57,7),(7,57),(7,21),(57,21),(21,7),(21,57)}CHAPTER1FUNDATION4GRAPHSCHAPTER1FUNDATIONInmathematics,agraphisanabstractrepresentationofasetofobjectswheresomepairsoftheobjectsareconnectedbylinks.Theinterconnectedobjectsarerepresentedbymathematicalabstractionscalledvertices,andthelinksthatconnectsomepairsofverticesarecallededges.Typically,agraphisdepictedindiagrammaticformasasetofdotsforthevertices,joinedbylinesorcurvesfortheedges.1)Graph:agraphisanorderedpairG=(V,E)comprisingasetVofverticesornodestogetherwithasetEofedgesorlines,whichisasubsetofV×V.2)Subgraph3)Path,simplepath,connect,cycle,simplecycleBAFDECG=(V,E),V=?,E=?G=(V,E),V={A,B,C,D,E,F}E={(A,B),(B,A),(A,F),(F,A),(B,F),(F,B),(E,F),(F,E),(B,C),(C,B),(C,E),(E,C)}5STRINGANDLANGUAGES1)Alphabet:anynonemptyfiniteset.={0,1},={a,b,c,d}2)Symbol3)String:astringoveranalphabetisafinitesequenceofsymbolsfromthatalphabet.01110,aaabc4)Length|aaabc|=55)Emptystring6)Reverseaaabc=cbaaa7)Substring:stringzisasubstringofwifzappearsconsecutivelywithinw.CHAPTER1FUNDATIONR8)Concatenation(zw)01110aaabcxxx=x01110=?9)Lexicographicordering(,0,1,00,01,10,11,000,)10)Language:alanguageisasetofstrings.CHAPTER1FUNDATIONkk4011100111001110011106BOOLEANLOGIC1)Negation0=1,1=02)Conjunction01=0,11=13)Disjunction01=14)Exclusiveor00=0,01=15)Equality00=1,10=06)Implication10=0,11=1,00=1,10=07)DistributivelawP(QR)=(PQ)(PR)P(QR)=(PQ)(PR)CHAPTER1FUNDATIONCHAPTER1FUNDATION•DEFINITIONS,THEOREMS,ANDPROOFS1Definition:apassagethatexplainsthemeaningofaterm(aword,phraseorothersetofsymbols),oratypeofthing.2Mathematicalstatement:ameaningfulcompositionofwordswhichcanbeconsideredeithertrueorfalse.3Proof:aproofisaconvincinglogicalargumentthatastatementistrue.4Theorm5Lemma6CorollaryCHAPTER1FUNDATION•TYPESOFPROOF1PROOFBYCONSTRUCTIONTHEOREM1.1Foreachevennumberngreaterthan2,thereexistsa3-regulargraphwithnnodes.2PROOFBYCONTRADICTION3PROOFBYINDUCTIONCHAPTER1FUNDATION练习题：1.已知函数f:{0,1,2,3,4}{0,1,2,3,4}的定义如下表：问：1)f(1)=?;2)f(f(f(f(4))))=?2.试写出满足下述要求的关系。1）自反的、传递的；2）对称的、不自反的；3）不对称的、传递的。3.写出下图的形式化定义。nf(n)01123440BAFDEC10#5030152011#