5 semester

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, 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