Categorii:
inchide meniul
Card Cadou
Oameni si Carti
L-V 09:00 - 19:00 0371.781.781

Algoritmi de optimizare in grafuri - Ciprian Ghise

19.62  Lei

sau 1962 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



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