The Stanford GraphBase: A Platform for Combinatorial Computing [Romanian]

Original in English by Donald E. Knuth

sgb

Stanford GraphBase: o platformă pentru calcul combinatorial

de Donald E. Knuth (New York: ACM Press, 1994), pp. 576 VIII 
co-publicat de Editura Addison-Wesley. 
ISBN 0-201-54275-7 (Ediţie originală cu copertă groasă) 
ISBN 0-321-60632-9 (Ediţie cu copertă moale, publicată în 2009)

Aceasta carte premiată demonstrează arta de programare gramaticală cu mai mult de 30 de exemple. Fiecare exemplu este un eseu programatic: o scurtă poveste care poate fi citită şi placută de oameni atît de uşor, deoarece poate fi citită şi interpretată de maşini. Programele conţin de explicaţii contemporane a multor algoritmi importanţi şi structuri de date. Ele definesc, de asemenea, un cîmp de lucru pentru calcul combinatorial, şi seturi standarte de date care pot fi utilizate pentru testele de evaluare a metodelor concurente, precum şi programele demonstrative şi jocuri care utilizează datele.

Sute de programe de exemplu, care utilizează Stanford GraphBase va fi distribuite în format electronic ca suplimente pentru volumul 4 de Arta programării a calculatoarelor (The Art of Computer Programming ) în momentul în care volumul este disponibil, deoarece Knuth va folosi Stanford GraphBase pentru multe dintre exemplele din această carte.

Subiecte principale includ:

  • contribuţii la înţelegerea noastră de algoritmi şi structuri de date semnificative

  • instrumentele standarte de evaluare a algoritmilor combinatoriali

  • stil de programare mai clarşi mai practic

  • probleme pentru cititorii care caută metode ce sunt chiar mai bune

Disponibil de la editori,  ACM Press sau Addison-Wesley Publishing Company.

Sursele domeniilor publice pentru toate programele şi datele Stanford GraphBase sunt disponibile gratuit. Ele pot fi obţinute, de exemplu, prin ftp anonim de la surse generale (master sources) pe f în directorul ~ f. Programele sunt extrem de portabile şi au fost instalate pe o mare varietate de calculatoare şi sisteme de operare.

Descarcărcaţi  sgb-words.txt, the 5757 five-letter words of English

Descarcărcaţi fişier contiguous, adiacenţe între Statele Unite contiguă şi DC - usa.dat, United States and DC

Exemple de grafice din TAOCP:

Alte exemple de grafice: knight3.gb (din lucrarea “aventurile unui cavaler lung şi slab'') (şi o imprimare beată de vorbă a textului – verbose text printout)

Această carte a fost citată de către Asociaţia Editorilor americani ca cea mai bună nouă carte de informatică, 1994.

Există un articol frumos cu lăudare on-line în depozitul algoritmului lui Stony Brook – Stony Brook Algorithm Repository.

border

Probleme provocatoare

Cartea conţine mai multe probleme încă nerezolvate, cu care sper că cititorii vor face progrese semnificative. Una dintre problemele cele mai amuzante se bazează cu sezonul de fotbal 1990: care este cel mai mare scor cu care Stanford poate birui Harvard printr-un lanţ simplu de rezultatele din acest an? Cea mai bună soluţie mea a fost 2279, dar Buel Chandler a îmbunătăţit-o, şi el a avut 2448 prin aplicarea ideilor de programare genetică la unele dintre algoritmii mei. Priviţi pagina minunată lui Chandler despre fotbal genetic pentru informaţii suplimentare – Chandler's cool page about genetic football.

News flash, 25 Noiembrie 2001: Mark Cooke tocmai a raportat despre descoperirea unei secvenţe prin care Stanford a biruit cu 2473 de puncte pe Harvard, împreună cu o limită superioară de potrivire (găsită în februarie 2002)! De asemenea, Harvard a biruit Stanford cu 2358; Unversitatea de stat din Pennsilvania a biuruit Columbia cu 2542 (şi acesta este scor maxim pentru toate perechile de echipe). Detalii vor urma…

border

ANUNT IMPORTANT

Eroare jenantă a micşorării a unităţii a fost corectată în cadrul programelor care creează graficele aleatorii (ra şi a). Când făceam această schimbare, am decis că era mai bine să conformez documentaţia decât să rămân în totalitate compatibil cu trecutul. Graficul care acum se numeşte ran), şi care merită în mod corespunzător acest nume, este acelaşi ca şi grafic cel utilizat fi numit ran (n) — cu excepţia cazului în care a=b, în cazul în care programul vechi a fost corect şi nici o schimbare nu a fost necesară.

Vă rugăm să faceţi actualizarea versiunii noi ale programelor sursă SGB, în cazul în care copia este datată mai devreme de iulie 1999. (Am facut, de asemenea, corecţii minore în mai anului 2007 — valoarasă modificare, dar nu esenţială. Totuşi, să afectaţi t şi jt în moduri mici.).

"Defecte" în fişiere de date

Deoarece fişierele de date au fost pregătite manual, acestea sunt supuse de erori umane. Acestea nu ar trebui să fie, prin urmare, considerate a fi surse clare de fapte, care sunt corectabile ca un articol în Wikipedia. Acestea sunt destinate pur şi simplu, ca exemplele întotdeauna îngeţate de tipice date, care sunt mai mult sau mai puţin exacte.

În special, recent am aflat că am uitat să includ o legătură între Fantine şi fiica ei copil Cosette, când am rezumat asemănările dintre personajele “Mizerabililelor” în fişierul de date jean.dat. Fantine şi Cosette apar împreună în capitolul 1.4.1 (şi apoi, desigur, – vai – ei nu se vor vedea unu pe altul din nou). La capitolul recitit, am văzut că dosarul meu ar fi avut "/" în loc de linia "/". Cu toate acestea, eu nu vor actualiza fişierul jean.dat, deoarece este "corect prin definiţie." 

Erată

O listă de corecţii a tuturor modificărilor aduse la primele tipărituri din această carte pot fi gasite aici – here.

Aici este o listă a tuturor unităţilor care au fost culese pana acum din 2009. O steluţă (*) marchează erori tehnice semnificative care nu sunt doar de tipar:

Voi depune cu recunoştinţă 0x$1.00 (2.56 dolari), în contul primei persoane care găseşte şi raportează orice altceva ce rămâne din punct de vedere tehnic, istoric, typografical, sau politic incorect. Vă rugăm să trimiteţi propunerile de corectură la sgb@cs.stanford.edu, sau trimiteţi-mi mail de melc lui prof. D. Knuth, Catedra de Calculatoare, Gates Building 4B, Stanford University, Stanford, CA 94305-9045 USA.

VA RUGAM SA NU TRIMITEŢI EMAIL LA SGB CU EXCEPŢIA RAPORTURILOR DESPRE ERORI! Şi dacă veţi-i raporta despre eroare prin e-mail, vă rugăm să nu includeţi echipamentele de orice fel, mesajul dvs. ar trebui să fie uşor de citit pe sisteme de operare brand-X pentru toate valorile de X.

ok ok