PředmětyPředměty(verze: 962)
Předmět, akademický rok 2024/2025
   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.
Vyučující: doc. RNDr. Martin Balko, Ph.D.
doc. RNDr. Vít Jelínek, Ph.D.
Bc. Jiří Kalvoda
Bc. Václav Lepič
Mgr. David Mikšaník
Bc. Josef Tkadlec, Ph.D.
Hadi Zamani, M.Sc.
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: T_KAM (06.05.2001)
Podmínky zakončení předmětu -

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.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (06.09.2023)
Literatura -

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

Poslední úprava: Fiala Jiří, doc. RNDr., Ph.D. (26.09.2023)
Požadavky ke zkoušce -

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 -

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.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (04.10.2023)
 
Univerzita Karlova | Informační systém UK