1. 
Discipline 
Combinatorics and Operations Research 
2. 
Course Specialty 
3, Mathematics and Information Technology (mathematical and software of mobile devices) 
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, st cut. FordFulkerson Theorem (maximal flow criterion). The problem of finding a maximum flow. FordFulkerson algorithm. The task of constructing a minimumcost maximum flow. BasakerGowen algorithm for constructing a minimumcost maximum flow. The traveling salesman problem. Littla algorithm. Branchandbound 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 