Proiectarea algoritmilor orientate pe problema

Trimisa la data: 2010-08-05 Materia: Informatica Pagini: 73 Comentarii: 0 (comenteaza) Autor: Dana_Br
Raporteaza o eroare
Lucrare de licenta despre Proiectarea algoritmilor orientate pe problema
Remarcabile in Pspace si NP sint problemele complete.Problemele Pspace-complete sint generalizari ale tuturor celorlalte probleme din Pspace in termeni de transformari care necesita timp polinomial. Mai precis: o problema este Pspace-completa sub transformari de timp polinomial daca apartine lui Pspace si oricare alta problema din Pspace este reductibila la ea prin transformari care necesita timp polinomial. Urmeaza ca daca o problema Pspace-completa ar apartine lui P atunci Pspace = P. Deoarece se crede ca aceasta egalitate nu este adevarata, este improbabil sa existe un algoritm de timp polinomial pentru o problema Pspace-completa.

Problemele NP se definesc in mod asemanator, rezultind aceleasi concluzii.
Clasa P are si ea problemele ei complete. Problemele P-complete sint generalizari ale tuturor celorlalte probleme din clasa P, in termenii transformarilor care necesita spatiu de lucru logaritmic. Formal, o problema este P-completa sub transformari spatiale logaritmice daca apartine clasei P si orice alta problema din P este reductibila la ea prin transformari ce utilizeaza spatiu logaritmic. Daca o problema P-completa ar apartine clasei Polylogspace, atunci ar fi adevarata incluziunea P ( Polylogspace.
Comanda prin: SMS / CARD
Comanda aceasta lucrare cu doar 10 Euro + TVA.
Completeaza-ti corect adresa de e-mail. Pe aceasta vei primi link-ul de descarcare a lucrarii de licenta dupa ce plata a fost confirmata!
E-mail:
Pentru operatorul Vodafone procesul presupune trimiterea a doua SMS-uri de verificare tarifate la valoarea unui SMS normal in aceasta retea.
Pentru operatorul Telekom procesul presupune trimiterea a doua SMS-uri de verificare tarifate la valoarea unui SMS normal in aceasta retea.
Selecteaza metoda de plata:
Alege metoda prin care doresti sa efectuezi plata:

3Imputernicire taxe si impozite

Lucrare de licenta despre Proiectarea algoritmilor orientate pe problema

Lucrare de licenta despre Proiectarea algoritmilor orientate pe problema
Cuprins

Complexitatea algoritmilor............5
Masurarea complexitatii...............5
Clase de complexitate.................5
Teze...................6
Complexitatea algoritmilor secventiali.............7
Metode de proiectare a algoritmilor orientate pe problema..........11
Problema Cautarii..........12
Cautarea secventiala.......12
Cautarea binara............13
Arbori binari de cautare............14
Pattern Matching...........15
Problema Sortarii..........17
Bubble Sort (sortare prin interschimbare)..........17
Insertion Sort (sortare prin inserare).............17
Shell Sort (sortare prin metoda Shell).............18
Radix Sort................19
Heap_Sort.................20
Merge_Sort si Quick_Sort..............24
Metode generale de proiectare a algoritmilor.......26
Metoda Divide-and-Conquer (divide-et-impera).......28
Descrierea metodei.......28
Modelul metodei..........28
Eficienta metodei........28
Modelul metodei pentru cazul arborelui binar de recursie:........30
Studii de caz............30
Sortarea prin prin interclasare..........30
Sortarea rapida (C.A.R. Hoare)...........32
Metoda Greedy...........36
Descrierea metodei......36
Modelul metodei.........36
Eficienta metodei.......37
Studii de caz...........37
Interclasare optimala.............37
Compresiile de date. Arbori Huffman.......41
Drum minim intr-un graf ( sursa - destinatie )........43
Problema rucsacului (Knapsack)............44
Programarea dinamica.............46
Descrierea metodei...............46
Modelul metodei..................48
Eficienta metodei................49
Comparatie intre metoda programarii dinamice si metoda greedy 49
Studii de caz....................50
Problema rucsacului (0/1)........50
Inmultire optima de matrici.............52
Arbori binari de cautare optimali.......53
Metoda Backtracking..............57
Descrierea Metodei...............57
Spatiul solutiilor. Restrictii..........57
Backtracking si Branch-and-Bound........59
Modelul metodei............60
Studii de caz..............61
Problema celor 8 dame............61
Submultimi de suma data..........62
Metoda "branch and bound"........65
Descrierea metodei...............65
Branch and Bound (BB) cu strategie cost minim (LC).......69
Modelul metodei pentru strategia LC..............69
Marginire................70
Modelul metodei pentru strategia LC cu marginire........70
Problema 0/1 a rucsacului ( 0/1 knapsack )........71
Algoritmul BB_LC pentru problema 0/1 a rucsacului:.........73
Nota:Textul de mai sus reprezinta un extras din lucrarea de licenta "Proiectarea algoritmilor orientate pe problema". Prin descarcarea prezentei lucrarii stiintifice, orice utilizator al site-ului www.referat.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.
Adauga comentariu:
Adauga comentariu
*Nu exista comentarii
Stiri
Student Center
Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Noutati
Stiri educatie
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Materiale educative Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.