This preview shows page 1-2-3-4-5-6-7-49-50-51-52-53-54-55-98-99-100-101-102-103-104 out of 104 pages.
Unary and BinarySlide 2Mathematical Prehistory: 30,000 BCPrehistoric UnaryPowerPoint UnarySlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17nth Triangular Numbernth Square NumberBreaking a square up in a new way.Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Look at the columns!Slide 34High School NotationSlide 36Slide 37area of square is ( n-1)2area of new square is ( n)2Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Sumerians [modern Iraq]Slide 48Babylonians absorb SumeriansEgyptiansHarrappans [Indus Valley Culture] Pakistan/IndiaChinaRhind Papyrus: Scribe Ahmes was the Martin Gardener of his day!Rhind Papyrus had 87 Problems.Slide 55A Frequently Arising CalculationSlide 57Action Shot: Mult by X is a SHIFTThe Geometric SeriesThe Geometric Series for X=2The Geometric Series for X=3The Geometric Series for X=½Slide 63Slide 64Slide 65Strings Of Symbols.Strings over the alphabet .Slide 68The set *Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Theorem: f and g are identicalSlide 81Slide 82Slide 83Theorem: Each natural number has a binary representation.Slide 85No Leading Zero Binary (NLZB)Theorem: Each natural number has a unique NLZBinary representation.Slide 88Slide 89Slide 90Slide 91BASE X representationBases In Different CulturesSlide 94Slide 95Slide 96Fundamental Theorem For Binary: Each of the numbers from 0 to 2n-1 is uniquely represented by an n-bit number in binary.Fundamental Theorem For Base-X: Each of the numbers from 0 to Xn-1 is uniquely represented by an n-“digit” number in base-X.Slide 99Other Representations: Egyptian Base 3Slide 101Slide 102Slide 103Study BeeUnary and BinaryGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 4 Sept 8, 2005 Carnegie Mellon UniversityYour Ancient HeritageLet’s take a historical view on abstract representations.Mathematical Prehistory:30,000 BCPaleolithic peoples in Europe record unary numbers on bones.1 represented by 1 mark2 represented by 2 marks3 represented by 3 marks4 represented by 4 marks…Prehistoric Unary1234PowerPoint Unary1234Hang on a minute! Isn’t unary a bit literal as a representation? Does it deserve to be viewed as an “abstract” representation?In fact, it is important to respect the status of each representation, no matter how primitive. Unary is a perfect object lesson.Consider the problem of finding a formula for the sum of the first n numbers. We already used induction to verify that the answer is ½n(n+1)Consider the problem of finding a formula for the sum of the first n numbers. First, we will give the standard high school algebra proof…1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S 21)(n n S1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2SLet’s restate this argument using a UNARY representationAlgebraic argument1 2 . . . . . . . . n= number of white dots.1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S 1 2 . . . . . . . . n= number of white dots= number of yellow dots n . . . . . . . 2 11 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S n+1 n+1 n+1 n+1 n+1= number of white dots= number of yellow dotsnnnnnnThere are n(n+1) dots in the grid1 + 2 + 3 + . . . + n-1 + n = Sn + n-1 + n-2 + . . . + 2 + 1 = S(n+1) + (n+1) + (n+1) + . . . + (n+1) + (n+1) = 2Sn (n+1) = 2S n+1 n+1 n+1 n+1 n+1= number of white dots= number of yellow dotsnnnnnn21)(n n SVery convincing! The unary representation brings out the geometry of the problem and makes each step look very natural.By the way, my name is Bonzo. And you are?Odette.Yes, Bonzo. Let’s take it even further…nth Triangular Numbern = 1 + 2 + 3 + . . . + n-1 + n = n(n+1)/2nth Square Numbern = n + n-1 = n2Breaking a square up in a new way.Breaking a square up in a new way.Breaking a square up in a new way. 1Breaking a square up in a new way. 1 + 3Breaking a square up in a new way. 1 + 3 + 5Breaking a square up in a new way. 1 + 3 + 5 + 7Breaking a square up in a new way. 1 + 3 + 5 + 7 + 9The sum of the first 5 odd numbers is 5 squared 1 + 3 + 5 + 7 + 9 = 52The sum of the first n odd numbers is n squared.PythagorasHere is an alternative dot proof of the same sum….nth Square Numbern = n + n-1 = n2nth Square Numbern = n + n-1 = n2nth Square Numbern = n + n-1 = n2Look at the columns!n = n + n-1Look at the columns!n = n + n-1 = Sum of first n odd numbers.High School Notationn + n-1 = 1 + 2 + 3 + 4 ... + 1 + 2 + 3 + 4 + 5 ... 1 + 3 + 5 + 7 + 9 … Sum of odd numbersHigh School Notationn + n-1 = 1 + 2 + 3 + 4 ... + 1 + 2 + 3 + 4 + 5 ... 1 + 3 + 5 + 7 + 9 … Sum of odd numbersCheck the next one out…( n-1)2 n-1n-1area of square is ( n-1)2( n-1)2 n-1n-1nnnnarea of new square is ( n)2( n-1)2 n-1n-1nnnnnnnn + + nnn-1n-1 = n (= n (n n + + n-1n-1)) = n = n nn ==nnNew shaded area = (( nn))2 =2 = (( n-1n-1))2 2 ++nnarea of new square is ( n)2(( nn))2 =2 = (( n-1n-1))2 2 ++nn (( nn))2 2 = = 11 + + 22 + … + + … + nn(( nn))2 =2 = (( n-1n-1))2 2 ++nn ((nn))2 2 = 1= 133 + 2 + 233 + 3 + 333 + … + + … + nn33 = [ = [ n(n+1)/2n(n+1)/2 ] ]22Can you find a formula for the sum of the first n squares? The Babylonians needed this sum to compute the number of blocks in their pyramids.Can you find a formula for the sum of the first n squares?The ancients grappled with problems of abstraction in representation and reasoning. Let’s look back to the dawn of symbols…Sumerians [modern Iraq]Sumerians [modern …
View Full Document
Unlocking...