PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Základy kombinatoriky a teorie grafů - NMIN331
Anglický název: Foundations of Combinatorics and Graph Theory
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní 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
Způsob výuky: prezenční
Garant: doc. RNDr. Pavel Valtr, Dr.
Vyučující: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Pavel Valtr, Dr.
Třída: M Bc. MMIB
M Bc. MMIB > Doporučené volitelné
M Bc. OM
M Bc. OM > Zaměření MSTR
M Bc. OM > Povinně volitelné
Kategorizace předmětu: Informatika > Diskrétní matematika
Matematika > Diskrétní matematika
Neslučitelnost : NDMA001
Záměnnost : NDMA001
Je záměnnost pro: NDMA001
Ve slož. prerekvizitě: NMAG351
Anotace -
Úvodní kurs, 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. Doporučeno pro zaměření Matematické struktury na Obecné matematice a pro obor MMIB.
Poslední úprava: G_M (16.05.2012)
Podmínky zakončení předmětu -

V průběhu semestru bude zadáno několik sérií příkladů, přičemž k dosažení zápočtu je potřeba získat alespoň 20 bodů, což odpovídá zhruba čtvrtině celkového počtu dosažitelných bodů. Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru a příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (15.02.2018)
Literatura -

Literatura dle doporučení učitele.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (17.04.2013)
Požadavky ke zkoušce -

Zkouška je ústní, v nutných případech budu probíhat distančně přes internet. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce.

Poslední úprava: Valtr Pavel, doc. RNDr., Dr. (11.02.2023)
Sylabus -

Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí).

Odhady faktoriálu a binomických koeficientů.

Princip inkluze a exkluze a jeho aplikace (šatnářka).

Vytvořující funkce a jejich aplikace.

Konečné projektivní roviny, latinské čtverce a jejich ortogononalita.

Hallova věta a aplikace.

Toky v sítích.

k-souvislost grafů, Mengerovy věty pro (ne)orientovane grafy ve verzích pro vrcholy a hrany.

Základni Ramseyovy věty, věta pro p-tice, Schurova věta a další aplikace.

Poslední úprava: G_M (16.05.2012)
 
Univerzita Karlova | Informační systém UK