Sorting and Searching algos

Programovani 2 Matematici, teoreticke cviceni
03.03.2026 út

0. Jeste ke slozitosti
0.0.7 Uvod do teorie grafu - priprava k domacimu ukolu
0.0.11 Kostra grafu a problem minimalni kostry grafu, 
0.0.13 Kruskaluv algo a vypocet slozitosti algoritmu, na cem zavisi velikost vstupu? (|V|,|E|, |V|+|E|, |E|~|V|, ...)
https://cs.wikipedia.org/wiki/Kruskal%C5%AFv_algoritmus

Co nevime?
- Jak merime velikost vstupu?
- Jakym algos radime hrany? A vubec presprocesing/razeni hran patri do algoritmu nebo je pocitano "vedle"?
- Reprezentace grafu, obecne datovych struktur a slozitosti operaci na nich - reseni - predpoklad ci dosazeni konrektni datove struktury
- Jak jsou implementovany dane operace napr. test na kruznici?

1. Searching algos

1.2 Proč vlastně chceme řadit (i) pole?
(Dat struct ... způsob organizace dat; analogie s dílnou; daný typ organizace přináší své výhody a nevýhody; "neexistuje dobrý DS pro všechny případy")


1.4 Hledání v nesetřízeném poli 
- slozitost v nejlepsim nejhorsim a spocitat i v prumernem pripade

1.6 Hledání v setřízeném poli 
- slozitost v nejlepsim nejhorsim a spocitat 
- binary search

na tabuly:
v strizenem listu l naleznete následující hodnoty: a) 7, b) 55, c) 41, d) 0
l=[2, 4, 7, 9, 12, 17, 32, 35, 41, 47, 55, 59, 60]

- jakou hosnotu vracime pokud se prvek v listu nenechazi?

1.10. Různé modifikace binárního vyhledávání:
- v setříděném poli určit počet výskytů dané hodnoty x
- v setříděném poli nalézt všechny prvky s danou hodnotou x (první a poslední index)
- v setříděném poli nalézt prvek s hodnotu x (pokud tam je) nebo nejbližší vyšší (pokud tam žádné x není).


2.1 Implementujte funkci binárního vyhledávání binarySearch(list, x)
(co funkce vrací, co vrací v případě nalezeného prvku a co v případě nenalezeného prvku?)
pro uvodni ladeni programu byva uzitecne si klidne par testovacich dat resp. vstupu zadat do kodu "napevno"

2.2 Pro funkci binárního vyhledávání diskutujme a navrhněme sérii testů/testovacích dat, které prověří funkčnost vaší implementace
(jaké případy chování testujeme? např: řadné vstupy, krajní meze, neplatné vstupy)
viz reseny priklad
(assert: např. https://realpython.com/python-assert-statement/)
(lehká zmínka o automatickém testování, typy testů, konkrétně unit testy a knihovna unittest)



3. Převod soustav (a dekompozice programu)

3.2 Prevedte cisla 58 a 113 do 2-kove soustavy tj. [58]_2 a [113]_3
3.3 Prevedte cisla 58 a 113 do 3-kove soustavy tj. [58]_3 a [113]_3
3.4 Prevedte cisla [58]_2 a [113]_2 zpet do 10-kove soustavy tj. [58]_10 a [113]_10
3.5 Prevedte cisla [58]_3 a [113]_3 zpet do 10-kove soustavy tj. [58]_10 a [113]_10
3.6 Prevedte cisla B2B a 1AE do 10-kove soustavy tj. [B2B]_10 a [1AE]_10
3.7 A zpet


3.11 Napište funkci, která přečte dvě int hodnoty: a) maxLimit a b) base 
a nalezne všechna čísla od 1 do maxLimit (v desítkové reprezentaci), která jsou v zápise o dané base palindromem 


4. Rozšiřující příklady

- rozklad čísla na cifry
    * zjistit, zda číslo obsahuje ve svém dekadickém zápisu cifru "7", případně kolik obsahuje cifer "7"
    * zjistit, zda je číslo dělitelné každou svou cifrou
- prvočísla
    * nalézt prvočíselný rozklad daného čísla 
- dlouhá čísla
    * porovnání dvou dlouhých čísel (které je větší)
    * násobení dvou dlouhých čísel (případně pro dobré studenty i dělení) 
- polynomy
    * spočítat derivaci polynomu 
- číselné soustavy
    * převod zápisu čísla z poziční číselné soustavy o základu z1 do soustavy o základu z2. 

Ukažte, že některé úlohy s posloupnostmi dat lze řešit "online", tedy bez uložení vstupní posloupnosti v paměti, tedy v konstantní prostorové složitosti - např.
    * nalézt maximum a počet jeho výskytů
    * nalézt druhou největší hodnotu a počet jejích vyskytů
    * určit, zda je posloupnost monotonní (pokud ano, tak jakým způsobem). 


U jiných úloh si potřebujeme uložit data do pole, tzn. potřebujeme prostorovou složitost O(N). V takovém případě často můžeme zrychlit výpočet pomocí vhodného předvýpočtu (např. seřadit si čísla podle velikosti nebo spočítat si v posloupnosti prefixové součty) nebo známe-li rozsah zpracovávaných čísel, někdy nám pomůže použití techniky "inverzního pole" - tedy pomocné pole indexované hodnotami (podobně jako v CountSortu) - např.
    * určit počet různých hodnot obsažených v posloupnosti
    * nalézt maximální hodnotu, která se v posloupnosti neopakuje (neboli má jediný výskyt)
    * nalézt minimální kladnou hodnotu, která v posloupnosti není obsažena.
Ve všech těchto případech existuje primitivní řešení s kvadratickou časovou složitostí, rychlejší využívající setřídění posloupnosti s časovou složitostí O(n log n), případně řešení s výše zmíněným "inverzním polem" má časovou složitost lineární (u druhé z těchto úloh ovšem lineární nejen vzhledem k délce posloupnosti N, ale i vzhledem k rozsahu hodnot zadaných dat, opět podobně jako u CountSortu).

Jednoduché operace s maticemi.
Při práci s obdélníkovou maticí o rozměrech N x M bude časová složitost algoritmu záviset na DVOU parametrech N, M: 
- nalézt maximální hodnotu pod hlavni diagonálou
- určit součet všech čísel pod vedlejší diagonálou
- transpozice matice
- inverze matice.