Popis předmětu - AE4M77KO

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
AE4M77KO Combinatorial Optimization
Role:  Rozsah výuky:3P+2C
Katedra:13135 Jazyk výuky:EN
Garanti:  Zakončení:Z,ZK
Přednášející:  Kreditů:6
Cvičící:  Semestr:L

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start

Anotace:

The goal is to show the problems and algorithms of combinatorial optimization (often called discrete optimization; there is a strong overlap with the term operations research). Following the courses on linear algebra, graph theory, and basics of optimization, we show optimization techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods.

Osnovy přednášek:

1. Introduction of Basic Terms of Combinatorial Optimization, Example Applications and Test on Preliminary Knowledge
2. Integer Linear Programming - Algorithms
3. Problem Formulation by Integer Linear Programming
4. Heuristics, Test
5. Shortest Paths
6. Network Flows and Cuts
7. Multicommodity network flows
8. Dynamic Programming, Test
9. Knapsack Problem and Pseudo-polynomial Algorithms
10. Traveling Salesman Problem and Approximation Algorithms
11. Monoprocessor Scheduling
12. Scheduling on Parallel Processors
13. Project Scheduling with Time Windows
14. Constraint Programming

Osnovy cvičení:

1. Introduction to the Experimental Environment and Optimisation library
2. Integer Linear Programming
3. Applications of Integer Linear Programming
4. Assignment of Term Projects
5. Branch and Bound Technique
6. Shortest Paths
7. Applications of Network Flows and Cuts
8. Presentation of Term Projects
9. Monoprocessor Scheduling - Earliest Deadline First
10. Approximation Algorithms - List Scheduling
11. Reserved
12. Test
13. Giving over Term Projects
14. Credits

Literatura:

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, third ed., 2006.
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.

Požadavky:

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6c

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr

Stránka vytvořena 14.3.2025 14:51:17, semestry: Z,L/2025-6, Z,L/2024-5, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. RNDr. Veronika Sobotíková, CSc.