Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS

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ů.

Osnovy 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 v stupu 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.

Osnovy 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 v stupu 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.

Literatura:
AIGNER, Martin a Gu?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.

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).

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

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr BI-SPOL.2015 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study V Není BI-WSI-PG.2015 Webové a softwarové inženýrství V Není BI-WSI-WI.2015 Webové a softwarové inženýrství V Není BI-WSI-SI.2015 Webové a softwarové inženýrství V Není BI-ISM.2015 Informační systémy a management V Není BI-ZI.2018 Znalostní inženýrství V Není BI-PI.2015 Počítačové inženýrství V Není BI-TI.2015 Teoretická informatika V Není BI-BIT.2015 Bezpečnost a informační technologie V Není BI-SPOL.21 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study V Není BI-PI.21 Počítačové inženýrství 2021 V Není BI-PG.21 Počítačová grafika 2021 V Není BI-MI.21 Manažerská informatika 2021 V Není BI-IB.21 Informační bezpečnost 2021 V Není BI-PS.21 Počítačové sítě a Internet 2021 V Není BI-PV.21 Počítačové systémy a virtualizace 2021 V Není BI-SI.21 Softwarové inženýrství 2021 V Není BI-TI.21 Teoretická informatika 2021 V Není BI-UI.21 Umělá inteligence 2021 V Není BI-WI.21 Webové inženýrství 2021 V Není