Basic Information
- Anotace (zdroj: SIS)
- Přednášející: Tomáš Dvořák (TODO (at) TODO)
- Cvičící: Pavel Koupil (pavel.koupil (at) matfyz.cuni.cz)
- Přednášky
- Rozvrh
- Přednáška: Středa 12:20 - 13:50 (místnost N1)
- Cvičení: Čtvrtek 11:30 - 12:15 (místnosti N8)
- Tabulka s body
Formal Requirements
- Cvičení:
- Účast na cvičení není povinná, ale je silně doporučována
- Během každého cvičení lze získat 1 bod za aktivní řešení příkladů (celkem 12)
- Domácí úkoly:
- Během semestru Vám bude zadáno 8 domácích úkolů
- Domácí úkoly budou mít standardní a rozšířenou verzi
- Standardní verze se bude skládat z 1 až 5 příkladů a lze za ni získat nejvýše 10 bodů
- Vyřešení rozšiřující části domácího úkolu Vám může nahradit 1 nezískaný bod za aktivitu na cvičení
- Na vyřešení domácího úkolu budete mít vždy alespoň 13 dnů
- Pozdě odevzdaný domácí úkol bude penalizován -2 body za každý započatý týden zpoždění
- Řešení domácího úkolu z algoritmizace se odevzdává emailem na pavel.koupil@matfyz.cuni.cz a lze odevzdat pouze jednou
Course Credit
- Pro zisk zápočtu je nutné získat alespoň 56 bodů
Schedule and Study Material
| Date | Content | Supplementary Material | Solution | Homework |
|---|---|---|---|---|
| 5. 10. 2023 | Úvodní cvičení NPRG062_01_Uvod.pdf Průběh cvičení Požadavky na zisk zápočtu Známky Vážení kuliček Invariant cyklu |
- | - | - |
| 12. 10. 2023 | Asymptotická složitost NPRG062_02_Asymptoticka_slozitost.pdf Asymptotická notace |
- | - | - |
| 19. 10. 2023 | Teorie čísel NPRG062_03_Teorie_cisel.pdf Eratosthenovo síto Prvočíselný rozklad Nejmenší společný násobek Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 3.1: Eratosthenovo síto (soubor eratosthenovo_sito.py) Cvičení 3.2: Prvočíselný rozklad (soubory prvociselny_rozklad.py a prvociselny_rozklad_funkce.py) Cvičení 3.3: Nejmenší společný násobek (soubory nejmensi_spolecny_nasobek.py a nejmensi_spolecny_nasobek_funkce.py) |
- |
| 26. 10. 2023 | Třídění NPRG062_04_Trideni.pdf merge_sort.py Haldové třídění nad polem Vylepšení třídění sléváním Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 4.1: HeapSort nad polem (soubor heap_sort.py) Cvičení 4.2: Vylepšení MergeSort (soubor merge_sort_reseni.py) |
- |
| 9. 11. 2023 | Binární půlení NPRG062_05_Binarni_puleni.pdf binarni_vyhledavani.py odmocnina.py Zobecnění binárního vyhledávání Výpočet odmocniny Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 5.1: Zobecnění binárního vyhledávání (soubor binarni_vyhledavani_reseni.py) Cvičení 5.2: Odmocnina (soubor odmocnina_reseni.py) |
- |
| 16. 11. 2023 | Základní datové struktury NPRG062_06_Zakladni_datove_struktury.pdf cyklicka_fronta.py fronta.py zasobnik.py Úprava cyklické fronty v poli Spojový seznam Implementace fronty a zásobníku - chybové stavy Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 6.1: Úprava cyklické fronty (soubor cyklicka_fronta_reseni.py) Cvičení 6.2: Implementace fronty a zásobníku - chybové stavy (soubory fronta_chybove_stavy.py a zasobnik_chybove_stavy.py) Cvičení 6.2: Implementace fronty a zásobníku - chybové stavy; řešení s výjimkami (soubory fronta_chybove_stavy_vyjimky.py a zasobnik_chybove_stavy_vyjimky.py) |
- |
| 23. 11. 2023 | Základní datové struktury II NPRG062_07_Zakladni_datove_struktury_II.pdf Další operace nad spojovými seznamy Rozšíření operací binární haldy Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 7.1: Další operace nad spojovými seznamy (soubor spojovy_seznam_rozsireny.py) Cvičení 7.2: Rozšíření operací binární haldy (soubor XXX.py) |
- |
| 30. 11. 2023 | NPRG062_08_Rekurze.pdf Rekurze vs iterace Hanojská věž Binární vyhledávání rekurzivně Rekurzivní generování |
- | Příklad 8.1: Rekurze vs iterace (soubory factorial.py, factorial_recursive.py, fibonacci.py, fibonacci_recursive.py a fibonacci_recursive_cached.py) Cvičení 8.1: Hanojská věž (soubor hanojska_vez.py) |
- |
| 7. 12. 2023 | Rekurzivní datové struktury NPRG062_09_Rekurzivni_datove_struktury.pdf Určení (průměrné) výšky stromu Symetrický binární strom Aritmetické výrazy Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Příklad 9.1: Určení (průměrné) výšky stromu (soubor vyska_stromu.py) Cvičení 9.2: Symetrický binární strom (soubor symetrie_stromu.py) Cvičení 9.3: Aritmetické výrazy (soubor aritmeticke_vyrazy.py) |
- |
| 14. 12. 2023 | Prohledávání stavového prostoru NPRG062_10_Prohledavani_stavoveho_prostoru.pdf Cesta šachovým koněm Magický čtverec řádu n Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
Cvičení 10.1: Cesta šachovým koněm (soubor cesta_konem.py) Cvičení 10.2: Magický čtverec řádu n (soubor magicky_ctverec.py) |
- |
| 21. 12. 2023 | Grafové algoritmy TBD Eulerovský graf Bipartitní graf Zadání domácího úkolu |
Zadání domácího úkolu: TBD |
TBD | - |
| 4. 1. 2024 | Grafové algoritmy II TBD Nalezení nejkratší cesty pomocí BFS Rozděl a panuj QuickSelect Plánování přednášek |
- | TBD | - |
| 11. 1. 2024 | Konzultace | - | - | - |
Recommended Literature
- Martin Mareš, Tomáš Valla. Průvodce labyrintem algoritmů. CZ.NIC, z.s.p.o.. Praha 2022.
odkaz ke stažení