|
Lecturer(s)
|
-
Kadavý Tomáš, Ing.
-
Šenkeřík Roman, prof. Ing. Ph.D.
|
|
Course content
|
- Modern informatics approaches to solving mathematical and optimization problems. Soft-computing vs. Hard-computing, Heuristic algorithms, Classification of heuristics. Point-based and population-based strategies. - Definition of objective function as a mathematical model of an optimization problem, arguments, constraints. Test functions for benchmarking of algorithms. - Multicriteria optimization, Pareto sets. Manycriteria optimization, including dynamic tasks. - Point-based heuristics I: Local Search, Random Search / Random Walk, Hill Climber. - Point-based heuristics II: Taboo Search, Simulated annealing. - Introduction to operational research. Problem complexity and transferability: Complexity classes, P, NP, NPC problems. - Permutation and combinatorial problems and their solutions I: Bin packing problem, the knapsack problem, traveling salesman problem, vehicle routing problem. - Permutation and combinatorial problems and their solutions II: Assignment problems, problems of production planning and data processing. - Formal models of computation, automata, machines, complexity, cellular automata and their applications. - Graphs and graph algorithms. - Complex networks and their analysis. - Generating random numbers.
|
|
Learning activities and teaching methods
|
|
Lecturing, Exercises on PC
|
| prerequisite |
|---|
| Knowledge |
|---|
| Knowledge from areas: Mathematics Teoretical Informatics Programming Optimization |
| Knowledge from areas: Mathematics Teoretical Informatics Programming Optimization |
| learning outcomes |
|---|
| The student can enumerate and define various types of optimization algorithms, including their properties and heuristic approaches. |
| The student can enumerate and define various types of optimization algorithms, including their properties and heuristic approaches. |
| The student understands the basic concepts of operations research, including complexity classes of problems such as P, NP, and NPC. |
| The student understands the basic concepts of operations research, including complexity classes of problems such as P, NP, and NPC. |
| The student has knowledge about algorithmic solvability of problems and basic search algorithms. |
| The student has knowledge about algorithmic solvability of problems and basic search algorithms. |
| The student can describe the principles of cellular automata and basic graph algorithms. |
| The student can describe the principles of cellular automata and basic graph algorithms. |
| The student understands the principles of complex networks and has knowledge about multi-criteria optimization, including Pareto sets. |
| The student understands the principles of complex networks and has knowledge about multi-criteria optimization, including Pareto sets. |
| Skills |
|---|
| The student can apply various heuristic algorithms to solve complex optimization problems. |
| The student can apply various heuristic algorithms to solve complex optimization problems. |
| The student can create and use objective functions for testing and benchmarking algorithms. |
| The student can create and use objective functions for testing and benchmarking algorithms. |
| The student is capable of designing solutions for various permutation and combinatorial problems, including stack filling problems and traveling salesman problems. |
| The student is capable of designing solutions for various permutation and combinatorial problems, including stack filling problems and traveling salesman problems. |
| The student has the skill to analyze and model complex networks. |
| The student has the skill to analyze and model complex networks. |
| The student can implement algorithms specifically designed for multi-criteria optimization, focusing on effective problem-solving and balancing different decision criteria. |
| The student can implement algorithms specifically designed for multi-criteria optimization, focusing on effective problem-solving and balancing different decision criteria. |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecturing |
| Exercises on PC |
| Lecturing |
| Exercises on PC |
| assessment methods |
|---|
| Written examination |
| Oral examination |
| Oral examination |
| Written examination |
|
Recommended literature
|
-
Demel J. Grafy a jejich aplikace. Academia, 2002.
-
Dreo J. Metaheuristics for hard optimization: methods and case studies. Berlin, 2006. ISBN 9783540230229.
-
Ilachinski, Andrew. Cellular automata : a discrete universe. 1st pub. Singapore : World Scientific, 2001. ISBN 981-238-183-X.
-
Koubková A., Pavelka J. Uvod do teoretické informatiky. Matfyzpress, 2003.
-
Kučera L. Kombinatorické algoritmy. Praha, 1983.
-
Linz, Peter. An introduction to formal languages and automata. 4th ed. Sudbury, Mass. : Jones and Bartlett Publishers, 2006. ISBN 0-7637-3798-4.
-
Naim B.E. Complex Networks. Springer, 2004. ISBN 13: 978-354022354.
-
Nešetřil J. Teorie grafů. MS, Praha, 1979.
-
Vaníček J., Papík M., Pregl R., Vaníček T. Teoretické základy informatiky. Alfa Publishing, 2006.
-
Zelinka I. Handbook of optimization: from classical to modern approach. Berlin, 2013. ISBN 9783642305030.
|