Divide Et Impera

Lucrarea de faţă prezintă o aplicaţie practică în domeniul matematicii şi informaticii deoarece rolul oricărui compilator este de a transforma programele scrise într-un limbaj de programare oarecare într-un cod echivalent, scris în limbaj de asamblare sau în limbaj maşină. În această lucrare ne punem problema rezolvării unor probleme atât matematice cât şi de programare într-un limbaj de programare cum ar fi de exemplu limbajul Pascal în limbaj de asamblare. În practică ne întâlnim deseori cu probleme de acest fel în programare.

Programele de acest fel permit experimentarea unor situaţii, care ar fi dificil sau imposibil de realizat în practică. Simulările pot fi mai instructive atunci când sunt utilizate pentru a ilustra idei şi experimente explorate în prealabil prin alte mijloace - idei, teste, discuţii, chestionare, etc.

Acest tip de programe asigură simularea unor situaţii, modele, în care rezultatele finale să fie obţinute din deciziile proprii ale utilizatorului aplicându-se la orice nivel.

Ghidaţi după datele furnizate de program, se pot selecta anumite opţiuni sau alege anumite situaţii şi apoi se obţin rezultatele deciziilor.

METODA DIVIDE ET IMPERA

Divide et Impera este o metoda generala de elaborare a algoritmilor, care consta in doua etape:

- Divide. Problema data este impartita in doua sau mai multe subprobleme de acelasi tip, dar de dimensiuni mai mici. Subproblemele se rezolva direct, daca dimensiunea lor permite aceasta, sau, fiind de acelasi tip se rezolva in mod recursiv, prin acelasi procedeu.

- Impera. Se combina solutiile problemelor pentru a obtine solutia problemei initiale.

Pentru a intui mai bine cum functioneaza aceasta metoda, sa ne gandim la modul de organizare a unui turneu de tenis. Concurentii participanti sunt impartiti in doua grupe. Se organizeaza turneul in cadrul fiecarei grupe, iar finala se va disputa intre cei doi castigatori ai turneului pe grupe. Castigatorul finalei este castigatorul intregului turneu. Organizarea turneului pe grupe se face dupa acelasi procedeu: se impart concurentii din cadrul grupei pe semigrupe, se organizeaza turneul pe semigrupe, iar castigatorul grupei se obtine intr-un meci de semifinala intre cei doi castigatori din cele doua semigrupe s.a.m.d. Impartirea se repeta pana cand avem doar doi jucatori, care joaca un meci 'direct'.

Am sa incerc sa descriu intr-un mod cat mai general aceasta metoda. Sa consideram ca procedura DIVIDE _ET_IMPERA trebuie sa rezolve o problema de dimensiune d si sa obtina solutia problemei in parametrul de iesire Sol P. Pentru aceasta se imparte problema data in ns subprobleme. Cum nu este obligatoriu ca subproblemele sa aiba aceeasi dimensiune, retinem in vectorul ds dimensiunile celor ns subprobleme. Rezolvam cele ns subprobleme, apeland succesiv procedura DIVEDE_ET_IMPERA pentru fiecare dintre ele si retinem solutiile obtinute in vectorul s.

Prin combinarea solutiilor subproblemelor din vectorul s. obtinem solutia problemei date.

procedure Divide_et_Impera(d:Dimensiune; var SolP:Solutie)

var ds:array [1 NMaxSubprobleme] of Dimensiune;

ns,i: 1 NMaxSubprobleme;

s: array[1 NMaxSubprobleme] of Solutie;

begin

if d < e then

Prelucrare (d, SolP)

else

begin

Divide (d,ns,ds);

for i:=1 to ns do Divide_et_Impera (ds [i], s[i] ) ;

Combina (ns , s , SolP)

end

end;

In cele mai multe situatii problema se imparte in doua subprobleme de dimensiuni aproximativ egale

APLICATII

PROBLEMA TURNURILOR DIN HANOI

Avem la dispozitie trei tije, numerotate 1,2,3, si n discuri de diametre diferite. Initial, toate discurile sunt plasate pe tija 1 in ordine descrescatoare a

B. Pătruţ, M. Miloşescu, Informatică (cls a IX-a), ed. Teora, 1999

Internet

Turbo Pascal 6.0, Ghid de utilizare, ed.Microinformatica

Cornelia Ivaşc, Mona Prună, Bazele informaticii (cls a X-a) Ed. Petrion, Bucureşti, 1995

Tudor Sorin, Informatică (cls a XI-a), ed. L&S Infomat

George Daniel Mateescu, Pavel Florin Moraru, Informatică (cls XI), Ed. Niculescu