CNAA Comisia de atestare Comisia de acreditare Comisiile de experţi Dispoziţii, instrucţiuni Acte normative

PREGĂTIREA CADRELOR Nomenclator Instituţii Consilii Seminare Teze

POTENŢIALUL ŞTIINŢIFIC Conducători de doctorat Deţinători de grad Doctoranzi Postdoctoranzi

 română | русский | english

Recomandări metodice generale.

În cadrul specialităţii 01.01.09 – Cibernetică Matematică se pregătesc specialişti de o calificare înaltă, capabili de a modela şi de a elabora metode eficiente de soluţionare a problemelor extremale cu caracter discret şi continuu. Direcţiile principale ţin de modelarea proceselor headback, dirijarea optimală, teoria grafurilor şi generalizări, matematica economică etc.

Conţinutul programei.

Logica matematică

1. Funcţii în algebra propoziţiilor. Reprezentarea prin f.n.p.
2. Problema completitudinii funcţionale: Teorema despre completitudinea funcţională în P2.
3. Funcţii finit predeterminate. Automate. Evenimente regulate şi reprezentarea lor prin automate.
4. Funcţii calculabile. Echivalenţa claselor de funcţii recursive şi funcţii calculabile după Turing.
5. Nerezolvabilitatea algoritmică a problemei completitudinii. Teorema lui Godel.

Combinatorică

1. Selecţii şi aranjamente. Repartiţii şi complectări. Sisteme de mulţimi.
2. Numerele lui Ştirling, Bell şi Fibonaci.
3. Metoda funcţiilor producătoare şi aplicaţiile ei.
4. Metoda includerii excluderii. Sisteme de reprezentanţi ale mulţimilor. Teorema Ramsey.
5. Sisteme de incidenţă şi matrice speciale. Pătrate şi dreptunghiuri latine.

Teoria grafurilor

1. Noţiunile de bază ale teoriei grafurilor. Reprezentarea grafurilor. Problema izomorfizmului.
2. Grafuri planare. Formula Euler. Criterii de planaritate.
3. Noţiune de clică şi mulţimi stabile în grafuri. Acoperirea grafurilor cu mulţimi de vârfuri şi muchii.
4. Convexitatea în grafuri. Teorema Menger. Grafuri Hamilton şi Euler.
5. Colorarea grafurilor. Problema a 4 culori. Teorema Vizing despre colorarea muchiilor.
6. Grafuri perfecte şi triangulate. Descompunerea simplicială a grafurilor triangulate.
7. Aspectele algoritmice ale teoriei grafurilor.
8. Noţiuni de bază ale teoriei hipergrafurilor. Hiperarbori.

Algoritmi şi complexitate

1. Estimarea complexităţii algoritmilor şi a problemelor. Dimensiunea problemei individuale. Exemple de algoritmi polinomiali. Metoda divide şi domină (divide et tempera).
2. Probleme de optimizare. Clasele P şi NP. Exemple de probleme NP-cornplete. Reducerea polinomială a problemei 3-realizabilităţii la problema despre clica maximală a grafului.

Algoritmi în matematica discretă.

1. Fluxuri în. reţele. Teorema Ford-Fulkerson despre fluxul maximal. Legătura reciprocă cu teoremele lui Dilworth, Menger şi Hall. Cuplaj maximal.
2. Fluxuri de cost minim în reţele şi metode de rezolvare. Metoda simplexului dual. Metoda ungară.
3. Metoda lanţurilor alternante de construire a cuplajului maximal într-un graf bipartit şi estimarea complexităţi lui.
4. Problema arborelui de acoperire minimal. Matroizi şi algoritmul greedy. Problema despre intersecţia matroizilor.
5. Problema sortării. Algoritmi de sortare şi selecţie.
6. Structuri de date. Arbori binari de căutare. Arbori optimali de căutare. AVL-arbori şi B-arbori.
7. Problemele geometriei computaţionale şi metodele ei. Localizarea punctului într-o subdiviziune rectilinie a planului (metoda fîşiilor, metoda lanţurilor monotone şi metoda deteriorării triunghiulare). Structuri de date multidimensionale. Arborii segmentelor.
8. Diagrama Voronov şi probleme cu caracter metric. Folosirea diagramei Voronov la construirea arborelui de acoperire minimă în plan. Triangulări. Algoritmul de triangulare a unei poligon simplu.

