Optimizimi i grafeve

Optimizimi i grafeve

 

Kodi i lëndës

Semestri

Kreditet e lëndës

Kredite

Leksione

Ushtrime/

Seminare

Laboratore

Detyra

 

II

3.5

1.5

0.5

0.5

6

 

     Titullari i lëndës: Ada GOGU, Doktor

 

 

Objektivat e lëndës

 

 

 

Lënda, Optimizimi i Grafeve, prezanton disa koncepte dhe metoda kryesore në teorinë e grafeve. Aktualisht, teoria e grafeve konsiderohet si nje mjet shume i fuqishem per zgjidhjen e problemeve te ndryshme qe lindin ne industri. Për rrjedhojë, synimi ynë kryesor  është që studenti të jetë i aftë për të propozuar metoda për probleme të ndryshme me të cilat mund të përballet në një kontekst industrial,  për t’i implementuar ato, dhe për të analizuar vlefshmerinë e tyre.

 

 

 

 

Përmbajtja

 

 

Problemet kombinatoriale, përkuzime dhe dhenia e kontekstit industrial. Teoria e kompleksitetit, konceptet bazë, Problemet P dhe NP. Kompleksiteti i algoritmeve, algoritmet pseudo-polinomiale. Kërkimi operacional dhe teoria e grafeve, nocionet bazë.  Grafet me dhe pa drejtim, ciklet, rrugët, disa grafe të vecantë.Problemet e rrugëve më të shkurtra, modelizimi dhe vetitë kryesore. Kodimi i grafeve dhe vlerësimi i algoritmeve. Algoritmet e rrugëve më të shkurtra, FORD, DJIKSTRA dhe BELLMAN, vlefshmëria dhe kompleksiteti i tyre. Probleme të tjera të rrugëve: rruga e dytë më e shkurtër, ruga më e gjatë, rruga me kapacitetin më të lartë, rruga me probabilietin më të ulet. Grafet me dy-pjesë dhe dy-ngjyra, pema mbuluese me koston më të ulët. Hyrje ne programimin linear, modelimi i problemeve, paraqitja e kushteve dhe objektivave përkatëse. Algoritmi Simplex, dhe dualiteti.Programimi linear me numra te plotë. Modelizimi i problemeve të optimizimit në logjistik, problemet e particionimit dhe mbulimit. Modelizimi i problemeve të optimizimit në transport, problemi i rrugëve me kapacitet. Problemet e skedulimit, modelizimi i tyre nëpërmjet grafit me potenciale. Programimi linear dhe metoda PERT për disa probleme skedulimi

 

 

Literatura e rekomanduar

 

R.K. Ahuja, T.L. Magnanti, J. B. OrlinNetwork Flows: Theory, Algorithms, and Applications 1993,  ISBN-10: 013617549X

 

M. R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979, ISBN-10: 0716710455.

 

J.F. Hêche, T. M. Liebling, D.Werra, Recherche opérationnelle pour ingénieurs I, 2003, ISBN: 2-88074-446-6

 

Gueret, Prins, Sevaux, Programmation linéaire, 2000, Editions Eyrolles

 

J. Carlier, P. Chrétienne, Problèmes d'ordonnancement, 1997, ISBN-10: 2225812756

 

 

 

<<< kthehu pas<<<

 

Bashkëpunime ndërkombëtare Shërbimet Copyright © 2010-2021 Universiteti Politeknik i Tiranës (UPT)
Fakulteti i Teknologjisë së Informacionit (FTI)
Sheshi Nënë Tereza 4, Tiranë
Telefon: +355.42.278159
Qendër Download Posta Elektronike Biblioteka