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 - Configuratia Hardware a unui P.C. Compatibil I.B.M.

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

Curs IT

1. HARDWARE (HARD): Reprezinta totalitatea componentelor materiale ale unui sistem informatic. 2. SOFTWARE (SOFT): Reprezinta totalitatea...

Criptografie si Securitatea Informatiei

1.1 Noţiuni de teoria numerelor 1.1.1 Numere prime Fiind date două numere naturale m şi n, spunem că m divide pe n, sau că n este multiplu al...

Retele de Calculatoare

1. Calculatorul electronic De-a lungul istoriei,omenirea a folosit suporturi fizice pentru a-si exprima ideile,pentru a le vizualiza , a se putea...

Prezentarea Sistemului Fox Pro

Elementele de baza ale sistemului FoxPro Principalele elemente ale mediului FoxPro sunt: Bara de meniuri Fereastra de comanda Elementele de...

Microcontrolere PIC

Capitolul 1: microcontroler PIC16F887 - Dispozitiv de ansamblu asupra PIC16F887 este una dintre cele mai noi produse de Microchip. Conţine toate...

Configurare Bios

Dupa ce am conectat la priza de curent alternativ atit calculatorul cit si monitorul apasam pe butonul de pornire a calculatorului si apoi pe...

Ai nevoie de altceva?