Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023

Sublineární algoritmy

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-SLA Z,ZK 5 2P+1C česky
Přednášející:
Dušan Knop (gar.)
Cvičící:
Dušan Knop (gar.), Šimon Schierreich
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
Rozvrh na zimní semestr 2022/2023:
Rozvrh není připraven
Rozvrh na letní semestr 2022/2023:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 27. 1. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7067806.html