Alg a Prg

Nový rok!

Náhradní výuka za termit 16. 12. 2024
kdy: úterý 07.01.2025 10:00
jak: onlajn
(hlasovaním ve třídě)

Zapoctovy test - terminy
Predbezne navrzene terminy, nutno zaslat potvrzeni:
- Pa 9:00
- Ct 14:00 Impakt; nebo po 16:00 MS .... resume po 16:00 na MSSSSSSMSMSMSMSMSMSSMSMSs

ALGORITMIZACE

https://docs.sympy.org/latest/tutorials/intro-tutorial/manipulation.html

1. BST
- def
- operace: search/find, insert, delete 
- slozitost operaci (bts je fajn ale muze zdegenerovat) visualgo priklady
- hloubka stromu
- degenerace 

AVL Tree 
- def
- operace 
- rotace
- hloubka a konstrukce "nejhorsiho" stromu
-- kolik vrcholů/nodů obsahuje AVL strom o hloubce 5
-- jakou hloubku musí mít strom s 13 vrcholy

2. QuickSort

3. MergeSort


5. VYHODNOCENI ARITMETICKEHO VYRAZU

PREfix, INfix, POSTfix format zapisu

Mejme aritmeticky vyraz ((6/3)+2)*(4-1)

1. Sestrojte odpovidajici strom aritmetickeho vyrazu
2.0 Vhodnym pruchodem stromu urcete prefix zapis (jsou nutne zavorky?)
2.1 Vhodnym pruchodem stromu urcete postfix zapis (jsou nutne zavorky?)
2.2 Vhodnym pruchodem stromu urcete infix zapis? (jsou nutne zavorky?)

3.0 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou stromem
3.1 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou prefixovym zapisem 
3.2 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou postfixovym zapisem

4.0 Prevedte postfix zapis na prefix (bez vyuziti stromu vyrazu)
4.1 Prevedte prefix zapis na postfix (bez vyuziti stromu vyrazu)
4.2 Prevedte infix zapis na postfix (bez vyuziti stromu vyrazu)
4.3 Prevedte infix zapis na prefix (bez vyuziti stromu vyrazu)

5.1 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou infixovym zapisem

6.1 Postavte strom vyrazu z prefix notace
6.2 Postavte strom vyrazu z postfix notace

Hashování
- 3 idee:
a) prima datová struktura - dict/map
b) klíčem indexované pole
c) mapování universa
b2) pro realizaci: key - value datove struktury -> dictionary

https://en.wikipedia.org/wiki/Hash_table
-- obrazky - zaplnění tabulky (load factor) vs primerna delka retizku-kolizi
-- (v pravo) dole: přehled programovacích jazyků a implentace hash table  


PROGRAMOVANI

Dictionary: https://www.programiz.com/python-programming/dictionary
- iterace: in ... keys, values(), items(): https://www.geeksforgeeks.org/python-dictionary/#iterating-through-a-dictionary
- podrobneji: https://realpython.com/python-dicts/
- jaké hodnoty/typy mohou být klíčem?

8. Napiste program, ktery ze standardniho vstupu precte text a v zadanem textu spocita vyskyt jednotlivych slov.
Prvnich 10 slov s nejcastejsim vyskytem vypise.



PRIKLADY 
1. Mějme standardní šachovnici. Na šachovnici je zadáno startovní (S) políčko, cílové (C) políčko a figurka.

Následuje série úloh:
1.1 Dosažitelnost
Dostanu se figurkou ze startu do cíle?
Rozhodněte, zdali lze ze startovního políčka dosáhnout cílové políčko pomocí koně (figurka šachů).
Dosazitelnost pozic, resp. které všechny políčka jsou dosažitelná

1.2 Jaká je nejkratší cesta ze startu do cíle?
V kolika nejméně tazích koněm (figurka šachů) lze dosáhnout cílové políčko ze startovní pozice (figurka šachů), pokud nelze vraťte hodnotu "-1".

1.3 Vypsat-evidovat nejkratší cestu
Vypište nějakou nejkratší cestu koněm (figurka šachů) ze startovního políčka do cílového.


1.5 Modifikace předchozích úkolů (jak dosažení, nejkratší cesta (délka) tak nejkratší cesta (výpis)), pro:
1.5.2 jiné figurky: střelec, věž, dám, baba jaga, ... (obecně jiný druh pohybu po šachovnici)
1.5.3 nestandardní šachovnice: s překážkami (zakázané pole; nemohu vstupit vs nemohu "přeletět"), nestandardní rozměry (třeba 11x11), toroidní (cirkulární) pole, ...



Unittesty
- proc a jak testujeme, automaticke testy
- uniittesty nejsou jedinymi testy, dalsi napr. integracni testy, stress testy, ...
- existuje rada presdefinovanych assertu

!! vice ve vzorovem prikladu, vcetne zadani cviceni: unittest.py !!

https://docs.python.org/3/library/unittest.html
https://realpython.com/python-unittest/
 


PRISTE
3. Typing annotation in Python and mypy

https://docs.python.org/3.12/library/typing.html
https://mypy.readthedocs.io/en/stable/cheat_sheet_py3.html

https://medium.com/@moraneus/exploring-the-power-of-pythons-typing-library-ff32cec44981