|
|
Main menu for Browse IS/STAG
Course info
KMA / TSI
:
Course description
Department/Unit / Abbreviation
|
KMA
/
TSI
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Network Theory
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
4
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
2
[Hours/Week]
Tutorial
1
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
Czech, English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
6 / -
|
0 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
1
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech, English
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KMA/TGD1
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KMA/DMA or KMA/DMB
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The goal is to introduce advanced graph theory, respective algorithms and methods for studying structure and dynamics of networks. The course is aimed at mathematical heart of the matter.
|
Requirements on student
|
Credit: project.
Exam: written and oral part.
|
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.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
-
Basic:
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
Basic:
Lesniak, L.; Chartrand, G.; Zhang, P. Graphs and Digraphs. Chapman and Hall/CRC, 2015. ISBN 978-1498735766.
-
Basic:
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
-
Basic:
Mareš, M.; Valla. Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-22-5.
-
Basic:
Fiedler, Miroslav. Speciální matice a jejich použití v numerické matematice. Vyd. 1. Praha : SNTL, 1981.
-
Basic:
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.
-
Extending:
Jackson, M.O. Social and Economic Networks. Princeton University Press, 2010. ISBN 978-0691148205.
-
Recommended:
Gibbons, Alan. Algorithmic graph theory. Cambridge : Cambridge University Press, 1994. ISBN 0-521-28881-9.
-
Recommended:
Andrásfai, B. Graph Theory - Flows, Matrices. Budapest, 1991.
-
Recommended:
Matoušek, J.; Nešetřil, J. Kapitoly z diskrétní matematiky. Karolinum, 2009. ISBN 978-80-246-1740-4.
-
Recommended:
Barabási, A.-L. Network Science. Cambridge University Press, 2016. ISBN 978-1107076266.
-
Recommended:
Newman, M. Networks. Oxford University Press, 2018. ISBN 978-0198805090.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
39
|
Preparation for comprehensive test (10-40)
|
25
|
Preparation for an examination (30-60)
|
40
|
Total
|
104
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
znát pojem grafu |
znát pojem algoritmu |
ovládat vlastnosti elementárních funkcí |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
vyřešit jednoduché kombinatorické úlohy |
využívat jednoduché datové struktury |
vyšetřit průběh funkce |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
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 - skills resulting from the course: |
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 - competences resulting from the course: |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Oral exam |
Skills - skills achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Interactive lecture |
Skills - the following training methods are used to achieve the required skills: |
Interactive lecture |
Practicum |
Competences - the following training methods are used to achieve the required competences: |
Lecture |
Practicum |
|
|
|
|