PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   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 2023
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: 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
Způsob výuky: prezenční
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
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: doc. RNDr. Vít Jelínek, Ph.D. (06.09.2023)

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. Maximální možný počet bodů, které lze získat, je zhruba 150. Konkrétní pravidla pro zisk zápočtu stanoví cvičící příslušného kroužku.

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: doc. RNDr. Jiří Fiala, Ph.D. (26.09.2023)

L. Kučera: Kombinatorické algoritmy

J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky

J. Nešetřil: Teorie grafů

Videozáznamy přednášek

Některá kombinatorická témata pokrývají online dostupná skripta A. Slavík: Kombinatorika

Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (06.09.2023)

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. Vít Jelínek, Ph.D. (04.10.2023)

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

Počet koster grafu.

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