PAZ1a
PAZ1b
ŠVK 2024
Na úspešné absolvovanie predmetu (získanie hodnotenia aspoň E) je potrebné získať minimálne 50 bodov, z toho aspoň 20 zo skúšky. Zároveň nutnou podmienkou je vyriešenie praktickej úlohy za aspoň polovicu bodov.
samotný algoritmus
viazanie šnúrok
drak prejde popod most, potom cez očko a nakoniec vojde do hradu
pojem (Matematika ZŠ)
jeden z najstarších algoritmov vôbec, vznikol niekedy okolo 300 rokov pnl a jeho autor nie je známy (Euklidov sa nazýva, pretože sa objavuje v jeho knihe)
LEGO
14.2.2024, študovňa A. Merici, UPJŠ, Košice https://ics.upjs.sk/fll
https://www.rtvs.sk/novinky/pecie-cele-slovensko/351614/sladky-valentin-s-pecie-cele-slovensko-vyskusajte-recept-na-minipavlovky
Bielkový sneh
Rúru predhrejte na 175 stupňov.
Vyšľaháme sneh z bielkov, vínneho kameňa a soli do peny.
Pridajte kryštálový cukor, kukuričný škrob, ocot a vanilku a pokračujte v šľahaní, kým nie sú bielky tuhé, hladké a lesklé.
Pripravte na papier na pečenie 12 ks mini pavloviek s priemerom 6cm .
Pečieme 10 minút. Znížte teplotu v rúre na 150 C a pečte, kým sa nafúknu, asi 20-30 minút.
Vypnite rúru, priotvorte dvierka rúry a nechajte vychladnúť v rúre.
Krém
Šľahačku spolu s cukrom a vanilkou do krémova vyšľahajte.
Ozdobte ovocím.
IKEA vydala návod, ako si vyrobiť nábytok z medovníka
https://www.stavebnictvoabyvanie.sk/byvanie/kuchyna/4354-ikea-vydala-navod-ako-si-vyrobit-nabytok-z-medovnika
A my sme tam stáli a pozerali sa ako sprostí (2021)
https://www.csfd.sk/film/1097211-a-my-sme-tam-stali-a-pozerali-sa-ako-sprosti/prehlad/
Desivo zábavná komédia o tom, čo nás čaká v blízkej budúcnosti, keď budeme aj naďalej len stáť a pozerať sa ako sprostí... Manažér Arturo zavedie vo svojej spoločnosti nový algoritmus, ten sa však ukáže byť natoľko efektívny, že kvôli nemu príde o zamestnanie.
Algoritmus je konečná postupnosť presne definovaných inštrukcií na splnenie určitej úlohy. Algoritmus je elementárnym pojmom informatiky – nie je ho možné popísať pomocou ešte elementárnejších pojmov – tak ako napr. pojmy bod a číslo v matematike. Algoritmus nazývame čiastočne správny, ak v prípade že skončí, dáva vždy správne výsledky. Algoritmus nazývame konečný, ak pre ľubovoľné vstupné údaje skončí v konečnom čase. Algoritmus, ktorý je čiastočne správny a konečný, sa nazýva správny. Algoritmizácia je schopnosť aktívne vytvárať algoritmy určené pre nemysliace zariadenie. Je nevyhnutná pri vytváraní počítačových programov. Program je algoritmus napísaný v programovacom jazyku.
Reprezentujú nasledovné zápisy algoritmus?
ZiskatMilionyEur
=======================
ZarobitPrvyMilionEur
DatDoBankyACakatNaUroky
1995
úroky vklad na 12M boli 11,5% ... čakať na dvojnásobok = $x$ rokov ($1,115^x > 2$)
from math import log
log(2, 1.115) #logaritmus cisla 2 pri zaklade 1.115
6.3676539421604135
SN(x, y)
===================
vysl ← 0
while x > 0
if x je neparne
vysl ← vysl + y
x ← ⌊x/2⌋
y ← y+y
return vysl
horné ohraničenie $$Ο\left(g\left(n\right)\right) = \left\{ f(n) | \exists c \in R^+, \exists n_0 \in N, \forall n \geq n_0 : 0 \leq f\left(n\right) \leq c.g(n) \right\}$$
dolné ohraničenie $$\Omega\left(g\left(n\right)\right) = \left\{ f(n) | \exists c \in R^+, \exists n_0 \in N, \forall n ≥ n_0 : 0 \leq c.g(n) \leq f\left(n\right) \right\}$$
tesné ohraničenie $$\Theta\left(g\left(n\right)\right) = \left\{ f(n) | \exists c_1, c_2 \in R^+, \exists n_0 \in N, \forall n ≥ n_0 : 0 \leq c_1.g(n) \leq f\left(n\right) \leq c_2.g(n) \right\}$$
zápis pomocou limity postupnosti $$O\left(g\left(n\right)\right) = \left\{f(n) | \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} < +\infty \right\}$$
Koľko zvukov zvierat zaspievate pri spievaní Old Mac Donald?
old_mac_donald(animals[1..n], noise[1..n])
==============================================================================
for i ← 1 to n
Spievaj "Old MacDonald had a farm, E I E I O"
Spievaj "and on his farm he had a animals[i], E I E I O"
Spievaj "With a noise[i], noise[i] here and a noise[i], noise[i] there"
Spievaj "Here a noise[j], there a noise[j], everywhere a noise[j], noise[j]"
for j ← i-1 downto 1
Spievaj "With a noise[j], noise[j] here and noise[j], noise[j] there"
Spievaj "Here a noise[j], there a noise[j], everywhere noise[j], noise[j]"
Spievaj "Old MacDonald had a farm, E I E I O"
prvé zviera ... 8 x zvuk
druhé zviera ... 8x druhé + 8x prvé, teda 16x
prvé zviera ... 8 x zvuk
druhé zviera ... 8x druhé + 8x prvé, teda 16x
tretie zviera ... 8x + 8x + 8x, spolu 24x
Počas spevu pre tri zvieratá sa vydá 8+16+24=48 zvieracích zvukov.
štyri ... 48+(8+24)=80 zvukov
zvierat | zvukov |
---|---|
1 | 8 |
2 | 24 |
3 | 48 |
4 | 80 |
. | . |
n | ? |
$n$ zvierat ... $ T(n) = 8 \cdot (1+2+3+\cdots+(n-1)+n) = $
$= 8 \cdot \frac{n}{2} \cdot (n+1) = 4n^2+4n $
$T(n) \in \Theta(n^2) \subset \Omega(n^2)$
$T(n) \in \Theta(n^2) \subset O(n^2)$
Aká je časová zložitosť kódu $T(n)$?
prvy(pole[1..n])
=======================
for i ← 1 to n-2
for j ← i to i+2
vysl ← vysl+pole[j]
Aká je časová zložitosť kódu $T(n)$?
prvy(pole[1..n])
=======================
for i ← 1 to n-2 ... (n-2)-krat
for j ← i to i+2 ... 3-krat
vysl ← vysl+pole[j] ... 1 scitanie
$T(n) \in O(n^2)$
presne $T(n) = (n-2) \cdot 3 \cdot 1 = 3n-6 \in O(n) \subset O(n^2)$, $T(n) \in \theta(n)$, ale $T(n) \notin \theta(n^2)$
druhy(pole[1..n])
=======================
for i ← 1 to n
for j ← i to n-i
vysl ← vysl+pole[j]
druhy(pole[1..n])
=======================
for i ← 1 to n ... n-krat
for j ← i to n-i ... (n-1);(n-3);...;2?1;0
vysl ← vysl+pole[j]
$T(n)=(n-1)+(n-3)+\cdots+1 \in O(n^2)$
treti(pole[1..n])
=======================
i ← 1
while i ≤ n
i ← 2*i
vysl ← vysl+pole[i]
treti(pole[1..n])
=======================
i ← 1
while i ≤ n
i ← 2*i ... mocniny 2
vysl ← vysl+pole[i]
$i=2^k$,
$2^k \le n$,
t.j. $k \le \log_2 n$, teda $T(n) \in O(\log_2 n)=O(\log n)$,
lebo $\log_2 n = \frac{\log_3 n}{\log_3 2} = \frac{1}{\log_3 2} \cdot \log_3 n = c \cdot \log_3 n$
rek_fcia(n)
=======================
if n = 0
return 1
else
return n*Rek_fcia(n-1)
faktorial
rekurentný vzťah $T(n) = T(n-1)+2$
$T(n) = T(n-1)+2 = \left(T(n-2)+2\right) + 2 = T(n-2)+2 \cdot 2 = $
$= T(n-3)+3 \cdot 2 = T(n-4)+4 \cdot 2 = ... = $
$ = T(n-(n-1))+(n-1) \cdot 2 = 1+(n-1) \cdot 2=2n-1 \in \Theta(n)$
rek_fcia2(n)
=======================
if n = 1
return 1
else
return 2*Rek_fcia2(n-1)
mocninu 2, presnejšie $2^{n-1}$ ; zložitosť rovnaká ako predch. úloha
rek_fcia3(n)
=======================
if n = 1
return 1
else
return n*Rek_fcia3(n/2)
$T(n) = T\left(\frac{n}{2}\right)+2$ ... rekurentný vzťah
$T(n) = T\left(\frac{n}{2}\right)+2 = (T\left(\frac{n}{4}\right)+2)+2 =T\left(\frac{n}{4}\right)+4=$
$=T\left(\frac{n}{8}\right)+6 = 2+2+\cdots+2 = (\log_2 n)\cdot 2 \in O(\log n)$