A. K. Dewdney

Indeholder "Preface", "Icons", "1. Algorithms. Cooking Up Programs", "2. Finite Automata. The Black Box", "3. Systems of Logic. Boolean Bases", "4. Simulation. The Monte Carlo Method", "5. Gödel's Theorem. Limits on Logic", "6. Game Trees. The Minimax Method", "7. The Chomsky Hierarchy. Four Computers", "8. Random Numbers. The Chaitin-Kolmogoroff Theory", "9. Mathematical Research. The Mandelbrot Set", "10. Program Correctness. Ultimate Debugging", "11. Search Trees. Traversal and Maintenance", "12. Error-Correcting Codes. Pictures from Space", "13. Boolean Logic. Expressions and Circuits", "14. Regular Languages. Pumping Words", "15. Time and Space Complexity. The Big-O Notation", "16. Genetic Algorithms. Solutions That Evolve", "17. The Random Access Machine. An Abstract Computer", "18. Spline Curves. Smooth Interpolation", "19. Computer Vision. Polyhedral Scenes", "20. Karnaugh Maps. Circuit Minimization", "21. The Newton-Raphson Method. Finding Roots", "22. Minimum Spanning Trees. A Fast Algorithm", "23. Generative Grammars. Lindenmayer Systems", "24. Recursion. The Sierpinski Curve", "25. Fast Multiplication. Divide and Conquer", "26. Nondeterminism. Automata That Guess Correctly", "27. Perceptrons. A Lack of Vision", "28. Encoders and Multiplexers. Manipulating Memory", "29. Cat Scanning. Cross-Sectional X-Rays", "30. The Partition Problem. A Pseudo-fast Algorithm", "31. Turing Machines. The Simplest Computers", "32. The Fast Fourier Transform. Redistributing Images", "33. Analog Computation. Spaghetti Computers", "34. Satisfiability. A Central Problem", "35. Sequential Sorting. A Lower Bound on Speed", "36. Neural Networks that Learn. Converting Coordinates", "37. Public Key Cryptography. Intractable Secrets", "38. Sequential Circuits. A Computer Memory", "39. Noncomputable Functions. The Busy Beaver Problem", "40. Heaps and Merges. The Fastest Sorts of Sorts", "41. NP-Completeness. The Wall of Intractability", "42. Number Systems for Computing. Chinese Arithmetic", "43. Storage by Hashing. The Key Is The Address", "44. Cellular Automata. The Game of Life", "45. Cook's Theorem. Nuts and Bolts", "46. Self-Replicating Computers. Codd's Machine", "47. Storing Images. A Cat in a Quad Tree", "48. The Scram. A Simplified Computer", "49. Shannon's Theory. The Elusive Codes", "50. Detecting Primes. An Algorithm that Almost Always Works", "51. Universal Turing Machines. Computers as Programs", "52. Text Compression. Huffmann Coding", "53. Disk Operating Systems. Bootstrapping the Computer", "54. NP-Complete Problems. The Tree of Intractability", "55. Iteration and Recursion. The Towers of Hanoi", "56. VLSI Computers. Circuits in Silicon", "57. Linear Programming. The Simplex Method", "58. Predicate Calculus. The Resolution Method", "59. The Halting Problem. The Uncomputable", "60. Computer Viruses. A Software Invasion", "61. Searching Strings. The Boyer-Moore Algorithm", "62. Parallel Computing. Processors with Connections", "63. The Word Problem. Dictionaries as Programs", "64. Logic Programming. Prologue to Expertise", "65. Relational Data Bases. Do-It-Yourself Queries", "66. Church's Thesis. All Computers Are Created Equal", "Index".

"Preface" handler om at det her er en guided tour omkring højdepunkter i det datalogiske landskab. Nyd turen. Det er en appetitvækker for kommende studerende og en genopfriskning for gamle ditto.
"Icons" handler om nogle små billeder han bruger. Som alle ikoner er de uforståelige i sig selv og kræver en forklaring.
"1. Algorithms. Cooking Up Programs" handler om et par eksempler på programmer og pseudokode. Her vises et lille program til at tegne tapeter, men han skriver ikke hvilke parametre, der har produceret det viste billede.
"2. Finite Automata. The Black Box" handler om endelige automater eller tilstandsmaskiner opfattet som små kasser med knapper på.
"3. Systems of Logic. Boolean Bases" handler om at fx (AND og NOT) er en base, og NAND er en base, dvs man kan vha en base producere alle logiske operatorer.
"4. Simulation. The Monte Carlo Method" handler om simuleret tid og events. Put events ind i en heap og stil uret frem og den næste ud af heapen.
"5. Gödel's Theorem. Limits on Logic" handler om at der findes sande sætninger uden beviser.
"6. Game Trees. The Minimax Method" handler om spilletræer og beskæring af samme.
"7. The Chomsky Hierarchy. Four Computers" handler om endelige automater, pushdown automater, lineært begrænsede automater og turingmaskiner. De genkender regulære sprog, kontekstfrie sprog, kontekstsensitive sprog og rekursivt enumerable sprog.
"8. Random Numbers. The Chaitin-Kolmogoroff Theory" handler om at definere en talfølges tilfældighed udfra størrelsen på det mindste program, der kan frembringe den.
"9. Mathematical Research. The Mandelbrot Set" handler om Pierre Fatou, John Hubbard, Adrien Douady og Benoit Mandelbrot. Og et lille programeksempel.
"10. Program Correctness. Ultimate Debugging" handler om at bevise at et program er korrekt. Og stopper med korrekt output på ethvert input. C. A. R. Hoare.
"11. Search Trees. Traversal and Maintenance" handler om binære søgetræer, balancerede træer og søgealgoritmer.
"12. Error-Correcting Codes. Pictures from Space" handler om fejlkorrigerende koder. Reed-Muller.
"13. Boolean Logic. Expressions and Circuits" handler om nand-gates og hvordan man laver et udtryk om til et elektrisk kredsløb.
"14. Regular Languages. Pumping Words" handler om at regulære sprog har den egenskab at ord, der er lange nok, altid kan pumpes, dvs de indeholder en del, der kan gentages igen og igen og stadig give et ord, der er med i sproget.
"15. Time and Space Complexity. The Big-O Notation" handler om en smart notation, så man kan snakke om at bubblesort har kvadratisk tidsforbrug.
"16. Genetic Algorithms. Solutions That Evolve" handler om eksempler på noget, man måske kan bruge genetisk inspirerede algoritmer til. Fx TSP, hvor en rute for Travelling SalesPerson kan kodes som en række tal og hvor to ruter så kan kombineres lige som en kønnet parring med overkrydsning mellem to talrækker. Jeg synes ikke det ser overbevisende ud, men det er da en meget sjov måde at prøve forskellige ruter.
"17. The Random Access Machine. An Abstract Computer" handler om en model for beregnelighed, der er ret tæt på virkelighedens computere.
"18. Spline Curves. Smooth Interpolation" handler om en fiks måde at specificere en pæn kurve mellem A og B.
"19. Computer Vision. Polyhedral Scenes" handler om at man kan fortolke stregtegninger som 3-D til en vis grad. Som "Ames Window Illusion" viser, så kan man dog snyde den slags selv med skygger og alt andet på plads, så selvfølgelig går det også galt med stregtegninger.
"20. Karnaugh Maps. Circuit Minimization" handler om tabeller af logik-funktioner. De kan kombineres for at finde et lille logisk kredsløb, der præcist beregner en given funktion. De holder op med at være praktiske for funktioner med mere end seks variable. Og de er kun tænkt som hjælp for mennesker, der designer kredsløb. Der er algoritmer til kredsløbsminimering, som er smartere.
"21. The Newton-Raphson Method. Finding Roots" handler om en sædvanligvis hurtigtkonvergerende metode til at finde rødder. Se fx Fast_inverse_square_root på wikipedia.
"22. Minimum Spanning Trees. A Fast Algorithm" handler om R. C. Prim og en grådig algoritme, der finder et minimalt udspændende træ for en graf. Steiner-træer er meget sværere at finde.
"23. Generative Grammars. Lindenmayer Systems" handler om grammatikker inspireret af fx rødalger.
"24. Recursion. The Sierpinski Curve" handler om rekursivt definerede kurver. I forlængelse af Lindenmayer systemer.
"25. Fast Multiplication. Divide and Conquer" handler om algoritmer for hurtigt at gange store tal sammen. Schönhage-Strassen, FFT. Arnold Schönhage og Volker Strassen. Hvor hurtigt kan det gå? (Der er efterfølgende fundet en asymptotisk bedre algoritme - Martin Fürer - men den er i praksis ikke bedre).
"26. Nondeterminism. Automata That Guess Correctly" handler om en ganske smart måde at ændre reglerne for en tilstandsmaskine på, så den accepterer en streng, hvis der bare findes en måde at ramme en accept-tilstand på. Det giver meget mindre tilstandsmaskiner og overlader bøvlet til implementeringen af tilstandsmaskinen.
"27. Perceptrons. A Lack of Vision" handler om at kigge på hvad perceptroner ikke kan. Fx at se om en figur er sammenhængende. Konklusionen er at verden er ikke simpel.
"28. Encoders and Multiplexers. Manipulating Memory" handler om et eksempel hvor man får input X der skal gemmes i adresse A. Eller MemoryBufferRegister MBR og MemoryAddressRegister MAR. En encoder tager 2^n input linier hvoraf en enkelt er 1 og levere output på n linier. En decoder gør det modsatte, dvs fra n input linier til 2^n output linier. En multiplexer har op til 2^n input linier og n control linier og 1 output linie. Med encoders, decoders, multiplexere og demultiplexere kan man bygge alle forbindelserne mellem en computers enkeltdele.
"29. Cat Scanning. Cross-Sectional X-Rays" handler om back-projecting og hvordan man kommer fra målinger af røntgen-intensitet til billeder. Den inverse Fourier-transformation og specielt formuleret for polære koordinater er bedre.
"30. The Partition Problem. A Pseudo-fast Algorithm" handler om at vælge to delmængder af en given mængde af heltal således at summen af de to delmængder er ens. Det er NP-hårdt. En algoritme PartitionFind ser ud til at være hurtigere, men nej. Men den er pseudo-hurtig eller pseudo-polynomiel, hvilket kan oversættes til at den er ok for små værdier. Et andet problem er subset-sum. Det løser PartitionFind også i pseudo-polynomiel tid.
"31. Turing Machines. The Simplest Computers" handler om en simpel tilstandsmaskine med 1 eller n bånd at læse og skrive på. Eet bånd er nok, men flere bånd giver mulighed for simplere og hurtigere programmer. Turing-maskiner er en af de simple modeller for generel beregnelighed.
"32. The Fast Fourier Transform. Redistributing Images" handler om Fourier transformationer på billeder.
"33. Analog Computation. Spaghetti Computers" handler om dimser, der i teorien kan løse nogle problemer hurtigt. I praksis er det nok noget andet. fx sortering af tusind tal ved at skære spagettistænger i tilsvarende længder og stable dem og finde den længste tusind gange? Det lyder upraktisk.
"34. Satisfiability. A Central Problem" handler om hvorvidt der er en smartere måde end at prøve alle værdier for at finde ud af hvilke logiske værdier der skal bruges for at få en givet stak af formler til at give TRUE. Det er der nok ikke.
"35. Sequential Sorting. A Lower Bound on Speed" handler om hvorfor sortering mindst kræver n * log(n) sammenligninger.
"36. Neural Networks that Learn. Converting Coordinates" handler om neurale net og status pr skrivetidspunktet, dvs ca 1995. Her 20 - 25 år senere er billedgenkendelse blevet virkeligt godt.
"37. Public Key Cryptography. Intractable Secrets" handler om Diffie-Hellman, dvs Martin Hellman, Ralph Merkle, Whitfield Diffie og deres arbejde. Public keys, private keys. Knapsack problemet (delmængde af subset-sum problemet). RSA-kryptosystemet (Rivest, Shamir og Adleman).
"38. Sequential Circuits. A Computer Memory" handler om hvordan RAM faktisk er skruet sammen. Flip-flops styret med clock-signaler. Eksempel på et modul med 8 ord på 4 bit hver. Nand-gates.
"39. Noncomputable Functions. The Busy Beaver Problem" handler om hvor længe en turing-maskine med n tilstande kan køre og faktisk stoppe af sig selv i modsætning til at køre ud over kanten. Tallene bliver hurtigt kæmpestore og det er svært at vide om maskinen er gået i en løkke og derfor aldrig stopper eller om den bare lige skal have 10 minutter mere til at blive færdig. Tibor Rado fandt på busy beaver problemet i 1962. Hvis vi kalder det maksimale antal trin en Turing-maskine med n trin kan køre og så stoppe for Sigma(n), så vokser Sigma funktionen hurtigere end enhver beregnelig funktion. Faktisk vokser den helt sindssygt hurtigt.
"40. Heaps and Merges. The Fastest Sorts of Sorts" handler om heapsort og flettesortering.
"41. NP-Completeness. The Wall of Intractability" handler om transformationer mellem fx SAT og Vertex Covering - kaldet VC. 3SAT nævnes i opgaverne. G3C = trefarvning af en graf.
"42. Number Systems for Computing. Chinese Arithmetic" handler om at bruge trits i stedet for bits. Balanced ternary. Modular digits. Nogle regneoperationer er nemme at køre i parallel, men så er der nogle andre, fx sammenligning, der bliver sværere.
"43. Storage by Hashing. The Key Is The Address" handler om hash-funktioner og kollisioner. Og om at det er nemmere at programmere end binære træer.
"44. Cellular Automata. The Game of Life" handler om Conway's regler for Life. Man kan bygge en computer i Life, hvilket er ret sjovt. Og Turing-maskiner, så Life kan lave universelle beregning.
"45. Cook's Theorem. Nuts and Bolts" handler om at SAT er NP-komplet. Ideen er at tage en Turing-maskine og omskrive transitionerne til logiske regler, så man ender med en sætning, der er præcis det samme som at Turing-maskinen skriver et 1-tal et bestemt sted på båndet.
"46. Self-Replicating Computers. Codd's Machine" handler om John von Neumann og en tilstandsmaskine med 29 tilstande. I midten af 1960'erne forbedrede E. F. Codd designet til en UCC (Universal Computer Constructor) som nøjes med 8 tilstande. I 1985 lavede Christopher Langton en 8-tilstands maskine med en tabel med 219 indgange. 1989 lavede John Byl en endnu mindre version med 6 tilstande og en tabel med 56 indgange og en startkonfiguration på 11 celler.
"47. Storing Images. A Cat in a Quad Tree" handler om sort/hvide billeder og quad-trees som har smarte egenskaber hvis man leder efter sammenhængende komponenter. Eksemplet er et 16 x 16 pixels billede af en kat med en mus.
"48. The Scram. A Simplified Computer" handler om en Simple Complete Random Access Machine. 8-bits ord og kun 16 af dem, så adresser er 4 bit lange. Oversættelse af instruktioner til mikrokode og fra mikrokode tilbage til maskinkode er vist. Og nogle diagrammer over kredsløb, der implementerer dem.
"49. Shannon's Theory. The Elusive Codes" handler om hvordan man håndterer støj og bitfejl. Den naive algoritme er at stave 1 som 111 og 0 som 000, men checksummer og fejlkorrigerende koder. Shannons teorem siger at vi for ethvert epsilon kan lave en ordlængde n og en kode C, så risikoen for en dekodningsfejl er mindre end epsilon. Men resultatet er konservativt, dvs upraktisk stor til praktisk brug og man kan typisk gøre det bedre.
"50. Detecting Primes. An Algorithm that Almost Always Works" handler om probabilistiske algoritmer. Rabin morede sig med at checke 2^p -1 for p in (1..500) og det gav præcis samme liste som en tabel over Mersenne primtallene selv om han kun brugte m=10 vidner i testen.
"51. Universal Turing Machines. Computers as Programs" handler om Turing-maskiner, der tager andre Turing-maskiner som input.
"52. Text Compression. Huffmann Coding" handler om Huffmann kodning, men det er jo blevet noget smartere med lzr-komprimering, så zip-filer er blevet ret smarte.
"53. Disk Operating Systems. Bootstrapping the Computer" handler om hvordan computere starter op. Man skal fx ikke længere vippe kontakter for at sætte startadressen som på en Data General Nova i sin tid (anno 1980).
"54. NP-Complete Problems. The Tree of Intractability" handler om en hob af problemer, der hænger sammen som ærtehalm.
"55. Iteration and Recursion. The Towers of Hanoi" handler om at selv om den kendte algoritme er rekursiv, er der også et par iterative løsninger. Og faktisk kan man altid omskrive iteration til rekursion og omvendt.
"56. VLSI Computers. Circuits in Silicon" handler om hvordan hardwaren ser ud nede på en VLSI-kreds. Det her er 1995, så udviklingen er jo gået sygt stærkt siden.
"57. Linear Programming. The Simplex Method" handler om lineær programmering og hvordan simplex-metoden kan bruges til at finde løsninger.
"58. Predicate Calculus. The Resolution Method" handler om logiske udtryk og manipulation af samme. Engang troede man at man kunne bygge matematikken op fra dette faste underlag.
"59. The Halting Problem. The Uncomputable" handler om at man ikke kan svare automatisk på om et program stopper. Det er logisk nok for nogle problemer er jo arvet fra matematik, fx er det nok ikke nemt lige at svare på om et program, der leder efter ulige perfekte tal nogensinde stopper. Det er jo ellers besnærende let at skrive programmet.
"60. Computer Viruses. A Software Invasion" handler om internet orme, virus og andre slags malware. Det er ikke en af opgaverne at skrive en ny virus.
"61. Searching Strings. The Boyer-Moore Algorithm" handler om en supersmart algoritme, der bruger sub-lineær tid for at finde matches.
"62. Parallel Computing. Processors with Connections" handler om Nick's klasse af problemer. De har gavn og glæde af flere processer. Fx matrix multiplikation.
"63. The Word Problem. Dictionaries as Programs" handler om Axel Thue. Desværre er problemet ækvivalent med Turing-maskiner.
"64. Logic Programming. Prologue to Expertise" handler om logikprogrammering med regler og fakta formuleret i prolog eller lignende. Ekspertsystemer baseret på samme. Men ikke så meget om hvorvidt det rigtigt er brugbart. Eksemplet brugt her er den katolske kirkes regler for hvem der må indgå giftemål.
"65. Relational Data Bases. Do-It-Yourself Queries" handler om at lave lister og nye databasetabeller med simple eller komplicerede forespørgsler i SQL eller lignende. Alt er mængder af tupler.
"66. Church's Thesis. All Computers Are Created Equal" handler om at Church viser at rekursive funktioner er de samme som hans lambda kalkyle. Turing viser kort efter at Turing maskiner og lambda kalkyle også er de samme. Church's formodning er at alt beregneligt er indeholdt i lambda kalkylen. Dvs at de generelle modeller for beregnelighed rammer samme mål. Formodningen er fra 1936, dvs i god tid inden computere blev almindelige.
"Index" er et udmærket opslagsregister.