Programarea liniară şi convexă.

1. Formulare problemelor de programare matematică. Teorema Kuhn-Takker.
2. Problema generală de programare liniară. Teoremele de dualitate. Metoda simplex.
3. Stabilitatea în programarea matematică. Programarea liniară cu parametri.
4. Probleme de programare liniară în numere întregi, metode de rezolvare.

Metode de optimizare fără restricţii.

1. Metode de optimizare fără restricţii (metoda gradient, metoda gradientului conjurat, metoda Newton, căutare aleatoare).
2. Metode de optimizare convexe (metoda gradientului proiectat, metoda gradientului condiţionat, metoda direcţiilor admisibile). Metoda funcţiilor de penalizare.
3. Algoritmi optimali în programarea matematică. Complexitatea informaţională şi de calcul a problemelor de programare convexă.
4. Metodele programării dinamice, metoda ramificării şi marginilor.
5. Metode de regularizare.
6. Metode de optimizare stohastice, metode de optimizare cu funcţii discontinuu derivabile.

Teoria jocurilor.

1. Definiţia jocului. Jocuri antogonistice. Teorema despre minimax pentru jocuri matriciale.
2. Determinarea strategiilor optimale mixte. Jocuri concav-convexe.
3. Definiţia jocului cu N persoane. Situaţie de echilibru pentru jocuri cu N persoane. Teorema Nash.
4. ocuri şi structuri ierarhice. Utilizarea jocurilor ierarhice la modelare sistemelor ierarhice cu doua nivele. Metodele de determinare a strategiilor optime pentru jocuri cu structuri ierarhice.

Teoria orarurilor

1. Sisteme de deservire la unul şi doua dispozitive. Intervale de directivă. Problema Bellman-Jonson.

Literatura de specialitate.

1. В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. Лекции по теории графов. М., Наука, 1990.
2. А.А.Зыков. Теория графов. М., Наука, 1987.
3. Х.Пападимитриу, К.Стайнглиц. Комбинаторная оптимизация. М., Мир, 1985.
4. Ф.Препарата и М.Шеймос. Вычислительная геометрия. Введение. М., Мир, 1989.
5. Ф.Харари. Теория графов. М., Мир, 1979.
6. К.А.Рыбников. Введение в комбинаторный анализ. М., МГУ, 1985.
7. М.Свами , К.Тхуласираман. Графы, сети и алгоритмы. М., Мир, 1984.
8. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.
9. В.С.Танаев, В.В.Шкурба. Введение в теорию расписаний. М., Наука, 1975.
10. Constantin Smadici. Cercetare operaţională, p. 1,2. Universitatea "Al. I. Cuza". Iaşi, Facultatea de Matematică.
11. C. Amihăesei. Curs de cercetări operaţională. Universitatea Al. I. Cuza.
12. A. Stefanescu, C. Zidăroiu. Cercetări operaţionale. Bucureşti. 1981.
13. I. Nădejde, C. Bergthaller, C. Zidăroiu, S. Sburlan. Probleme de cercetare operaţională: Programare matematică. Editura academiei Republicii Socialiste România. Bucureşti. 1971.
14. В.Г.Карманов. Математическое программирование. M., Hayкa. 1975.
15. Ю.Б. Гермеер. Игры с непротивоположными интересами. М., Наука, 1976.
16. B.C. Taнaeв, B.B.Шкурба. Введение в теорию расписаний. М., Наука, 1975.
17. А.Ахоб Дж.Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.
18. Э.Рейгольд, Ю.Нивергельт, Н.Део. Комбинаторные алгоритмы: теория и практика. М., Мир, 1980.
19. С.В.Яблонский. Введение в дискретную математику. М., Наука, 1980.

Specialitatea

01.01.09 – Cibernetică matematică şi cercetări operaţionale