UNIVERSITATEA TEHNIC GHEORGHE ASACHI DIN IAIFacultatea de Construcii i InstalaiiProgram de studii de master Inginerie Structural

Personaliti cu contribuii semnificative n evoluia instrumentelor de calcul automat i a algoritmicii

noiembrie 2013Personaliti cu contribuii semnificative n evoluia instrumentelor de calcul automat i a algoritmicii

1

Informatica reprezint tiina care se ocupa cu prelucrarea informaiilor cu ajutorul computerelor. Bazele acestei tiine s-au dezvoltat cu mult nainte de aparitia mijloacelor moderne de calcul automat, n secolul XX.Uncomputer este o main care prelucreaz informaii (date) pe baza unui program (o list de instruciuni).Cel mai vechi instrument cunoscut pentru utilizarea n calcul esteabacul. Se crede c a fost inventat nBabiloncirca n anul 2400 .Hr.. Prima oar era folosit prin trasarea unor linii n nisip cu pietricele. Acesta a fost probabil primul computer i cel mai avansat sistem de calcul cunoscut din aceea perioad, precednd metoda elen cu 2000 ani. Abacul este o tbli dreptunghiular, folosit de oameni n antichitate pentru efectuarea calculelor. Abace cu un design modern sunt nc folosite astzi ca instrumente de calcul.Mecanismul de la Antikytheraeste considerat a fi cel mai vechi computer analogic mecanic cunoscut. A fost proiectat pentru a calcula poziiile astronomice ale astrelor. A fost descoperit n 1901 ntr-o epav n largul insulei grecetiAntikythera, ntre Kythera i Creta. A fost datat n perioada circa100 .Hr.. Artefacte tehnologice de complexitate similar nu au mai aprut pn nsecolul al XIV-lea, atunci cnd ceasurile mecanice astronomice au aprut nEuropa.nsecolul al III-lead.Hr. a aprut nChina anticCarul ndreptat spre sud. Acest Car era un mic vehicul cu dou roi, care a funcionat ca obusol. Avea un indicator care ntotdeauna arta sudul, indiferent de poziia n care era pus Carul. De obicei, indicatorul era o ppu sau o figur cu un bra ntins. Se presupune c era folosit pentru navigaie, dar poate avea, de asemenea, i alte scopuri. Este primul mecanism cunoscut cu roi dinate care a fost folosit mai trziu n calculatoarele analogice. Chinezii au inventat i un abac mai sofisticat n jurul secolului al II-lea .Hr., cunoscut sub numele de abac chinezesc.Dispozitivele mecanice analogice de calcul au aprut din nou o mie de ani mai trziu, n lumea islamic medieval. Exemple de dispozitive din aceasta perioada includ: equatoriumul lui Arzachel (equatoriumul este un instrument astronomic de calcul a poziiilor atrilor) sau astrolabul luiAl-Biruni(astrolabul este un instrument astronomic istoric folosit de astronomi, navigatori, i astrologi).Inginerii care puteau fi programate pentru a reda diferite musulmani au construit o serie de automate, inclusiv unele automate muzicale, modele muzicale. Aceste dispozitive au fost dezvoltate de ctre fraiiBanu Musai de matematicienii musulmaniAl-Jazari, care au fcut progrese importante n criptografie, cum ar fi dezvoltarea criptanalizei a analizei frecvenelor de ctre Alkindus. (Criptografiareprezint o ramur a matematicii care se ocup cu securizarea informaiei precum i cu autentificarea i restricionarea accesului ntr-un sistem informatic. Criptanaliza este studiul metodelor de obinere a nelesului informaiilor criptate, fr a avea acces la informaia secret necesar n mod normal pentru aceasta. De regul, aceasta implic gsirea unei chei secrete. ntr-un limbaj non-tehnic, aceasta este practica spargerii codurilor.)Dup ceJohn Napiera descoperit nsecolul al XVII-lealogaritmiicare sunt folosii n scopuri computaionale, a urmat o perioad de progres considerabil n care inventatori i oameni de tiin au fabricat unelte de calcul.n1623,Wilhelm Schickarda proiectat o main de calcul, dar a abandonat proiectul, deoarece cldirea n care se afla prototipul a fost distrus de un incendiu n 1624.n jurul anului1640,Blaise Pascal, un cunoscut matematician francez, a construit primul dispozitiv mecanic bazat pe un design descris de matematicianul grecHeron din Alexandria.Apoi, n1672,Gottfried Wilhelm Leibniza inventatSocotitorul n treptecare a fost finalizat n1694. Nici unul dintre aceste dispozitive timpurii de calcul nu au fost calculatoare n sensul modern al cuvntului, i a fost nevoie de un progres considerabil n matematic nainte ca primele calculatoare moderne s poat fi concepute.nsecolul al VII-lea, matematicianul indianBrahmaguptaa dat prima explicaie a sistemului de numeraie hinduso-arab i utilizarea luizeroatt ca substituent ct i cacifr zecimal. (Un substituent este un element care poate nlocui un alt element, cu care are proprieti asemntoare.)Aproximativ n jurul anului825, matematicianul persanAl-Khwarizmia scris o carte, despre calculul cu cifre hinduse, care a dus la rspndirea sistemului indian de numeraie nOrientul Mijlociui apoi n Europa. n jurul secolului al XII-lea a existat o traducere a acestei cri scris nlimba latinnumitAlgoritmi de numero Indorum. Aceste cri prezentau concepte noi pentru efectuarea unei serii de pai n scopul realizrii unei sarcini. De aici a derivat termenul algoritm. (Un algoritm nseamn n matematic i informatic o metod sau o procedur de calcul, alctuit din paii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementeaz n mod concret prin programarea adecvat a unui calculator, sau a mai multora).n jurul secolului al III-a lea .Hr., matematicianul indianPingalaa descoperit sistemul binar de numeraie. n acest sistem, folosit i astzi de toate computerele moderne, o secven de unu i zero poate reprezenta orice numr.n1703,Gottfried Leibnitza dezvoltat logica ntr-un sens matematic formal, n scrierile sale despre sistemul de numeraie binar. n sistemul su, valorile unu i zero reprezint valorile adevrat i fals (true i false) sau pornit/oprit (on/off). Dar a fost nevoie de mai bine de un secol pentru ca George Boole s publice algebra boolean n 1854 cu un sistem complet care permite proceselor de calcul s fie modelate matematic. (Algebra boolean este o algebr format din: elementele {0,1}; dou operaii binare numite SAU i SI, notate simbolic cu + sau i sau U; i o operaie unar numit NU (negaie), notat simbolic 0 sau O.n aceast perioad, au fost inventate primele dispozitive mecanice pe baza unui model binar. Revoluia industrial a dus la evoluia mecanizrii a numeroase sarcini, printre care i esutul. Cu ajutorulcartelelorperforate funciona rzboiul de esut al luiJoseph Marie Jacquardn1801, unde o gaur n cartel reprezenta binarul unu iar lipsa gurii binarul zero. Rzboiul lui Jacquard era departe de a fi un computer, dar a demonstrat c mainile pot funciona pe baza sistemelor binare.Dezvoltnd o idee anterioar a luiJacques de Vaucanson, Jacquard i doteaz rzboiul de esut cu un ingenios mecanism care selecta difereniat firele de urzeal dup un "program" nscris pe plcue perforate (inventatorul cartelelor perforate fiindBasile Bouchon). Cartela perforat este o bucat de hrtie rigid care conine informaii digitale reprezentate de prezena sau absena de guri n poziii predefinite.n perioada1833-1835,Charles Babbagea inventat maina analitic, care se baza direct pe cartelele perforate pentru programare ale lui Joseph Marie Jacquard. Aceast main era alimentat de un motor cu aburi. Babbage nu a reuit s o construiasc pn la moartea sa, din cauza limitrilor tehnologice ale vremii. Cu toate acestea, o main construit n1991dup schiele sale s-a dovedit a funciona perfect.O invenie important au reprezentat-o roile dinate, ca nlocuitor al mrgelelor de la abac.

Alan Turinga descris n1936un model matematic care astzi i poart numele i care rezum funcionarea unei maini de calcul programabile (Maina Turing). Pn n secolul trecut, calculatoarele mecanice, mainile contabile i casele de marcat erau reproiectate n sensul utilizrii motoarelor electrice, poziia roilor dinate reprezentnd starea unei variabile. Din anii 1930, mai multe companii (de exemplu Friden, Marchant Calculator i Monroe) au realizat calculatoare mecanice de birou capabile s efectueze adunri, scderi, nmuliri i mpriri. n 1948 a aprut Curta, un mic calculator mecanic, portabil.Primul calculator de birou electronic a fost calculatorul britanic Anita Mk.VII (1958), care folosea pentru afiaj tuburi Nixie i 177 de tiratroane miniaturizate (tiratronul este un tub electronic cu trei electrozi). n1963, Friden a introdus mainaEC-130cu patru funcii care costa 2200 de dolari i era proiectat numai pe baza tranzistoarelor. EC-130 avea o capacitate de 13 digii i un afiaj pe un tub catodic de 130 mm. n1965,Laboratoarele Wangau produsLOCI-2, un calculator de birou care avea o capacitate de 10 digii i utiliza un afiaj cu tuburi Nixi. LOCI-2 putea calcula i logaritmi.Calculatorul digital a aprut datorit dezvoltrii n perioada dinainte de i dup cel de-al doilea rzboi mondial, cnd componentele electronice (la acea vreme, relee, rezistoare, condensatoare, bobine, i tuburi electronice) au nlocuit echivalentele lor mecanice. Prin urmare calculul digital a nlocuit calculul analogic. n perioada celui de-al doilea rzboi mondial, au existat trei direcii paralele de dezvoltare a tehnologiei calculatoarelor: 1. Z3 (Zuse), 2. calculatorulAtanasoffBerryi 3.calculatoareleColossusiENIAC, acestea au fost construite manual cu ajutorul circuitelor ce conineau relee sau tuburi electronice, i adesea foloseau cartelele sau benzile perforate ca dispozitiv de intrare i ca mediu de stocare. Aceste maini nu semnau cu calculatoarele moderne numerice. Niciun moment nu este considerat unanim a fi momentul naterii calculatoarelor numerice. Pentru ca o main de calcul s fie (considerat) un calculator universal, trebuie s existe un mecanism convenabil de citire-scriere, cum ar fi banda perforat. Pe baza modelului teoretic al mainii universale de calcul a lui Alan Turing, John von Neumann a definit o arhitectur ce utilizeaz aceeai memorie att pentru stocarea programelor ct i a datelor: practic toate calculatoarele moderne utilizeaz aceast arhitectur (vulnerabil la virui).n19431945ENIAC(Electronic Numerical Integrator And Computer) a fost construit nStatele Unite, el a fost primul calculator electronic generic care efectua pe secund 5000 de operaii de adunare i scdere, fiind de o mie de ori mai rapid dect alte maini care efectuau aceste operaii. Era un calculator numeric Turing-complet, capabil de a fi reprogramat pentru a rezolva o gam larg de probleme de calcul. Maina cntrea 30 de tone i avea peste 18.000 de tuburi. Una dintre marile realizri inginereti ale mainii era minimizarea arderii tuburilor, problem comun la acea vreme. Maina a fost utilizat aproape permanent de-a lungul urmtorilor zece ani.Primul calculator numeric cu program stocat (considerate Maini von Neumann din prima generaie) poate fi consideratEDVAC(a fost proiectat dar care nu a funcionat) sau Baby sauSmall-Scale Experimental Machine(care a i funcionat,1948).n iunie1951,UNIVAC I(Universal Automatic Computer) a fost primul calculator vndut unei instituii oficiale (Biroul de Recensmnt al Statelor Unite).n1952,IBMa anunat public maina electronic de prelucrare a datelorIBM 701i primul calculator IBM mainframe.Primul limbaj de programare generic de nivel nalt care a fost implementat vreodat,Fortran, era dezvoltat i la IBM pentru 704 n19551956i a fost lansat la nceputul lui1957.IBMa fabricat n1954un calculator mai mic i mai ieftin care s-a dovedit foarte popular, IBM 650, care cntrea peste 900 kg.A doua generaie: calculatoarele cu tranzistoare au nceput s fie produse dup1953. Tranzistoarele au fost inventate n1947i au nlocuit tuburile electronice. Primul computer cu tranzistoare a aprut laUniversitatea din Manchester.A treia i a patra generaie de calculatoare se bazeaz pe invenia circuitului integrat de ctre Jack St. Clair Kilby (i Robert Noyce). Circuitul integrat a dus la inventarea microprocesorului, de ctreTed Hoff, Federico Faggin i Stanley Mazor de laIntel.PotrivitTOP500din noiembrie2010, cel mai puternic computer din lume este calculatorul chinezescTianhe-I(sau TH1) cu o vitez de 2,566 petaFLOPS adic 2,566x1015 operaii pe secund.Astzi computerele nu sunt doar maini de prelucrat informaii, ci i dispozitive care faciliteaz comunicarea respectivelor informaii ntre doi sau mai muli utilizatori, de exemplu sub form de numere, text, imagini, sunet sau video.n principiu, orice computer care deine un anumit set minimum de funcii (altfel spus, care poate emula o main Turing) poate ndeplini funciile oricrui alt asemenea computer, indiferent c este vorba de un Personal Digital Assistant sau PDA sau de un supercomputer . Aceast versatilitate a condus la folosirea computerelor cu arhitecturi asemntoare pentru cele mai diverse activiti, de la calculul salarizrii personalului unei companii pn la controlul roboilor industriali sau medicali (calculatoare universale).Unalgoritm(cuvntul are la origine numele matematicianului persanAl-Khwarizmi) nseamn nmatematiciinformatico metod sau o procedur de calcul, alctuit din paii elementari necesari pentru rezolvarea unei probleme sau categorii de probleme. De obicei algoritmii se implementeaz n mod concret prin programarea adecvat a unui calculator, sau a mai multora. Din diverse motive exist i algoritmi nc neimplementai, teoretici.Algoritmul este noiunea fundamental a informaticii. Totul este construit n jurul algoritmilor (i astructurilor de date, cum ar filistelesaugrafurile).Cteva exemple de algoritmi:-algoritmul de construcie a unui automobil (urmrind procedeele i schiele de fabricaie);-algoritmul de folosire a unei maini-unelte (citind manualul de folosire);-algoritmul de explorare a unui labirint n vederea gsirii unei ieiri (una din soluii: se ine o mn pe perete i se merge fr a o dezlipi de acesta).-algoritmul (ordinea operaiilor, sau "check list") la decolarea unui turbojet. Acest algoritm desigur nu ine n mod direct de domeniul matematicii sau informaticii.Cele mai importante proprieti ale unui algoritm, ndeplinite de diverii algoritmi ntr-o msur mai mare sau mai mic, sunt urmtoarele:Corectitudinea - este proprietatea algoritmului de a furniza o soluie corect a problemei date. n acest sens este de dorit ca algoritmii s se bazeze pe fapte i relaii matematice demonstrabile.Caracterul univoc sau determinist - plecnd de la un set de date iniial anume, rezultatul este unic, sau altfel spus, repetarea execuiei algoritmului duce ntotdeauna la aceleai rezultate.Generalitatea - este proprietatea unui algoritm de a rezolva oclassau categorie de probleme, i nu doar o singur problem particular. Claritatea - proprietatea algoritmului de a descrie cu exactitate i fr ambiguiti paii care trebuiesc parcuri n rezolvarea problemei.Verificabilitatea - acea proprietate a algoritmilor care permite ca fiecare pas s poat fi verificat ntr-un timp rezonabil de ctre om, folosind mijloace de validare de ncredere.Optimalitatea - proprietatea unui algoritm de a se termina dup un numr minim de pai. De exemplu, dac se cere s se calculeze suma primelor 'n' numere naturale, se poate aplica formula de calcul, i astfel algoritmul se termin ntr-un singur pas, pe cnd dac am aduna toate numerele de la 1 la n, el s-ar termina abia nnpai, i deci nu ar fi optim. nteoria complexitiise folosetenotaia O(n).Finitudinea - este proprietatea algoritmului de a se termina ntr-un numr finit de pai. Exist i algoritmi care nu se termin ntr-un numr mrginit de pai, dar acetia se numesc "metode algoritmice".Eficiena - este proprietatea unui algoritm de a se termina nu numai ntr-un numr finit, ci i "rezonabil" de pai, chiar dac acesta nu este cel mai mic posibil (nu este optim). Algorimul este ineficient i dac rezultatul se obine ntr-un timp mai lung dect cel dorit sau permis.Existena unei intrri (datele de prelucrat). ntruct operatorii se aplic unui operand (sau i mai multor operanzi deodat), este de neconceput un algoritm fr niciun operand. Intrrile permise formeaz mpreun un set (mulime) specific de obiecte sau valori, care se numete "domeniul" algoritmului.Existena unei ieiri (rezultatele). Este de neconceput un algoritm care nu are nicio ieire, deoarece n acest caz intr n discuie nsi utilitatea sa.n funcie de modul deimplementare, un algoritm poate fi:-recursiv- face uz de sine nsui, n mod repetat-iterativ (repetitiv)-serialsauparalel-deterministsaualeatoriu(probabilistic)-exact sau aproximativ

Charles Antony Richard Hoare(n. 11 ianuarie 1934, Colombo, Sri Lanka) este un informatician britanic, celebru pentru inventarea, n 1960, a algoritmului de sortare quicksort, unul dintre cei mai eficieni i mai utilizai algoritmi de sortare. De asemenea, a dezvoltat logica hoare pentru verificarea corectitudinii programelor, i limbajul formal CSP, folosit pentru descrierea interaciunilor proceselor concurente (de exemplu, problema filosofilor). A primit, n 1980, Premiul Turing din partea ACM. Kenneth Eugene Iverson(n.17 decembrie 1920, Camrose, Alberta, Canada - d. 19 octombrie 2004, Toronto, Canada) a fost un informatician canadian, celebru pentru dezvoltarea limbajul de programare APL n 1957. A primit Premiul Turing din partea ACM n 1979 pentru contribuiile aduse n domeniile notaiei matematice i teoriei limbajelor de programare.

Edsger Wybe Dijkstra(n. 11 mai 1930, Rotterdam - d. 6 august 2002, Nuenen) a fost un informatician olandez. i-a luat licena n fizica teoretica la Universitatea din Leiden. Dup o perioad de lucru ca cercettor la Burroughs Corporation, a lucrat la Universitatea Tehnica din Eindhoven i mai apoi la Universitatea din Austria, Texas, de unde s-a retras n 2000.Dijkstra a rmas celebru pentru algoritmul drumului minim ntr-un graf, algoritm care-i poart numele. Este un algoritm care calculeaza drumurile minime de la un nod al unui graf la toate celelalte noduri din graf .Grafurile pe care poate lucra algoritmul lui Dijkstra sunt, in general, ponderate si orientate arcele sunt orientate de la un nod la alt nod (nu se poate merge si invers) si au un anumit cost de care se va tine seama in aflarea drumului minim.Daca graful este neponderat (arcele nu au costuri asociate) atunci drum minim intre doua noduri se considera drumul alcatuit din numar minim de arce .Pentru a gasi drumul minim de la un nod X la un nod Y se poate aplica o cautare prin cuprindere pornind de la nodul X prima aparitie a lui Y in coada algoritmului de cautare prin cuprindere presupune existenta unui drum cu numar minim de arce de la X la Y, care poate fi reconstituit. Pe un astfel de graf se poate aplica si algoritmul lui Dijkstra, daca transformam in prealabil graful intr-unul ponderat, asociind fiecarui arc acelasi cost (de exemplu, costul 1).Drumul de cost minim intre doua noduri obtinut in urma aplicarii algoritmului lui Dijkstra va avea si numar minim de arce din moment ce toate arcele au acelasi cost.Algoritmul lui Dijkstra functioneaza atat pe grafuri conexe cat si pe grafuri neconexe. Un graf este conex daca din orice nod al sau se poate ajunge in orice alt nod. In cazul grafurilor orientate, pentru ca intre doua noduri sa existe un drum in graf, nu este suficient sa existe o succesiune de arce intre cele doua noduri, ci arcele trebuie sa fie si orientate in sensul corespunzator. Un drum intr-un graf orientat trebuie sa parcurga numai arce orientate identic, de la nodul sursa pana la nodul destinatie. Daca nu exista nici un drum de la nodul de start la un alt nod al grafului atunci algoritmul lui Dijkstra va raporta existenta unui drum de lungime infinita intre ele acest rezultat indica, de fapt, lipsa oricarui drum intre cele doua noduri Date de intrare: Algoritmul porneste de la un graf orientat si ponderat cu N noduri De asemenea, e nevoie de un nod de start apartinand grafului acesta este nodul de la care se doreste aflarea drumurilor minime pana la celelalte noduri din graf Date de iesire: Rezultatul algoritmului se prezinta sub forma unui tablou D cu N intrari, continand distantele minime de la nodul de start la toate celelalte noduri din graf De asemenea, tot ca rezultat se poate obtine si arborele drumurilor minime (in cazul in care ne intereseaza nu numai lungimile minime ale drumurilor, ci si drumurile propriu-zise) acesta este un arbore generalizat care se va obtine sub forma unui tablou T cu N intrari (implementarea cu indicatori spre parinte) Fie X nodul de start acesta se marcheaza ca vizitat Ideea gasirii drumului minim de la X la un un alt nod este cautarea treptata: se presupune ca drumul minim este alcatuit dintr-un singur arc (arcul direct intre X si nodul tinta, care poate sa nu existe, costul sau fiind infinit in acest caz), apoi se cauta drumuri mai scurte alcatuite din 2 arce, apoi din 3, etc. un drum minim nu poate avea mai mult de N-1 arce, deci algoritmul are N-1 pasi (al N-lea este banal) Dupa pasul k (1 k N-1), tabloul D va contine lungimile drumurilor minime de la nodul X la celelalte noduri, toate aceste drumuri fiind alcatuite din maxim k arce Astfel, D[Y] = L dupa pasul k inseamna ca de la X la Y exista un drum minim de lungime L alcatuit din maxim k arce Deci, dupa pasul k, au fost gasite numai drumurile minime alcatuite din maxim k arce abia la finalul algoritmului (dupa pasul N-1) drumurile minime obtinute sunt definitive, ele fiind drumuri minime alcatuite din maxim N-1 arce La inceputul fiecarui pas k avem un set de k-1 noduri marcate (in cadrul pasilor precedenti) nodurile marcate sunt cele pentru care se cunoaste drumul minim (initial, doar nodul de start este marcat deoarece doar pentru el se cunoaste drumul minim) In cadrul pasului k trebuie executate 3 operatiuni: Se gaseste acel nod Y nemarcat care are D[Y] minim (acesta este singurul dintre nodurile nemarcate pentru care se poate spune sigur ca drumul minim are lungimea D[Y]) pentru celelalte noduri nemarcate valoarea corespunzatoare din tabloul D s-ar putea sa nu reprezinte lungimea drumului minim ci un drum minim intermediar (alcatuit din maxim k-1 arce) care poate fi imbunatatit in cadrul pasilor viitori ai algoritmului Nodul Y se marcheaza ca vizitat Pentru fiecare nod Z ramas nemarcat se executa urmatorul algoritm:if D[Z] > D[Y] + Arc(Y , Z) then beginD[Z] := D[Y] + Arc(Y , Z);T[Z] := YendLogica este urmatoarea: D[Y] contine lungimea drumului minim de la nodul de start la nodul Y care trece numai prin noduri marcate (Y fiind, la inceputul pasului k, nodul nemarcat care avea D[Y] minim) acest drum este alcatuit din maxim k-1 arce D[Y] fiind minim, il marcam pe Y deoarece nu poate exista un drum mai scurt de la X la Y D[Z] contine lungimea celui mai scurt drum de la nodul de start la nodul Z alcatuit din maxim k-1 arce acest drum trece doar prin noduri marcate, fara sa tina cont ca, intre timp, si Y a fost marcat S-ar putea sa existe un drum mai scurt decat D[Z] de la nodul de start la Z alcatuit din maxim k arce care trece numai prin noduri marcate, inclusiv nodul Y unicul drum cu aceasta proprietate care poate fi mai scurt decat D[Z] este cel care include drumul minim pana la Y si arcul direct intre Y si Z, deci lungimea sa este D[Y] + Arc(Y , Z).

Kristen Nygaard(n. 27 august 1926 d. 10 august 2002) a fost un informatician norvegian, considerat a fi unul din prinii programarii orientate obiect, ca fiind coautor, mpreun cu Ole-Johan Dahl, al limbajelor de programare Simula, limbaje care au folosit pentru prima oar noiunile clase, subclase, motenire i creare dinamic de obiecte. Pentru aceast realizare, cei doi au primit Premiul Turing n 2001.

Knuth - Morris - PrattIdeea de baz a algoritmului descoperit de Knuth, Morris i Pratt este urmtoarea: cnd o nepotrivire este detectat, "nceputul fals" se constituie din caractere pe care le tim deja, din moment ce ele se afl n ablon. ntr-un anumit mod, ar trebui s ne putem folosi de aceast informaie, n loc s deplasm indiceleinapoi peste toate aceste caractere cunoscute.Ca un simplu exemplu, s presupunem c primul caracter din ablon nu mai apare din nou (ablonul este de forma10000000). De asemenea, s presupunem c avem un nceput fals de lungimej, la o poziie oarecare n text. Cnd nepotrivirea este detectat, tim deja cjcaractere s-au potrivit i c nu avem nevoie s deplasm napoi indicelei, din moment ce nici unul dintre celej - 1caractere precedente nu se potrivete cu primul caracter din ablon. Aceast schimbare ar putea fi implementat nlocuindi i - (j - 1)cui i + 1. Efectul practic al acestei schimbri este limitat datorit faptului c un asemenea ablon particular este puin probabil, ns ideea merit reinut iar algoritmul Knuth - Morris - Pratt este o generalizare a ei. Surprinztor, ntotdeauna este posibil o aranjare a lucrurilor astfel nctinu este decrementat niciodat.Deplasarea peste ntreg ablonul la detectarea unei nepotriviri nu conduce la o soluie corect atunci cnd acesta s-ar putea afla la poziia detectrii nepotrivirii. De exemplu, atunci cnd cutm10100111n1010100111, detectm o prim nepotrivire la al cincilea caracter, dar pentru a continua cutarea ar trebui s ne ntoarcem la al treilea caracter, deoarece altfel am pierde potrivirea. Cu toate acestea, ne putem da seama dinainte exact de ceea ce trebuie s facem, deoarece depinde numai de ablon, ca n figura urmtoare:

Poziii de renceput pentru algoritmul Knuth - Morris - Pratt

jurmator[j]

101010011110100111

201010011110100111

311010011110100111

421010011110100111

5010100111 10100111

6110100111 10100111

7110100111 10100111

Vectorulurmator[m]va fi folosit pentru a determina ct de mult trebuie ca algoritmul "s se ntoarc" atunci cnd o nepotrivire este detectat. S ne imaginm c deplasm o copie a primelor j caractere ale ablonului de la stnga la dreapta, ncepnd cu primul caracter al copiei peste cel de-al doilea caracter al ablonului i oprindu-ne cnd toate caracterele suprapuse se potrivesc (sau nu exist nici unul). Caracterele suprapuse definesc urmtorul loc posibil unde ablonul s-ar putea potrivi, dac o nepotrivire este detectat lap[j]. Distana de ntoarcere (urmator[j]) este dat de numrul de caractere suprapuse. n particular, pentruj > 0, valoarea luiurmator[j]este valoarea maximk < jpentru care primelekcaractere ale ablonului se potrivesc cu ultimelekcaractere dintre primelejcaractere ale ablonului. Dup cum vom vedea, este util s lum prin definiieurmator[0] -1.Vectorulurmatord o metod imediat de a limita (de fapt, dup cum vom vedea, de a elimina) ntoarcerea indicatoruluiin text, dup cum am specificat mai sus. Atunci cndiijindic spre caractere care nu se potrivesc (testarea pentru o potrivire ncepnd la poziiai - j + 1n text), urmtoarea poziie posibil pentru o potrivire estei - urmator[j]. Dar, prin definiia tablouluiurmator, primeleurmator[j]caractere de la acea poziie se potrivesc cu primeleurmator[j]caractere ale ablonului, deci nu este nevoie cais se ntoarc att de mult: putem s l lsm nemodificat i s setm indicatoruljlaurmator[j], ca n urmtorul algoritm:01: KMP(p, a)02: M lungime(p)03: N lungime(a)04: INIIALIZEAZ-URMTOR(p)05: pentrui 0, Nij 0, M06: ct timpj 0ia[i] p[j]07: j urmator[j]08: dacj = M09: returneazi - M10: altfel11: returneazi

Cndj = 0ia[i]nu se potrivete cup[0], nu este nici o suprapunere, deci dorim s incrementmii s-l pstrm pejla nceputul ablonului. Definindurmator[0]ca-1,jva fi setat la-1n buclact timp; apoiieste incrementat ijva primi valoarea0cnd buclapentrueste iterat Funcional, acest algoritm este asemntor cualgoritmul forei brute, dar este posibil s ruleze mai repede pentru abloane care se repet des.Mai rmne de calculat tabloulurmator. Programul care face acest lucru este neltor: este acelai program ca cel de mai sus, ns potrivete ablonul cu el nsui:01: INIIALIZEAZ-URMTOR(p)02: M lungime(p)03: urmator[0] -104: j -1;04: pentrui 0, M05: ct timpj 0ip[i] p[j]06: j urmator[j]07: j j + 108: urmator[i] j

Imediat ceiijsunt incrementate, s-a stabilit c primelejcaractere ale ablonului se potrivesc cu caracterele din poziiilep[i - j - 1]..p[i - 1]- ultimelejcaractere din primeleicaractere ale ablonului. Iar acesta este cel mai marejcu aceast proprietate, din moment ce o "posibil potrivire" a ablonului cu sine nsui ar fi fost pierdut. De aceea,jeste exact valoarea ce trebuie atribuit luiurmator[i].Algoritmul Knuth - Morris - Pratt are complexitatea (M + N). (nu folosete niciodat mai mult de M + N comparaii). Aceast proprietate reiese evident din pseudocod: orijeste incrementat ori este resetat din tabloulurmatorcel mult o dat pentru fiecarei.Cu toate acestea, algoritmul Knuth - Morris - Pratt nu este semnificativ mai rapid dect metoda precedent n multe aplicaii practice. ns, metoda are un avantaj practic major: ncepe secvenial prin intrare i nu se "ntoarce" prin ea niciodat. Astfel este convenabil de utilizat pentru fiiere mari citite de la un dispozitiv extern.

Bibliografie

www.cs.upt.ro/~calin/resources/sdaa/dijkstra.ppt http://fictiongirls.wikispaces.com/~+Informaticieni+celebri ro.wikipedia.org/wiki/Istoria_informaticii http://thon.3x.ro/kmp.htm

1