Categorii:
inchide meniul
Produse Naturiste
Oameni si Carti
L-V 09:00 - 19:00 0371.781.781

Algoritmi de optimizare in grafuri - Ciprian Ghise

18.9  Lei

sau 1890 de puncte. Detalii.

In stoc

Cod: ROV978-606-8426-60-0

An aparitie: 2015

Autor: Ciprian Ghise

Categoria: Software

Editie: Necartonata

Editura: ROVIMED

Format: 240 x 170 mm

Nr. pagini: 77



In perioada 11-30 Septembrie toate comenzile in valoare de peste 100 de lei primesc DUBLU puncte de fidelitate. Afla mai multe despre punctele de fidelitate aici.
Transport Gratuit peste 30 de lei
Puncte de fidelitate
30 de Zile Drept de Retur
 

Lucrarea abordeaza doua capitole mari din teoria grafurilor: Algoritmi de drum minim maxim in grafuri si Fluxuri in retele. Lucrarea de fata este structurata in trei parti. Prima parte a lucrarii numita Notiuni introductive contine un scurt istoric al teoriei grafurilor precum si vocabularul de baza in teoria grafurilor. Partea a doua Distante si drumuri minime prezinta principalele probleme de drum minim si cinci algoritmi importanti de drum minim• algoritmul Dantzig, algoritmul Ford, algoritmul Dijsktra, algoritmul Bellman-Ford si algoritmul Floyd-Warshall. Partea a treia Fluxuri in retele incepe cu introducerea conceptelor necesare: retea, capacitate, flux, retea reziduala, taietura precum si a unor rezultate fundamentale, dupa care se continua cu doi algoritmi de determinare a fluxului maxim: algoritmul generic si algoritmul de etichetare Ford-Fulkerson. Algoritmii prezentati in lucrare sunt insotiti de teoreme care demonstreza corectitudinea lor, de o analiza a ordinului de complexitate, de exemple care faciliteaza intelegerea corecta si completa a lor, precum si de implementarea lor in limbajul Borland Pascal.

Fragment:

" Teorema 2.3. Algoritmul Bellman-Ford determina distantele d(s,y) si drumurile minime D syp, yE V, in raport cu varful sursa s din graful orientat G=(V,A) cu functia valoare v:A--> R.
Demonstratie. Pentru inceput aratam ca la al i -lea pas din ciclul repeta avem urmatorul rezultat: daca d(x)#infinit, atunci reprezinta valoarea unui drum de la s la x. Aratam prin inductie dupa numarul de iteratii a ciclului repeta . La iteratia 0 avem pasul 1 al algoritmului, care este evident. Fie iteratia i, consideram momentul cand distanta la un varf x d(x) este actualizata cu d(y)+v(y,x). Din ipoteza inductiei d(y) este valoarea unui drum de la s la y. Atunci d(y)+ valoarea arcului (y,x) este valoarea unui drum de la s la x care trece prin y.
Deoarece un drum de la varful s la oricare alt varf poate sa contina cel mult n-1 arce, rezulta ca, atunci cand nu exista circuite cu valoare negativa, corpul ciclului repeta se poate executa de cel mult n ori. Daca corpul ciclului repeat se executa si a n+1 oara atunci graful contine circuite cu valoare negativa.
Cand s-a ajuns la pasul 3 algoritmul determina drumurile minime de la varful sursa s catre toate celelalte varfuri, daca Presupunem ca d(x) nu reprezinta drumul minim de la s la x. Asta inseamna ca exista un arc (y,x) cu proprietatea ca d(y)+v(y,x)<d(x). Dar asta contrazice faptul ca iesirea din ciclul repeta se face cand, dupa o parcurgere a tuturor arcelor sirul d nu a suferit nici o modificare (adica nici o valoare d(x) nu mai poate fi micsorata). "

Cartea Algoritmi de optimizare in grafuri - Ciprian Ghise face parte din categoria Software a librariei online Libris.ro si este scrisa de Ciprian Ghise. Cartea a fost publicata in 2015 la editura ROVIMED.
Livrarea se face din stoc din depozitul de carte Libris in 24-48 ore, in zilele lucratoare. Transportul este gratuit prin curier rapid, oriunde in Romania, pentru orice comanda de minimum 30 de lei. Pentru orice solicitare apelati call center-ul Libris de luni pana vineri intre orele 9-19.

Altii au comandat si...

De acelasi autor

commentarii

Scrie un comentariu

Campurile marcate cu * sunt obligatorii

Prin publicarea comentariului, esti de acord cu termenii si conditiile

Notificare prin e-mail cand apar comentarii noi

Comentarii

Nici o parere introdusa.
Fii primul care adauga un comentariu ...



sus
Feedback Wishlist