Ř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á ú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 zde.
Ř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á ú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á ú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á ú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ěť.
Ú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 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 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 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: 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?
Ú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.
Ú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í.