PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Kombinatorika a grafy 1 - NDMX011
Anglický název: Combinatorics and Graph Theory 1
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: zrušen
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Vít Jelínek, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
doc. Andreas Emil Feldmann, Dr.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMA001, NDMI011
Záměnnost : NDMI011
Je neslučitelnost pro: NDMI011
Je záměnnost pro: NDMI011
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: Mgr. Petr Jedelský (22.08.2019)
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.
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Petr Jedelský (22.08.2019)

Zápočet je nutnou podmínkou účasti u zkoušky.

Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod.

Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadávání opravných domácích úloh.

Literatura -
Poslední úprava: Mgr. Petr Jedelský (22.08.2019)
  • Kučera: Kombinatorické algoritmy
  • Matoušek, Nešetřil: Kapitoly z diskrétní matematiky
  • Nešetřil: Teorie grafů
  • Videozáznamy přednášek
Požadavky ke zkoušce -
Poslední úprava: Mgr. Petr Jedelský (22.08.2019)

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.

Sylabus -
Poslední úprava: Mgr. Petr Jedelský (22.08.2019)

Dvojí počítání: Spernerova věta, Maximální počet hran grafu bez K4 a bez K3.

Počet koster grafu (determinantový důkaz) a elektrické sítě.

Vytvořující funkce (chápané jako Taylorovy řady), aplikace: Catalanova, Fibonacciho čísla, řešení rekurenci, asymptotika rekurencí.

Konečné projektivní roviny.

Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódů (Gilbert-Varshamov). Hammingův dolní odhad.

Maximální párování v grafech, Hallova věta a aplikace (Birkhoff-von Neumannova věta), Tutteho věta.

k-souvislost, Mengerovy věty. Ušaté lemma, struktura 2-souvislých grafů.

Základní Ramseyovy věty, Ramseyova věta pro p-tice, nekonečná Ramseyova věta.

Königova věta o nekonečné větvi.

 
Univerzita Karlova | Informační systém UK