|
1. |
Discipline |
Combinatorics and Operations Research |
|
2. |
Course Specialty |
3, Mathematics and Information Technologies (Web Programming and Internet Technologies) |
|
3. |
Semester |
5 |
|
4. |
Amount of credits |
2 |
|
5. |
Full name of the lecturer |
Buzulutskaya Hanna Nikolaevna |
|
6. |
Objectives of studying the discipline |
Investigation of basic methods of solving extremal problems in graph theory and linear programming. Increasing the professional competence level in solving optimization problems. Formation of students’ skills in abstract mathematical thinking and the ability of applying it to specific tasks. Improving students’ mathematical culture. After the study as a result a student should be able to: apply graph theory to practical problems; draw up network models; use methods of dynamic programming. |
|
7. |
Basis |
Mathematical analysis Algebra and Number Theory Optimization methods |
|
8. |
Main contant |
The emergence history of extreme problems of graph theory. Hamiltonian cycle.Problems of constructing a minimum spanning tree of a weighted graph. Prim’s algorithm and its correctness. Kruskal’s algorithm and its correctness. Directed graphs. The problem of finding the shortest path between two given vertices. Dijkstra’s algorithm. The problem of finding all shortest paths in the graph. Floyd algorithm. Finding the cycle of negative weight. Flow network, flow, s-t cut. Ford-Fulkerson Theorem (maximal flow criterion). The problem of finding a maximum flow. Ford-Fulkerson algorithm. The task of constructing a minimum-cost maximum flow. Basaker-Gowen algorithm for constructing a minimum-cost maximum flow. The traveling salesman problem. Littla algorithm. Branch-and-bound algorithm. Scheduling (project management). Statement of the problem, main stages of the solution. Building a network model, ranking, finding critical paths. Construction work schedule and distribution among team members. Timetable optimization. Dynamic programming: basic concepts and algorithms. Solution of traveling salesman problem using methods of dynamic programming. The problem of resource allocation. |
|
9. |
Recommended literature |
1. Bakhtin V.I., Kovalenya A.P., Lebedev A.V., Lysenko Yu. Operations Research. – Minsk, BSU, 2003. 2. Minieka E. Optimization algorithms for networks and graphs, 1978. 1977. 3. Basaker P., T. Saaty Finite graphs and networks. 1974.
|
|
10. |
Teaching Methods |
Lectures, practical lessons, … |
|
11. |
Language |
Russian |
|
12. |
Current control |
Tests |
|
13. |
Appraisal Form |
Credit |