Logo ČVUT
Loading...
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025
Fakulty | Celoškolská nabídka volitelných předmětů | Katalog předmětů ECTS | Nastavení | English version
Úvodní stránka > Fakulta informačních technologií > katedra teoretické informatiky > Vybrané aplikace kombinatoriky

Vybrané aplikace kombinatoriky

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-VAK.21 Z 3 2R česky
Garant předmětu:
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Viz https://ggoat.fit.cvut.cz/bi-vak/index.html

Předmět si klade za cíl představit studentům přístupnou formou různá odvětví teoretické informatiky a kombinatoriky. K problematice, na rozdíl od základních kurzů, přistupujeme od aplikací k teorii. Společně si tak nejdříve osvěžíme základní znalosti potřebné k návrhu a analýze algoritmů a představíme si některé základní datové struktury. Dále se budeme, za aktivní účasti studentů, věnovat řešení populárních a snadno formulovatelných úloh z různých oblastí (nejen teoretické) informatiky. Mezi oblasti, ze kterých budeme vybírat problémy k řešení, bude patřit například teorie grafů, kombinatorická a algoritmická teorie her, aproximační algoritmy, optimalizace a další. Studenti si také prakticky vyzkouší implementaci řešení studovaných problémů se speciálním zaměřením na efektivní využití existujících nástrojů.

Požadavky:

Předpokládáme, že student ovládá znalosti získané v předmětech Diskrétní matematika a logika (BI-DML) a Programování a algoritmizace 1 (BI-PA1).

Osnova přednášek:

1. Problémy šatnářek a vodníků: Přes problém šatnářky a problém vodníků vhodně navážeme a dále rozšíříme některé vybrané znalosti ze základního kurzu BI-DML. Tyto znalosti budeme dále využívat ve zbytku kurzu. Důležitým pojmem v celém zbytku kurzu bude také důkaz, ukážeme si tedy příklady nějakých důkazů, které vypadají zdánlivě správně, ale ve skutečnosti neplatí.

2. Číselné problémy: Věnovat se budeme zajímavým problémům z diskrétní matematiky, jako je například snídaňový problém, CSP, Spernerovo lemma a jeho aplikace, problém Herkula a hydry a podobné.

3. Grafové problémy: Představíme si úlohy, které lze řešit pomocí teorie grafů, ale vytvoření grafového modelu se pro tyto úlohy může zdát neintuitivní. Příkladem takového problému je například odměřování pomocí nádob, rekonstrukce průchodu tunelem a mnohé další.

4. Geometrie a kreslení grafů: Cílem hodiny je seznámit studenta se základními problémy výpočetní geometrie, které s sebou nesou mnoho problémů v podobě práce s reálnými čísly. Ukážeme si, jak se podobné problémy dají řešit a seznámíme se s tím, proč je zajímavé umět graf pěkně nakreslit.

5. Řešení manželských problémů: Stable marriage problem je základním problémem v teorii párování. Úkolem je najít mezi stejně velkými skupinami (heterosexuálních) mužů a žen přiřazení do manželských svazků takové, které co nejvíce odpovídá jejich preferencím, tedy žádná dvojice nebude mít tendenci toto manželství opustit. Zmíněný problém má mnoho zobecnění, ať už v podobě stable roommate problému, případně ve hrách věnujících se tvorbě koalic. Za práci na tomto poli byla L. S. Shapleymu a A. E. Rothovi dokonce udělena Nobelova cena.

6. Hry jednoho až dvou hráčů: Představíme si jednoduché kombinatorické hry, jako je například Nim, Toads and Frogs, Tic-Tac-Toe. Tyto jednoduché hry vhodně zobecníme a ukážeme si některé vybrané vlastnosti složitějších her, jako jsou například šachy, Shannonovo číslo, Go, Game of Life, Poker.

