BI-VAK: Vybrané aplikace kombinatoriky

Semestr
letní
Zakončení
zápočet
Hodinová dotace
2 hodiny prosemináře/týden
Vyučující
Šimon Schierreich (schiesim@fit.cvut.cz), Václav Blažej, Dušan Knop, Ondřej Suchý, Tomáš Valla

Náplní semináře je přehlídka těch nejelegantnějších problémů a témat z algoritmů, teorie her, teoretické informatiky, diskrétní matematiky, kombinatoriky a mnoha dalších. Kromě toho budeme přemýšlet nad zajímavými problémy a společně je řešit. Například:

Seminář je určen hlavně pro nové studenty, kteří chtějí získat rozhled v oboru teoretické informatiky, teorie grafů, kombinatoriky a chtějí se dozvědět něco o aproximací, online algoritmech a dalších.

Řecký hrdina Herkules bojoval s příšerou Hydrou Lernskou, i když to měl dost těžké – v κ-tém tahu hry Herkules utne jednu hlavu a Hydře ihned naroste κ kopií příslušného krku, i s případnými dalšími hlavami. Jak má Herkules porazit Hydru? A proč mu vlastně nic jiného nezbývá? A proč k tomu nutně potřebuje ovládat nekonečnou matematiku?
image/svg+xml programy SAT P vs NP Aproximace her grafů Lineární Teorie Kreslení BI-VAK

Předběžný plán témat

  1. Problémy šatnářek a vodníků
  2. Číselné problémy
  3. Grafové problémy
  4. Geometrie a kreslení grafů
  5. Řešení manželských problémů
  6. Hry jednoho až dvou hráčů
  7. Jak nakrájet dort
  8. Nepřesná řešení těžkých úloh
  9. On-line algoritmy
  10. Problémy vhodné pro obecné řešiče – SAT
  11. Problémy vhodné pro obecné řešiče – LP a ILP
  12. Alternativní výpočetní modely
  13. Paralelní algoritmy