ASU1 - Algoritmy a štruktúry údajov¶

Prerekvizity¶

  • PAZ1a
  • PAZ1b

Podmienky¶

  • 30 b - cvičenia (aktívna účasť, desaťminútovky)
  • 20+ b - domáce úlohy (teoretické aj praktické)
  • 50 b - skúška (praktické riešenie úlohy + záverečný test)
  • +4 b - úlohu vyriešenú počas programátorskej súťaže ŠVK 2026

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.

ASU1 - Algoritmy a štruktúry údajov¶

web¶

  • stránka predmetu https://ics.upjs.sk/~rkb/?cmd=asu1
  • testovač DomJudge https://rpr.ics.upjs.sk/

Algoritmus¶

  • 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) image.png

  • LEGO

    28.1.2026, UPJŠ, Košice https://ics.upjs.sk/fll

image.png

  • Sladký Valentín s Pečie celé Slovensko. Vyskúšajte recept na minipavlovky
https://www.rtvs.sk/novinky/pecie-cele-slovensko/351614/sladky-valentin-s-pecie-cele-slovensko-vyskusajte-recept-na-minipavlovky

image-2.png

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.
  • Od receptov nie je ďaleko ani k skladaniu nábytku

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

image-3.png

  • 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.

  • definícia (Wikipedia)

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.

  • OpenAI image.png

image.png

Úloha¶

Reprezentujú nasledovné zápisy algoritmus?

ZiskatMilionyEur
=======================
ZarobitPrvyMilionEur
DatDoBankyACakatNaUroky

  • 1995

    https://nbs.sk/statisticke-udaje/financne-trhy/urokove-sadzby/priemerne-urokove-miery-vkladov-v-bankach/

    úroky vklad na 12M boli 11,5% ... čakať na dvojnásobok = $x$ rokov ($1,115^x > 2$)

In [1]:
from math import log
log(2, 1.115) #logaritmus cisla 2 pri zaklade 1.115
Out[1]:
6.3676539421604135

  • 2021

    https://www.martinus.sk/950779-najtazsie-je-zarobit-prvy-milion/kniha

    https://e.dennikn.sk/2234232/banky-zacinaju-uctovat-zaporne-uroky-na-vklady-zatial-len-pre-firmy-a-na-velke-sumy/

image-3.png

SN(x, y)
===================
vysl ← 0
while x > 0
  if x je neparne
    vysl ← vysl + y
  x ← ⌊x/2⌋
  y ← y+y
return vysl

Časová a pamäťová zložitosť¶

O notácia¶

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¶

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[i], there a noise[i], everywhere a noise[i], noise[i]"
  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)$