Cercetări operaționale

Semestrul de primăvară

Titular de curs: lector superior Sergiu Corlat, E-mail: [email protected] ,
Web Page: http://sites.google.com/site/scorlat

Structura:    Curs teoretic –30 ore ( 2 ore săptămînal)

Laborator - 60 ore (4 ore săptămînal)

Activităţi individuale ale masterandului – 60 ore

Activităţi de învăţare
Masteranzii ascultă un curs de lecţii ce ţin de rezolvarea problemelor de optimizare din diverse subdomenii matematice: programmare liniară, convexă şi neliniară, extinse pe structuri de date de natură complexă(grafuri, primitive geometrice, structuri abstracte). Printre problemele cercetate se numără problemele clasice: a fluxului maxim, problema comisului voiajor, a cuplsjului maxim, problema de tran sport, etc. Pe parcursul orelor de laborator masteranzii sunt antrenaţi în rezolvarea practică a problemelor, folosind algoritmii studiaţi la orele teoretice, şi realizarea aplicaţiilor software pentru implementarea acestora. Activităţile individuale se orientează către elaborarea aplicaţiilor individuale sau a proiectelor de grup pentru utilizarea practică a algoritmilor studiaţi în rezolvarea problemelor reale şi urmează să fie presentate public la finele fiecărui modul.

Conţinutul cursului:
1. Programare liniară Descrierea generală a problemei. Interpretări. Metode de rezolvare. Metoda simplex. Probleme de transport. Metode de rezolvare.
2. Probleme min / max în pe grafuri Metode de parcurgere. Problema arborelui de cost minim: formulare, metode de rezolvare, algoritmi. Problema celui mai scurt drum: algoritmii Kruscal, Floyd. Problema comisului voiajor. Clasificare, complexitate, metode de rezolvare. Problema mulţimii maxim independente. Variaţii. Abordări practice. Metode de rezolvare. Problema cuplajului maxim. Formulare. Tehnici de rezolvare. Reducerea la problema mulţimii maxim independente. Centrul şi mediana în graf. Probleme asociate. k-centre şi mediane.
3. Probleme de transport în reţea. Flux maxim în reţele. Teorema despre fluxul maxim şi tăietura minimă. Algoritmul Ford – Fulkerson. Flux maxim pentru surse şi destinaţii multiple. Problema repartizărilor optime.
4. Probleme min / max pe structuri geometrice. Noţiuni generale. Structuri geometrice primare în 2D, 3D. Problema celei mai apropiate perechi de puncte. Înfăşurătoarea convexă a unui sistem de puncte. Algoritmul Graham. Modificarea Andrew. Nucleul poligonului simplu. Repartizarea echidistantă în plan. Poligonul şi diagrama Voronoi.

Bibliografie
1. А. Схрейвер. Теория линейного и челочисленного прграммирования. Москва, Мир, 1991
2. Gibbons Alan. Algorithmic ghaph theory, 1999, Addison Wesley
3. Новиков Ф.А. Дискретная математика для программистов, 2001, Питер, Санкт Петербург
4. Майника Э. Алгоритмы оптимизации на сетях и графах. 1981, Мир, Москва
5. Препарата Ф, Вычислительная геометрия. Введение,1989, Мир, Москва
6. Кристофидес П.,Теория графов. Алгоритмический подход, 1978,Мир, Москва
7. Corlat S. Algoritmi şi problem de geometrie computaţională. Chişinău, Prut Internaţional, 2009.
8. Ф.В. Кротов, Б.А. Лагоша. Основы теории оптимального управления. Москва, Высшая школа, 1990
9. Р.Габасов, Ф. Кириллова Методы оптимизации. Минск, БГУ, 1981

Evaluare
Activitatea masterandului va fi monitorizată la fiecare tip de activitate şi va fi apreciată prin note. La sfîrşitul cursului va avea loc examenul final (180 min., scris ), care va include un test complex de întrebări la nivel de cunoaştere, integrare şi aplicare a cunoştinţelor. Nota finală se va constitui din reuşita academică obţinută pe parcursul semestrului (30%), activităţile individuale şi de laborator (40%) şi examenul final (30%).

Onestitatea academică
Lucrând în cadrul acestui curs este important de dezvoltat spiritul de echipă şi de lucru în grup. Vă încurajez să vă ajutaţi reciproc în cadrul seminarelor şi activităţilor multimedia, efectuând temele în cadrul activităţilor individuale, dar...r e ţ i n e ţ i.. fiecare temă, activitate sau lucrare prezentată spre evaluare trebuie sa fie una personală. Nu se acceptă plagierea, copierea, utilizarea materialelor din Internet, etc.

Va rog să citiţi cu atenţie Codul de Etică şi Regulamentul studentului UnAŞM