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:
Studenti se naučí nejdůležitější pokročilé algoritmy a datové struktury z různých odvětví informatiky, které nejsou pokryty přednáškami bakalářského stupně a jinými přednáškami magisterského stupně. Poznají také způsoby zvládnutí úloh, které dle dnešních poznatků nejsou zvládnutelné optimálním způsobem v polynomiálně omezeném výpočetním čase.

Osnovy přednášek:

1.		Pokročilé algoritmy pro toky v sítích.
2.		Párování: hledání v bipartitním i obecném grafu, nejlacinější párování, paralelní pravděpodobnostní algoritmus.
3.		Rovinné grafy: podmínky rovinnosti, testování rovinnosti, isomorfismus rovinných grafů.
4.		Zpracování digitálního signálu: rychlá Fourierova transformace a metody spektrální komprese.
5.		Geometrické algoritmy: konvexní obal a Voroného diagram, a další.
6.		Proudové (streaming) algoritmy.
7.		Prvočíselnost: testování pravděpodobnostní a deterministické, důkaz prvočíselnosti.
8.		Aproximační algoritmy.
9.		Aproximační schémata.
10.		Online algoritmy.
11.		Obecné heuristické metody: simulované žíhání, tabu search, genetické algoritmy.
12.		Specializované heuristické metody: spektrální heuristiky, TSP.
13.		Pravděpodobnostní algoritmy a pravděpodobnostní analýza algoritmů.

Osnovy cvičení:

1.		[2] Pomalost/nekonečnost FF algoritmu, ověření paralelního algoritmu pro párování, speciální případy párování.
2.		Kuratowského věta jako algoritmus testování planarity, nerovinnost K5 a K33, rovinná nakreslení málo souvislých grafů, pravděpodobnostní důkaz neisomorfismu.
3.		Fourierovy obrazy základních funkcí, konvoluce a FT, kosinová transformace.
4.		Aplikace konvexního obalu a Voroného diagramu a jejich souvislost.
5.		Základní příklady proudových algoritmů.
6.		Aproximace problému loupežníků a bin-packing.
7.		Základní poznatky spektrální teorie grafů.
8.		Příklady pravděpodobností analýzy jednoduchých heuristik.
9.		[5] Referáty studentů o experimentálním zkoumání jimi naprogramovaných algoritmů.

Literatura:
Kučera, L. ''Algovize''. Praha: Univerzita Karlova, 2009. ISBN 978-80-902938-5-4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. ''Introduction to Algorithms (3d Edition)''. The MIT Press, 2009. ISBN 0262033844. Kleinberg, J., Tardos, E. ''Algorithm Design''. Addison Wesley, 2005. ISBN 0321295358.

Požadavky:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-PAL/

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

Plán Obor Role Dop. semestr MI-WSI-SI.2016 Webové a softwarové inženýrství V 2 MI-NPVS.2016 Návrh a programování vestavných systémů V 2 MI-ZI.2016 Znalostní inženýrství V 2 MI-ZI.2018 Znalostní inženýrství V 2 MI-WSI-ISM.2016 Webové a softwarové inženýrství V 2 MI-WSI-WI.2016 Webové a softwarové inženýrství V 2 MI-SP-TI.2016 Systémové programování PZ 2 MI-WSI-ISM.2016 Webové a softwarové inženýrství V 2 MI-PSS.2016 Počítačové systémy a sítě V 2 MI-SPOL.2016 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study VO 2 MI-SP-SP.2016 Systémové programování V 2