|
|
|
||
Úvodní kurs, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po
strukturální, tak po algoritmické stránce. Doporučeno pro zaměření Matematické struktury na Obecné matematice
a pro obor MMIB.
Poslední úprava: G_M (16.05.2012)
|
|
||
V průběhu semestru bude zadáno několik sérií příkladů, přičemž k dosažení zápočtu je potřeba získat alespoň 20 bodů, což odpovídá zhruba čtvrtině celkového počtu dosažitelných bodů. Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru a příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce. Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (15.02.2018)
|
|
||
Literatura dle doporučení učitele. Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)
|
|
||
Zkouška je ústní, v nutných případech budu probíhat distančně přes internet. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce. Poslední úprava: Valtr Pavel, doc. RNDr., Dr. (11.02.2023)
|
|
||
Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí).
Odhady faktoriálu a binomických koeficientů.
Princip inkluze a exkluze a jeho aplikace (šatnářka).
Vytvořující funkce a jejich aplikace.
Konečné projektivní roviny, latinské čtverce a jejich ortogononalita.
Hallova věta a aplikace.
Toky v sítích.
k-souvislost grafů, Mengerovy věty pro (ne)orientovane grafy ve verzích pro vrcholy a hrany.
Základni Ramseyovy věty, věta pro p-tice, Schurova věta a další aplikace.
Poslední úprava: G_M (16.05.2012)
|