Udmærket bog, hvis nogen skulle spørge om hvad datalogi går ud på. Men kræver at de gider pløje sig igennem en hel bog, så det er nok at prædike for de allerede omvendte. I en spritny udgave ville billedgenkendelse og cache-oblivious algoritmer være savnet, men det er det jo heller ikke.
Hvis man hopper lidt i bogen, er det svagt irriterende at kapitlerne er markeret for oven på siden, men unummererede, men man kan jo finde det ved næste kapitelside, som har kapitelnummeret stående med kæmpestore typer.… (meer)

Indeholder "Preface", "Introduction", "1. Innumeracy and Math Abuse", " Light Bulbs that Generate Power", " Death by Aftermath", " Death by Filtering", " Instant Wealth and Rebounding Grades", " Drunk, Drugged, Depressed and Dangerous!", " The Irrelevant Fund", " A Million Drops in the Bucket", " The National Security Googol", " The Incredible Expanding Toyota", " Chart Abuse", " Graphic Distortion", "2. Statistics and Damned Lies", " The Great Pepsi Challenge", " Lotteries and Lightning", " Death Threats", " What Happens When You Toss Seven Coins 128 Times", " The Naked Fund Manager", " Numerical Terrorism at the Nuclear Plant", " Hitting the Hites", " Occult Samples", "3. The Mathematics of Advertising", " A Game for the Numerate", " Ivory Liquid Goes to Camp", " One-Page Wonders", " Will Life Jackets Kill You?", " For Sale: High-Price/Low-Performance Computers", " The 226.8 Gram Canary", "4. Intelligent Dice", " Dr. Lotto Dies Under the Knife", " Winning Ways?", " Winning Big", " Revenge of the Dice", " The World's Smartest Human Screws Up - or Does She?", " Her Answer? 'Switch'", "5. The Law of Zero Return", " Shortchanged!", " Portrait of the Bull", " Following the Herd", " Charts and Chicken Entrails", " Self-Fulfilling Prophets", " Dividend Spin", " The Money Forest", " The Law of Zero Return", "6. Caveat Emptor", " Casting Out Nines", " Hidden Costs", " Putting Your Best Foot into Your Mouth", "7. The Government Figures", " Getting Elected", " Staying Elected: Cooking the Stats", " Canadians Get the Picture", " Inflated Remarks", " More Money = Less Brains", " Cooking by Radar", " Number Numbness in the Think Tank", " Penny Larceny", "8. Living with Risk", " Testing the Waters", " The Plutonium Scare", " Numerically Enhanced Drugs", " Nightlining Oat Bran", " Testing Positive", " Planes (Trains) and Automobiles", "9. Gee-Whiz Media Math", " Sex and the Single Statistic", " Environmental Blunders", " The Unexpected Expectancy", " Inflating Inflation", " Sports Reports", "10. The Tip of the Iceberg", " The Educational Crisis", " Invasion of the Nerds", " What Do Mathematicians Do?", " Junk Science", "11. Everybody is a Mathematician", " The World of Games", " The World of Sherlock Holmes", " Mathematics in Life", " Jockeying for Position", " Mathematics Is Too Simple", "12. Street Math", " Numbers, Growth, and Decay", " When Numbers Combine", " Working with Probability", " Morbidity, Mortality, and Worse", " Combinatorics Counts", "Annotated Bibliography", "Acknowledgments: The Abuse Detectives", " Be a Math Abuse Detective", " Further Acknowledgments".

Nogle kedelige eksempler på journalist- eller reklame-matematik. Spar 200% på din elregning. Blah, blah, blah. Omkring side 68 er der en gennemgang af Monty Hall problemet, som er svagt mindre uinteressant end resten.

Forfatteren dokumenterer uforvarende at en forkert påstand fanger opmærksomheden og derfor er en god reklame.… (meer)