PředmětyPředměty(verze: 825)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Kombinatorika a grafy I - NDMI011
Anglický název: Combinatorics and Graph Theory I
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017 do 2017
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
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.
Andreas Emil Feldmann, Dr.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMA001
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. Jiří Fiala, Ph.D. (14.02.2018)

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: 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)

  • 1 Odhady faktoriálu a binomických koecientů
  • 1 Počet koster úplneho grafu (nedeterminantový důkaz).
  • 1.5 Vytvořující funkce (chápané jako Taylorovy řady), aplikace
  • 1.5 Konečné projektivní roviny, latinské čtverce, jejich ortogonalita.
  • 1 Dvojí počítání - počet koster Kn-e, Spernerova věta
  • 1 Toky v sítích (minimaxová věta).
  • 1 Hallova věta a aplikace (Birkhoff-von Neumannova věta, doplňování latinských čtvercù). Maximální párování v bipartitním grafu.
  • 1 k-souvislost, Mengerovy věty pro (ne)orientované grafy ve verzích pro vrcholy a hrany.
  • 0.5 Ušaté lemma, struktura 2-souvislých grafù.
  • 1.5 Základní Ramseyovy věty, Ramsey pro p-tice, Schurova věta.
  • 2 Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódù (Gilbert-Varshamov). Hammingův a Elias-Bassalygův dolní odhad.

Rozšiřující témata: Steinerovy systémy trojic. Maximální počet hran grafu bez K4 a bez K3.

 
Univerzita Karlova | Informační systém UK