Il progetto di scrittura del libro è stato avviato dall'autore a . Inizialmente, si prevedeva di pubblicarlo in un volume, ma la quantità di materiale si è rivelata così grande che il numero di volumi è stato aumentato a sette. I primi tre volumi sono stati pubblicati abbastanza rapidamente: volume 1 nel 1968, volume 2 nel 1969 e volume 3 nel 1973, seguiti da una pausa fino al febbraio 2005, in cui l'autore ha pubblicato la prima parte del quarto volume. Fu presa la decisione di pubblicare le parti rimanenti del quarto volume circa due volte l'anno in numeri separati, dopodiché l'intero quarto volume sarebbe stato ufficialmente pubblicato. I numeri 0, 1, 2, 3 e 4 sono stati pubblicati nel periodo 2005-2009 e nel 2011 è stato pubblicato il volume 4A, che includeva informazioni su questi numeri. Sempre nel 2005 è uscito il Numero 1 "MMIX - A RISC Computer for the New Millennium", le cui informazioni saranno incluse nella nuova, quarta edizione del primo volume. Il numero 6 è stato pubblicato nel 2015 Soddisfabilità, che rappresenta il terzo medio del futuro volume 4B.

Poiché Knuth aveva sempre considerato The Art of Programming il progetto principale della sua vita, si ritirò nel 1993 con l'intenzione di concentrarsi completamente sulla scrittura delle parti mancanti e riordinare quelle esistenti. Credeva che ci sarebbero voluti 20 anni per completare il lavoro.

YouTube enciclopedico

