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:
- Jak programovat pomocí dlaždiček v koupelně?
- Proč druhý hráč v piškvorkách nikdy nemůže vyhrát? A proč i přesto nejsou piškvorky nuda?
- Jak nám matematika může pomoci nakrájet dort, vytvořit stabilní manželství či vybrat sekretářku?
- Proč se mnoho jednoduchých her dá vyřešit pomocí operace XOR?
- Jak pomocí návrhu optimálního jídelníčku vyřešit <doplň svůj oblíbený problém>?
- Jak s malou chybou řešit rozumně velké instance těžkých problémů?
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?
Předběžný plán témat
- Problémy šatnářek a vodníků
- Číselné problémy
- Grafové problémy
- Geometrie a kreslení grafů
- Řešení manželských problémů
- Hry jednoho až dvou hráčů
- Jak nakrájet dort
- Nepřesná řešení těžkých úloh
- On-line algoritmy
- Problémy vhodné pro obecné řešiče – SAT
- Problémy vhodné pro obecné řešiče – LP a ILP
- Alternativní výpočetní modely
- Paralelní algoritmy