Základy kombinatoriky a teorie grafů (NMIN331) - cvičení


Cvičení probíhá každou středu od 10:40 v učebně K9.

Cvičení povede Martin Balko. E-mail cvičícího: balko (AT) kam.mff.cuni.cz

Stránky přednášejícího.


Podmínky získání zápočtu:
  • Získání alespoň 20 bodů.
  • V průběhu semestru zadám několik sérií příkladů, kde každý příklad bude ohodnocen určitým počtem bodů podle obtížnosti. Všechny úlohy (domácí i ty řešené na cvičeních) budou dostupné zde na webu.
  • Termín pro vyřešení a sepsání úkolů bude zhruba do konce semestru, ale vyplatí se řešení odevzdávat průběžně.
  • Příklady je možné odevzdávat opakovaně, vždy se počítá nejlepší dosažený výsledek.
  • Účast na cvičeních je nepovinná.
  • Z důvodu ochrany osobních údajů u prvních odevzdaných řešení napište kromě jména i přezdívku, pod kterou chcete mít své body zveřejněny na webu. U dalších řešení už stačí psát buď jméno, nebo přezdívku. Pokud jste první sérii úkolů odevzdali jen pod svým jménem, bude uveřejněno na webu. Pokud Vám to nevyhovuje, napište mi email s přezdívkou a já to změním.
  • Aktuální seznam bodů:
Přezdívka:  1   2   3   4a   4b   5   6   7a   7b   8   9   10   11   12   13   14   15   Součet   Zápočet 
 Maxim Dokonalý  3 3 2 2 3 2 3 2 2 2 3 2 2 3 2 3 3 42 ---
  Erhart   3 3
  Sépiak   1.5 3 3 2 2 1 2 3 3 20.5 ANO
  Radon   2.5 2 2 1.5 2 2 2 1.5 2 2 3 22.5 ANO
Oříšek   1 3 2 2.5 2 3 2 2 2 2 21.5 ANO
  Šplíchal   3 3 2 3 2 2 3 3 21 ANO
   
  • Zadání domácích úkolů: [PDF] (poslední aktualizace 10.5.2016)

Jednotlivá cvičení:
  • První cvičení (24.2.2016): Úvod, podmínky zápočtu, opakování z teorie grafů. Probrány příklady 1, 2, 3 a 5. Seznam příkladů ze cvičení [PDF].
  • Druhé cvičení (2.3.2016): Opakování z teorie grafů podruhé. Probrány příklady 1, 2, 3 a 7. Seznam příkladů ze cvičení [PDF].
  • Třetí cvičení (9.3.2016): Toky v sítích. Probrány příklady 1, 2, 3, 4 a 5, ukázán příklad sítě, na které selže Ford-Fulkersonův algoritmus. Seznam příkladů ze cvičení [PDF].
  • Čtvrté cvičení (16.3.2016): Aplikace Hallovy věty. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Páté cvičení (23.3.2016): Grafová souvislost. Probrány příklady 1, 2, 3a a 3b. Seznam příkladů ze cvičení [PDF].
  • Šesté cvičení (30.3.2016): Grafová souvislost podruhé. Cvičení vedl Pavel Valtr.
  • Sedmé cvičení (6.4.2016): Rovinné grafy. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Osmé cvičení (13.4.2016): Ramseyova teorie. Probrány příklady 1, 2 a 3. Seznam příkladů ze cvičení [PDF].
  • Deváté cvičení (20.4.2016): Ramseyova teorie podruhé. Probrány příklady 1a, 1b, 2 a 5. Seznam příkladů ze cvičení [PDF].
  • Desáté cvičení (27.4.2016): Vytvořující funkce - úvod. Probrány příklady 1, 2, 3a, 3b, 3d, 4a, 5 a 6. Seznam příkladů ze cvičení [PDF].
  • Jedenácté cvičení (4.5.2016): Cvičení se nekonalo (Rektorský den).
  • Dvanácté cvičení (11.5.2016): Vytvořující funkce - aplikace. Probrány příklady 1, 2, 3, 4 a 5. Seznam příkladů ze cvičení [PDF].
  • Třinácté cvičení (18.5.2016): Hamiltonovské kružnice. Probrány příklady 1, 3, 4 a část 5. Seznam příkladů ze cvičení [PDF].
  • Čtrnácté cvičení (25.5.2016): NP-úplnost polynomiální převoditelnost. Probrán příklad 1, definice Turingova stroje. Seznam příkladů ze cvičení [PDF].

Valid XHTML 1.0 Transitional