The Art of Computer Programming -The Art of Computer Programming
Forfatter | Donald Knuth |
---|---|
Land | forente stater |
Språk | Engelsk |
Sjanger |
Sakprosa- monografi |
Forlegger | Addison-Wesley |
Publiseringsdato |
1968– (boken er fremdeles ufullstendig) |
Media type | Trykk ( Innbundet ) |
ISBN | 0-201-03801-3 |
519 | |
LC -klasse | QA76,75 |
The Art of Computer Programming ( TAOCP ) er en omfattende monografi skrevet av datamaskin vitenskapsmann Donald Knuth som dekker mange typer programmering algoritmer og deres analyse .
Knuth begynte prosjektet, opprinnelig tenkt som en enkelt bok med tolv kapitler, i 1962. De tre første bindene av det som da var forventet å være et syv bind sett ble utgitt i 1968, 1969 og 1973. Arbeidet begynte for alvor med bind 4 i 1973, men ble suspendert i 1977 på grunn av arbeidet med å sette opp på grunn av den andre utgaven av bind 2. Skriving av den siste kopien av bind 4A begynte på langhånd i 2001, og den første forhåndsfascikelen på nett, 2A, dukket opp senere i 2001 . Den første utgaven av bind 4 dukket opp i pocketbok som Fascicle 2 i 2005. Innbundet bind 4A, som kombinerte bind 4, Fascicles 0–4, ble utgitt i 2011. Bind 4, Fascicle 6 ("Satisfiability") ble utgitt i desember 2015; Bind 4, Fascicle 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") ble utgitt i november 2019.
Fascicles 5 og 6 forventes å utgjøre de to første tredjedelene av bind 4B. Knuth har ikke kunngjort noen estimert dato for utgivelse av bind 4B, selv om metoden hans som ble brukt for bind 4A, er å gi ut hardback -volumet en gang etter utgivelsen av pocketbåndene som er inneholdt i det. Kortsiktige publisistestimater satte utgivelsesdatoen i mai eller juni 2019, noe som viste seg å være feil.
Historie
Etter å ha vunnet et Westinghouse Talent Search -stipend, meldte Knuth seg på Case Institute of Technology (nå Case Western Reserve University ), hvor hans prestasjoner var så enestående at fakultetet stemte for å tildele ham en master i realfag etter fullført bachelorgrad. I løpet av sommerferien ble Knuth ansatt av Burroughs Corporation for å skrive kompilatorer , og tjente mer i sommermånedene enn professorene gjorde for et helt år. Slike bedrifter gjorde Knuth til et diskusjonstema blant matematikkavdelingen, som inkluderte Richard S. Varga .
I januar 1962, da han var doktorgradsstudent ved matematikkavdelingen ved Caltech, ble Knuth kontaktet av Addison-Wesley for å skrive en bok om kompilatordesign, og han foreslo et større omfang. Han kom med en liste med 12 kapitletitler samme dag. Sommeren 1962 jobbet han på en FORTRAN -kompilator for UNIVAC. I løpet av denne tiden kom han også med en matematisk analyse av lineær sondering , som overbeviste ham om å presentere materialet med en kvantitativ tilnærming. Etter doktorgraden i juni 1963 begynte han å arbeide med manuskriptet sitt, som han avsluttet sitt første utkast med i juni 1965, kl.3000 håndskrevne sider. Han hadde antatt at omtrent fem håndskrevne sider ville oversettes til én trykt side, men forlaget hans sa i stedet at omtrent 1+1 / 2 håndskrevne sider oversatt til en trykt side. Dette betydde at han hadde omtrent2000 trykte sider med materiale, som samsvarer tett med størrelsen på de tre første utgitte bindene. Forlaget var nervøs for å godta et slikt prosjekt fra en doktorgradsstudent. På dette tidspunktet mottok Knuth støtte fra Richard S. Varga, som var vitenskapelig rådgiver for forlaget. Varga var på besøk hos Olga Taussky-Todd og John Todd på Caltech . Med Vargas entusiastiske tilslutning godtok forlaget Knuths utvidede planer. I den utvidede versjonen vil boken bli utgitt i syv bind, hver med bare ett eller to kapitler. På grunn av veksten i kapittel 7, som var færre enn 100 sider av manuskriptet fra 1965, pr. 4A s. vi, har planen for bind 4 siden utvidet seg til å omfatte bind 4A, 4B, 4C, 4D og muligens mer.
I 1976 utarbeidet Knuth en andre utgave av bind 2, som krevde at den skulle settes på nytt, men typestilen som ble brukt i den første utgaven (kalt hot type ) var ikke lenger tilgjengelig. I 1977 bestemte han seg for å bruke litt tid på å lage noe mer passende. Åtte år senere kom han tilbake med T E X , som for tiden brukes til alle bind.
Tilbudet om en såkalt Knuth-belønningssjekk verdt "en heksadesimal dollar" (100 HEX- base 16 cent, i desimal , er $ 2,56) for eventuelle feil som ble funnet, og korrigering av disse feilene i påfølgende utskrifter, har bidratt til det svært polerte og fremdeles autoritativ karakter av verket, lenge etter at den ble publisert. Et annet kjennetegn ved volumene er variasjonen i vanskeligheten med øvelsene. Knuth har til og med en numerisk vanskelighetsgrad for vurdering av disse øvelsene, som varierer fra 0 til 50, hvor 0 er trivielt, og 50 er et åpent spørsmål i samtidsforskning.
Knuths engasjement lyder:
Denne serien med bøker er kjærlig dedikert
til Type 650 -datamaskinen en gang installert på
Case Institute of Technology ,
som jeg har tilbrakt mange hyggelige kvelder med.
Monteringsspråk i boken
Alle eksemplene i bøkene bruker et språk som kalles " MIX -samlingsspråk", som kjører på den hypotetiske MIX -datamaskinen. For øyeblikket blir MIX -datamaskinen erstattet av MMIX -datamaskinen, som er en RISC -versjon. Programvare som GNU MDK finnes for å gi emulering av MIX -arkitekturen. Knuth anser bruken av samlingsspråk som er nødvendig for hastigheten og minnebruk av algoritmer å bli bedømt.
Kritisk respons
Knuth ble tildelt Turing-prisen fra 1974 "for sine store bidrag til analysen av algoritmer [...], og spesielt for sine bidrag til" kunsten med dataprogrammering "gjennom sine kjente bøker i en kontinuerlig serie med denne tittelen." American Scientist har inkludert dette verket blant "100 eller så bøker som formet et århundre av vitenskap", med henvisning til det tjuende århundre, og i datavitenskapssamfunnet blir det sett på som den første og fremdeles den beste omfattende behandlingen av emnet. Omslagene i den tredje utgaven av bind 1 siterer Bill Gates som sa: "Hvis du synes du er en virkelig god programmerer ... les (Knuth's) Art of Computer Programming ... Du bør definitivt sende meg et resumé hvis du kan lese det hele. " New York Times omtalte det som "profesjonens definerende avhandling".
Volumer
Fullført
- Bind 1 - grunnleggende algoritmer
- Kapittel 1 - Grunnleggende begreper
- Kapittel 2 - Informasjon strukturer
- Bind 2 - Seminumeriske algoritmer
- Kapittel 3 - Tilfeldige tall
- Kapittel 4 - Regning
- Bind 3 - Sortering og søk
- Bind 4A - kombinatoriske algoritmer
- Kapittel 7 - Kombinerende søk (del 1)
Planlagt
- Volum 4B ... - Kombinatoriske algoritmer (kapitlene 7 og 8 utgitt i flere undervolumer)
- Kapittel 7 - Kombinerende søk (fortsettelse)
- Kapittel 8 - Rekursjon
- Bind 5 - syntaktiske algoritmer
- Kapittel 9 - Leksikalsk skanning (inkluderer også stringsøk og datakomprimering )
- Kapittel 10 - Parsing teknikker
- Bind 6-Theory of Context-Free Languages
- Volume 7 - Iler Teknikker
Kapittel skisserer
Fullført
Bind 1 - grunnleggende algoritmer
- Kapittel 1 - Grunnleggende begreper
- 1.1. Algoritmer
- 1.2. Matematiske forspill
- 1.2.1. Matematisk induksjon
- 1.2.2. Tall, fullmakter og logaritmer
- 1.2.3. Summer og produkter
- 1.2.4. Heltallsfunksjoner og elementær tallteori
- 1.2.5. Permutasjoner og faktorier
- 1.2.6. Binomiske koeffisienter
- 1.2.7. Harmoniske tall
- 1.2.8. Fibonacci tall
- 1.2.9. Generere funksjoner
- 1.2.10. Analyse av en algoritme
- 1.2.11. Asymptotiske representasjoner
- 1.2.11.1. Den O-notasjon
- 1.2.11.2. Eulers summeringsformel
- 1.2.11.3. Noen asymptotiske beregninger
- 1.3 MMIX ( MIX i innbundet versjon, men oppdatert av artikkel 1)
- 1.3.1. Beskrivelse av MMIX
- 1.3.2. MMIX Assembly Language
- 1.3.3. Søknader om permutasjoner
- 1.4. Noen grunnleggende programmeringsteknikker
- 1.4.1. Subrutiner
- 1.4.2. Coroutines
- 1.4.3. Tolkende rutiner
- 1.4.3.1. En MIX -simulator
- 1.4.3.2. Spor rutiner
- 1.4.4. Input og Output
- 1.4.5. Historie og bibliografi
- Kapittel 2 - Informasjonsstrukturer
- 2.1. Introduksjon
- 2.2. Lineære lister
- 2.2.1. Stabler, køer og Deques
- 2.2.2. Sekvensiell tildeling
- 2.2.3. Koblet tildeling ( topologisk sortering )
- 2.2.4. Sirkulære lister
- 2.2.5. Dobbeltkoblede lister
- 2.2.6. Arrays og ortogonale lister
- 2.3. Trær
- 2.3.1. Krysser binære trær
- 2.3.2. Binær tre representasjon av trær
- 2.3.3. Andre representasjoner av trær
- 2.3.4. Grunnleggende matematiske egenskaper for trær
- 2.3.4.1. Gratis trær
- 2.3.4.2. Orienterte trær
- 2.3.4.3. "Uendelig lemma"
- 2.3.4.4. Opptelling av trær
- 2.3.4.5. Banelengde
- 2.3.4.6. Historie og bibliografi
- 2.3.5. Lister og søppelsamling
- 2.4. Multilinkede strukturer
- 2.5. Dynamisk lagertildeling
- 2.6. Historie og bibliografi
Bind 2 - Seminumeriske algoritmer
- Kapittel 3 - Tilfeldige tall
- 3.1. Introduksjon
- 3.2. Generering av ensartede tilfeldige tall
- 3.2.1. Den lineære kongruensielle metoden
- 3.2.1.1. Valg av modul
- 3.2.1.2. Valg av multiplikator
- 3.2.1.3. Styrke
- 3.2.2. Andre metoder
- 3.2.1. Den lineære kongruensielle metoden
- 3.3. Statistiske tester
- 3.3.1. Generelle testprosedyrer for å studere tilfeldige data
- 3.3.2. Empiriske tester
- 3.3.3. Teoretiske tester
- 3.3.4. Den spektrale testen
- 3.4. Andre typer tilfeldige mengder
- 3.4.1. Numeriske fordelinger
- 3.4.2. Tilfeldig prøvetaking og blanding
- 3.5. Hva er en tilfeldig rekkefølge ?
- 3.6. Sammendrag
- Kapittel 4 - Regning
- 4.1. Posisjonsnummer systemer
- 4.2. Floating Point Aritmetic
- 4.2.1. Enkeltpresisjonsberegninger
- 4.2.2. Nøyaktigheten av flytende aritmetikk
- 4.2.3. Dobbel-presisjonsberegninger
- 4.2.4. Fordeling av flytende tall
- 4.3. Multiple Precision Aritmetic
- 4.3.1. De klassiske algoritmene
- 4.3.2. Modulær aritmetikk
- 4.3.3. Hvor fort kan vi multiplisere?
- 4.4. Radix -konvertering
- 4.5. Rasjonell regning
- 4.5.1. Brøk
- 4.5.2. Den største fellesdeleren
- 4.5.3. Analyse av Euklids algoritme
- 4.5.4. Faktorisering i primtal
- 4.6. Polynomisk regning
- 4.6.1. Divisjon av polynomer
- 4.6.2. Faktorisering av polynomer
- 4.6.3. Evaluering av fullmakter ( eksponering ved tilleggskjede )
- 4.6.4. Evaluering av polynomer
- 4.7. Manipulering av Power Series
Bind 3 - Sortering og søk
- Kapittel 5 - Sortering
- 5.1. Kombinatoriske egenskaper ved permutasjoner
- 5.1.1. Inversjoner
- 5.1.2. Permutasjoner av et multisett
- 5.1.3. Kjører
- 5.1.4. Tablåer og involusjoner
- 5.2. Intern sortering
- 5.2.1. Sortering etter innsetting
- 5.2.2. Sortering etter utveksling
- 5.2.3. Sortering etter utvalg
- 5.2.4. Sortering etter sammenslåing
- 5.2.5. Sortering etter distribusjon
- 5.3. Optimal sortering
- 5.3.1. Minimumssammenligningssortering
- 5.3.2. Sammenslåing av minimumssammenligning
- 5.3.3. Valg av minimumssammenligning
- 5.3.4. Nettverk for sortering
- 5.4. Ekstern sortering
- 5.4.1. Flerveis sammenslåing og utskifting
- 5.4.2. Polyphase Merge
- 5.4.3. Cascade -sammenslåingen
- 5.4.4. Lese kassett bakover
- 5.4.5. Den oscillerende sorten
- 5.4.6. Praktiske hensyn ved sammenslåing av bånd
- 5.4.7. Ekstern Radix -sortering
- 5.4.8. To-båndssortering
- 5.4.9. Skiver og trommer
- 5.5. Oppsummering, historie og bibliografi
- 5.1. Kombinatoriske egenskaper ved permutasjoner
- Kapittel 6 - Søk
Bind 4A - kombinatoriske algoritmer, del 1
- Kapittel 7 - Kombinatorisk søk
- 7.1. Nuller og en
- 7.1.1. Boolsk grunnleggende
- 7.1.2. Boolsk evaluering
- 7.1.3. Bitvise triks og teknikker
- 7.1.4. Binære beslutningsdiagrammer
- 7.2. Generere alle muligheter
- 7.2.1. Generere grunnleggende kombinatoriske mønstre
- 7.2.1.1. Genererer alle n- tupler
- 7.2.1.2. Genererer alle permutasjoner
- 7.2.1.3. Genererer alle kombinasjoner
- 7.2.1.4. Genererer alle partisjoner
- 7.2.1.5. Genererer alle angitte partisjoner
- 7.2.1.6. Genererer alle trær
- 7.2.1.7. Historie og flere referanser
- 7.2.1. Generere grunnleggende kombinatoriske mønstre
- 7.1. Nuller og en
Planlagt
Volum 4B, 4C, 4D - kombinatoriske algoritmer
- Kapittel 7 - Kombinatorisk søk (fortsettelse)
- 7.2. Generere alle muligheter (forts.)
- 7.2.2. Backtrack programmering (publisert i Fascicle 5)
- 7.2.2.1. Dancing lenker (publisert i fascikkel 5)
- 7.2.2.2. Tilfredshet (publisert i Fascicle 6)
- 7.2.2.3. Begrensningstilfredshet
- 7.2.2.4. Hamiltoniske stier og sykluser (online utkast i pre-fascicle 8A)
- 7.2.2.5. Klikk
- 7.2.2.6. Dekker ( Vertex cover , Set cover problem , Exact cover , Clique cover )
- 7.2.2.7. Firkanter
- 7.2.2.8. Et potpourri av gåter (online utkast i pre-fascicle 9B) (inkluderer Perfect digital invariant )
- 7.2.2.9. Estimering av backtrack -kostnader (kapittel 6 i "Selected Papers on Analysis of Algorithms", og Fascicle 5, s. 44−47, under overskriften "Løpetidsestimater")
- 7.2.3. Generering av inekvivalente mønstre (inkluderer diskusjon av Pólya -oppregningsteoremet ) (se "Teknikker for Isomorph -avvisning", kapittel 4 i "Klassifiseringsalgoritmer for koder og design" av Kaski og Östergård)
- 7.2.2. Backtrack programmering (publisert i Fascicle 5)
- 7.3. Korteste veier
- 7.4. Grafiske algoritmer
- 7.4.1. Komponenter og traversal
- 7.4.2. Spesielle klasser av grafer
- 7.4.3. Utvidelsesgrafer
- 7.4.4. Tilfeldige grafer
- 7.5. Grafer og optimalisering
- 7.5.1. Bipartite matching (inkludert matching av maksimal kardinalitet , stabilt ekteskapsproblem , Mariages Stables )
- 7.5.2. Oppgaveproblemet
- 7.5.3. Nettverk flyter
- 7.5.4. Optimale undertrær
- 7.5.5. Optimal matchning
- 7.5.6. Optimal bestilling
- 7.6. Uavhengighetsteori
- 7.6.1. Uavhengighetsstrukturer
- 7.6.2. Effektive matroid -algoritmer
- 7.7. Diskret dynamisk programmering (se også Transfer-matrix method )
- 7.8. Gren-og-bundet teknikker
- 7.9. Herculean oppgaver (aka NP-harde problemer)
- 7.10. Nesten optimalisering
- 7.2. Generere alle muligheter (forts.)
- Kapittel 8 - Rekursjon (kapittel 22 i "Utvalgte artikler om analyse av algoritmer")
Bind 5 - syntaktiske algoritmer
- Kapittel 9 - Leksikalsk skanning (inkluderer også stringsøk og datakomprimering)
- Kapittel 10 - Parsing teknikker
Bind 6-Theory of Context-free Languages
Bind 7 - kompileringsteknikker
Engelske utgaver
Gjeldende utgaver
Dette er de nåværende utgavene i rekkefølge etter volumnummer:
-
The Art of Computer Programming, Volumes 1-4A Boxed Set . Tredje utgave (Reading, Massachusetts: Addison-Wesley, 2011), 3168 sider. ISBN 978-0-321-75104-1 , 0-321-75104-3
- Bind 1: grunnleggende algoritmer . Tredje utgave (Reading, Massachusetts: Addison-Wesley, 1997), xx+650 sider. ISBN 978-0-201-89683-1 , 0-201-89683-4 . Errata: [1] (2011-01-08), [2] (2020-03-26, 27. utskrift ). Tillegg: [3] (2011).
- Bind 2: Seminumeriske algoritmer . Tredje utgave (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762 sider. ISBN 978-0-201-89684-8 , 0-201-89684-2 . Errata: [4] (2011-01-08), [5] (2020-03-26, 26. utskrift). Tillegg: [6] (2011).
- Bind 3: Sortering og søk . Andre utgave (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780 sider.+Foldout. ISBN 978-0-201-89685-5 , 0-201-89685-0 . Errata: [7] (2011-01-08), [8] (2020-03-26, 27. utskrift). Tillegg: [9] (2011).
- Bind 4A: kombinatoriske algoritmer, del 1 . Første utgave (Reading, Massachusetts: Addison-Wesley, 2011), xv+883 sider. ISBN 978-0-201-03804-0 , 0-201-03804-8 . Errata: [10] (2020-03-26,? Utskrift).
- Volume 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium . (Addison-Wesley, 2005-02-14) ISBN 0-201-85392-2 . Errata: [11] (2020-03-16) (kommer i fjerde utgave av bind 1)
- Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links . (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6 . Errata: [12] (2020-03-27) (blir en del av bind 4B)
- Bind 4, Fascicle 6: Tilfredshet . (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3 . Errata: [13] (2020-03-26) (blir en del av bind 4B)
Tidligere utgaver
Komplette bind
Disse bindene ble erstattet av nyere utgaver og er i orden etter dato.
- Bind 1: grunnleggende algoritmer . Første utgave, 1968, xxi+634pp, ISBN 0-201-03801-3 .
- Bind 2: Seminumeriske algoritmer . Første utgave, 1969, xi+624pp, ISBN 0-201-03802-1 .
- Bind 3: Sortering og søk . Første utgave, 1973, xi+723pp+foldout, ISBN 0-201-03803-X . Errata: [14] .
- Bind 1: grunnleggende algoritmer . Andre utgave, 1973, xxi+634pp, ISBN 0-201-03809-9 . Errata: [15] .
- Bind 2: Seminumeriske algoritmer . Andre utgave, 1981, xiii+ 688pp, ISBN 0-201-03822-6 . Errata: [16] .
- The Art of Computer Programming, Volumes 1-3 Boxed Set . Andre utgave (Reading, Massachusetts: Addison-Wesley, 1998), s. ISBN 978-0-201-48541-7 , 0-201-48541-9
Fascicles
Volume 4 's fascicles 0–4 ble revidert og utgitt som Volume 4A:
- Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions . (Addison-Wesley Professional, 2008-04-28) vi+240pp, ISBN 0-321-53496-4 . Errata: [17] (2011-01-01).
- Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binære beslutningsdiagrammer . (Addison-Wesley Professional, 2009-03-27) viii+260pp, ISBN 0-321-58050-8 . Errata: [18] (2011-01-01).
- Volume 4, Fascicle 2: Generating All Tuples and Permutations . (Addison-Wesley, 2005-02-14) v+127pp, ISBN 0-201-85393-0 . Errata: [19] (2011-01-01).
- Bind 4, Fascicle 3: Generering av alle kombinasjoner og partisjoner . (Addison-Wesley, 2005-07-26) vi+150pp, ISBN 0-201-85394-9 . Errata: [20] (2011-01-01).
- Volume 4, Fascicle 4: Generating All Trees; Historien om kombinatorisk generasjon . (Addison-Wesley, 2006-02-06) vi+120pp, ISBN 0-321-33570-8 . Errata: [21] (2011-01-01).
Volume 4 's fascicles 5-6 vil bli en del av volumet 4B:
- Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links . (Addison-Wesley, 2019-11-22) xiii+382pp, ISBN 978-0-13-467179-6 . Errata: [22] (2020-03-27)
- Bind 4, Fascicle 6: Tilfredshet . (Addison-Wesley, 2015-12-08) xiii+310pp, ISBN 978-0-13-439760-3 . Errata: [23] (2020-03-26)
Pre-fascicles
Volume 4 's pre-fascicles 5A, 5B og 5C ble revidert og utgitt som fascikkel 5.
Volume 4 's pre-fascikkel 6A ble revidert og utgitt som fascikkel 6.
- Volume 4, Pre-fascicle 8A: Hamiltonian Paths and Cycles
- Volume 4, Pre-fascicle 9B: A Potpourri of Puzzles
Se også
Referanser
Merknader
Sitater
Kilder
- Slater, Robert (1987). Portretter i silisium . MIT Press . ISBN 0-262-19262-4.
- Shasha, Dennis ; Lazere, Cathy (1995). Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists . Copernicus. ISBN 0-387-97992-1.
Eksterne linker
- Oversikt over emner (Knuths personlige hjemmeside)
- Muntlig historieintervju med Donald E. Knuth ved Charles Babbage Institute , University of Minnesota, Minneapolis. Knuth diskuterer programvarepatentering, strukturert programmering , samarbeid og utviklingen av TeX . Den muntlige historien diskuterer skrivingen av The Art of Computer Programming .
- "Robert W Floyd, In Memoriam", av Donald E. Knuth - (om påvirkning av Bob Floyd )
- TAoCP og dens innflytelse av informatikk (Softpanorama)