Náplň přednášek
Vybíráme v následujících témat:
1) Množiny, relace, funkce a základní početní metody. Algoritmy a jejich složitost. Metoda matematické indukce. Permutace a kombinace, binomické koeficienty a kombinatorické identity. Přerovnávání. Princip inkluze a exkluze.
2) Rekurentní vztahy. Použití, konstrukce a řešení rekurentních vztahů. Vytvořující funkce.
3) Dirichletův princip a jeho aplikace. Příklady grafů, definice.
4) Základní pojmy z teorie grafů a způsoby reprezentace grafů.
5) Komunikační sítě, nejkratší a nejširší cesty, jejich spolehlivost a toky v sítích. Bipartitní grafy. Stromy a kostry grafu. Prohledávání stromů - metody a algoritmy. Mosty a artikulace. Vrcholová a hranová souvislost grafů. Bloky. Konstrukce spolehlivých komunikačních sítí. Orientované a ohodnocené grafy. Sítě a toky v sítích. Řezy, věta o maximálním toku a minimálním řezu. Algoritmy na hledání maximálního toku v síti.
6) Planární a neplanární grafy. Rovinné a planární graf. Kritérium planarity grafu. Míra neplanarity grafu. Souvislost a navrhování obvodů.
7) Hlavní problém teorie kódování. Ekvivalence kódů, nutná a postačující podmínka existence (n, M, d) - kódů, Hammingova hranice, perfektní kódy.
8) Konečná tělesa a vektorové prostory. Ortogonální latinské čtverce, projektivní a afinní roviny.
9) Kódy a latinské čtverce. Latinské čtverce a vzájemně ortogonální latinské čtverce, užití latinských čtverců v kódování.
10) Základní pojmy teorie kombinatorických designů. Symetrické designy. Využití v teorii kódování.
11) Steinerovy systémy trojic. Konstrukce a vztah k faktorizaci grafů.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.
Vybíráme v následujících témat:
1) Množiny, relace, funkce a základní početní metody. Algoritmy a jejich složitost. Metoda matematické indukce. Permutace a kombinace, binomické koeficienty a kombinatorické identity. Přerovnávání. Princip inkluze a exkluze.
2) Rekurentní vztahy. Použití, konstrukce a řešení rekurentních vztahů. Vytvořující funkce.
3) Dirichletův princip a jeho aplikace. Příklady grafů, definice.
4) Základní pojmy z teorie grafů a způsoby reprezentace grafů.
5) Komunikační sítě, nejkratší a nejširší cesty, jejich spolehlivost a toky v sítích. Bipartitní grafy. Stromy a kostry grafu. Prohledávání stromů - metody a algoritmy. Mosty a artikulace. Vrcholová a hranová souvislost grafů. Bloky. Konstrukce spolehlivých komunikačních sítí. Orientované a ohodnocené grafy. Sítě a toky v sítích. Řezy, věta o maximálním toku a minimálním řezu. Algoritmy na hledání maximálního toku v síti.
6) Planární a neplanární grafy. Rovinné a planární graf. Kritérium planarity grafu. Míra neplanarity grafu. Souvislost a navrhování obvodů.
7) Hlavní problém teorie kódování. Ekvivalence kódů, nutná a postačující podmínka existence (n, M, d) - kódů, Hammingova hranice, perfektní kódy.
8) Konečná tělesa a vektorové prostory. Ortogonální latinské čtverce, projektivní a afinní roviny.
9) Kódy a latinské čtverce. Latinské čtverce a vzájemně ortogonální latinské čtverce, užití latinských čtverců v kódování.
10) Základní pojmy teorie kombinatorických designů. Symetrické designy. Využití v teorii kódování.
11) Steinerovy systémy trojic. Konstrukce a vztah k faktorizaci grafů.
V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.