PředmětyPředměty(verze: 996)
Předmět, akademický rok 2026/2027
   
Kombinatorika a grafy 1 - NDMI011
Anglický název: Combinatorics and Graph Theory 1
Podoba výuky: přednáška+cvičení
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023 do 2026
Počet semestrů výuky: 1
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Maximální kapacita předmětu: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Forma uskutečňování: prezenční
Možnost opakovaného zápisu: 2 / 2 / 2 / 2
Garant: doc. RNDr. Vít Jelínek, Ph.D.
prof. RNDr. Jiří Fiala, Ph.D.
Vyučující: Mgr. Eliška Červenková
prof. Mgr. Zdeněk Dvořák, Ph.D.
Mgr. Tomáš Hons
doc. RNDr. Vít Jelínek, Ph.D.
Bc. Volodymyr Kuznietsov
Mgr. David Mikšaník
Bc. Josef Tkadlec, Ph.D.
Bc. Adéla Karolína Žáčková
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMA001, NDMX011
Záměnnost : NDMX011
Je neslučitelnost pro: NDMI031, NDMX011
Je prerekvizitou pro: NDMI069, NDMI021, NDMI068, NPFL049
Je záměnnost pro: NDMA001, NDMI031, NDMX011
Anotace -
Základní kurs oboru oboru informatika, 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.
Poslední úprava: Maxová Jana, RNDr., Ph.D. (04.11.2026)
Podmínky zakončení předmětu -

Zápočet bude udělen za aktivní účast na cvičeních (přesný rozsah a konkrétní interpretaci aktivní účasti stanoví cvičící příslušného kroužku). Až dvě chybějící účasti je možné nahradit vyřešením zadaných domácích úkolů, jejichž řešení student osobně odprezentuje cvičícímu. V odůvodněných případech (zejména kombinované studium) je možné touto formou nahradit i více účastí. Zápočet je nutnou podmínkou účasti u zkoušky, přednášející může stanovit výjimku pro předtermíny.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Literatura -

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press (1998)

R. Diestel: Graph Theory (4th edition), Springer (2010)

Skripta https://iuuk.mff.cuni.cz/~rakdver/kg1/notes.pdf

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Kontroly studia předmětu a podmínky pro jejich úspěšné vykonání, způsob hodnocení -

Forma zkoušky je kombinovaná: písemná a ústní. Požadavky na znalosti u zkoušky odpovídají sylabu předmětu.

Je požadována i schopnost zobecnit a aplikovat získané teoretické znalosti při praktickém řešení úloh.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
Sylabus -
  • Vytvořující funkce. Použití v enumerativní kombinatorice a při řešení rekurencí, počítání binárních stromů, Catalanova čísla.
  • Asymptotické odhady v kombinatorice. Elementární analytické metody, odhady faktoriálu a koeficientů vytvořujících funkcí, entropické odhady.
  • Dvojí počítání a extremální kombinatorika. Kombinatorické identity a odhady, maximální počet hran grafů bez trojúhelníků a čtyřcyklů a další příklady.
  • Náhodné grafy a pravděpodobnostní metoda. Základní modely náhodných grafů a jejich vlastnosti, modelování reálných sítí.
  • Existenční důkazy pravděpodobnostní metodou, Ramseyova věta a odhady Ramseyových čísel.
  • Souvislost grafů. Hranová a vrcholová souvislost, Mengerova věta a její vztah k tokům v sítích.
  • Expandery a separátory. Expanze grafů a její souvislost s náhodnými grafy a s vlastními čísly matice sousednosti.
  • Párování v grafech. Párování největší velikosti v bipartitních grafech, stabilní párování.
  • Informační entropie a samoopravné kódy. Entropie a komprese dat, základní parametry samoopravných kódů, detekce a oprava chyb, kombinatorické meze pro parametry kódů, vybrané konstrukce (Hammingovy, Hadamardovy a Reedovy–Solomonovy kódy).

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
Výsledky učení -

Po absolvování předmětu student/studentka:

  • Sestaví vytvořující funkci pro jednoduchý kombinatorický problém, využije ji k řešení rekurence nebo enumerativní úlohy a odhadne růst vybraných kombinatorických posloupností.
  • Použije metodu dvojího počítání k odvození kombinatorických identit a jednoduchých extremálních odhadů, například pro maximální počet hran grafů s určitými zakázanými podgrafy.
  • V modelu náhodného grafu (G(n,p)) vypočte očekávaný počet vybraných podgrafů a na příkladech vysvětlí, jak se různé modely náhodných grafů liší svými vlastnostmi a možnostmi využití.
  • Vysvětlí tvrzení konečné Ramseyovy věty a použije pravděpodobnostní metodu k jednoduchému existenčnímu důkazu, například při odvozování dolních odhadů Ramseyových čísel.
  • Rozliší hranovou a vrcholovou souvislost grafu a použije Mengerovu a Hallovu větu při řešení jednoduchých úloh o disjunktních cestách, separátorech a párováních. Vysvětlí jejich souvislost s toky v sítích a rozliší úlohy hledání párování největší velikosti a stabilního párování.
  • Vysvětlí pojem expanze grafu a její důsledky pro existenci malých vyvážených separátorů a vztah s lineárně-algebraickými vlastnostmi matice souvislosti.
  • Vysvětlí vztah mezi informační entropií a možnostmi bezeztrátové komprese dat a na jednoduchém příkladu odhadne průměrnou délku prefixového kódu.
  • Z minimální Hammingovy vzdálenosti kódu určí jeho schopnost detekovat a opravovat chyby a pomocí základních kombinatorických mezí odhadne možné parametry samoopravných kódů.
  • Vysvětlí principy lineárních kódů a na příkladu vybrané algebraické konstrukce ukáže, jak lze vytvořit kód s požadovanou minimální vzdáleností. Porovná existenční výsledky s konkrétními konstrukcemi a vysvětlí význam efektivního kódování a dekódování.

Poslední úprava: Dvořák Zdeněk, prof. Mgr., Ph.D. (02.11.2026)
 
Univerzita Karlova | Informační systém UK