|
Lecturer(s)
|
-
Pěchota Jan, RNDr. Ph.D.
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Spectral and algebraic properties of graphs. 2. Hypergraphs. Hypermatrices. 3. Structural properties of graphs and digraphs. Edge-colored multigraphs. 4. Matroids. Graph algorithms and a bit of computational complexity. 5. Basic optimisation on networks. 6. Flows and circulations in networks. 7. Diffusion processes on graphs. Random walks on graphs. 8. Random graphs. 9. Large networks models. 10. Structural properties of networks. 11. Network dynamics. 12. Algorithms for dynamic networks. 13. Dynamic processes on networks. Applications.
|
|
Learning activities and teaching methods
|
Interactive lecture, Lecture, Practicum
- Contact hours
- 39 hours per semester
- Preparation for an examination (30-60)
- 40 hours per semester
- Preparation for comprehensive test (10-40)
- 25 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| znát pojem grafu |
| znát pojem algoritmu |
| ovládat vlastnosti elementárních funkcí |
| Skills |
|---|
| vyřešit jednoduché kombinatorické úlohy |
| využívat jednoduché datové struktury |
| vyšetřit průběh funkce |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| popsat algoritmy řešení vybraných grafových úloh |
| popsat algoritmy řešení základních úloh kombinatorické optimalizace |
| ovládat základní pojmy výpočetní složitosti |
| Skills |
|---|
| aplikovat algoritmy k řešení vybraných grafových úloh |
| použít vhodné algoritmy k řešení základních úloh kombinatorické optimalizace |
| posoudit výpočetní složitost vybraných optimalizačních úloh |
| zvolit vhodnou heuristickou metodu pro jednoduché optimalizační úlohy |
| Competences |
|---|
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Interactive lecture |
| Skills |
|---|
| Interactive lecture |
| Practicum |
| Competences |
|---|
| Lecture |
| Practicum |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Skills |
|---|
| Oral exam |
| Written exam |
| Competences |
|---|
| Oral exam |
| Written exam |
|
Recommended literature
|
-
Andrásfai, B. Graph Theory - Flows, Matrices. Budapest, 1991.
-
Barabási, A.-L. Network Science. Cambridge University Press, 2016. ISBN 978-1107076266.
-
Barabási, Albert-László,; Watts, Duncan J.,; Newman, M. E. J. The structure and dynamics of networks. Princeton : Princeton University Press, 2006. ISBN 0-691-11357-2.
-
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
Fiedler, Miroslav. Speciální matice a jejich použití v numerické matematice. Vyd. 1. Praha : SNTL, 1981.
-
Gibbons, Alan. Algorithmic graph theory. Cambridge : Cambridge University Press, 1994. ISBN 0-521-28881-9.
-
Jackson, M.O. Social and Economic Networks. Princeton University Press, 2010. ISBN 978-0691148205.
-
Lesniak, L.; Chartrand, G.; Zhang, P. Graphs and Digraphs. Chapman and Hall/CRC, 2015. ISBN 978-1498735766.
-
Mareš, M.; Valla. Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-22-5.
-
Matoušek, J.; Nešetřil, J. Kapitoly z diskrétní matematiky. Karolinum, 2009. ISBN 978-80-246-1740-4.
-
Newman, M. Networks. Oxford University Press, 2018. ISBN 978-0198805090.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
|