6 mar 2014 · Chapters 1 and 8 of Mathematics for Computer Science by E Lehman, F T Leighton, Web link: math stanford edu/∼lekheng/flt/kleiner pdf
Previous PDF | Next PDF |
[PDF] Mathematics for Computer Science
Department of Electrical Engineering and Computer Science and the Computer Science The standard procedure for establishing truth in mathematics was invented by Eu http://oldwww acm org/pubs/membernet/stories/floyd pdf written by
[PDF] Mathematics for Computer Science - courses - MIT
genuine understanding Proofs also play a growing role in computer science; they A mathematical proof of a proposition is a chain of logical deductions leading to the http://oldwww acm org/pubs/membernet/stories/floyd pdf written by his
[PDF] Mathematics for Computer Science Eric Lehman and Tom Leighton
Graphs are the most useful mathematical objects in computer science The probability density function ( pdf ) for a random variable R with codomain V is a
[PDF] Mathematics for Computer Scientists - UK FTVS
Mathematics for Computer Scientists 4 Contents Contents Introduction 5 1 Numbers 6 2 The statement calculus and logic 20 3 Mathematical Induction 35
[PDF] Discrete Mathematics For Computer Science - Skyline University
Chapters 1 and 8 of Mathematics for Computer Science by E Lehman, F T Leighton, Web link: math stanford edu/∼lekheng/flt/kleiner pdf Further reading :
[PDF] Discrete Mathematics For Computer Science
6 mar 2014 · Chapters 1 and 8 of Mathematics for Computer Science by E Lehman, F T Leighton, Web link: math stanford edu/∼lekheng/flt/kleiner pdf
[PDF] Mathematics for Computer Science Facts & Formulae - Mathcentre
Mathematics for Computer Science Facts Formulae mathcentre is a project offering students and staff free resources to support the transition from
[PDF] Discrete Mathematics For Computer Scientists cepuneporg
Rather than enjoying a good PDF subsequent to a mug of coffee in the afternoon, on the other hand they juggled bearing in mind some harmful virus inside their
[PDF] Discrete Mathematics For Computer Science wwwcepuneporg
Fundamentals of Discrete Math for Computer Science-Tom Jenkyns 2012-10-16 the mathematical foundation of computer science Discrete mathematics is the basis of much of Read Online Discrete Mathematics For Computer Science pdf
[PDF] DISCRETE MATHEMATICS FOR COMPUTER SCIENCE
Discrete Mathematics for Computer Science Key College Publishing, Emeryville , Cali- fornia, 2006 Examinations There will be a final exam (covering the
[PDF] mathématiques appliquées à l'économie pdf
[PDF] mathématiques appliquées a l'informatique
[PDF] mathématiques appliquées à la gestion
[PDF] mathématiques appliquées a la gestion pdf
[PDF] mathématiques appliquées à la gestion pdf gratuit
[PDF] mathématiques appliquées à la médecine
[PDF] maths 9th ncert solutions chapter 9
[PDF] maths class 9 herons formula extra questions
[PDF] maths elevations
[PDF] maths libres fractions décimales
[PDF] maths libres les fractions
[PDF] maths quiz questions with answers for class 7 pdf
[PDF] maths syllabus in uae
[PDF] matlab 2 dimensional fourier transform
Version of March 6, 2014
Notes for Part IA CST 2013/14Discrete Mathematics
For Computer Science
Prof Marcelo Fiore
Marcelo.Fiore@cl.cam.ac.uk
- 0 -Version of March 6, 2014
Lecture plan
Proofs
1. Preliminaries (pages 5-11) and introduction (pages 12-38).
2. Implication (pages 39-57) and bi-implication (pages 58-68).
3. Universal quantification (pages 69-77) and conjunction
(pages 78-85).4. Existential quantification (pages 86-99).
5. Disjunction (pages 100-111) and a little arithmetic
(pages 112-127).6. Negation (pages 128-147).
- 1 -Version of March 6, 2014Numbers
7. Number systems (pages 148-160).
8. The division theorem and algorithm (pages 161-171) and
modular arithmetic (pages 172-178).9. On sets (pages 179-185), the greatest common divisor
(pages 186-193), and Euclid's algorithm (pages 194-215) and theorem (pages 216-221).10. The Extended Euclid's Algorithm (pages 222-235) and the
Diffie-Hellman cryptographic method (pages 236-240). - 2 -Version of March 6, 2014
11. Mathematical induction: the Principle of Induction
(pages 241-259), the Principle of Induction from a basis (pages 260-264), and the Principle of Strong Induction from a basis (pages 264-286). Sets12. Extensionality, subsets and supersets, separation, Russell's
paradox, empty set, powerset, Hasse and Venn diagrams, the powerset Boolean algebra (pages 287-313).13. Unordered and ordered pairing, products, big unions, big
intersections, and disjoint unions (pages 314-339). - 3 -Version of March 6, 2014
14. Relations, internal diagrams, relational composition, matrices,
directed graphs, reachability, preorders, and reflexive-transitive closure (pages 340-368).15. Partial functions, (total) functions, bijections, andequivalence
relations and set partitions (pages 369-397).16. Calculus of bijections, characteristic (or indicator)functions,
finite and infinite sets, surjections, and enumerability and countability (pages 398-420).17. Choice, injections, Cantor-Bernstein-Schroeder theorem, direct
and inverse images, replacement and set-indexing, unbounded cardinality, and foundation (pages 421-449). - 4 -Version of March 6, 2014
A Zen story
from the Introduction ofMathematics Made Difficultby C.E. Linderholme
One of the great Zen masters had an eager disciple who never lost an opportunity to catch whatever pearls of wisdom might dropfrom the master's lips, and who followed him about constantly. One day, deferentially opening an iron gate for the old man, the disciple asked, `How may I attain enlightenment?' The ancient sage, though with- ered and feeble, could be quick, and he deftly caused the heavy gate to shut on the pupil's leg, breaking it. - 5 -Version of March 6, 2014
What are we up to?
?Learn to read and write, and work with, mathematicalarguments. ?Doing some basic discrete mathematics. ?Getting a taste of computer science applications. - 6 -Version of March 6, 2014
What is it that we do?
In general:
Mathematical models and methods to analyse problems that arise in computer science.In particular:
Make and study mathematical constructions by means of definitions and theorems. We aim at understanding their properties and limitations. - 7 -Version of March 6, 2014
Application areas
algorithmics - compilers - computability - computer aided verification computer algebra - complexity - cryptography - databases digital circuits - discrete probability - model checking - network routing - program correctness - programming languages - security semantics - type systems - 8 -Version of March 6, 2014
Preliminaries
Complementary reading:
?Preface and Part I ofHow to Think Like a MathematicianbyK.Houston.
- 9 -Version of March 6, 2014
Some friendly advice
by K. Houston from the Preface ofHow to Think Like a Mathematician
It's up to you.Be active.
Think for yourself.Question everything.
Observe.Prepare to be wrong.
Seek to understand.Develop your intuition.Collaborate.Reflect.
- 10 -Version of March 6, 2014
Study skills
Part I ofHow to Think Like a Mathematician
by K. Houston ?Reading mathematics ?Writing mathematics ?How to solve problems - 11 -Version of March 6, 2014Proofs
Topics
Proofs in practice. Mathematical jargon: statement, predicate, theorem, proposition, lemma, corollary, conjecture, proof, logic, axiom, definition. Mathematical statements: implication, bi-implication, universal quantification, conjunction, existential quantification, disjunction, negation. Logical deduction: proof strategies and patterns, scratch work, logical equivalences. Proof by contradiction. Divisibility and congruences. Fermat'sLittle Theorem.
- 12 -Version of March 6, 2014
Complementary reading:
?Parts II, IV, and V ofHow to Think Like a MathematicianbyK.Houston.
?Chapters 1 and 8 ofMathematics for Computer SciencebyE.Lehman, F.T.Leighton, and A.R.Meyer.?
Chapter 3 ofHow to Prove itby D.J.Velleman.
Chapter II ofThe Higher Arithmeticby H. Davenport. - 13 -Version of March 6, 2014Objectives
?To develop techniques for analysing and understandingmathematical statements.?To be able to present logical arguments that establishmathematical statements in the form of clear proofs.
?To prove Fermat's Little Theorem, a basic result in thetheory of numbers that has many applications incomputer science; and that, in passing, will allowyou to solve the following ...
- 14 -Version of March 6, 2014Puzzle
5pirates have accumulated a tower of
ncubes each of which con- sists of n3 golden dice, for an unknown (but presumably large) num- ber n. This treasure is put on a table around which they sit on chairs numbered from 0to4, and they are to split it by simultaneously tak-
ing a die each with every tick of the clock provided that five ormore dice are available on the table. At the end of this process there will be rremaining dice which will go to the pirate sitting on the chair numbered r. What chair should a pirate sit on to maximise his gain? - 15 -Version of March 6, 2014
Proofs in practice
We are interested in examining the following statement:The product of two odd integers is odd.
This seems innocuous enough, but it is in fact full of baggage.For instance, it presupposes that you know:
?what a statement is; ?what the integers (...,-1,0,1,...) are, and that amongst them there is a class of odd ones (...,-3,-1,1,3,...) ?what the product of two integers is, and that this is in turn aninteger. - 16 -Version of March 6, 2014
More precisely put, we may write:
Ifmandnare odd integers then so ism·n.
which further presupposes that you know: ?what variables are; ?what if ...then ... statements are, and how one goes about proving them; ?that the symbol "·" is commonly used to denote the product
operation. - 17 -Version of March 6, 2014
Even more precisely, we should write
For all integersmandn, ifmandnare odd then so
ism·n. which now additionally presupposes that you know: ?what for all ... statements are, and how one goes about proving them. Thus, in trying to understand and then prove the above statement, we are assuming quite a lot of mathematical jargon that one needs to learn and practice with to make it a useful, and in fact verypow- erful, tool. - 18 -Version of March 6, 2014
Some mathematical jargon
Statement
A sentence that is either true or false - but not both.Example 1
eiπ+1=0Non-example
`This statement is false' - 19 -Version of March 6, 2014
THEOREMOFTHEDAY
Euler"s IdentityWithτandethemathematicalconstantsτ=2π=6.2831853071 7958647692 5286766559 0057683943 3879875021 1641949889 1846156328 1257241799 7256069650 6842341359...ande=2.7182818284 5904523536 0287471352 6624977572 4709369995 9574966967 6277240766 3035354759 4571382178 5251664274...
(thefirst100 placesofdecimalbeing given),and usingi to denote⎷ -1,wehave e iτ/2+1=0.Squaring bothsidesofeiτ/2=-1 giveseiτ=1,encodingthedefiningfact thatτradiansmeasuresonefullcircumference.The calculationcan
be confirmedexplicitly usingthe evaluation ofez,foranycomplex numberz,asaninfinitesum:ez=1+z+z2/2!+z3/3!+z4/4!+....The
even powersofi=⎷ -1alternatebetween 1and-1,whiletheodd powersalternatebetweeniand-i,soweget twoseparatesums,onewithi"s(theimaginary part)and onewithout(therealpart).Bothconvergerapidlyas showninthetwo plotsabove: therealpart to 1,theimaginary
to 0.Inthelimitequalityisattained,eiτ=1+0×i,whenceeτi=1.Thevalueofeiτ/2may be confirmedinthesameway.
Combiningasitdoesthesixmostfundamentalconstantsofmathematics:0, 1, 2,i,τande,theidentityhasanairofmagic.J.H.Conway,in
TheBookofNumbers
Weblink:
Further reading:
From www.theoremoftheday.org byRobinWhitty.Thisfilehosted byLondonSouthBankUniversity
- 20 -Version of March 6, 2014Predicate
A statement whose truth depends on the value of one or more variables.Example 2
1. ` eix=cosx+isinx2. `the function
fis differentiable' - 21 -Version of March 6, 2014Theorem
A very important true statement.
Proposition
A less important but nonetheless interesting true statement. Lemma A true statement used in proving other true statements.Corollary
A true statement that is a simple deduction from a theorem or proposition.Example 3
1. Fermat's Last Theorem
2. The Pumping Lemma
- 22 -Version of March 6, 2014
THEOREMOFTHEDAY
Fermat"sLastTheoremIfx,y,zand n areintegers satisfying x n+yn=zn,It iseasytoseethatwe canassumethatall theintegersinthetheoremarepositive.Sothefollowingisalegitimate,but totally different,way
ofassertingthetheorem:wetake aballatrandomfromUrnA; thenreplaceitandtake a2nd ballatrandom.DothesameforUrnB.The
probabilitythatbothAballsareblue,fortheurns shown here,is57×5
7.TheprobabilitythatbothBballsarethesame colour (both blueorboth
red)is(47)2+(3
7)2.NowthePythagoreantriple52=32+42tellsusthat theprobabilitiesare equal:25
49=949+16
49.What ifwe choosen>2 balls
withreplacement?Canwe againfilleach oftheurnswithNballs,redand blue,sothat takingnwithreplacementwillgive equalprobabilities?
Fermat"sLastTheoremsays:onlyinthetrivialcasewhere all theballsinUrnAareblue(whichincludes,vacuously,thepossibilitythatN=0.)
Another,muchmoreprofoundrestatement: ifan+bn,forn>2and positiveintegersaandb,isagainann-th powerofanintegerthenthe
elliptic curvey2=x(x-an)(x+bn),knownastheFreycurve,cannotbemodular (isnotarationalmap ofamodularcurve).Soit isenoughto
provetheTaniyama-Shimura-Weilconjecture:allrationalelliptic curvesaremodular.Fermat"sinnocentstatementwasfamouslyleftunprovedwhenhediedin 1665andwasthelastofhisunproved'theorems"tobesettledtrueorfalse,hencethe name.Thenon-modularityoftheFreycurvewasestablishedinthe1980sbythesuccessiveeffortsofGerhardFrey,Jean-PierreSerre andKenRibet.TheTaniyama-Shimura-Weilconjecturewasat thetimethoughttobe'inaccessible"butthetechnicalvirtuosity(nottomentionthecourageandstamina)ofAndrewWilesresolvedthe'semistable"case,whichwasenoughtosettleFermat"sassertion.HisworkwasextendedtoafullproofofTaniyama-Shimura-Weilduringthelate90sbyChristopheBreuil,BrianConrad,FredDiamondandRichardTaylor.
Weblink:
Further reading:
Fermat"sLastTheorem
Created byRobinWhittyfor
www.theoremoftheday.org - 23 -Version of March 6, 2014
THEOREMOFTHEDAY
xy izisalso aword ofL.automaton(DFA)whose edgesarelabelledfromΣ.Aboveleft,suchaDFAis shown,whichrecognisesthelanguage consisting ofallpositive
multiplesof7,writtenin basetwo.Thenumber95×7=665=29+27+24+23+20isexpressedin base2as1010011001.Togetherwith
anyleadingzeros,thesedigits,readleft toright,willcausethe edgesoftheDFAto betraversedfromtheinitialstate(heavy verticalarrow)to
anacceptingstate(coincidentallythesamestate,markedwithadouble circle),as showninthetablebelowtheDFA.Noticethat thebracketed
partofthetable correspondstoa cycleintheDFAandthismay occurzero ormoretimeswithoutaffectingthestring"srecognition.Thisisthe
ideabehindthepumpinglemma,inwhichp,the'pumpinglength",may betakento bethenumberofstatesoftheDFA.SoaDFAcan besmartenoughtorecognisemultiplesofaparticularprimenumber.But itcannotbesmartenoughrecognise allprimenumbers,
evenexpressedinunarynotation(2=aa,3=aaa,5=aaaaa,etc).Theproof,aboveright,typifiesthe application ofthepumpinglemmain
disproofsof regularity:assume arecognisingDFAexistsandexhibitawordwhich,when'pumped"mustfalloutsidetherecognisedlanguage.
Weblink:
(anddon"tmissFurther reading:
ModelsofComputation andFormalLanguages
Created byRobinWhittyfor
www.theoremoftheday.org - 24 -Version of March 6, 2014Conjecture
A statement believed to be true, but for which we have no proof.Example 41. Goldbach's Conjecture
2. The Riemann Hypothesis
3. Schanuel's Conjecture
- 25 -Version of March 6, 2014
Proof Logical explanation of why a statement is true; a method for establishing truth. Logic The study of methods and principles used to distinguish good (correct) from bad (incorrect) reasoning.Example 5
1. Classical predicate logic
2. Hoare logic
3. Temporal logic
- 26 -Version of March 6, 2014
AxiomA basic assumption about a mathematical situation.Axioms can be considered facts that do not need to beproved (just to get us going in a subject) or they can beused in definitions.