====== 0 - Příprava na složitost ====== ==== Řešené úlohy ==== === Uvažování nad kódem === **Řešená úloha 1:** Který fragment programu z následujících dvou proběhne rychleji? (Předpokládáme, že oba běží v identickém SW/HW prostředí.)


int n = 100; 
int sum = 0;
for (i = 0; i < n; i++) 
  for (j = 0; j < i; j++) 
    sum += i+j;


int n = 75;
int sum = 0;
for (i = 0; i < n; i++) 
  for (j = 0; j < n; j++) 
    sum += i+j;

++++ Řešení (rozbalit)| Ten nalevo, protože $\sum_{i=0}^{99} i = 100\frac{99}{2} = 4950 < 5625 = 75^2$ Vyplatí se znát vzorec pro součet $q$ členů aritmetické posloupnosti: $\sum_{i = 1}^{q} a_i = q \frac{a_1 + a_q}{2} $. [[https://en.wikipedia.org/wiki/Arithmetic_progression|Vizuální důkaz.]] [[https://www.onlinegdb.com/B10Gs6y2W | Simulace běhu]] ++++ ----- **Řešená úloha 2:** Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura ''xyz()'' volána právě **2000 krát**.


i = 50;
do {
  for (j = 0; j < 70; j++) {
    if (j > ___) xyz();
  }
  i++;
} while (i < 150);

Můžete zkusit svůj tip [[https://www.onlinegdb.com/B1WXapy2W | zde]]. ++++ Řešení (rozbalit)| Vnější cyklus vykoná $100$ iterací. Protože $2000 / 100 = 20$, musí podmínka platit vždy ve $20$ iteracích vnitřního cyklu. Z toho $70 - 20 = 50$ musí být první $j$, pro které bude podmínka platit, tj. **chybějící konstanta je** $49$. ++++ ---- === Výpočetní úlohy === **Řešená úloha 3:** Ke zpracování $k$-tého řádku matice velikosti $n \times n$ je zapotřebí $2k$ operací. Kolik je potřeba operací ke zpracování celé matice? a) $2n^2$ \\ b) $n^2 / 2$ \\ c) $n(n+1) / 2$ \\ d) $n(n-1)$ \\ e) $n(n+1)$ ++++ Řešení (rozbalit)| Správně je **e)**: Součet pro $n$ řádků (aritmetická posloupnost): $\sum_{k=1}^n 2k = n\frac{2 + 2n}{2} = n(n+1)$. ++++ ---- **Řešená úloha 4:** Úloha, jejíž doba řešení je $Cn^2$, kde $n$ je rozsah vstupních dat, se řeší na počítači pro $n=5000$. Je zakoupen nový počítač, který je cca $2.5\times$ rychlejší. Jak lze zvětšit rozsah vstupních dat, aby byla úloha vyřešena na novém počítači ve stejném čase? ++++ Řešení (rozbalit)| Sestavíme rovnici mezi $2.5$-násobkem času běhu na starém počítači a časem běhu na novém PC $C n_{new}^2 &= 2.5 C n_{old}^2$. Z toho vypočteme $n_{new} = \sqrt{2.5 \cdot 5000^2} \approx 7905.694$ Tj. za stejný čas lze úloha vyřešit na $2.5\times$ rychlejším počítači pro $n_{new}=7905$ (po zaokrouhlení dolů). Neboli, data lze zvětšit $\sqrt{2.5} \approx 1.58 \times$. ++++ ---- === Konstrukční úlohy === **Řešená úloha 5:** Pole obsahuje kladné a nulové prvky. Popište, jak zorganizujete jeden průchod polem, po jehož doběhnutí budou všechny nenulové prvky shromážděny na začátku pole a jejich pořadí zůstane zachováno. Např: z $(3, 2, 0, 6, 0, 0, 9, 0, 2, 0)$ vytvořit $(3, 2, 6, 9, 2, 0, 0, 0, 0, 0)$ ++++ Řešení (rozbalit)| Procházíme seznamem zleva, jakmile najdeme 0, zapamatujeme si pozici a pokračujeme ukazatelem dál, dokud nenajdeme nenulové číslo. To pak prohodíme za 0 na zapamatované pozici. Další pozice s nulou je jistě o jedno pole napravo od té předchozí. Ukazatelem pokračujeme dál, prohazujeme takto každé nenulové číslo které najdeme. Algorimtus končí, jakmile se dostaneme ukazatelem na konec seznamu. [[https://trinket.io/python/aab6486ab2 | alternativní implementace v Pythonu]] ++++ ---- **Řešená úloha 6:** Seznam obsahuje $N+1$ celých čísel, každé leží v intervalu $[1,N]$, čísla nejsou v seznamu nijak uspořádána. Víme, že v seznamu se vyskytuje jedno číslo dvakrát, ostatní jen jednou. Určete duplikované číslo. Musí vám stačit jeden průchod seznamem a konstantně velká přidaná paměť. ++++ Řešení (rozbalit)| Využijeme opět součtu posloupnosti, jelikož víme, že seznam obsahuje každé z nich alespoň jednou. Pokud označíme $d$ hodnotu čísla které hledáme (je v seznamu dvakrát), pak součet všech čísel v seznamu je roven $S = d + \sum_{i=1}^N i$. Stačí tedy sečíst všechna čísla v seznamu a vypočítat $d = S - N\frac{N+1}{2}$. [[https://trinket.io/python3/d306655e20 | implementace v Pythonu]] ++++ ---- ==== Další úlohy ==== **Úloha 7:** Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura ''xyz()'' volána právě **2100 krát**.


for (i = 0; i < 70; i++) {
  j = 0;
  do {
    if (j > ___) {
      xyz();
    }
    j++;
  } while (j < 90);
}

Můžete zkusit svůj tip [[https://www.onlinegdb.com/Bysg36kh- | zde]]. ---- **Úloha 8:** Do následujícího kódu doplňte chybějící výraz v podmínce tak, aby byla procedura ''uvw()'' volána právě **49 krát**.


for (i = 0; i < 7; i++) {
  j = i;
  while (j < ___) {
    uvw();
    j++;
  }
}

Můžete zkusit svůj tip [[https://www.onlinegdb.com/ByEGxRx3W | zde]]. ---- **Úloha 9:** Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura ''uvw()'' volána právě **85 krát**.


i = 0;
while (i < 10) {
  for (j = i; j < ___; j++) {
    uvw();
  }
  i++;
}

Můžete zkusit svůj tip [[https://www.onlinegdb.com/By56--Z3Z | zde]]. ---- **Úloha 10:** Řešíme úlohu na počítači pro velikost vstupu $n=5000$. Je zakoupen nový počítač, který je cca $2.5\times$ rychlejší. O kolik lze zvětšit rozsah vstupních dat, aby byla úloha vyřešena na novém počítači ve stejném čase? Řešte pro různé doby řešení úlohy: a) $C n^3$ \\ b) $C n^{0.5}$ \\ c) $C n \log_2 n$ ---- **Úloha 11:** {{page>courses:b4b33alg:internal:tutorial-notes:00#11&noheader&nofooter}} Stroj provádí $10^9$ operací za sekundu. Pro výpočet je k dispozici 1 hodina. Určete, jaká může být maximální hodnota $n_{\max}$, která určuje velikost vstupních dat, v případě že počet nezbytných opreací pro zpracování dat o velikosti $n$ je $n^{3/2}$. A co v případě že zpracování vyžaduje \\ a) $N^{5/4}$ operací \\ b) $N \cdot \log_2(N) \cdot \log_2 (\log_2 N)$ operací \\ c) $N^2 \cdot \log_2 N$ operací \\ ---- **Úloha 12:** {{page>courses:b4b33alg:internal:tutorial-notes:00#12&noheader&nofooter}} Metoda A potřebuje k vyřešení úlohy $n^2 + 17$ operací, Metoda B potřebuje $2n + 80$ operací, přičemž celé číslo $n$ popisuje rozsah vstupních dat. Pro jaká $n$ je výhodnější použít metodu A? [[https://www.wolframalpha.com/input/?i=n%5E2%2B17+%3C+2n+%2B+80 | výpočet]] ---- **Úloha 13:** {{page>courses:b4b33alg:internal:tutorial-notes:00#13&noheader&nofooter}} Každý ze dvou seznamů čísel je uspořádán v neklesajícím pořadí. Popište, jak vytvoříte třetí seznam, který bude obsahovat pouze taková čísla, která se vyskytují v obou daných seznamech. Musí vám stačit jeden průchod každým z daných seznamů. [[https://trinket.io/python/5040d42d6c | implementace v Pythonu]] ---- **Úloha 14:** Seznam obsahuje kladná čísla, záporná čísla a nuly v nahodilém pořadí. Najděte takový souvislý podseznam, v němž součet všech jeho prvků je maximální možný mezi všemi souvislými podseznamy. Uvažte, zda na to může stačit jeden průchod daným seznamem. [[https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ | implementace]] ---- **Úloha 15:** {{page>courses:b4b33alg:internal:tutorial-notes:00#15&noheader&nofooter}} Je dána zafixovaná matice M o rozměru $N \times N$. Máme postupně odpovídat na množství dotazů stejného formátu: > Jaký je součet všech hodnot v podmatici, která má levý horní roh na pozici $(i_1, j_1)$ a pravý dolní roh na pozici $(i_2, j_2)$? Hodnoty $i_1, j_1, i_2, j_2$ budou v každém dotazu obecně jiné. K dispozici máte paměťový prostor stejně velký jako zabírá M. Určete, jaké hodnoty si musíte předpočítat, abyste na každý dotaz odpověděli v co nejkratším čase a nezávisle na velikosti hodnot $i_1, j_1, i_2, j_2$. [[https://www.geeksforgeeks.org/submatrix-sum-queries/ | implementace]] ---- **Úloha 16:** V rovině je dána kružnice se středem v počátku a poloměrem $R$. Popište, jak určíte, kolik celočíselných mřížových bodů leží uvnitř této kružnice. Neprocházejte všechny mřížové body ve čtvereci o velikosti $2R\times2R$, využijte pouze mřížové body ležící blízko kružnice. Napište kompletní kód Vašeho řešení.