• 1 / 5

  In qualità di esperto riconosciuto di progettazione di compilatori, nel 1962 Knuth iniziò a scrivere un libro sulla progettazione di compilatori. Ben presto si rese conto che la portata del materiale doveva essere molto più ampia. Nel giugno 1965 terminò di scrivere la prima versione di ciò che originariamente voleva pubblicare in un libro di dodici sezioni. Il volume del testo scritto a mano era di 3000 pagine. Secondo i calcoli di Knuth, questo volume avrebbe dovuto contenere 600 pagine stampate, ma, come gli disse il suo editore, volume reale sarebbero 2000 pagine. A questo proposito, la struttura del libro è stata rivista a favore di più volumi, 1-2 sezioni ciascuno. Da allora, a causa della costante crescita del materiale, si decise che anche il quarto volume sarebbe stato suddiviso in libri separati: 4A, 4B, 4C e possibilmente 4D. Ma anche questa divisione, a quanto pare, non sarà definitiva, poiché le sezioni 7.1 e 7.2.1 occupano già più di 650 pagine in totale.

  Nel 1976 Knuth produsse una seconda edizione del secondo volume, che richiedeva la riscrittura. Ma il design tipografico (monotipo) utilizzato nella prima edizione non era più disponibile a questo punto. Per evitare simili delusioni in futuro, nel 1977 Knuth iniziò a sviluppare il proprio sistema tipografico. set di computer. Secondo i suoi calcoli, il lavoro non avrebbe dovuto richiedere più di sei mesi, ma ci sono voluti circa dieci anni prima che fosse completato. Il sistema si chiamava TeX ed è attualmente utilizzato per la composizione di tutti i volumi di The Art of Programming. Inoltre, successivamente, TeX è diventato lo standard de facto per la scrittura di articoli e monografie nelle scienze naturali.

  Come gli altri libri di Knuth, The Art of Programming è contrassegnato dal suo "marchio": per ogni errore riscontrato nel testo, l'autore paga un dollaro esadecimale, ovvero $ 2,56 (0x100 centesimi, in base 16). Un altro caratteristica distintiva libro è un'abbondanza di esercizi per l'autorealizzazione, vari gradi di difficoltà, che vanno da semplici enigmi"per il riscaldamento" e la fine questioni aperte. La difficoltà di ogni esercizio è valutata su una scala numerica da 0 a 50. Quindi, nelle prime edizioni, il numero 50 era contrassegnato dal Grande  Teorema Fattoria, ma nella terza edizione questa valutazione è stata “svalutata” a 45, poiché da quella volta la sua dimostrazione aveva già cessato di essere un problema aperto.

  Sommario simboli per il terzo volume, 1978 "Ordinamento e ricerca" (a sinistra - valutazione, a destra - breve spiegazione)

  • Triangolo nero - Consigliato
  • M - Con un pregiudizio matematico
  • VM - Richiede la conoscenza di "matematica superiore"
  • 00 - Richiede una risposta immediata
  • 10 - Semplice (per 1 minuto)
  • 20 - Difficoltà media (per 15 minuti)
  • 30 - Difficoltà aumentata
  • 40 - Per "matpraktikum"
  • 50 - Problema di ricerca

  Il piano originale per scrivere il libro suggeriva la seguente suddivisione del materiale.

  • Volume 1. Algoritmi di base.
    • Capitolo 1. Concetti di base.
    • Capitolo 2. Strutture informative.
  • Volume 2. Algoritmi derivati.
    • Capitolo 3. Numeri casuali.
    • Capitolo 4. Aritmetica.
  • Volume 3. Ordinamento e ricerca.
    • Capitolo 5. Ordinamento.
    • Capitolo 6
  • Volume 4. Algoritmi combinatori.
    • Capitolo 7. Ricerca combinatoria.
    • Capitolo 8. Ricorsività.
  • Volume 5. Algoritmi sintattici.
    • Capitolo 9. Ricerca lessicografica.
    • Capitolo 10. Ricerca sintattica.
  • Volume 6. Teoria dei linguaggi.
  • Volume 7. Compilatori.

  In effetti, questo schema è stato implementato fino al terzo volume incluso.

  A questo momento volume pubblicato 4A, che contiene le prime sezioni del capitolo 7. Le nuove sezioni dovrebbero essere inizialmente pubblicate in numeri separati (circa 128 pagine), circa due numeri all'anno (i numeri 0, 1, 2, 3 e 4 sono stati pubblicati in modo simile prima dell'uscita del volume 4A).

  Linguaggio di esempio orientato alla macchina

  I programmi di esempio nel libro utilizzano un "assemblatore MIX" progettato per essere eseguito su un ipotetico computer MIX. Nella terza edizione, l'obsoleto MIX è stato sostituito da MMIX, che ha una vera e propria architettura RISC. È disponibile un software che fornisce l'emulazione della macchina (M)MIX su computer standard compatibili con IBM. GNU Compiler Collection ha la capacità di compilare codice C/C++ per l'architettura MMIX di destinazione.

  Molti lettori sono scoraggiati dall'uso del linguaggio basso livello, ma Knuth ritiene giustificata la sua scelta, in quanto il legame con l'architettura è necessario per poter giudicare con precisione caratteristiche dell'algoritmo come velocità, consumo di memoria, ecc. In conseguenza di questa scelta, tuttavia, il pubblico di destinazione si restringe molto. Inoltre, lo scopo della sua applicazione come "libro di ricette" per programmatori pratici, molti dei quali non conoscono il linguaggio assembly e, se lo conoscono, non hanno voglia di tradurre algoritmi di basso livello dal libro in linguaggi, è anche limitato. alto livello. Molte guide pratiche che presentano lo stesso materiale in modo più popolare vengono pubblicate proprio per questo motivo.

  Critica

  La caratteristica principale della monografia di Knuth, che la distingue favorevolmente da altri libri sulla programmazione, è l'eccezionale livello di qualità del materiale e della presentazione accademica, nonché la profondità dell'analisi delle questioni in esame. Grazie a questo, è diventato un vero bestseller e un libro di riferimento per ogni programmatore professionista. The Art of Programming è stata nominata da American Scientist come una delle 12 migliori monografie fisiche e matematiche del 20° secolo, insieme a Dirac sulla meccanica quantistica, Einstein sulla relatività, Russell e Whitehead sui fondamenti della matematica e pochi altri.

  La copertina della terza edizione del primo volume del libro contiene una citazione di Bill Gates: "Se ti consideri davvero un buon programmatore…, leggi The Art of Programming (Knuth)… Se riesci a leggere tutto questo, dovresti assolutamente inviarmi il tuo curriculum.”.

  Edizioni

  Originale

  Terzo (attuale)

  In ordine crescente di numeri di volume:

  • Volume 1: Algoritmi fondamentali. Terza edizione (Lettura, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
  • Volume 1, Fascicolo 1: MMIX - Un computer RISC per il nuovo millennio. (Addison-Wesley, 14 febbraio 2005) ISBN 0-201-85392-2 (sarà nella quarta edizione del volume 1)
  • Volume 2: Algoritmi seminumerici. Terza edizione (Lettura, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
  • Volume 3: Ordinamento e ricerca. Seconda edizione (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
  • Volume 4A: Algoritmi Combinatoriali, Parte 1(Upper Saddle River, New Jersey: Addison-Wesley, 2011), xvi+883pp. ISBN 0-201-03804-8
  • Volume 4, Fascicolo 6: Soddisfabilità. (Addison-Wesley Professional, 2015), xiii+310pp. ISBN 978-0-13-439760-3

  Precedente

  Per data di pubblicazione:

  • Volume 1, prima edizione, 1968. 634pp. ISBN 0-201-03801-3.
  • Volume 2, prima edizione, 1969, xi+624pp, ISBN 0-201-03802-1 .
  • Volume 3, prima edizione, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
  • Volume 1, seconda edizione, 1973, xiii+634pp, ISBN 0-201-03809-9 .
  • Volume 2, seconda edizione, 1981, xiii+ 688pp. ISBN 0-201-03822-6.
  • Volume 4, Fascicolo 2: Generazione di tutte le tuple e permutazioni, (Addison-Wesley, 14 febbraio 2005) v+127pp, ISBN 0-201-85393-0
  • Volume 4, Fascicolo 3: Generazione di tutte le combinazioni e partizioni. (Addison-Wesley, 26 luglio 2005) vi+150pp, ISBN 0-201-85394-9
  • Volume 4, Fascicolo 4: Generazione di tutti gli alberi - Storia della generazione combinatoria, (Addison-Wesley, 6 febbraio 2006) vi+120pp, ISBN 0-321-33570-8
  • Volume 4, Fascicolo 0: Introduzione agli algoritmi Combinatoriali e alle Funzioni Booleane, (Addison-Wesley Professional, 28 aprile 2008) vi+240pp, ISBN 0-321-53496-4
  • Volume 4, Fascicolo 1: Trucchi e tecniche bit per bit; Diagrammi di decisione binaria(Addison-Wesley Professional, 27 marzo 2009) viii+260pp,

  Nel mercato globale della letteratura informatica, ci sono molti libri progettati per insegnare algoritmi di base e utilizzati nella programmazione. Ce ne sono parecchi e competono tra loro in larga misura. Tuttavia, tra questi c'è un libro speciale. Questo è un tre volumi "The Art of Programming" di D. E. Knuth, che si distingue da tutta la concorrenza, è incluso nel fondo d'oro della letteratura mondiale sull'informatica ed è un libro di riferimento per quasi tutti coloro che sono associati alla programmazione.

  Come editori, vediamo il valore del libro in quanto è inteso non tanto per insegnare le tecniche di programmazione, ma per insegnare, se possibile, "l'arte" della programmazione, offre molte ricette per migliorare i programmi e, soprattutto , ti insegna a trovare queste ricette da solo.

  Non è un segreto che i nostri programmatori siano tra gli specialisti più qualificati al mondo. Rappresentano adeguatamente la Scuola nazionale di programmazione e informatica all'estero, che ha dato un contributo significativo alla formazione dei fondamenti fondamentali dell'informatica. Per mantenere questo livello e andare avanti, è necessario pubblicare tempestivamente libri in russo che riflettano i principali risultati mondiali in questo settore. Il tre volumi "The Art of Programming" di DE Knuth è uno di questi libri.

  Siamo orgogliosi che le biblioteche di programmatori, insegnanti, studenti, studenti delle scuole superiori e molti altri si arricchiranno di questo classico libro e che così facendo contribuiremo a una comprensione più profonda dei fondamenti dell'informatica. Siamo profondamente convinti che il libro "The Art of Programming" di D. E. Knuth possa avvicinare una persona alla perfezione. Ci auguriamo che la nostra edizione russa di questo meraviglioso libro confermi ancora una volta che i veri valori non diventano obsoleti nel corso degli anni.

  - Victor Shtonda, Gennady Petrikovets, Alexey Orlovich, editori

  Informazioni sull'arte della programmazione

  Ogni libro ha il suo destino. Alcuni appaiono impercettibilmente e altrettanto impercettibilmente scompaiono nel corso del tempo, ricoperti di polvere sugli scaffali delle biblioteche. Altri dentro certo periodo sono richiesti da una ristretta cerchia di specialisti fino a quando non vengono sostituiti da nuovi libri di consultazione. Altri ancora, elevandosi al di sopra del tempo, esercitano una potente influenza sullo sviluppo tecnologico della società. Non sono molti i libri che rientrano in quest'ultima categoria. Il loro rilascio è sempre una vacanza. Passano gli anni, le tecnologie cambiano, ma le nuove generazioni rileggono le loro pagine con costante interesse. È a questi libri che appartiene il lavoro in più volumi del famoso scienziato americano Donald Erwin Knuth "The Art of Programming" offerto al lettore.

  Sono passati quasi 30 anni dalla prima edizione nel 1972 negli USA di questo libro. È stato tradotto nella maggior parte delle lingue del mondo, incluso il russo. Ad oggi, nel territorio dei paesi della CSI, il libro in tre volumi di D. E. Knuth è diventato una rarità bibliografica. Nel 1998 è stata pubblicata negli Stati Uniti la terza edizione di The Art of Programming, che mantiene la sequenza di presentazione del materiale versione precedente, ma l'elenco dei riferimenti è stato notevolmente ampliato, che include i risultati più recenti e più importanti, sono stati aggiunti nuovi esercizi e commenti e sono state eliminate le imprecisioni. Data la popolarità mondiale di The Art of Programming, avremmo dovuto aspettarci una nuova edizione tradotta in russo, che tieni tra le mani, da molto tempo.

  Qual è il successo di "The Art of Programming" di D. E. Knuth?

  In primo luogo, questo libro è un eccellente libro di testo per scrivere e analizzare algoritmi informatici. Le sue sezioni possono essere incluse in molti corsi universitari su tecnologie di programmazione, teoria degli algoritmi e matematica discreta. Il libro può essere studiato anche da studenti delle scuole superiori che hanno familiarità con le basi della programmazione. Come linguaggio principale per la scrittura di algoritmi, l'autore ha scelto il linguaggio delle istruzioni macchina di un ipotetico calcolatore universale MESCOLARE. Ciò consente di creare programmi ottimali, tenendo conto delle caratteristiche dei computer. Trasferire programmi MIX su computer reali o riscriverli in linguaggi di alto livello non è difficile. La logica di come funzionano i programmi è quasi sempre spiegata con semplici diagrammi di flusso.

  In secondo luogo, il materiale accuratamente selezionato incluso nel libro include le principali classi fondamentali di algoritmi, che in una forma o nell'altra si incontrano più spesso nella pratica della programmazione.

  In terzo luogo, un fattore importante per il successo del libro di D. E. Knuth è la presentazione enciclopedica. Il professor Knuth ha una capacità unica di tracciare un problema dal contesto storico della sua origine a all'avanguardia. Numerosi i riferimenti alle opere di maestri antichi (fino all'antichità), contenuti in contesto contemporaneo creare nel lettore uno speciale senso di appartenenza sviluppo storico idee e metodi scientifici.

  In quarto luogo, va notata la padronanza della presentazione. Il libro è destinato a una vasta gamma di lettori, dagli studenti alle prime armi ai programmatori professionisti. Tutti saranno interessati ad apprendere algoritmi informatici al proprio livello. Il materiale è sufficiente. Per comprendere l'essenza dei metodi, non è richiesta la conoscenza di sezioni speciali di matematica o di tecnologie di programmazione speciali. Si può rintracciare una certa composizione "musicale" della costruzione della trama (in casa, D. E. Knuth ha un piccolo organo su cui suona).

  L'elenco degli ingredienti per il successo di The Art of Programming può essere facilmente proseguito.

  L'autore di queste righe ha frequentato il corso "The Art of Programming" tenuto dal Professor Knuth nel 1976-1977 durante uno stage presso la Stanford University. Quindi si sono formate le basi algoritmiche delle tecnologie di programmazione, alle cui origini si trovava D. E. Knuth. Ci sono state molte discussioni, seminari, idee creative.

  I libri significativi sono sempre collegati al destino dell'autore. Donald Erwin Knuth iniziò a lavorare a The Art of Programming nel 1962. Continua ancora oggi. Ha molti progetti. In vista dei nuovi volumi de "L'arte della programmazione" che i lettori attendono con impazienza.

  - Professor Anatoly Anisimov

  Dall'editore di traduzione

  Sono passati circa 25 anni dalla prima edizione di The Art of Programming di D. E. Knuth. Tuttavia, il libro non solo non è diventato obsoleto, ma rimane ancora la guida principale all'arte della programmazione, un libro da cui si impara a capire l'essenza e le caratteristiche di quest'arte.

  Negli anni per lingua ingleseè già stata pubblicata la terza edizione del 1° e 2° volume, nonché la seconda edizione del 3° volume. L'autore ha apportato modifiche e integrazioni significative. Basti pensare che il numero degli esercizi è quasi raddoppiato e molti degli esercizi inclusi nelle precedenti edizioni (soprattutto le relative risposte) sono stati modificati. Molti capitoli e sezioni sono stati significativamente integrati e rivisti, sono state corrette imprecisioni ed errori tipografici, sono stati aggiunti numerosi nuovi riferimenti alla letteratura e sono stati utilizzati i risultati teorici degli ultimi anni.

  Il capitolo 3 è stato notevolmente modificato, in particolare le sezioni 3.5 e 3.6, nonché le sezioni 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5, ecc.

  Naturalmente, c'era bisogno di una nuova edizione del libro.

  La traduzione è stata effettuata secondo la terza edizione del 1° e 2° volume e la seconda edizione del 3° volume. Vengono inoltre prese in considerazione integrazioni e correzioni gentilmente fornite dall'autore.

  Durante la traduzione, abbiamo cercato di preservare lo stile, le designazioni e il modo di presentare il materiale dell'autore. Nella maggior parte dei casi sono stati utilizzati i termini adottati nella letteratura scientifica in russo. Gli equivalenti inglesi sono stati citati ove necessario. Per molte ragioni, in particolare per la complessità di alcune sezioni, leggere L'arte della programmazione è tutt'altro che facile. Uno dei motivi che rendono difficile la comprensione del libro è il modo in cui l'autore lo presenta; una volta che ti ci abitui, puoi renderlo molto più facile da leggere.

  A causa dell'abbondanza di materiale (spesso poco connesso tra loro), è impossibile strutturare il libro in modo tale che vari concetti e definizioni vengano introdotti immediatamente alla prima menzione. Pertanto, nel Capitolo 1, possono essere discussi concetti senza riferimento, le cui definizioni rigorose sono date nel 3° volume. Ecco perché il ruolo dell'indice delle materie è così grande, senza il quale la comprensione del libro sarebbe notevolmente difficile. Ci auguriamo che il lettore non sia sorpreso di trovare riferimenti ai capitoli 7, 8 e successivi non inclusi nei tre volumi proposti. Insieme all'autore, speriamo che vengano pubblicati molto presto e, ovviamente, appaiano immediatamente nella traduzione russa come continuazione di questa edizione.

  Si dovrebbe anche prestare attenzione alla notazione tutt'altro che standard usata dall'autore. Oltre alle definizioni, queste designazioni possono apparire nel 1° volume e sono introdotte nel 2°. Pertanto, senza un indice di notazione, sarebbe estremamente difficile utilizzare il libro. Voglio anche prestare attenzione alla notazione [A], dove A è un'affermazione. Questa voce si trova nelle formule, e talvolta nel testo, e denota un valore uguale all'indicatore A.

  - Professor Yu. V. Kozachenko

  PREFAZIONE

  Cari lettori! Hai in mano un libro

  di pubblicare ciò che ci hai chiesto in migliaia di lettere. Abbiamo dovuto passare anni a controllare e ricontrollare con attenzione un'infinità di ricette e selezionare per voi le migliori, le più interessanti, le più perfette.

  Ora, senza ombra di dubbio, possiamo dire che se segui le istruzioni, allora ogni piatto risulterà uguale per te come per noi, anche se non hai mai cucinato prima.
  - Il ricettario McCall (1963)

  Il processo di preparazione dei programmi per un computer digitale è un'attività molto eccitante. E il punto non è solo che si giustifica da un punto di vista economico e scientifico; può anche evocare sentimenti estetici, argomenti simili che sperimentano la personalità creativa quando scrivono musica o poesie. Hai tra le mani il primo volume di un'edizione multi-volume, il cui scopo è quello di fornire al lettore una varietà di conoscenze e abilità che costituiscono il mestiere del programmatore.

  I capitoli seguenti non sono un'introduzione alla programmazione del computer; si presume che tu abbia già una certa esperienza in questo settore. In effetti, i requisiti per il lettore sono molto semplici; tuttavia, un programmatore alle prime armi avrà bisogno di tempo e pratica per capire di cosa si tratta calcolatore digitale. Quindi il lettore deve avere:

  a) una certa comprensione di come funziona un computer digitale con un programma memorizzato; allo stesso tempo non è necessario comprendere l'elettronica, l'importante è capire come i comandi possono essere archiviati nella memoria del computer e poi eseguiti in sequenza;

  b) la capacità di esporre il problema in termini chiari e definiti, comprensibile al computer(i computer non hanno l'intelligenza umana, quindi fanno esattamente quello che gli viene detto, né più né meno; questo è solitamente il fatto più difficile da capire per gli utenti inesperti);

  c) conoscenza del più semplice metodi informatici, come l'organizzazione di cicli (esecuzione ripetuta di un certo insieme di comandi), nonché l'utilizzo di sottoprogrammi e variabili con indici;

  d) conoscenza del comune termini informatici, ad esempio "memoria", "registri", "bit", "virgola mobile", "overflow", "software"; la maggior parte dei termini non definiti nel testo sono spiegati in un indice alfabetico alla fine di ogni volume.

  Queste quattro condizioni possono probabilmente essere combinate in un unico requisito: il lettore deve avere esperienza nella scrittura e nel debug di almeno quattro programmi per almeno un computer.

  Ho cercato di scrivere questi libri in modo tale che possano servire a diversi scopi. In primo luogo, sono una guida di riferimento che riunisce le conoscenze provenienti da diverse importanti aree della scienza. In secondo luogo, possono essere utilizzati come ausili di autodidattica e libri di testo di programmazione o di informatica per le università. Per questo motivo ho incluso un gran numero di esercizi e fornito risposte alla maggior parte di essi. Inoltre, ho cercato di concentrarmi sui fatti, invece di "versare acqua" e impegnarmi in un ragionamento generale.

  Questo libro in tre volumi è destinato a tutti coloro che sono seriamente interessati ai computer e non solo ai professionisti. In effetti, uno dei miei obiettivi principali è stato quello di rendere i metodi di programmazione più accessibili a persone in altri campi. Di norma, questi specialisti ottengono grandi vantaggi utilizzando i computer, ma non possono permettersi di perdere tempo alla ricerca delle informazioni necessarie, frammenti delle quali sono sparsi in molte riviste tecniche.

  Il tema di questi libri può essere formulato come segue: "Analisi non numerica". I computer sono solitamente associati alla risoluzione di problemi numerici, come trovare le radici di un'equazione, l'interpolazione numerica, l'integrazione, ecc. Ma tali argomenti non sono trattati in questo libro in tre volumi (tranne quando è necessario farlo lungo il percorso) . La programmazione numerica per computer è un campo estremamente interessante e in rapido sviluppo;

  molto è stato scritto su questo argomento buoni libri. Ma dagli anni '60, i computer sono stati sempre più utilizzati per risolvere problemi in cui i numeri giocano un ruolo secondario. Ora la capacità del computer di prendere decisioni, e non solo di eseguire, viene alla ribalta. operazioni aritmetiche. Quando si risolvono problemi non numerici, a volte è necessario eseguire operazioni di addizione e sottrazione, ma la necessità di moltiplicazione e divisione si verifica abbastanza raramente. Ma, ovviamente, anche qualcuno che si occupa principalmente di numeri programmazione computer, trarranno vantaggio solo dallo studio di metodi non numerici, poiché sono anche la base di programmi numerici.

  I risultati della ricerca nel campo dell'analisi non numerica sono sparsi in molte riviste tecniche. Il mio obiettivo era estrarre da questa enorme quantità di informazioni solo metodi fondamentali che possono essere applicati a diversi tipi di situazioni di programmazione. Ho cercato di generalizzare le informazioni selezionate al fine di ottenere quella che più o meno può essere chiamata "teoria", e anche di mostrare come applicare questa teoria a vari problemi pratici.

  Naturalmente, "analisi non numerica" ​​è un nome estremamente sfortunato per questo campo della scienza. È un peccato, anzitutto, perché contiene solo la negazione di un altro concetto; sarebbe molto meglio scegliere un termine più significativo che non abbia il prefisso "non". Il nome "elaborazione delle informazioni" copre un'area più ampia rispetto al materiale qui considerato e "metodi di programmazione" una più ristretta. Credo che per l'argomento trattato in questi libri, il nome più appropriato sia l'analisi degli algoritmi, che può essere decifrata come "la teoria delle proprietà di alcuni algoritmi informatici".

  La serie completa di libri, intitolata L'arte della programmazione, ha la seguente struttura di base.

  Volume 1. Algoritmi di base

  Capitolo 1. Concetti di base Capitolo 2. Strutture informative

  Volume 2. Algoritmi derivati

  Capitolo 3 Numeri casuali Capitolo 4 Aritmetica

  Volume 3. Ordinamento e ricerca

  Capitolo 5 Ordinamento Capitolo 6 Ricerca

  Volume 4. Algoritmi combinatori

  Capitolo 7 Ricerca Combinatoria Capitolo 8 Ricorsività

  Volume 5 Algoritmi sintattici

  Capitolo 9 Ricerca lessicografica Capitolo 10 Analisi

  Il volume 4 copre un argomento molto ampio, quindi in realtà è composto da tre libri separati (volumi 4A, 4B e 4C). Ci sono anche piani per il rilascio di due volumi aggiuntivi su argomenti più specializzati: Volume 6, Theory of Languages ​​(Capitolo 11) e Volume 7, Compilers (Capitolo 12).

  Ho iniziato questo lavoro nel 1962 con l'intenzione di scrivere un unico libro che contenesse tutti i capitoli elencati, ma mi sono presto reso conto che era necessario approfondire gli argomenti scelti, e non solo "scivolare in superficie". Il risultato è stato un testo di tale lunghezza che il materiale di ogni capitolo è stato più che sufficiente per studiare durante un semestre universitario. Ed è diventato chiaro che era necessario suddividere il materiale in diversi volumi separati. So che un libro che contiene solo uno o due capitoli sembra piuttosto strano, ma ho deciso di mantenere la numerazione dei capitoli originale per semplificare i riferimenti incrociati. Una versione ridotta dei volumi 1-5 è prevista per fungere da riferimento più generale e/o da libro di testo per studenti; conterrà la maggior parte del materiale in questi volumi, con omesse informazioni più specifiche. L'edizione ridotta manterrà la stessa numerazione dei capitoli dell'edizione completa.

  Il volume 1 può essere visto come un "crossover" dell'intera serie di capitoli, nel senso che contiene le informazioni di base utilizzate in tutti gli altri libri. D'altra parte, i volumi 2-5 possono essere letti indipendentemente l'uno dall'altro. Il volume 1 non è solo un riferimento da utilizzare come guida durante la lettura di altri volumi; può anche fungere da libro di testo universitario o guida allo studio autonomo sulla struttura dei dati (concentrarsi sul capitolo 2) o sulla matematica discreta (concentrarsi sulle sezioni 1.1, 1.2, 1.3.3 e 2.3.4) o sulla programmazione in linguaggio macchina (concentrarsi su sezioni 1.3 e 1.4).

  Questi capitoli sono scritti da un punto di vista diverso rispetto ai libri di programmazione più moderni, cioè non ho cercato di insegnare al lettore come usare il software di qualcun altro. Invece, miravo a insegnare al lettore come scrivere i propri programmi di qualità superiore.

  Il mio obiettivo originale era introdurre i lettori all'avanguardia della ricerca scientifica in ciascuna delle aree di studio in esame. Ma è molto difficile stare al passo con gli affari di un'industria economicamente redditizia; crescita esplosiva informatica reso il mio sogno impossibile. In senso figurato, mi sono trovata sulla riva di un oceano sconfinato contenente decine di migliaia di piccoli risultati ottenuti da decine di migliaia di persone di talento in tutto il mondo. Quindi ho dovuto pormi un nuovo obiettivo: concentrarmi sui metodi "classici" che rimarranno rilevanti per molti decenni e descriverli nel miglior modo possibile al meglio delle mie capacità. In particolare, ho cercato di tracciare la storia di ogni argomento e di gettarvi solide basi. ulteriori sviluppi. Ho cercato di utilizzare una terminologia precisa, coerente con quella usata nelle pubblicazioni moderne, e ho cercato di riferire su tutte le idee conosciute di programmazione sequenziale che si distinguono per la loro semplicità ed eleganza di formulazione.

  Ora qualche parola sul contenuto matematico di questa pubblicazione in più volumi. Il materiale è presentato in modo tale da essere abbastanza accessibile anche a persone con un'istruzione secondaria; potranno visualizzare frammenti più complessi o semplicemente ometterli. Allo stesso tempo, coloro che hanno un'attitudine per la matematica potranno apprendere interessanti metodi matematici legati alla matematica discreta. Tale dualità di presentazione delle informazioni è stata raggiunta, da un lato, assegnando un voto a ciascun esercizio (in modo che il lettore possa distinguere gli esercizi matematicamente complessi da quelli semplici), e dall'altro, grazie a una tale organizzazione delle sezioni in cui i principali risultati matematici sono formulati prima delle dimostrazioni. Le prove si propongono o da svolgere autonomamente come esercizi (le cui risposte sono date in una sezione separata), o da trovare alla fine della sezione.

  Un lettore interessato principalmente alla programmazione piuttosto che alla matematica potrebbe voler interrompere la lettura di una sezione non appena il materiale matematico diventa troppo difficile da comprendere. D'altra parte, il lettore-matematico troverà molto da solo fatti interessanti. Molte pubblicazioni matematiche sull'argomento della programmazione sono state errate, quindi uno degli obiettivi di questo libro è fornire al lettore le basi matematiche corrette per l'argomento della presentazione. E poiché mi considero un matematico, il mio dovere diretto è quello di presentare correttamente (per quanto posso) il materiale da un punto di vista matematico.

  Per leggere la maggior parte del materiale matematico, è sufficiente conoscere la matematica elementare, poiché quasi tutto il resto della teoria è sviluppato qui. Ma a volte ho bisogno di teoremi più profondi nella teoria delle variabili complesse, nella teoria della probabilità, nella teoria dei numeri, ecc. In questi casi, mi riferisco a libri che contengono una presentazione dettagliata di questi argomenti.

  La decisione più difficile che ho dovuto prendere nella preparazione di questi libri è stata come presentare vari metodi. I vantaggi dei diagrammi di flusso e delle descrizioni passo passo degli algoritmi sono ben noti; questi problemi sono discussi nell'articolo "Computer-Drawn Flowcharts" in ACM Communications, vol. 6 (settembre 1963), pagine 555-563. Per descrivere qualsiasi algoritmo informatico è necessario anche un linguaggio formale e preciso. Quindi ho dovuto decidere quale linguaggio usare: uno algebrico come ALGOL o FORTRAN, o uno orientato alla macchina. Probabilmente molti degli informatici di oggi non saranno d'accordo con la mia decisione di usare un linguaggio orientato alla macchina, ma mi sono assicurato che fosse giusta scelta. Ci sono i seguenti motivi per questo.

  a) Un programmatore è fortemente influenzato dal linguaggio in cui sono scritti i programmi. Attualmente, la tendenza prevalente è quella di scegliere i costrutti linguistici più semplici e non ottimali per un computer. E un programmatore che conosce un linguaggio orientato alla macchina tende a usarne di più metodi efficaci e quindi crea programmi migliori.

  b) Tutti i programmi di cui abbiamo bisogno, scritti in un linguaggio orientato alla macchina, con rare eccezioni, saranno di piccole dimensioni. E questo significa che se abbiamo un computer con una potenza di calcolo minima, non avremo problemi nell'utilizzo di tali programmi.

  c) Le lingue di alto livello non sono appropriate per discutere importanti dettagli di basso livello come la comunicazione coroutine, la generazione di numeri casuali, l'aritmetica ad alta precisione e molte altre questioni correlate. uso efficiente memoria.

  d) Chiunque sia seriamente interessato ai computer dovrebbe avere una buona conoscenza del linguaggio macchina, in quanto è alla base del funzionamento di un computer.

  e) Una certa conoscenza del linguaggio macchina è comunque necessaria per comprendere l'output dei programmi riportati in molti degli esempi.

  f) Nuovi linguaggi algebrici entrano e passano di moda circa ogni cinque anni mentre cerco di parlare di "verità eterne".

  D'altra parte, ammetto che scrivere programmi in linguaggi di alto livello e fare il debug di questi programmi è molto più semplice. In effetti, dal 1970, io stesso ho usato raramente il linguaggio macchina di basso livello per i miei programmi, perché i computer moderni hanno una grande quantità di memoria e un'alta velocità. Ma per risolvere molti dei problemi discussi in questo libro, valore più alto ha l'arte della programmazione. Ad esempio, alcuni calcoli combinatori devono essere ripetuti trilioni di volte e risparmieremo circa 11,6 giorni di lavoro riducendo il tempo di calcolo nel ciclo interno di un solo microsecondo. Allo stesso modo, ha senso dedicare uno sforzo extra per scrivere un programma che verrà utilizzato molte volte al giorno su molti computer, soprattutto perché il programma deve essere scritto solo una volta.

  E se si decide di utilizzare un linguaggio orientato alla macchina, quale linguaggio dovrebbe essere preferito? Potrei scegliere la lingua per una particolare macchina X, ma poi quelli che usano un computer diverso lo penseranno questo libro scritto solo per i possessori di computer X. Inoltre, la macchina X probabilmente ne ha molti caratteristiche peculiari, per cui il materiale di questo libro è del tutto inapplicabile, ma è tuttavia necessario enunciarlo. E infine, tra due anni, il produttore della macchina X produrrà la macchina X+1 o 10X, e il computer X non interesserà più a nessuno.

  Per risolvere questo problema, ho provato a sviluppare un computer "perfetto" con molto regole semplici funziona (che puoi imparare in, diciamo, solo un'ora) e molto simile alle macchine reali. Non c'è motivo per uno studente di evitare di apprendere le caratteristiche dei vari computer; dopo aver appreso una lingua, tutte le altre saranno assimilate molto più facilmente. Inoltre, un programmatore serio deve essere preparato al fatto che nel corso del suo lavoro dovrà fare i conti con vari linguaggi macchina. Pertanto, c'è solo uno svantaggio nell'usare una macchina immaginaria: la difficoltà di eseguire programmi scritti per essa. Fortunatamente, questo non è davvero un problema, poiché molti volontari si sono offerti volontari per scrivere macchine fittizie per l'ipotetica macchina. Questi simulatori sono ideali per scopi didattici e sono ancora più facili da utilizzare rispetto a un vero computer.

  Ho cercato di collegarmi ai migliori vecchi articoli su ciascun argomento, oltre a menzionare i lavori più recenti. Quando mi riferisco alle fonti letterarie, ho utilizzato le abbreviazioni standard per i titoli dei periodici, ad eccezione delle riviste più citate, per le quali sono state utilizzate le seguenti abbreviazioni.

  SACM - Comunicazioni dell'Associazione per le macchine informatiche

  JACM - Giornale dell'Associazione per le macchine informatiche

  Socio J. - The Computer Journal (British Computer Society)

  Matematica. Socio - Matematica del calcolo

  AMM - Mensile matematico americano

  SICOMP - Giornale SIAM sull'Informatica

  FOCS - Simposio IEEE sui fondamenti dell'informatica

  SODA - Simposio ACM-SIAM sugli algoritmi discreti

  Simposio STOC - ACM sulla teoria dell'informatica

  Crelle - Journal fur die reine und angewandte Mathematik

  Ad esempio, "CACM 6 (1963), 555-563" indica un riferimento alla rivista menzionata in uno dei paragrafi precedenti di questa prefazione. Ho anche usato l'abbreviazione "CMatA" per riferirmi a Concrete Mathematics, a cui si fa riferimento nell'introduzione alla Sezione 1.2.

  La maggior parte materiale tecnico questi libri rappresentano gli esercizi. Se l'idea di un esercizio non banale non mi apparteneva, allora ho provato a citarne l'autore. I riferimenti alla letteratura sono generalmente riportati nel testo della sezione o nella risposta all'esercizio. Ma in molti casi, gli esercizi si basano su materiale inedito a cui non è possibile fare riferimento.

  Durante i lunghi anni di lavoro su questi libri, molte persone mi hanno aiutato, a cui sono grato dal profondo del cuore. Prima di tutto, voglio esprimere la mia gratitudine a mia moglie Jill) per la sua infinita pazienza, per aver preparato alcune delle illustrazioni e per aiuto costante in ogni cosa. Sono anche grato a Floyd Robert W. per aver dedicato così tanto tempo negli anni '60 al miglioramento e all'approfondimento di questo materiale. Migliaia di altre persone mi hanno anche dato un aiuto prezioso. Ci vorrebbe un altro libro come questo solo per elencare i loro nomi! Molti di loro mi hanno gentilmente concesso di utilizzare i loro vecchi lavori inediti. La mia ricerca al Caltech e alla Stanford University è stata generosamente finanziata dal National fondazione scientifica(National Science Foundation) e il Dipartimento di Ricerca Marina (Office of Naval Research). Addison-Wesley mi è stato di grande aiuto e supporto sin da quando ho iniziato il progetto nel 1962. Mi sembra che per tutte queste persone la migliore gratitudine sia questa pubblicazione. Dimostra che i loro contributi hanno portato a libri in cui spero di aver scritto ciò che si aspettavano.

  Prefazione alla terza edizione

  Dopo aver trascorso dieci anni a sviluppare i sistemi di digitazione METAFONT e TEX, ora posso realizzare il mio sogno di utilizzare questi sistemi per scrivere un libro. L'arte della programmazione. Alla fine, sono stato in grado di inserire il testo completo di questo libro in un personal computer e quindi di ottenerlo versione elettronica, che ti consentirà di apportare in futuro eventuali modifiche alla tecnologia di stampa e visualizzazione sullo schermo. Questo modo di lavorare mi ha dato l'opportunità di apportare letteralmente migliaia di miglioramenti; Ho raggiunto ciò che sognavo da così tanto tempo.

  In questa nuova edizione ho potuto verificare ogni parola del testo, cercando di conservare il vigore giovanile della mia ricerca originaria e al tempo stesso portare una maggiore maturità di giudizio. Sono stati aggiunti dozzine di nuovi esercizi e dozzine di vecchi hanno ricevuto risposte nuove o migliorate.

  Continua così il lavoro sul libro "The Art of Programming". Ecco perché alcune parti di questo libro iniziano con l'icona "In corso di costruzione" (questa è una sorta di scusa per il fatto che le informazioni fornite non sono i dati più recenti). Le mie cartelle sono piene di materiale importante che ho intenzione di includere nell'ultima, gloriosa quarta edizione del volume 1; probabilmente uscirà tra 15 anni. Ma prima devo finire i volumi 4 e 5. Voglio che vengano pubblicati non appena sono pronti per la stampa.

  Gran parte del duro lavoro nella preparazione di questa nuova edizione è stato svolto da Phyllis Winkler e Silvio Levy, che hanno digitato e modificato professionalmente il testo per la seconda edizione, e da Jeffrey Oldham, che ha convertito quasi tutte le illustrazioni originali nel formato METAP0ST. Ho corretto tutti gli errori che i lettori attenti (Barry) hanno riscontrato nella seconda edizione (oltre a errori che, purtroppo, nessuno ha notato), e ho cercato di evitare di introdurre nuovi errori nel nuovo materiale. Tuttavia, ammetto che permangono ancora alcuni difetti e vorrei correggerli il prima possibile. Pertanto, per ogni errore di battitura*, oltre che per un errore relativo alla sostanza del materiale presentato o alle informazioni storiche fornite, pagherò volentieri $ 2,56 a chi lo trova per primo. Nella pagina web il cui indirizzo è riportato sul retro frontespizio, contiene un elenco aggiornato di tutti i bug segnalatimi**.

  * Si riferisce all'originale di questa pubblicazione. - ca. ed.
  ** Errori noti al momento della preparazione dell'edizione russa sono stati corretti. -Approssimativamente ed.

  D.E.K.
  Stanford, California
  aprile 1997

  Il mondo è cambiato negli ultimi vent'anni.
  - Bill Gates (1995)

  
  CAPITOLO 1. CONCETTI FONDAMENTALI ................................................ .................. ... 27
  1.1. ALGORITMI ................................................... ....... 27
  1.2. INTRODUZIONE MATEMATICA ................................................ 37
  1.2.1. Induzione matematica ............................................... 38
  1.2.2. Numeri, poteri e logaritmi .................................. 49
  1.2.3. Somme e prodotti .................................. 56
  1.2.4. Funzioni intere e teoria dei numeri elementari ..... 68
  1.2.5. Permutazioni e fattoriali .................................. 75
  1.2.6. Coefficienti binomiali ................................... 82
  1.2.7. Numeri armonici ................................................... 105
  1.2.8. Numeri di Fibonacci ................................................ 109
  1.2.9. Generazione di funzioni .................................. 118
  1.2.10. Analisi dell'algoritmo .................................. 127
  *1.2.11. Rappresentazioni asintotiche ............................. 138
  *1.2.11.1. Simbolo o .......................................... 138
  *1.2.11.2. La formula della somma di Eulero .................. 143
  *1.2.11.3. Applicazione di formule asintotiche .................. 148
  1.3. MESCOLARE ................................................. ........... 156
  1.3.1. Descrizione del MIX ............................. 156
  1.3.2. Linguaggio assembly per computer MIX ................................ 178
  1.3.3. Domanda di permuta ................................ 198
  1.4. ALCUNE TECNICHE FONDAMENTALI DI PROGRAMMAZIONE.................... 221
  1.4.1. Sottoprogrammi ................................................. 221
  1.4.2. Coroutine ................................................. .. 229
  1.4.3. Programmi per interpreti ................................................ ... 237
  1.4.3.1. Simulatore MIX ................................... 239
  *1.4.3.2. Programmi di instradamento.............................. 248
  1.4.4. Ingresso e uscita ............................................... ............... 251
  1.4.5. Storia e bibliografia ............................... 266

  CAPO 2. STRUTTURE INFORMATIVE ............................................. 271
  2.1. INTRODUZIONE ................................................. ..... 271
  2.2. ELENCHI LINEARI ............................................... .... 277
  2.2.1. Pile, code e mazzi.................................. 277
  2.2.2. Distribuzione sequenziale ............................. 283
  2.2.3. Distribuzione associata ................................ 295
  2.2.4. Elenchi ciclici ................................................ 315
  2.2.5. Due volte liste collegate................................ 322
  2.2.6. Array ed elenchi ortogonali .................................. 341
  2.3. ALBERI................................................. ..... 352
  2.3.1. Attraversare gli alberi binari.................. 362
  2.3.2. Rappresentazione degli alberi come alberi binari........ 380
  2.3.3. Altre rappresentazioni di alberi.............................. 395
  2.3.4. Proprietà matematiche di base degli alberi.................. 410
  2.3.4.1. Alberi liberi ............................. 410
  2.3.4.2. Alberi orientati ............................. 420
  *2.3.4.3. Il lemma dell'albero infinito................... 431
  *2.3.4.4. Enumerazione degli alberi.............................. 435
  2.3.4.5. Lunghezza del percorso ............................. 449
  *2.3.4.6. Storia e bibliografia ............................. 456
  2.3.5. Elenchi e raccolta dei rifiuti .................................. 459
  2.4. STRUTTURE A CONNESSIONE MULTIPLA ................................................ 476
  2.5. ASSEGNAZIONE DINAMICA DELLA MEMORIA ................................................ .. 488
  2.6. STORIA E BIBLIOGRAFIA ................................................ 512

  RISPOSTE AGLI ESERCIZI ................................................ ................................. 521

  APPENDICE A. TABELLE DEI VALORI DI ALCUNE COSTANTI .................................... 683
  AI Costanti di base (decimali) ............................................... 683
  A.2. Costanti di base (ottali) ............................................... 684
  AZ Valori dei numeri armonici, numeri di Bernoulli e numeri di Fibonacci...... 685

  APPENDICE B. SIMBOLI PRINCIPALI ................................................ ................. 687

  INDICE ................................................. ................................ 692
  
  

  27 dicembre 2011 alle 13:32

  L'arte della programmazione?

  • Programmazione

  Mi piace leggere articoli di programmazione che non contengono una singola riga di codice. Tali articoli si sviluppano perfettamente "in profondità" e spesso danno un motivo per guardare cose consolidate da un'angolazione diversa. Pertanto, a rischio di incorrere nell'ira di una certa fetta di pubblico per il mio già stentato karma, ho comunque deciso di pubblicare questo articolo, nella speranza che possa dare a qualcuno non solo spunti di riflessione, ma anche un aiuto per prendere un nuovo sguardo alle loro attività.

  Inizio

  È successo che nell'attuale luogo di lavoro, i programmatori sono lasciati a se stessi. Cioè, ovviamente, codificano a beneficio dell'impresa, ma in modo completamente incontrollabile, fino all'assenza di un banale tester. TOR anche per i programmi "pesanti" raramente supera il volume di tre fogli A4 (di cui uno è le firme di tutti i soggetti coinvolti).

  Le chiamate su problemi software vanno direttamente ai programmatori. Da quando tutto questo è iniziato.
  
  Ho notato che il numero di chiamate al mio collega (una persona che lavora nella specialità e nello specifico in questo posto è diversi anni più lungo di me) è un ordine di grandezza (senza esagerare) superiore al numero di chiamate al mio software. Allo stesso tempo, le chiamate sono generalmente più "pesanti". La prevalenza e la complessità dei nostri prodotti è approssimativamente la stessa.

  Nel processo di comunicazione, mi sono interessato alle opinioni dei colleghi sulla programmazione, dopo di che ho guardato codici sorgente alcuni programmi e tutto è andato a posto.

  Opus sulle personalità creative

  Per vari motivi personali e di lavoro, comunico con persone creative. Fondamentalmente, questi sono musicisti e artisti di varie direzioni. Sono spesso con loro in vari ambienti, dai loro habitat a negozi e caffè.

  A casa, queste persone, di regola, hanno un pasticcio creativo - da un divano schizzato di vernice e pareti squallide a un terribile tipo di elettrodomestici e utensili.

  Le azioni di queste persone hanno un certo vettore, ma i suoi parametri non sono impostati da numeri in virgola mobile, ma dalla direzione "sud-sud-ovest". Questo vale non solo per andare al negozio (l'acquisto di qualcosa sulla lista con queste persone è semplicemente irrealistico), ma per tutto in generale, compresa la creatività.

  Quando lavora su un pezzo, l'artista/musicista di solito parte da questo stesso "vettore sud-sud-ovest" - da un certo stato d'animo, concetto (nato all'interno o emesso dal cliente, questo è in questo caso non così importante). Il risultato finale è, nella maggior parte dei casi, molto vago. In tutta onestà, notiamo che questa è la parte del leone del piacere della creatività: fare come si fa. Questo, in sostanza, è un tentativo di "esprimersi".

  programmatori creativi

  Torniamo alla conversazione sui programmatori. Nel corso della comunicazione, si è scoperto che alcuni colleghi, non senza orgoglio, parlano di se stessi come rappresentanti della "professione creativa". In tal modo, usano davvero un approccio creativo ("vettore sud-ovest-ovest") con praticamente set completo attributi. Di conseguenza, compaiono moduli di connettività completamente eccentrica, classi con una gerarchia "Farò una figura del genere qui", i metodi sono magicamente divisi in "interessanti" (ben progettati, con una chiara gestione degli errori - come implementare la crittografia e protocolli di rete) e "non interessante" (elenchi chilometrici di esportazione dei dati, con molto copia-incolla).

  La gestione degli errori viene eseguita come risulta: qui controlliamo i valori di ritorno e nel file adiacente abbiamo meccanismi di gestione delle eccezioni. Qui utilizziamo i puntatori intelligenti, lì lavoriamo direttamente. E un mucchio di altre cose del genere.

  Di conseguenza opere simili si ottiene un prodotto del tutto imprevedibile. Il problema principale di uno dei nostri sviluppatori è correggere i bug nuova versione comporta costantemente la comparsa di nuovi errori in moduli già apparentemente sottoposti a debug, ed è già irrealistico impedirlo senza una riscrittura completa di tutto e di tutto. È molto difficile mantenere un prodotto del genere - il perfezionamento dei punti più elementari richiede una lunga meditazione sul codice nel tentativo di capire come fare qualcosa in modo che tutto non crolli, e preferibilmente senza copia-incolla della "creatività" esistente ".

  Morale di questa favola

  La programmazione non consiste nell'esprimere te stesso, indipendentemente da ciò che potrebbero affermare i giovani romantici. buon codice- è chiaramente progettato e costruito secondo determinate regole documento. Purtroppo per alcuni, un programmatore è un robot che, a seconda della qualità delle istruzioni in esso contenute, spiega a un altro robot con efficienza variabile cosa vogliono da esso queste masse proteiche. Non c'è posto per la creatività nella programmazione: dalla denominazione di file e variabili ai modelli, tutto è soggetto a una logica chiara e ha la massima efficienza. Di conseguenza, per questa efficienza, il programmatore riceve non solo i soldi del datore di lavoro, ma anche la tranquillità quando accompagna il prodotto e un senso di controllo sulla situazione in caso di problemi con il programma.

  Anche se al programmatore non viene fornito un TOR ben scritto, è necessario comprendere chiaramente cosa accadrà alla fine. Se c'è la possibilità che ciò che è scritto debba essere profondamente modificato, tanto meglio: i compiti di scrittura del software con la probabilità di essere pesantemente modificato sono molto eccitanti e per nulla facili.

  Ebbene, in conclusione, la frase di Steve McConnell - "Scrivi il codice come se fosse accompagnato da uno psicopatico violento che sa dove abiti". E uno psicopatico probabilmente si arrabbierà molto se si spaccherà la testa per la mancanza di logica e di ordine.

  Annotazione al libro L'arte della programmazione, volumi 1-3:
  Molte persone sanno che la programmazione non è solo un complesso lavoro mentale, ma anche un processo creativo. L'autore di questo libro, Donald Erwin Knuth, è professore alla Stanford University e ha scritto molti libri di matematica e informatica. La famosa opera "The Art of Programming", il cui primo volume è stato pubblicato più di 20 anni fa, ha portato fama allo scienziato. Nel suo libro, Donald Knuth spiega e analizza gli algoritmi di base utilizzati nella programmazione. Questa è la terza edizione dell'acclamata serie di libri L'arte della programmazione.

  Questa versione contiene 3 volumi di The Art of Programming:

  L'arte della programmazione. Volume 1. Algoritmi di base.
  L'arte della programmazione. Volume 2. Algoritmi derivati.
  L'arte della programmazione. Volume 3. Ordinamento e ricerca.

  Il primo volume della collana di libri L'arte della programmazione inizia con una descrizione dei concetti e dei metodi di base della programmazione. L'autore si sofferma quindi sulla considerazione delle strutture informative: la rappresentazione delle informazioni all'interno di un computer, le relazioni strutturali tra gli elementi dei dati e come lavoro efficace con loro. Vengono forniti esempi di applicazioni elementari per metodi di simulazione, calcoli simbolici, metodi numerici e metodi di sviluppo software. Rispetto all'edizione precedente sono stati aggiunti decine di algoritmi semplici, ma allo stesso tempo molto importanti. Secondo tendenze moderne ricerca, anche la sezione di introduzione matematica è stata sostanzialmente rivista.

  Il secondo volume presenta la teoria degli algoritmi derivati. Capitoli separati contengono una descrizione del processo di generazione di numeri casuali e dei modi per utilizzarli in un ambiente informatico. L'autore considera applicati i concetti fondamentali della teoria della probabilità sistemi informatici, fornendo al lettore algoritmi già pronti programmi per computer. Merita un'attenzione speciale nuovo metodo l'autore della generazione di numeri casuali e una descrizione di algoritmi per il calcolo delle serie di potenze formali.

  La terza edizione del terzo volume contiene recensione completa algoritmi classici di ordinamento e ricerca. Le informazioni presentate in esso integrano la discussione sulle strutture dei dati fornita nel primo volume. L'autore considera i principi della creazione di database grandi e piccoli, nonché la memoria interna ed esterna. Il libro contiene una selezione di algoritmi informatici accuratamente testati e ne analizza l'efficacia. Inoltre, una sezione speciale è dedicata ai metodi di ordinamento ottimale e alla descrizione della nuova teoria della permutazione e dell'hashing universale.

  Nome: L'arte della programmazione - Volume 1.

  Il primo volume della collana di libri L'arte della programmazione inizia con una descrizione dei concetti e dei metodi di base della programmazione. Quindi l'autore procede a considerare le strutture informative, la rappresentazione delle informazioni all'interno di un computer, le relazioni strutturali tra gli elementi dei dati e come lavorare efficacemente con essi. Per i metodi di simulazione, calcoli simbolici, metodi numerici, metodi di sviluppo software, vengono forniti esempi di applicazioni elementari. Rispetto all'edizione precedente sono stati aggiunti decine di algoritmi semplici, ma allo stesso tempo molto importanti. In accordo con le moderne tendenze della ricerca, la sezione dell'introduzione matematica è stata sostanzialmente rivista.

  Ogni libro ha il suo destino. Alcuni appaiono impercettibilmente e altrettanto impercettibilmente scompaiono nel corso del tempo, ricoperti di polvere sugli scaffali delle biblioteche. Altri in un certo periodo sono richiesti da una ristretta cerchia di specialisti, fino a quando nuovi libri di consultazione non li sostituiranno. Altri ancora, elevandosi al di sopra del tempo, esercitano una potente influenza sullo sviluppo tecnologico della società. Non sono molti i libri che rientrano in quest'ultima categoria. Il loro rilascio è sempre una vacanza. Passano gli anni, le tecnologie cambiano, ma le nuove generazioni rileggono le loro pagine con costante interesse. È a questi libri che appartiene il lavoro in più volumi del famoso scienziato americano Donald Erwin Knuth "The Art of Programming" offerto al lettore.
  Qual è il successo di Art of Programming di D. E. Knuth:
  In primo luogo, questo libro è un eccellente libro di testo per scrivere e analizzare algoritmi informatici. Le sue sezioni possono essere incluse in molti corsi universitari su tecnologie di programmazione, teoria degli algoritmi e matematica discreta. Il libro può essere studiato anche da studenti delle scuole superiori che hanno familiarità con le basi della programmazione. Come linguaggio principale per la scrittura di algoritmi, l'autore ha scelto il linguaggio delle istruzioni macchina dell'ipotetico computer universale MIX. Ciò consente di creare programmi ottimali, tenendo conto delle caratteristiche dei computer. Trasferire programmi MIX su computer reali o riscriverli in linguaggi di alto livello non è difficile. La logica di come funzionano i programmi è quasi sempre spiegata con semplici diagrammi di flusso.
  In secondo luogo, il materiale accuratamente selezionato incluso nel libro include le principali classi fondamentali di algoritmi, che in una forma o nell'altra si incontrano più spesso nella pratica della programmazione.
  In terzo luogo, un fattore importante per il successo del libro di D. E. Knuth è la presentazione enciclopedica. Il professor Knuth si distingue per la sua capacità unica di tracciare un problema dal contesto storico della sua origine allo stato attuale. Numerosi riferimenti alle opere di antichi maestri (fino ai tempi dell'antichità), racchiusi in un contesto moderno, creano nel lettore uno speciale senso di coinvolgimento nello sviluppo storico delle idee e dei metodi scientifici.

  Download gratuito e-libro in formato conveniente, guarda e leggi:
  Scarica il libro The Art of Programming - Volume 1 - Knut D. E. - fileskachat.com, download veloce e gratuito.

  Scarica djvu
  Di seguito puoi acquistare questo libro al miglior prezzo scontato con consegna in tutta la Russia.