7. Krájení dortu: V rámci hodiny dojde k představení základních problémů teorie férového dělení. Ta se zabývá férovým dělením nějakého statku mezi hráče a nachází mnoho aplikací v problémech reálného světa. Problematika bude ilustrována na příkladu problému krájení dortu — tzv. Cake-Cutting Problem

8. Nepřesná řešení těžkých úloh: Na příkladu problému výběru sekretářky si ukážeme, jakým způsobem lze řešit problémy, které jsou za předpokladu platnosti hypotézy P != NP pro velké instance považovány za algoritmicky neřešitelné. Ukážeme si, jak pro podobné úlohy hledat řešení, které sice není to nejlepší možné, nicméně od nejlepšího výsledku se v nejhorším případě liší o předem známý konstantní faktor. Jiné řešení podobných neřešitelných úloh spočívá ve vytvoření algoritmů typu Monte-Carlo, Las Vegas a další.

9. On-line algoritmy U většiny představených algoritmů známe celý vstup již na začátku výpočtu. V mnoha praktických úlohách ale informace o vstupu dostáváme postupně a musíme na změny či dodatečné informace o vstupu pružně reagovat. V průběhu lekce si tak na příkladu problému řazení a sekretářky ukážeme, jak takové algoritmy fungují, jak je navrhovat a použít. V neposlední řadě budeme také diskutovat, zda pro každý off-line algoritmus existuje jeho on-line protějšek, a vysvětlíme si, co to znamená kompetetivní on-line algoritmus.

10. Problémy vhodné pro obecné řešiče – SAT: Seznámit studenty s problémem splnitelnosti a jeho variantami. SAT je prominentní problém celé informatiky, který je, mimo jiné, základem celé teorie složitosti. Na jednu stranu se po teoretické stránce pro větší instance jedná o neřešitelný problém, na druhou stranu ale existuje mnoho velice dobře optimalizovaných komerčních i open-source řešičů, které mnoho úloh dokáží spočítat velice rychle. Proto si studenti prakticky vyzkouší, jak lze redukovat některé výpočetní problémy na problém splnitelnosti a získat tak relativně efektivní algoritmus bez nutnosti vymýšlení a implementace složitého algoritmu. Student se také dozví, jak redukovatelnost souvisí s příslušností problému do třídy složitosti NP.

11. Problémy vhodné pro obecné řešiče – LP a ILP: Seznámit studenty s teorií lineárního programování a s jeho celočíselnou variantou. Dále si studenti prakticky vyzkouší, jak lze vyjádřit některé výpočetní problémy jako (celočíselné) lineární programy. Takto vyjádřené problémy následně vyřešíme v nějakém volně dostupném řešiči LP. Student se také dozví, jak redukovatelnost souvisí s příslušností problému do třídy složitosti NP.

12. Alternativní výpočetní modely: Krom standardního výpočetního modelu RAM lze provádět výpočty i na dalších výpočetních modelech. Hezkým příkladem mohou být kupříkladu komparátorové sítě, případně kachlíkovací model. Cílem hodiny je tedy představit tyto modely výpočtu a ukázat jejich (omezenou) sílu.

13. (rezerva) Paralelní algoritmy Moderní procesory mají často k dispozici nejen jedno jádro, ale více jader. Pro provádění složitějších výpočtů lze také využívat stroje sestávající z mnoha vzájemně propojených procesorů. Zavedeme paralelní výpočetní model PRAM a jeho varianty. Pokusíme se některé známe problémy vyřešit výrazně rychleji než sekvenčním výpočet, tedy typicky v polylogaritmickém a konstantním čase.

Osnova cvičení:

1. Problémy šatnářek a vodníků: Přes problém šatnářky a problém vodníků vhodně navážeme a dále rozšíříme některé vybrané znalosti ze základního kurzu BI-DML. Tyto znalosti budeme dále využívat ve zbytku kurzu. Důležitým pojmem v celém zbytku kurzu bude také důkaz, ukážeme si tedy příklady nějakých důkazů, které vypadají zdánlivě správně, ale ve skutečnosti neplatí.

