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 / PayPal
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
Vizitatorii acestei lucrari de licenta au mai cautat:
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
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!
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10 Bacalaureat 2019 Vezi subiectele examenului de Bacalaureat din 2019 Evaluare Nationala 2019 Ultimele informatii despre evaluare nationala
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.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles