PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   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 2016 do 2016
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: RNDr. Martin Tancer, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
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.
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
Sylabus -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (04.05.2015)

  • 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