2. Číselné problémy: Věnovat se budeme zajímavým problémům z diskrétní matematiky, jako je například snídaňový problém, CSP, Spernerovo lemma a jeho aplikace, problém Herkula a hydry a podobné.

3. Grafové problémy: Představíme si úlohy, které lze řešit pomocí teorie grafů, ale vytvoření grafového modelu se pro tyto úlohy může zdát neintuitivní. Příkladem takového problému je například odměřování pomocí nádob, rekonstrukce průchodu tunelem a mnohé další.

4. Geometrie a kreslení grafů: Cílem hodiny je seznámit studenta se základními problémy výpočetní geometrie, které s sebou nesou mnoho problémů v podobě práce s reálnými čísly. Ukážeme si, jak se podobné problémy dají řešit a seznámíme se s tím, proč je zajímavé umět graf pěkně nakreslit.

5. Řešení manželských problémů: Stable marriage problem je základním problémem v teorii párování. Úkolem je najít mezi stejně velkými skupinami (heterosexuálních) mužů a žen přiřazení do manželských svazků takové, které co nejvíce odpovídá jejich preferencím, tedy žádná dvojice nebude mít tendenci toto manželství opustit. Zmíněný problém má mnoho zobecnění, ať už v podobě stable roommate problému, případně ve hrách věnujících se tvorbě koalic. Za práci na tomto poli byla L. S. Shapleymu a A. E. Rothovi dokonce udělena Nobelova cena.

6. Hry jednoho až dvou hráčů: Představíme si jednoduché kombinatorické hry, jako je například Nim, Toads and Frogs, Tic-Tac-Toe. Tyto jednoduché hry vhodně zobecníme a ukážeme si některé vybrané vlastnosti složitějších her, jako jsou například šachy, Shannonovo číslo, Go, Game of Life, Poker.

7. Krájení dortu: V rámci hodiny dojde k představení základních problémů teorie férového dělení. Ta se zabývá férovým dělením nějakého statku mezi hráče a nachází mnoho aplikací v problémech reálného světa. Problematika bude ilustrována na příkladu problému krájení dortu — tzv. Cake-Cutting Problem

8. Nepřesná řešení těžkých úloh: Na příkladu problému výběru sekretářky si ukážeme, jakým způsobem lze řešit problémy, které jsou za předpokladu platnosti hypotézy P != NP pro velké instance považovány za algoritmicky neřešitelné. Ukážeme si, jak pro podobné úlohy hledat řešení, které sice není to nejlepší možné, nicméně od nejlepšího výsledku se v nejhorším případě liší o předem známý konstantní faktor. Jiné řešení podobných neřešitelných úloh spočívá ve vytvoření algoritmů typu Monte-Carlo, Las Vegas a další.

9. On-line algoritmy U většiny představených algoritmů známe celý vstup již na začátku výpočtu. V mnoha praktických úlohách ale informace o vstupu dostáváme postupně a musíme na změny či dodatečné informace o vstupu pružně reagovat. V průběhu lekce si tak na příkladu problému řazení a sekretářky ukážeme, jak takové algoritmy fungují, jak je navrhovat a použít. V neposlední řadě budeme také diskutovat, zda pro každý off-line algoritmus existuje jeho on-line protějšek, a vysvětlíme si, co to znamená kompetetivní on-line algoritmus.

10. Problémy vhodné pro obecné řešiče – SAT: Seznámit studenty s problémem splnitelnosti a jeho variantami. SAT je prominentní problém celé informatiky, který je, mimo jiné, základem celé teorie složitosti. Na jednu stranu se po teoretické stránce pro větší instance jedná o neřešitelný problém, na druhou stranu ale existuje mnoho velice dobře optimalizovaných komerčních i open-source řešičů, které mnoho úloh dokáží spočítat velice rychle. Proto si studenti prakticky vyzkouší, jak lze redukovat některé výpočetní problémy na problém splnitelnosti a získat tak relativně efektivní algoritmus bez nutnosti vymýšlení a implementace složitého algoritmu. Student se také dozví, jak redukovatelnost souvisí s příslušností problému do třídy složitosti NP.

