Search
Ř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} $. Vizuální důkaz.
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.
xyz()
i = 50; do { for (j = 0; j < 70; j++) { if (j > ___) xyz(); } i++; } while (i < 150);
Můžete zkusit svůj tip zde.
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$.
Ř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)$
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?
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$.
Ř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)$
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.
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ěť.
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}$.
implementace v Pythonu
Ú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); }
Ú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.
uvw()
for (i = 0; i < 7; i++) { j = i; while (j < ___) { uvw(); j++; } }
Ú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++; }
Ú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: 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: 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?
výpočet
Úloha 13: 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ů.
Ú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.
implementace
Úloha 15: 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$.
Ú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í.