Muy chévere. Gracias
2012/4/6 Owen Densmore <o...@backspaces.net> > A couple of friends from Silicon Valley are taking the Stanford Algorithms > course with me. One of the "readings" for the class is: > > Mathematics for Computer Science > Eric Lehman and Tom Leighton > 2004 > http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf > > > ... which is a surprisingly complete survey of most of your > basic undergraduate math, done very well. > > -- Owen > > Here is the table of contents: > > Contents > 1 What is a Proof? 15 > 1.1 Propositions..................................... 15 > 1.2 Axioms........................................ 19 > 1.3 LogicalDeductions ................................. 20 > 1.4 ExamplesofProofs ................................. 20 > 1.4.1 ATautology................................. 21 > 1.4.2 AProofbyContradiction ......................... 22 > 2 Induction I 23 > 2.1 AWarmupPuzzle.................................. 23 > 2.2 Induction....................................... 24 > 2.3 UsingInduction................................... 25 > 2.4 ADivisibilityTheorem............................... 28 > 2.5 AFaultyInductionProof.............................. 30 > 2.6 CourtyardTiling................................... 31 > 2.7 AnotherFaultyProof................................ 33 > 3 Induction II 35 > 3.1 GoodProofsandBadProofs............................ 35 > 3.2 APuzzle....................................... 36 > 3.3 Unstacking...................................... 40 > 3.3.1 StrongInduction .............................. 40 > 3.3.2 AnalyzingtheGame ............................ 41 > 4 Number Theory I 45 > 4.1 ATheoryoftheIntegers .............................. 46 > 4.2 Divisibility...................................... 46 > 4.2.1 Turing’sCode(Version1.0) ........................ 47 > 4.2.2 TheDivisionAlgorithm .......................... 50 > 4.2.3 BreakingTuring’sCode .......................... 51 > 4.3 ModularArithmetic................................. 51 > 4.3.1 CongruenceandRemainders....................... 51 > 4.3.2 Factsaboutremandmod......................... 52 > 4.3.3 Turing’sCode(Version2.0)........................ 54 > 4.3.4 CancellationModuloaPrime....................... 55 > 4.3.5 MultiplicativeInverses........................... 56 > 4.3.6 Fermat’sTheorem............................. 57 > 4.3.7 FindingInverseswithFermat’sTheorem................ 58 > 4.3.8 BreakingTuring’sCode—Again..................... 58 > 5 Number Theory II 61 > 5.1 DieHard....................................... 61 > 5.1.1 DeathbyInduction............................. 62 > 5.1.2 AGeneralTheorem............................. 63 > 5.1.3 TheGreatestCommonDivisor...................... 64 > 5.1.4 PropertiesoftheGreatestCommonDivisor............... 65 > 5.2 TheFundamentalTheoremofArithemtic .................... 67 > 5.3 ArithmeticwithanArbitraryModulus...................... 68 > 5.3.1 RelativePrimalityandPhi......................... 68 > 5.3.2 GeneralizingtoanArbitraryModulus.................. 70 > 5.3.3 Euler’sTheorem .............................. 71 > 6 Graph Theory 73 > 6.1 Introduction..................................... 73 > 6.1.1 Definitions.................................. 74 > 6.1.2 SexinAmerica ............................... 74 > 6.1.3 GraphVariations .............................. 76 > 6.1.4 ApplicationsofGraphs .......................... 77 > 6.1.5 SomeCommonGraphs .......................... 77 > 6.1.6 Isomorphism ................................ 79 > 6.2 Connectivity..................................... 80 > 6.2.1 ASimpleConnectivityTheorem ..................... 80 > 6.2.2 DistanceandDiameter........................... 81 > 6.2.3 Walks..................................... 83 > 6.3 AdjacencyMatrices................................. 83 > 6.4 Trees ......................................... 84 > 6.4.1 SpanningTrees ............................... 86 > 6.4.2 TreeVariations ............................... 87 > 7 Graph Theory II 89 > 7.1 ColoringGraphs................................... 89 > 7.1.1 k-Coloring.................................. 90 > 7.1.2 BipartiteGraphs .............................. 90 > 7.2 PlanarGraphs.................................... 91 > 7.2.1 Euler’sFormula............................... 93 > 7.2.2 ClassifyingPolyhedra ........................... 94 > 7.3 Hall’sMarriageTheorem.............................. 95 > 7.3.1 AFormalStatement ............................ 97 > 8 Communication Networks 99 > 8.1 CompleteBinaryTree................................ 99 > 8.1.1 LatencyandDiameter ...........................100 > 8.1.2 SwitchSize .................................101 > 8.1.3 SwitchCount ................................101 > 8.1.4 Congestion .................................101 > 8.2 2-DArray ......................................103 > 8.3 Butterfly .......................................104 > 8.4 Benes ̆Network ...................................106 > 9 Relations 111 > 9.0.1 RelationsonOneSet............................111 > 9.0.2 RelationsandDirectedGraphs ......................112 > 9.1 PropertiesofRelations ...............................112 > 9.2 EquivalenceRelations ...............................113 > 9.2.1 Partitions ..................................113 > 9.3 PartialOrders ....................................114 > 9.3.1 DirectedAcyclicGraphs..........................116 > 9.3.2 PartialOrdersandTotalOrders......................116 > 10 Sums, Approximations, and Asymptotics 119 > 10.1 The Value of an Annuity.............................. 119 > 10.1.1 TheFutureValueofMoney........................119 > 10.1.2 AGeometricSum..............................120 > 10.1.3 ReturnoftheAnnuityProblem......................121 > 10.1.4 InfiniteSums................................122 > 10.2 Variants of Geometric Sums............................ 123 > 10.3 Sums of Powers................................... 125 > 10.4 Approximating Sums................................ 126 > 10.4.1 IntegrationBounds.............................127 > 10.4.2 Taylor’sTheorem..............................128 > 10.4.3 BacktotheSum...............................130 > 10.4.4 AnotherIntegrationExample.......................131 > 11 Sums, Approximations, and Asymptotics II 133 > 11.1 Block Stacking.................................... 133 > 11.1.1 HarmonicNumbers............................135 > 11.2 Products.......................................137 > 11.3 Asymptotic Notation................................ 138 > 12 Recurrences I 143 > 12.1 TheTowersofHanoi ................................143 > 12.1.1 FindingaRecurrence............................144 > 12.1.2 ALowerBoundforTowersofHanoi...................145 > 12.1.3 Guess-and-Verify..............................146 > 12.1.4 ThePlug-and-ChugMethod .......................147 > 12.2 Merge Sort...................................... 149 > 12.2.1 TheAlgorithm...............................149 > 12.2.2 FindingaRecurrence............................150 > 12.2.3 SolvingtheRecurrence...........................150 > 12.3 More Recurrences.................................. 152 > 12.3.1 ASpeedyAlgorithm............................152 > 12.3.2 AVerificationProblem...........................153 > 12.3.3 AFalseProof................................154 > 12.3.4 AlteringtheNumberofSubproblems..................155 > 12.4 TheAkra-BazziMethod..............................155 > 12.4.1 SolvingDivideandConquerRecurrences................ 156 > 13 Recurrences II 159 > 13.1 AsymptoticNotationandInduction .......................159 > 13.2LinearRecurrences .................................160 > 13.2.1 GraduateStudentJobProspects .....................160 > 13.2.2 FindingaRecurrence............................161 > 13.2.3 SolvingtheRecurrence...........................162 > 13.2.4 JobProspects ................................164 > 13.3 GeneralLinearRecurrences ............................165 > 13.3.1 AnExample.................................167 > 13.4InhomogeneousRecurrences ...........................167 > 13.4.1 AnExample.................................168 > 13.4.2 HowtoGuessaParticularSolution ...................169 > 14 Counting I 173 > 14.1 CountingOneThingbyCountingAnother ...................174 > 14.1.1 Functions ..................................174 > 14.1.2 Bijections...................................175 > 14.1.3 TheBijectionRule .............................176 > 14.1.4 Sequences ..................................177 > 14.2 Two Basic Counting Rules............................. 178 > 14.2.1 TheSumRule................................178 > 14.2.2 TheProductRule..............................179 > 14.2.3 PuttingRulesTogether...........................180 > 14.3 MoreFunctions:InjectionsandSurjections...................181 > 14.3.1 ThePigeonholePrinciple.........................182 > 15 Counting II 187 > 15.1 The Generalized Product Rule........................... 188 > 15.1.1 DefectiveDollars..............................189 > 15.1.2 AChessProblem..............................189 > 15.1.3 Permutations................................190 > 15.2 The Division Rule.................................. 191 > 15.2.1 AnotherChessProblem..........................191 > 15.2.2 KnightsoftheRoundTable........................192 > 15.3 Inclusion-Exclusion................................. 193 > 15.3.1 UnionofTwoSets.............................194 > 15.3.2 UnionofThreeSets.............................195 > 15.3.3 UnionofnSets...............................196 > 15.4 TheGrandSchemeforCounting .........................197 > 16 Counting III 201 > 16.1 The Bookkeeper Rule................................ 201 > 16.1.1 20-MileWalks................................201 > 16.1.2 BitSequences................................202 > 16.1.3 k-elementSubsetsofann-elementSet..................202 > 16.1.4 AnAlternativeDerivation.........................203 > 16.1.5 WordofCaution ..............................203 > 16.2 BinomialTheorem .................................203 > 16.3 Poker Hands..................................... 204 > 16.3.1 Hands with a Four-of-a-Kind....................... 205 > 16.3.2 HandswithaFullHouse.........................205 > 16.3.3 HandswithTwoPairs...........................206 > 16.3.4 HandswithEverySuit...........................208 > 16.4 Magic Trick...................................... 209 > 16.4.1 TheSecret..................................209 > 16.4.2 TheRealSecret...............................211 > 16.4.3 SameTrickwithFourCards?.......................212 > 16.5 CombinatorialProof................................212 > 16.5.1 Boxing.................................... 213 > 16.5.2 CombinatorialProof............................214 > 17 Generating Functions 217 > 17.1 Generating Functions................................ 217 > 17.2 Operations on Generating Functions....................... 218 > 17.2.1 Scaling....................................218 > 17.2.2 Addition...................................219 > 17.2.3 Right Shifting................................ 220 > 17.2.4 Differentiation................................221 > 17.3 TheFibonacciSequence ..............................222 > 17.3.1 FindingaGeneratingFunction ......................222 > 17.3.2 FindingaClosedForm...........................224 > 17.4 Counting with Generating Functions....................... 225 > 17.4.1 ChoosingDistinctItemsfromaSet....................225 > 17.4.2 BuildingGeneratingFunctionsthatCount............... 225 > 17.4.3 ChoosingItemswithRepetition.....................227 > 17.5 An“Impossible”CountingProblem .......................229 > 18 Introduction to Probability 231 > 18.1 Monty Hall...................................... 231 > 18.1.1 TheFour-StepMethod...........................232 > 18.1.2 ClarifyingtheProblem...........................232 > 18.1.3 Step1:FindtheSampleSpace.......................233 > 18.1.4 Step2:DefineEventsofInterest.....................235 > 18.1.5 Step3:DetermineOutcomeProbabilities................236 > 18.1.6 Step4:ComputeEventProbabilities...................239 > 18.1.7 An Alternative Interpretation of the Monty Hall Problem....... 240 > 18.2 Strange Dice..................................... 240 > 18.2.1 AnalysisofStrangeDice..........................241 > 19 Conditional Probability 245 > 19.1 TheHaltingProblem ................................246 > 19.1.1 SolutiontotheHaltingProblem .....................246 > 19.1.2 WhyTreeDiagramsWork.........................248 > 19.2APosterioriProbabilities ..............................250 > 19.2.1 ACoinProblem...............................251 > 19.2.2 AVariantoftheTwoCoinsProblem...................252 > 19.3MedicalTesting ...................................254 > 19.4ConditionalProbabilityPitfalls ..........................256 > 19.4.1 CarnivalDice ................................256 > 19.4.2 OtherIdentities...............................258 > 19.4.3 DiscriminationLawsuit ..........................258 > 19.4.4 On-TimeAirlines..............................260 > 20 Independence 261 > 20.1 Independent Events................................. 261 > 20.1.1 Examples..................................261 > 20.1.2 WorkingwithIndependence.......................262 > 20.1.3 SomeIntuition...............................262 > 20.1.4 AnExperimentwithTwoCoins.....................263 > 20.1.5 AVariationoftheTwo-CoinExperiment................ 264 > 20.2 MutualIndependence...............................266 > 20.2.1 DNATesting................................267 > 20.2.2 PairwiseIndependence..........................268 > 20.3TheBirthdayParadox...............................270 > 20.3.1 TheFour-StepMethod...........................270 > 20.3.2 AnAlternativeApproach.........................272 > 20.3.3 AnUpperBound..............................272 > 20.3.4 ALowerBound...............................274 > 20.3.5 TheBirthdayPrinciple...........................275 > 21 Random Variables 277 > 21.1 Random Variables.................................. 277 > 21.1.1 IndicatorRandomVariables........................278 > 21.1.2 RandomVariablesandEvents......................278 > 21.1.3 ConditionalProbability..........................279 > 21.1.4 Independence................................280 > 21.1.5 AnExamplewithDice...........................281 > 21.2 Probability Distributions.............................. 282 > 21.2.1 BernoulliDistribution...........................284 > 21.2.2 UniformDistribution............................284 > 21.2.3 TheNumbersGame............................285 > 21.2.4 BinomialDistribution...........................287 > 21.2.5 Approximating the Cumulative Binomial Distribution Function... 290 > 21.3 Philosophy of Polling................................ 291 > 22 Expected Value I 293 > 22.1 Betting on Coins................................... 293 > 22.2 EquivalentDefinitionsofExpectation......................296 > 22.2.1 MeanTimetoFailure............................297 > 22.2.2 MakingaBabyGirl.............................298 > 22.3 AnExpectationParadox ..............................298 > 22.4 LinearityofExpectation ..............................300 > 22.4.1 ExpectedValueofTwoDice........................301 > 22.4.2 TheHat-CheckProblem..........................302 > 22.4.3 TheChineseAppetizerProblem .....................303 > 23 Expected Value II 305 > 23.1 TheExpectedNumberofEventsthatHappen.................. 305 > 23.1.1 ACoinProblem—theEasyWay.....................306 > 23.1.2 TheHardWay................................306 > 23.2 TheCouponCollectorProblem..........................307 > 23.2.1 ASolutionUsingLinearityofExpectation............... 307 > 23.3 Expected Value of a Product............................ 309 > 23.3.1 TheProductofTwoIndependentDice..................309 > 23.3.2 TheProductofTwoDependentDice...................310 > 23.3.3 Corollaries..................................310 > 24 Weird Happenings 315 > 24.1 The New Grading Policy.............................. 316 > 24.1.1 Markov’sInequality............................316 > 24.1.2 LimitationsoftheMarkovInequality..................317 > 24.2 The Tip of the Tail.................................. 317 > 24.2.1 UpperBound:TheUnionBound.....................318 > 24.2.2 LowerBound:“Murphy’sLaw”.....................318 > 24.2.3 TheBigPicture...............................319 > 24.3 ChernoffBounds ..................................320 > 24.3.1 MITAdmissions ..............................321 > 24.3.2 ProvingChernoffBounds .........................322 > 24.4Hashing .......................................324 > 24.4.1 TheFirstCollision .............................325 > 24.4.2 NRecordsinNBins ............................325 > 24.4.3 AllBinsFull.................................326 > 25 Random Walks 327 > 25.1 ABug’sLife.....................................327 > 25.1.1 ASimplerProblem.............................328 > 25.1.2 ABigIsland.................................329 > 25.1.3 LifeExpectancy...............................332 > 25.2TheGambler’sRuin................................334 > 25.2.1 FindingaRecurrence............................335 > 25.2.2 SolvingtheRecurrence...........................335 > 25.2.3 InterpretingtheSolution..........................337 > 25.2.4 SomeIntuition...............................337 > 25.3 Pass the Broccoli................................... 338 > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org > -- Alfredo
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
