Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi

Curs
8.4/10 (5 voturi)
Domeniu: Calculatoare
Conține 7 fișiere: doc
Pagini : 63 în total
Cuvinte : 16420
Mărime: 146.85KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Georgescu Horia

Extras din document

Despre algoritmi

• Diferenţe între informatică şi matematică

1) În lucrul pe calculator, majoritatea proprietăţilor algebrice nu sunt satisfăcute.

- elementul neutru: egalitatea a+b=a poate fi satisfăcută fără ca b=0: este situaţia în care b0, dar ordinul său de mărime este mult mai mic decât al lui a.

- comutativitate: să considerăm următoarea funcţie scrisă în Pascal:

function f(var a:integer):integer;

begin a:=a+1; f:=a end;

Secvenţa de instrucţiuni:

a:=1; write (a+f(a))

produce la ieşire valoarea 1+2=3, pe când secvenţa de instrucţiuni:

a:=1; write (f(a)+a))

produce la ieşire valoarea 2+2=4.

- asociativitate: pentru simplificare vom presupune că numerele sunt memorate cu o singură cifră semnificativă şi că la înmulţire se face trunchiere. Atunci rezultatul înmulţirilor (0.50.7)0.9 este 0.30.9=0.2, pe când rezultatul înmulţirilor 0.5(0.70.9) este 0.50.6=0.3.

2) Nu interesează în general demonstrarea teoretică a existenţei algoritmilor, ci accentul este pus pe elaborarea algoritmilor.

Vom pune în vedere acest aspect prezentând o elegantă demonstraţie a următoarei propoziţii:

Propoziţie. Există ,RQ cu Q.

Pentru demonstraţie să considerăm numărul real x=aa, unde a= .

Dacă xQ, propoziţia este demonstrată.

Dacă xQ, atunci xaQ şi din nou propoziţia este demonstrată.

• Aspecte generale care apar la rezolvarea unei probleme

Aşa cum am spus, informaticianului i se cere să elaboreze un algoritm pentru o problemă dată, care să furnizeze o soluţie (fie şi aproximativă, cu condiţia menţionării acestui lucru).

Teoretic, paşii sunt următorii:

1) demonstrarea faptului că este posibilă elaborarea unui algoritm pentru determinarea unei soluţii;

2) elaborarea unei algoritm (caz în care pasul anterior devine inutil);

3) demonstrarea corectitudinii algoritmului;

4) determinarea timpului de executare a algoritmului;

5) demonstrarea optimalităţii algoritmului (a faptului că timpul de executare este mai mic decât timpul de executarea al oricărui alt algoritm pentru problema studiată).

• Timpul de executare a algoritmilor

Un algoritm este elaborat nu numai pentru un set de date de intrare, ci pentru o mulţime de astfel de seturi. Timpul de executare se măsoară în funcţie de lungimea n a datelor de intrare.

Ideal este să determinăm o formulă matematică pentru T(n)=timpul de executare pentru orice set de date de intrare de lungime n. Din păcate, acest lucru nu este în general posibil. De aceea, în majoritatea cazurilor ne mărginim la a evalua ordinul de mărime al timpului de executare.

Mai precis, spunem că timpul de executare este de ordinul f(n) şi exprimăm acest lucru prin T(n)=O(f(n)), dacă raportul între T(n) şi f(n) tinde la un număr real atunci când n tinde la .

De exemplu, dacă f(n)=nk pentru un anumit număr k, spunem că algoritmul este polinomial.

Un algoritm se numeşte "acceptabil" dacă este este polinomial.

• Corectitudinea algoritmilor

În demonstrarea corectitudinii algoritmilor, există două aspecte importante:

 Corectitudinea parţială: presupunând că algoritmul se termină (într-un număr finit de paşi), trebuie demonstrat că rezultatul este corect;

 Terminarea programului: trebuie demonstrat că algoritmul se încheie în timp finit.

Evident, condiţiile de mai sus trebuie îndeplinite pentru orice set de date de intrare admis.

Modul tipic de lucru constă în introducerea în anumite locuri din program a unor invarianţi, adică relaţii ce trebuie îndeplinite la orice trecere a programului prin acel loc.

Preview document

Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 1
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 2
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 3
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 4
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 5
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 6
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 7
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 8
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 9
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 10
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 11
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 12
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 13
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 14
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 15
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 16
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 17
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 18
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 19
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 20
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 21
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 22
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 23
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 24
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 25
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 26
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 27
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 28
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 29
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 30
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 31
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 32
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 33
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 34
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 35
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 36
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 37
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 38
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 39
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 40
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 41
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 42
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 43
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 44
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 45
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 46
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 47
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 48
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 49
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 50
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 51
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 52
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 53
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 54
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 55
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 56
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 57
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 58
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 59
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 60
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 61
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 62
Java - Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programării Dinamice, Algoritmi - Pagina 63

Conținut arhivă zip

  • c1_algo.doc
  • C2_arbori.doc
  • C3_grafuri.doc
  • C4_Greedy.doc
  • C5_back.doc
  • C6_DivImp.doc
  • C7_progdin.doc

Alții au mai descărcat și

Arhitectura calculatoarelor - configurația hardware a unui PC compatibil IBM

CAPITOLUL I CONFIGURATIA HARDWARE A UNUI P.C. COMPATIBIL I.B.M. Configuratia unui PC compatibil IBM Introducere Au trecut mai bine de doua...

Limbaje Formale și Translatoare

1. Introducere Curs1 LFT Limbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare. Pentru a putea însă folosi limbaje...

Programare HTML și XML

CAPITOLUL I NOTIUNI GENERALE [13, 28, 78, 77] 1.1 INTERNET Internet-ul, sau reteaua mondială de calculatotore, reprezintă un puternic instrument...

Inginerie Software

Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...

Limbaje de Asamblare

Introducere. Necesitatea programării în limbaje de asamblare Modalităţile de programare s-au schimbat imens de la inventarea calculatorului, în...

Proiectarea unei interfețe pentru comanda unui motor de curent continuu folosind un microcontroler

Microcontrolerele Siemens SAB 80C166 Caracteristici Firma Siemens a dezvoltat propria linie de microcontrolere. Aceasta cuprinde microcontrolere...

Algoritmi

ETAPELE REZOLVARII UNEI PROBLEME ALGORITMUL – reprezintă o succesiune finită şi ordonată de operaţii univoc determinate, efectuate mecanic, care...

Software de Sistem

Cap.1 - INTRODUCERE 1.1 DEFINIŢII Propoziţia simplă este o aserţiune, o afirmaţie, exprimată minimal printr-o acţiune concretă, un predicat,...

Ai nevoie de altceva?