Algoritmy a datové struktury – ALG119001

FAQ

Kdo učí? Aleš Podolník.

Kde a kdy? Úterý, 16:40, učebna C116, Celetná

Jak se ozvat? Na pracovní e-mail – podolnik zavináč ipp tečka cas tečka cz

Kde sedí? Na Ústavu fyziky plazmatu (kampus AV ČR na Slovance).

Sylabus v SISu

Nástroje

V učebně jsou k dispozici počítače. Přihlašovací údaje byste měli mít od katedry, případně si je vyřiďte. Vlastní počítač se může hodit, pokud budeme programovat, tak v Pythonu, jehož instalace bude na vás. Pokud s tím budete potřebovat pomoc, jsem po hodině k dispozici. Většinu materiálů budu ale poskytovat ve formě tzv. iPython notebooku, který vám nasdílím ve službě Google Colaboratory, takže není třeba si lokální instalaci zařizovat. Doporučuji pak mít vytvořený Google účet, abychom měli společný základ, který (v ideálním případě) bude nezávislý na konkrétním počítači.

Letní semestr 2024/2025

Tady budou přibývat věci.

• 18. 2. 2025: Úvodní hodina, slidy, příklady.
• 25. 2. 2025: Lineární struktury, slidy, příklady s řešením úkolů.
• 4. 3. 2025: Programovací techniky, slidy, příklady s řešením úkolů.
• 11. 3. 2025: Úvod do složitosti, slidy, příklady.
• 18. 3. 2025: Něco k vyčíslitelnosti, slidy, příklady.
• 25. 3. 2025: Nekonalo se.
• 1. 4. 2025: Třídicí algoritmy, slidy, příklady.
• 8. 4. 2025: Nekoná se
• 15. 4. 2025: Grafy, slidy, příklady.
• 22. 4. 2025: Grafy 2, slidy.
• 29. 4. 2025: Nekoná se
• 6. 5. 2025: Poslední přednáška, slidy.
• 13. 5. 2025: Nekoná se (rektorský den)

Zkouška

Zkouška bude probíhat na Ústavu fyziky plazmatu (U Slovanky 2525/1a) ve velké zasedací místnosti (1. patro nad recepcí). Termíny naleznete v SISu.

Průběh zkoušky

Povolené pomůcky

• Vlastní příprava tématu (vizte níže)
• Psací potřeby

Počítač si nosit netřeba.

Na přípravu před zkouškou budete mít 45 minut. Samotná ústní část bude trvat také 45 minut. Zkouška má 2 části.

• Vlastní téma – z témat níže si vyberte jedno (kromě tématu 1) a připravte si k němu materiály na cca 20 min. K této části si prosím připravte doma nebo u zkoušky max. 2 A4 rukou psaného textu. Chcete-li, oboustranně, ale berte na vědomí, že zkouška má omezenou časovou dotaci ;).
• Přidělené téma – bude zadáno nějaké podtéma z témat specifikovaných níže.

Témata

1. Základy programování (nelze vybrat pro přípravu doma)

   Napište jednoduchý algoritmus na papír formou diagramu a komentujte jeho kroky (zadání programu bude přiděleno až na zkoušce).

2. Lineární datové struktury

   Schéma operační paměti. Reprezentace pole, spojový seznam. Fronta a zásobník a příklady.

3. Nelineární datové struktury

   Definice stromu. Halda a k čemu je. Graf a základní pojmy.

4. Program a programovací techniky

   Definice funkce. Rekurze. Převod mezi rekurzivním programem a sekvenčním výpočtem. Algoritmy podle metody.

5. Složitost

   Měření velikosti problému a třída složitosti. Příklad odhadu složitosti na vybraném algoritmu. Paměťová složitost algoritmu.

6. Vyčíslitelnost

   Turingův stroj. Základní pojmy vyčíslitelnosti a rozhodnutelnosti. Co je vyřešení a ověření problému.

7. Třídicí algoritmy

   Třídicí algoritmy s kvadratickou složitostí. Optimalizované třídicí algoritmy. Důkaz, že třídicí algoritmus má složitost minimálně N log N.

8. Grafy

   Graf a základní pojmy. Reprezentace grafu v algoritmu. Prohledávání do hloubky. Prohledávání do šířky. Nejkratší cesta. Hledání mostů. Minimální kostra. Důkaz obarvení 5 barvami.

AI a tak

Používání AI nástrojů pro řešení problémů, které případně dostanete zadané, není to, co byste se tady měli naučit. Když si ale budete něco zkoušet sami, rozhodně to zkuste.