Sublineární algoritmy

Přihlášení do KOSu pro zápis předmětu Nerozvrhuje se

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
NI-SLA	Z,ZK	5	2P+1C	česky

Garant předmětu:

Dušan Knop

Přednášející:

Dušan Knop

Cvičící:

Dušan Knop

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět si klade za cíl představit studentům základní algoritmy využívající pro svou práci menší než lineární prostor, a to na třech standardních přístupech. Tyto algoritmy přirozeně nemohou pracovat přesně a deterministicky – využívají principů náhodných výpočtů. Na druhou stranu se ale většinou dají s úspěchem aplikovat i v případě, že jsou vstupní data velice rozsáhlá. Představíme algoritmy pro streamovací model výpočtů i pro náhodný přístup ke vstupním datům. V neposlední řadě se budeme věnovat také aplikacím těchto algoritmů a přístupům v návrhu polynomiálních algoritmů pro různé problémy.

Požadavky:

Předpokládáme, že student ovládá znalosti získané v předmětech Algoritmy a grafy I & II (BI-AG1, BI-AG2) a Pravděpodobnost a statistika (BI-PST).

Osnova přednášek:

1. Motivace a opakování koncentračních nerovností

2. Morrisovo Počítadlo

3. Různá čísla na vstupu I

4. Různá čísla na vstupu II

5. Turniketový model

6. Testování skupin

7. Získání řídkého vektoru

8. Řídká Fourierova transformace

9. Property Testing I

10. Property Testing II -- grafové algoritmy

11. Konvoluce polynomů

12. (Modulární) součet podmnožiny

13. Řetězcové algoritmy

Osnova cvičení:

1 Koncentrační nerovnosti

2 Různá čisla na vstupu

3 Testování skupin

4 Řikdké vektory

5 Property testing

6 Konvoluce

Cíle studia:

Naučit se používat koncentrační nerovnosti a získat zkušenosti a povědomí o sublineárních algoritmech.

Studijní materiály:

- Simon Foucart, Holger Rauhut: A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis, Birkhäuser 2013, ISBN 978-0-8176-4947-0

- David P. Woodruff (2014), „Sketching as a Tool for Numerical Linear Algebra“, Foundations and Trends® in Theoretical Computer Science: Vol. 10: No. 1–2, pp 1-157. http://dx.doi.org/10.1561/0400000060

Poznámka:

https://courses.fit.cvut.cz/MI-AVY

Další informace:

https://courses.fit.cvut.cz/NI-SLA

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)