Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

CUPRINS
Introducere ............. 4
I. Metoda backtracking ............. 6
I.1. Varianta iterativa ........ 6
I.2. Varianta recursiva ....... 12
II. Metoda divide et impera ...... 13
III. Aplicatii la metoda backtracking ............ 20
III.1. Problema colorarii hartilor ......... 20
III.2. Partitiile unei multimi . 26
III.3. Problema descompunerii unui numar natural . 28
IV. Aplicatii la metoda divide et impera ...... 33
IV.1. Sortarea prin interclasare ........... 33
IV.2. Problema plierii ......... 36
Concluzii finale .......... 41
Bibliografie .............. 43

Alte date

?

În decursul anilor, informatica a fost revolutionata de cateva noi metode de programare. Printre acestea se numara programarea structurata, modulara si cea orientata pe obiecte. Aceste metode se refera la modul in care sunt construiti algoritmii, respectiv programele. Aplicarea corecta a acestor metode poate duce in anumite situatii la imbunatatirea cu cel putin un ordin de marime a productivitatii, fiabilitatii si a costului intretinerii sistemelor software.

Începutul programarii structurate apartine profesorului E. W. Dijkstra de la Universitatea Eindhoven care in 1965 sugereaza ideea construirii unor programe mai bune prin evitarea instructiunii GoTo. În acest fel se evita transferul explicit al executiei de la o instructiune la alta. Urmatorul pas important apartine lui Bohm si Jacopini care, in 1966, publica o lucrare in care demonstreaza ca sunt suficiente 3 tipuri de transfer a executiei pentru a exprima logica interna a oricarui program: secventa, selectia si iteratia.

Un program poate fi privit ca un sistem. Structura unui program, adica componentele si relatiile dintre ele, reprezinta o proprietate esentiala a sa.

La nivelul cel mai elementar se observa ca un program este compus din instructiuni. O astfel de instructiune este o informatie care descrie exact un obiect supus prelucrarii sau o operatie pe care o masina reala sau virtuala o poate executa. Calculatoarele prelucreaza informatiile prin executarea unor operatii simple. Desi operatiile sunt elementare, prin inlantuirea unei multimi de operatii se poate ajunge la operatii deosebit de complexe. Combinarea operatiilor nu se face la intamplare, ea supunandu-se unor reguli bine precizate. Desi un algoritm este o multime finita de operatii cunoscute care se executa intr-o ordine bine stabilita asupra unor date de intrare si conduc intr-un timp finit la un set de date de iesire. Algoritmii trebuie sa cuprinda analiza tuturor situatiilor posibile, nelasand nimic la voia intamplarii.

O modalitate de descriere a algoritmilor este pseudocodul. Aceasta reprezinta o notatie textuala ce permite exprimarea logicii programelor intr-un mod oarecum formalizat fara a fi necesare totusi reguli de sintaxa riguroase ca in limbajele de programare. În principiu, in orice pseudocod se folosesc 2 tipuri de propozitii: propozitii standard si propozitii nestandard.

Programarea modulara este metoda ce are la baza principiul modularizarii. Termenul modular este folosit pentru a desemna un programa care a fost structurat in mai multe parti, puternic independente numite module. Pentru a evolua obiectiv calitatea structurii unui program rezultat din procesul de proiectare se folosesc in principal doua marimi: consistenta si cuplajul modulelor. Fiecare modul are trei atribute de baza: functia, logica interna si interfata.

Un modul Turbo Pascal este o colectie de constante, variabile, proceduri si functii care sunt compilate separat si pot fi folosite de alte module sau de programul principal.

Programarea modulara conduce la o centralizare a tuturor datelor de un anumit tip sub controlul unui modul de gestionare a tipului.

Programarea orientata pe obiecte este o metoda de programare care duce la cresterea productivitatii construirii produselor program. Ea reprezinta o evolutie naturala de la metodele de programare: este mai structurata decat incercarile anterioare de structurare a programelor, mai modulara si mai abstracta decat incercarile anterioare de ascundere a datelor si de abstractizare.

De multe ori, pusi in fata unei probleme pentru care trebuie sa elaboram un algoritm, nu stim cum sa incepem. De aceea lucrarea de disertatie trateaza doua din metodele de programare si anume metoda backtracking si metoda divide et impera. Pentru exemplificare s-au intocmit programe demonstrative pentru colorarea unei harti cu n tari si c culori, partitiile unei multimi, descompunerea unui numar natural, sortarea prin interclasare a elementeleor unui vector si problema plierii.În capitolele I si II voi prezenta metodele generale de elaborare a algoritmilor care ne vor ajuta la rezolvarea unor clase de probleme.

CAP. I. METODA BACKTRACKING

O metoda simpla de rezolvare a problemelor a caror solutie se prezinta sub forma: x1,x2,... ,xi, ..., consta in a genera intr-un mod oarecare toate solutiile posibile si de a verifica daca ele satisfac conditiile interne. Dezavantajul acestei metode consta in faptul ca timpul cerut este foarte mare.

Acest proces poate fi reprezentat cu ajutorul unui arbore care reprezinta multimea solutiilor partiale. Reprezentare se face dupa cum urmeaza:

- radacina arborelui este reprezentata de vectorul nul;

- fii unui nod de nivel k-1 reprezinta elementele multimii Sk.

Fig. 1

În situatia descrisa in figura 1, algoritmul parcurge arborele in ordinea indicata de sagetile punctate.

Solutiile se pot determina prin incercari succesive de extindere a unei solutii partiale. În fiecare etapa a cautarii pentru care nu este posibila o extindere a solutiei partiale curente, se revine la o solutie partiala anterioara si se incearca din nou. Se reduce astfel foarte mult numarul solutiilor generate.

Aceasta metoda a fost numita backtracking de catre D.H.Lehmer in 1950 si a fost prezentata in forma actuala pentru prima data de R.J.Walker.

Metoda este utilizata pe scara larga pentru rezolvarea problemelor combinatorice din domeniul analizei sintactice, jocurilor si optimizarilor, aplicandu-se in cazul problemelor a caror solutie se prezinta sub forma: x1,x2,... ,xi, ..., atunci cand nu exista nici o alta cale de rezolvare a problemei propuse deoarece timpul de executie este de ordin exponential. Metoda utilizeaza structura de stiva si poate fi programata si iterativ si recursiv.

I.1. VARIANTA ITERATIV?