Optimization of Data Streams

Lecturer:

Marcel Jiřina (gar.)

Tutor:

Marcel Jiřina (gar.), Petr Hošek

Supervisor:

Department of Biomedical Informatics

Synopsis:

Introduction to data flows and their definitions. Networks and graphs. Optimization, and pseudoptimal solution, heuristics. Finding shortest paths in time-varying networks - problem formulation, NP-completeness, the question of time needed to find a solution. Minimum time-varying tree-graphs - Parallel networks, pseudopolynomial algorithm. The problem of finding maximum flow in time-varying network - max-flow min-cut algorithm. Optimizing the flow of prices in the network - (k,c)-flow problem. Finding paths in a network that has a maximum capacity. Finding paths in a network that is the fastest. Finding the best paths in the network when there is more criteria - MinSum-MinSum and MinSum-MinMax problem. Dynamic programming.

Requirements:

Students should have basic knowledge of higher mathematics, in particular, skills in operations with matrices and the basics of differential and integral calculus.

Syllabus of lectures:

1. Introduction to data flows and their definitions. Networks and graphs.

2. Optimization, and pseudo-optimal solution, heuristics.

3. Finding shortest paths in time-varying networks - problem formulation, NP-completeness, the question of time needed to find a solution.

4. Minimum time-varying tree-graphs - Parallel networks, pseudopolynomial algorithm.

5. The problem of finding maximum flow in time-varying network - max-flow min-cut algorithm.

6. Optimizing the flow of prices in the network - (k,c)-flow problem.

7. Finding paths in a network that has a maximum capacity.

8. Finding paths in a network that is the fastest

9. Finding the best paths in the network when there is more criteria - MinSum-MinSum and MinSum-MinMax problem.

10. Dynamic programming.

Syllabus of tutorials:

1. Introduction to data flows and their definitions. Networks and graphs.

2. Optimization, and pseudo-optimal solution, heuristics.

3. Finding shortest paths in time-varying networks - problem formulation, NP-completeness, the question of time needed to find a solution.

4. Minimum time-varying tree-graphs - Parallel networks, pseudopolynomial algorithm.

5. The problem of finding maximum flow in time-varying network - max-flow min-cut algorithm.

6. Optimizing the flow of prices in the network - (k,c)-flow problem.

7. Finding paths in a network that has a maximum capacity.

8. Finding paths in a network that is the fastest

9. Finding the best paths in the network when there is more criteria - MinSum-MinSum and MinSum-MinMax problem.

10. Dynamic programming.

Study Objective:

The aim of the study is to acquaint students with basic concepts and in particular with the algorithms of the graph theory. Students should acquire knowledge about finding the shortest (cheapest, fastest) paths in the network (graph) and be able to implement the algorithms.

Study materials:

[1] Bagley B. a kol.: Physician Quality Reporting Guide: Essentials of Data Collection, Work Flow Optimization and Physician Engagement for Practices, Healthcare Intelligence Network, 2008, ISBN: 1934647225

[2] Pardo R.: Design, Testing, and Optimization of Trading Systems, 1992, ISBN: 0471554464

[3] Manacapilli T.: Air Education and Training Command Cost and Capacity System: Implications for Organizational and Data Flow Changes, RAND Corporation, 2004, ISBN: 0833035037

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Bakalářský studijní obor Plánování a řízení krizových situací - prezenční (compulsory elective course)
• Bakalářský stud. obor Plánování a řízení krizových situací,zaměření Bezp. a krizový management (compulsory elective course)