# Programování II pro matematiky ## Teoretické cvičení 03 **17. 3. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Příklady - Řešení příkladů - Domácí úkol --- ## Opakování - Hornerovo schéma $$ a(x) = a\_n \cdot x^n + a\_\text{n-1} \cdot x^{n-1} + a\_{n-2} \cdot x^{n-2} \dots + a\_1 \cdot x + a\_0 $$ - složitost $\mathcal{O}(n^2)$ -- $$ a(x) = ( \dots ((a\_n \cdot x + a\_{n-1}) \cdot x + a\_{n-2})\cdot x + \dots + a\_1)\cdot x + a\_0 $$ - složitost $\mathcal{O}(n)$ --- ## Opakování - sčítání polynomů ``` a = [2, -5, 0, 4, 6] # 6x^4 + 4x^3 -5x + 2 b = [11, 0, -2] # -2x^2 + 11 def soucet(a, b): c = [] if len(a) < len(b): a, b = b,a for i in range(len(b)): c.append(a[i]+b[i]) for i in range(len(b), len(a)): c.append(a[i]) return c print(soucet(a, b)) ``` -- - časová složitost $\mathcal{O}(n)$ -- - paměťová složitost $\mathcal{O}(n)$ --- ## Opakování - součin polynomů ``` a = [2, -5, 0, 4, 6] # 6x^4 + 4x^3 -5x + 2 b = [11, 0, -2] # -2x^2 + 11 def soucin(a, b): c = [0] * (len(a)+len(b)-1) for i in range(len(a)): for j in range(len(b)): c[i+j] += a[i] * b[j] return c print(soucin(a, b)) ``` -- - časová složitost $\mathcal{O}(n^2)$ -- - paměťová složitost $\mathcal{O}(n)$ --- ## Prvočíselný rozklad Máme dané číslo $x$ a chceme zjistit je prvočíselný rozklad - Rozkládané číslo postupně zkoušet dělit všemi prvočísly - Exponenciální složitost - V současné době není znám polynomiální algoritmus - (existuje otevřená otázka s * * * jestli [P = / != NP](https://cs.wikipedia.org/wiki/Probl%C3%A9m_P_versus_NP), kde prvočíselný rozklad je v NP) -- ``` import math def rozklad_delenim(cislo): horni_mez = int(math.sqrt(cislo)) prvocisla = eratosthenovo_sito(horni_mez) rozklad = [] for prvocislo in prvocisla: while cislo % prvocislo == 0: rozklad.append(prvocislo) cislo /= prvocislo if cislo != 1: rozklad.append(cislo) return rozklad ``` --- ## Příklady Máme danou posloupnost $N$ čísel. Najděte algoritmus a určete jeho časovou a prostorovou složitost. - Nalezněte maximum a počet jeho výskytů - Nalezněte maximální číslo, které se neopakuje - Nalezněte číslo s maximálním počtem výskytů Máme danou posloupnost $N$ kladných čísel, číslo $K$ - Určete souvislý úsek se součtem rovným přesně $K$ Máme danou posloupnost $N$ čísel - Určit souvislý úsek s maximálním součtem :-) Máme danou posloupnost $0$ a $1$ délky $N$, postupně dostaneme $K$ dotazů na úsek $x$, $y$ – určit počet jedniček v dotazovaném úseku. --- ## Řešení Máme danou posloupnost $N$ čísel. Najděte algoritmus a určete jeho časovou a prostorovou složitost. Nalezněte maximum a počet jeho výskytů: -- Vstup: ``` 1 2 4 5 4 3 3 5 0 1 ``` -- Algoritmus (vstup neprázdné `pole`): ``` vyskytu = 0 maximum = pole[0] for i in range(len(pole)): if pole[i] > maximum: maximum = pole[i] vyskytu = 0 if pole[i] == maximum: vyskyu += 1 return maximum, vyskytu ``` -- - Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(1)$ --- ## Řešení Máme danou posloupnost $N$ čísel. Nalezněte maximální číslo, které se neopakuje ``` 1 2 4 5 4 3 3 5 0 1 ``` -- - Nemám čísla omezená - Seřadím si čísla on největšiho po nejmenší (z přednášky v $N \cdot \log(N)$ a pak najdu v lineárním čase výsledek) - $\mathcal{O}(N \cdot \log(N))$, paměťová složitost $\mathcal{O}(N)$ - Vím, že čísla jsou omezená - Uložím vstup do pole - Najdu minimální a maximální číslo ve vstupním poli - Vytvožím si pole $0$ o velikost maximum - minimum - Projdu vstupní pole a při potkání čísla zvětším hodnotu v poli - Projdu vstupní pole a najdu maximum bez opakování - $\mathcal{O}(N + (\max(vstup) - \min(vstup))$, paměťová složitost $\mathcal{O}(N + (\max(vstup) - \min(vstup))$ - Požiji hashování: - Místo předchozího pole $0$ použiji hashovací tabulku - $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ## Řešení Máme danou posloupnost $N$ čísel. Nalezněte číslo s maximálním počtem výskytů ``` 1 2 4 5 4 3 3 5 0 1 ``` -- Variace na přechozí příklad --- ## Řešení Máme danou posloupnost $N$ kladných čísel, číslo $K$ Určete souvislý úsek se součtem rovným přesně $K$ ``` 1 2 4 5 4 3 3 5 0 1 ``` -- Algoritmus (vstup neprázdné `pole`, číslo `K`): ``` soucet = 0 zacatek = 0 konec = 0 for i in range(len(pole)): if soucet + pole[i] < K konec = i soucet += pole[i] while soucet > K: soucet -= pole[zacatek] zacatek += 1 if soucet == K return zacatek, konec return None ``` -- - Časová složitost $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ --- ## Řešení Máme danou posloupnost $N$ čísel. Určit souvislý úsek s maximálním součtem. Viz první cvičení. --- ## Řešení Máme danou posloupnost $0$ a $1$ délky $N$, postupně dostaneme $K$ dotazů na úsek $x$, $y$ – určit počet jedniček v dotazovaném úseku. ``` 0 1 0 0 1 1 1 0 1 ``` -- Vytvoříme si pomocnou strukturu s prefixovými součty (na začátek vložíme číslo `0`): ``` 0 0 1 1 1 2 3 4 4 5 ``` Pak výsledek dostaneme pomocí `prefix[y+1]-prefix[x]` --- ## Řešení - pokračování Algoritmus pro prefixové součty (vstup neprázdné `pole`): ``` prefix = [0]*(len(pole)+1) suma = 0 for i in range(len(pole)) suma += pole[i] prefix[i+1] = suma ``` Algoritmus pro dotaz (vstup `x`, `y`): ``` return prefix[y+1]-prefix[x] ``` -- Vytvoření prefixových součtů bude trvat $\mathcal{O}(N)$, paměťová složitost $\mathcal{O}(N)$ Celkově bude časová složitost $\mathcal{O}(K+N)$, paměťová složitost $\mathcal{O}(N)$ --- ## Domácí úkol Máme dané dvourozměrné pole o rozměrech $R \times S$. Pole obsahuje pouze $0$, nebo $1$. Postupně dostaneme $K$ dotazů - každý dotaz určuje část pole (například pomocí souřadnic $x_0, y_0$ a $x_1, y_1$). Najděte algoritmus, který co nejefektivněji (z pohledu časové složitosti) určí počet jedniček v dané části pole. Zapište váš algoritmus v nějakém pseudokódu (nebo Pythonu). Určete časovou a prostorovou složitost vašeho algoritmu. ### Příklad ``` 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 ``` Pro část pole podle souřadnic $0, 1$ a $1,3$ program vrátí odpověď $4$.