This preview shows page 1-2-3-4-5-6-7-8-9-60-61-62-63-64-65-66-67-121-122-123-124-125-126-127-128-129 out of 129 pages.
Induction II: Inductive PicturesSlide 2Slide 3Sk´ “1+2+4+8+…+2k = 2k+1 -1” Use induction to prove k¸0, SkSlide 5Slide 6Slide 7Invariant Induction Suppose we have a time varying world state: W0, W1, W2, … Each state change is assumed to come from a list of permissible operations. We seek to prove that statement S is true of all future worlds.Odd/Even Handshaking Theorem: At any party, at any point in time, define a person’s parity as ODD/EVEN according to the number of hands they have shaken. Statement: The number of people of odd parity must be even.Slide 10Slide 11Slide 12Slide 13Inductive Definition of T(n)Slide 15Guess a closed form formula for T(n). Guess G(n)Two equivalent functions?Inductive Proof of EquivalenceSlide 19Solving Recurrences Guess and VerifyTechnique 2 Guess Form and Calculate CoefficientsSlide 22GRAPHSDefinition: GraphsDefinition: Directed GraphsDefinition: TreeClassic Visualization: TreeSlide 28Slide 29Choice TreeDefinition: Labeled TreeSlide 32Slide 33Inductive Definition Of Labeled Tree W(n)Slide 35Slide 36Slide 37Invariant: LabelSum W(n) = T(n)Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50The Lindenmayer GameSlide 52Slide 53Aristid Lindenmayer (1925-1989)The Koch GameSlide 56Slide 57The Koch Game F+F--F+FThe Koch Game F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+FKoch CurveSlide 61Slide 62Hilbert’s Space Filling CurvePeano-Gossamer CurveSierpinski TriangleLindenmayer 1968Slide 67Inductive LeafSlide 69Slide 70Formal Grammar: G = (T, V, S, P)Example.Slide 73S 1 SSS 1 bS 1 baDefinition of x k yLanguage Produced By Formal Grammar GLanguage = {a,b}+Evaluating A Formal DerivationSlide 79G = BalancedYo, dude! ((())()) is like totally balancedExpressions in Propositional LogicYo, dude! :(xÆy) is like totally an expression in propositional logic.Meaning: The Part Symbol Dude IgnoresInductively Associate a MEANING M(E) of any expression EExpressions in First Order LogicE.g., Number TheorySlide 88Statements in JavaExpressions in JavaNumerical Expressions in JavaPrograms in JavaSlide 93Symbol TemplatesTemplate Example.Template ExamplesAlgebra Game TemplatesAlgebra Game Allows substitution too!Example UBL = { S, =}Example UBL = { S, =}Slide 101Slide 102UBLPropositional LogicExample: p, : p q implies qSlide 106Slide 107First-order PredicatesInductive Grammar NotationGrammar:Computer Language SyntaxThe Natural NumbersInductive Definition of +Defining One to Ten1 + 1 = 2Inductive Definition of *Inductive Definition of ^Inductive Definition of Base 10 Notation. = { 0, 1, 2, 3, . . .}Slide 120a = [a DIV b]*b + [a mod b]45 = [45 DIV 10]*10 + [ 45 MOD 10] = 4*10 + 5Giuseppe Peano [1889] Axiom’s For Slide 124Lemma: 0 + x = xLemma: Sx + y = S(x+y)Theorem: Commutative Property Of Addition: x + y = y + x“God Made Induction On The Naturals. Everything Else Is The Work Of Man.”ReferencesInduction II:Inductive PicturesGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 14 Feb 26, 2004 Carnegie Mellon UniversityInductive Proof: “Standard” Induction“Least Counter-example”“All Previous” Induction Inductive Definition:RecurrencesRecursive ProgrammingTheorem? (k¸0)1+2+4+8+…+2k = 2k+1 -1Try it out on small examples:20 = 21 -120 + 21 = 22 -120 + 21 + 22= 23 -1Sk´ “1+2+4+8+…+2k = 2k+1 -1”Use induction to prove k¸0, SkEstablish “Base Case”: S0. We have already check it. Establish “Domino Property”: k¸0, Sk ) Sk+1“Inductive Hypothesis” Sk: 1+2+4+8+…+2k = 2k+1 -1Add 2k+1 to both sides:1+2+4+8+…+2k + 2k+1= 2k+1 +2k+1 -11+2+4+8+…+2k + 2k+1= 2k+2 -1FUNDAMENTAL LEMMA OF THE POWERS OF TWO:The sum of the first n powers of 2, is one less than the next power of 2.Yet another way of packaging inductive reasoning is to define an “invariant”.Invariant (adj.) 1. Not varying; constant. 2. (mathematics) Unaffected by a designated operation, as a transformation of coordinates.Yet another way of packaging inductive reasoning is to define an “invariant”.Invariant (adj.)3. (programming) A rule, such as the ordering an ordered list or heap, that applies throughout the life of a data structure or procedure. Each change to the data structuremust maintain the correctness of the invariant.Invariant InductionSuppose we have a time varying world state: W0, W1, W2, …Each state change is assumed to come from a list of permissible operations. We seek to prove that statement S is true of all future worlds. Argue that S is true of the initial world.Show that if S is true of some world – then S remains true after one permissible operation is performed.Odd/Even Handshaking Theorem: Odd/Even Handshaking Theorem: At any party, at any point in time, define a At any party, at any point in time, define a person’s parity as ODD/EVEN according to person’s parity as ODD/EVEN according to the number of hands they have shaken.the number of hands they have shaken. Statement: The number of people of odd Statement: The number of people of odd parity must be even.parity must be even.Initial case: Zero hands have been shaken at the start of a party, so zero people have odd parity.If 2 people of different parities shake, then they both swap parities and the odd parity count is unchanged. If 2 people of the same parity shake, they both change. But then the odd parity count changes by 2, and remains even.Inductive Definition of n! [said n “factorial”]0! = 1; n! = n*(n-1)!0! = 1; n! = n*(n-1)!F:=1;For x = 1 to n doF:=F*x;Return FProgram for n! ?0! = 1; n! = n*(n-1)!F:=1;For x = 1 to n doF:=F*x;Return FProgram for n! ? n=0 returns 1n=1 returns 1n=2 returns 20! = 1; n! = n*(n-1)!F:=1;For x = 1 to n doF:=F*x;Return FLoop Invariant: F=x!True for x=0. If true after k times through – true after k+1 times through.Inductive Definition of T(n)T(1) = 1T(n) = 4 T(n/2) + nNotice that T(n) is inductively defined for positive powers of 2, and undefined on other values.Inductive Definition of T(n)T(1) = 1T(n) = 4T(n/2) + nNotice that T(n) is inductively defined for positive powers of 2, and undefined on other values.T(1)=1 T(2)=6 T(4)=28 T(8)=120Guess a closed form formula for T(n).Guess G(n)G(n) = 2n2 - nLet the domain of G be the powers of two.Two equivalent functions?G(n) = 2n2 - nLet the domain of G be the powers of two.T(1) = 1T(n) = 4 T(n/2) + nDomain of T are the powers of two.Inductive Proof of EquivalenceInductive Proof of
View Full Document
Unlocking...