PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
Kombinatorika a grafy 1 - NDMI011
Anglický název: Combinatorics and Graph Theory 1
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. RNDr. Vít Jelínek, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: T_KAM (06.05.2001)
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. Martin Koutecký, Ph.D. (28.09.2020)

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

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

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: RNDr. Pavel Zakouřil, Ph.D. (07.02.2017)
  • 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: doc. RNDr. Jiří Fiala, Ph.D. (14.02.2018)

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: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

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