Divide Et Impera

Previzualizare atestat:

Cuprins atestat:

Introducere 3
Metoda Divide et Impera 4
Aplicatii 6
Problema Turnurilor din Hanoi 6
Cel mai mare divizor comun 8
Problema plierilor 10
Fractali 13
Problema taieturilor 15
Descompunere 18
Compunerea performantelor unor algoritmi de cautare si sortare 19
Algoritmi de cautare. Cautarea binara 19
Descompuneri 22
Algoritmi de sortare 24
Sortarea prin interclasare (MergeSort) 25
Sortarea rapida (QuickSort) 28
Bibliografie 31
Cuprins 32

Extras din atestat:

Lucrarea de fata prezinta o aplicatie practica in domeniul matematicii si informaticii deoarece rolul oricarui compilator este de a transforma programele scrise intr-un limbaj de programare oarecare intr-un cod echivalent, scris in limbaj de asamblare sau in limbaj masina. In aceasta lucrare ne punem problema rezolvarii unor probleme atat matematice cat si de programare intr-un limbaj de programare cum ar fi de exemplu limbajul Pascal in limbaj de asamblare. In practica ne intalnim deseori cu probleme de acest fel in programare.

Programele de acest fel permit experimentarea unor situatii, care ar fi dificil sau imposibil de realizat in practica. Simularile pot fi mai instructive atunci cand sunt utilizate pentru a ilustra idei si experimente explorate in prealabil prin alte mijloace - idei, teste, discutii, chestionare, etc.

Acest tip de programe asigura simularea unor situatii, modele, in care rezultatele finale sa fie obtinute din deciziile proprii ale utilizatorului aplicandu-se la orice nivel.

Ghidati dupa datele furnizate de program, se pot selecta anumite optiuni sau alege anumite situatii si apoi se obtin 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

Bibliografie:

B. Patrut, M. Milosescu, Informatica (cls a IX-a), ed. Teora, 1999

Internet

Turbo Pascal 6.0, Ghid de utilizare, ed.Microinformatica

Cornelia Ivasc, Mona Pruna, Bazele informaticii (cls a X-a) Ed. Petrion, Bucuresti, 1995

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

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

Download atestat

Primești atestatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc, jpg, htm, exe, pas
Diacritice:
Nu
Nota:
9/10 (1 voturi)
Anul redactarii:
2004
Nr fișiere:
22 fisiere
Pagini (total):
32 pagini
Imagini extrase:
32 imagini
Nr cuvinte:
3 837 cuvinte
Nr caractere:
20 178 caractere
Marime:
257.83 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Atestat
Materie:
Informatica
Data publicare:
22.09.2017
Structură de fișiere:
  • JPG
    • fractali.jpg
    • Header.jpg
    • Menu.jpg
  • Programe
    • CMMDC.EXE
    • CMMDC.PAS
    • FRACTALI.EXE
    • FRACTALI.PAS
    • Sortare_interclasata.exe
    • Sortare_rapida.exe
    • Sortare_rapida.pas
    • Sotare_interclasata.pas
    • Turnurile din Hanoi.EXE
    • Turnurile_din_Hanoi.PAS
  • Atestat informatica.doc
  • Cel_mai_mare_divizor_comun.htm
  • Fractali.htm
  • index.htm
  • inline.htm
  • Prezentare.htm
  • sortare_interclasata.htm
  • sortarea_rapida.htm
  • Turnurile_din_Hanoi.htm
Predat:
Grup Şcolar Bicaz
Profil:
Real
Profesorului:
Vancea Ioan

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Argument Am ales aceasta tema datorita faptului ca metoda Divide et Impera este un principiu...
Divide et impera se bazeaza pe un principiu extrem de simplu: descompunem problema in doua sau...
Divide et impera - sortari Prezentare generala Divide et impera este o tehnica speciala prin...
Descompunerea cazului ce trebuie rezolvat intr-un numar de subcazuri mai mici ale aceleiasi...
NOTIUNI INTRODUCTIVE Metoda de programare DIVIDE ET IMPERA consta in impartirea problemei...
Sus!