PortadaGruposCharlasMásPanorama actual
Buscar en el sitio
Este sitio utiliza cookies para ofrecer nuestros servicios, mejorar el rendimiento, análisis y (si no estás registrado) publicidad. Al usar LibraryThing reconoces que has leído y comprendido nuestros términos de servicio y política de privacidad. El uso del sitio y de los servicios está sujeto a estas políticas y términos.

Resultados de Google Books

Pulse en una miniatura para ir a Google Books.

Cargando...

The New Turing Omnibus: 66 Excursions in Computer Science (1993)

por A. K. Dewdney

MiembrosReseñasPopularidadValoración promediaConversaciones
349273,491 (3.73)Ninguno
No other volume provides as broad, as thorough, or as accessible an introduction to the realm of computer science as A. K. Dewdney's The Turing Omnibus. For everyone from the curious beginner to the working professional, The New Turing Omnibus offers 66 concise, brilliantly written mathematically oriented articles on the major points of interest in computer science theory, technology, and applications. Foundational for this tour: information on algorithms, detecting primes, noncomputable functions, and self-replicating computers--plus fundamental sections on the Mandelbrot set, genetic algorithms, the Newton-Raphson Method, neural networks that learn, DOS systems for personal computers, and computer viruses.… (más)
Ninguno
Cargando...

Inscríbete en LibraryThing para averiguar si este libro te gustará.

Actualmente no hay Conversaciones sobre este libro.

Mostrando 2 de 2
Good background about the most interesting parts of programming. ( )
  mykl-s | Feb 25, 2023 |
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. ( )
  bnielsen | Oct 5, 2020 |
Mostrando 2 de 2
sin reseñas | añadir una reseña
Debes iniciar sesión para editar los datos de Conocimiento Común.
Para más ayuda, consulta la página de ayuda de Conocimiento Común.
Título canónico
Información procedente del conocimiento común inglés. Edita para encontrar en tu idioma.
Título original
Títulos alternativos
Fecha de publicación original
Personas/Personajes
Lugares importantes
Acontecimientos importantes
Películas relacionadas
Epígrafe
Dedicatoria
Primeras palabras
Citas
Últimas palabras
Aviso de desambiguación
Editores de la editorial
Blurbistas
Idioma original
Información procedente del conocimiento común inglés. Edita para encontrar en tu idioma.
DDC/MDS Canónico
LCC canónico

Referencias a esta obra en fuentes externas.

Wikipedia en inglés (1)

No other volume provides as broad, as thorough, or as accessible an introduction to the realm of computer science as A. K. Dewdney's The Turing Omnibus. For everyone from the curious beginner to the working professional, The New Turing Omnibus offers 66 concise, brilliantly written mathematically oriented articles on the major points of interest in computer science theory, technology, and applications. Foundational for this tour: information on algorithms, detecting primes, noncomputable functions, and self-replicating computers--plus fundamental sections on the Mandelbrot set, genetic algorithms, the Newton-Raphson Method, neural networks that learn, DOS systems for personal computers, and computer viruses.

No se han encontrado descripciones de biblioteca.

Descripción del libro
Resumen Haiku

Debates activos

Ninguno

Cubiertas populares

Enlaces rápidos

Valoración

Promedio: (3.73)
0.5
1
1.5
2
2.5 2
3 8
3.5 1
4 17
4.5
5 3

¿Eres tú?

Conviértete en un Autor de LibraryThing.

 

Acerca de | Contactar | LibraryThing.com | Privacidad/Condiciones | Ayuda/Preguntas frecuentes | Blog | Tienda | APIs | TinyCat | Bibliotecas heredadas | Primeros reseñadores | Conocimiento común | 203,190,094 libros! | Barra superior: Siempre visible