Course: Network Theory

« Back
Course title Network Theory
Course code KMA/TSI
Organizational form of instruction Lecture + Tutorial
Level of course Bachelor
Year of study 3
Semester Summer
Number of ECTS credits 4
Language of instruction Czech
Status of course Compulsory, Compulsory-optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Čada Roman, Doc. Ing. Ph.D.
  • Tomiczková Světlana, RNDr. Ph.D.
Course content
* basic graph theory terminology * graph matrix description - algebraic properties - Kirchhoff's laws * weighted graphs * flows - Ford-Fulkerson theorem - optimal flows * basic graph problems solvable in polynomial time - min spanning tree - distance - connectivity - Eulerian graphs - acyclic graphs - CPM * introduction to complexity theory - basic terminology - polynomiality - NPC - basic NP-complete problems

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
professional knowledge
znát pojem grafu
znát pojem algoritmu
ovládat vlastnosti elementárních funkcí
professional skills
vyřešit jednoduché kombinatorické úlohy
využívat jednoduché datové struktury
vyšetřit průběh funkce
general eligibility
N/A
learning outcomes
professional 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
professional 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
general eligibility
N/A
teaching methods
professional knowledge
Lecture
Interactive lecture
professional skills
Interactive lecture
Practicum
general eligibility
Lecture
Practicum
assessment methods
professional knowledge
Oral exam
professional skills
Oral exam
Written exam
general eligibility
Oral exam
Written exam
Recommended literature
  • Andrásfai, B. Graph Theory - Flows, Matrices. Budapest, 1991.
  • Gibbons, Alan. Algorithmic graph theory. Cambridge : Cambridge University Press, 1994. ISBN 0-521-28881-9.
  • Holenda, Jiří; Ryjáček, Zdeněk. Lineární algebra II : úvod do diskrétní matematiky. 1. vyd. Plzeň : ZČU, 1992. ISBN 80-7082-060-8.
  • Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
  • Vágó, I. Graph Theory - Application to the Calculation of Electrical Networks. Budapest, 1985.


Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Applied Sciences Financial Informatics and Statistics (2016) Economy 2 Summer
Faculty of Applied Sciences Financial Informatics and Statistics (1) Economy 2 Summer
Faculty of Applied Sciences Financial Informatics and Statistics (2016) Economy 2 Summer
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 3 Summer
Faculty of Applied Sciences General Mathematics (2012) Mathematics courses 3 Summer
Faculty of Education Studies in Mathematics (1) Mathematics courses 3 Summer
Faculty of Electrical Engineering Telecommunication and Multimedia Systems (12) Electrical engineering, telecommunication and IT 1 Summer
Faculty of Applied Sciences Mathematics for Business Studies (2011) Mathematics courses 2 Summer
Faculty of Applied Sciences Mathematics and its Applications (2017) Mathematics courses 3 Summer
Faculty of Applied Sciences Mathematics and its Applications (2017) Mathematics courses 3 Summer
Faculty of Applied Sciences Mathematics and its Applications (2015) Mathematics courses 3 Summer
Faculty of Applied Sciences Mathematics and its Applications (2016) Mathematics courses 3 Summer
Faculty of Education Studies in Mathematics (15) Mathematics courses 3 Summer
Faculty of Applied Sciences Financial Informatics and Statistics (2017) Economy 2 Summer
Faculty of Applied Sciences Mathematics and Management (2011) Mathematics courses 2 Summer
Faculty of Applied Sciences Financial Informatics and Statistics (2017) Economy 2 Summer
Faculty of Education Studies in Mathematics (14) Mathematics courses 3 Summer
Faculty of Education Studies in Mathematics (13) Mathematics courses 3 Summer
Faculty of Applied Sciences Mathematics and its Applications (2015) Mathematics courses 3 Summer
Faculty of Applied Sciences Mathematics and its Applications (2016) Mathematics courses 3 Summer
Faculty of Applied Sciences Financial Informatics and Statistics (2007) Economy 2 Summer