11. Problémy vhodné pro obecné řešiče – LP a ILP: Seznámit studenty s teorií lineárního programování a s jeho celočíselnou variantou. Dále si studenti prakticky vyzkouší, jak lze vyjádřit některé výpočetní problémy jako (celočíselné) lineární programy. Takto vyjádřené problémy následně vyřešíme v nějakém volně dostupném řešiči LP. Student se také dozví, jak redukovatelnost souvisí s příslušností problému do třídy složitosti NP.

12. Alternativní výpočetní modely: Krom standardního výpočetního modelu RAM lze provádět výpočty i na dalších výpočetních modelech. Hezkým příkladem mohou být kupříkladu komparátorové sítě, případně kachlíkovací model. Cílem hodiny je tedy představit tyto modely výpočtu a ukázat jejich (omezenou) sílu.

13. (rezerva) Paralelní algoritmy Moderní procesory mají často k dispozici nejen jedno jádro, ale více jader. Pro provádění složitějších výpočtů lze také využívat stroje sestávající z mnoha vzájemně propojených procesorů. Zavedeme paralelní výpočetní model PRAM a jeho varianty. Pokusíme se některé známe problémy vyřešit výrazně rychleji než sekvenčním výpočet, tedy typicky v polylogaritmickém a konstantním čase.

Cíle studia:

Cílem předmětu je představit posluchačům šíři témat, kterým se teoretická informatika věnuje, a motivovat ho do studia tohoto oboru.

Studijní materiály:

AIGNER, Martin a Günter M. ZIEGLER. Proofs from the book. 4. vyd. Berlin: Springer, 2010. ISBN 978-3-642-00855-9.

BERLEKAMP, Elwyn R., John H. CONWAY a Richard K. GUY. Winning ways, for your mathematical plays. New York: Academic Press, 1982. ISBN 978-0-120-91150-9.

BRANDT, Felix, Vincent CONITZER, Ulle ENDRISS, Jérôme LANG a Ariel D. PROCACCIA. Handbook of computational social choice. New York: Cambridge University Press, 2016. ISBN 978-1-107-06043-2.

CORMEN, Thomas H., Charles E. LEISERSON, Ronald L. RIVEST a Clifford STEIN. Introduction to Algorithms. 3. vyd. Cambridge: The MIT Press, 2009. ISBN 978-0-262-03384-8.

MAREŠ, Martin a Tomáš VALLA. Průvodce labyrintem algoritmů. V Praze: CZ.NIC, 2017. ISBN: 978-80-88168-22-5.

MATOUŠEK, Jiří. Lineární programování: Úvod pro informatiky [online]. Praha: ITI, 2006. Dostupné z: https://iti.mff.cuni.cz/series/2006/311.pdf.

MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 4., upr. a dopl. vyd. V Praze: Karolinum, 2009. ISBN 978-80-246-1740-4.

STEWART, Ian. Jak rozkrájet dort a další matematické záhady. Praha: Argo, Dokořán, 2009. ISBN 978-80-7363-187-1.

Poznámka:

Výukové materiály budou dostupné na https://courses.fit.cvut.cz/BI-VAK.21

Další informace:
https://ggoat.fit.cvut.cz/bi-vak/index.html
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 16. 6. 2024
Copyright © Jiří Kosek, 2010–2022 | Copyright © ČVUT, 2010–2022
Provozuje Výpočetní a informační centrum ČVUT
Dotazy a připomínky zasílejte na HelpDesk ČVUT nebo na spravcekos@cvut.cz
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7025806.html