<jupyter_start><jupyter_text>3. Podatkovne strukture in algoritmi         <NAME>, Lucami, FE      Kontakt: prof. dr. <NAME>, <EMAIL>, skype=akosir_sid  1   3. Podatkovne strukture in algoritmi  Cilji  ■ Cilji- Spoznati pomen podatkovnih struktur in algoritmov v optimizaciji- Pomen računske in prostorske zahtevnosti- Umestitev	   Računalniški program = podatkovna struktura + algoritem     - Osnovno spoznanje:    Načrtovanje algoritmov se ne začne pri postopku, ampak pri podatkovni strukturi! Pomembni pojmi- Podatkovne strukture- Algoritmi    - Računska in prostorska zahtevnost algoritmov     - Velikost podatkov    - Razredi zahtevnosti  2   3. Podatkovne strukture in algoritmi  Poglavja  Poglavja (1) 3.1.Algoritem in psevdokoda■ Definicija in osnovne lastnosti algoritma $\large{*}$■ Psevdokoda $\large{*}$ 3.2. Podatkovne strukture■ Opis podatkovne strukture $\large{*}$ ■ Vrste podatkovnih struktur $\large{*}$■ Podatkovna struktura Sklad■ Podatkovna struktura Seznam■ Podatkovna struktura Vrsta■ Podatkovna struktura Graf■ Primer uporabe podatkovne strukture: sprehod po grafu v širino 3   3. Podatkovne strukture in algoritmi  Poglavja  Poglavja (2) 3.3. Računska in prostorska zahtevnost algoritma■ Opis računske in prostorske zahtevnosti algoritma $\large{*}$ ■ Velikost vhodnih podatkov $\large{*}$■ Definicija razredov zahtevnosti $\large{*}$■ Razredi zahtevnosti – seznam ■ Časovna in prostorska (spominska) zahtevnost ■ Izvedba analize zahtevnosti algoritma ■ Primer: razcep simetrične matrike ■ Zahtevnost algoritma - opažanja  4   3. Podatkovne strukture in algoritmi  3. 1. Algoritem in psevdokoda  3. 1. Algoritem in psevdokoda■ Uvod■ Definicija in osnovne lastnosti algoritma■ Psevdokoda 5   3. Podatkovne strukture in algoritmi  3. 1. Algoritem in psevdokoda  ■ Uvod- Zakaj je računska in prostorska zahtevnost bistvena- Algoritem sestopanje (angl. backtracking) reši vse probleme- Postopek ```python 1: def sestopiR(n, S, k, x, resitev): 2:     n globina drevesa S množica odločitev, S[k] možne odločitve na k-tem koraku, k trenutni korak 3:     x vektor, ki vsebuje naše dosedanje odločitve, x[0] je odločitev na prvem koraku, x[1] na drugem... 4:    for (i = 0; i < S[k].length; i++) { 5:        x = S[k][i];                     i-ti element množice S[k] 6:        if lahkoVodiKCilju(k, x) { 7:            if (k == n) {                   9:            resitev.dodajNovoResitev(x); 10:        }                              11:        else {12:         gremo na naslednji nivo z odločitvijo x[i] = S[k][i]13:        sestopiR(n, S, k + 1, x, resitev);14:      }15:    }16:  }```- Ta algoritem ima eksponentno zahtevnost in je praktično neuporaben- Zato je iskanje algoritmov z uporabno zajtevnostjo bistveno pri optimizaciji  6   3. Podatkovne strukture in algoritmi  3. 1. Algoritem in psevdokoda  ■ Definicija in osnovne lastnosti algoritma- **Definicija (Algoritem):** _Algoritem je končno zaporedje natančno določenih korakov na vhodnih podatkih._- Osnovne lastnosti in zahteve algoritmov    - Vhodni podatki: vhodni podatki so podani;    - Rezultati:rezultati so vedno na voljo ob koncu izvajanja;    - Natančnost: koraki so za vse vhodne podatke natančno določeni;    - Determičnost: vmesni in končni rezultati so natančno določeni in odvisni le od vhodnih podatkov (izjema so stohastični algoritmi);     - Končno korakov: za vsak nabor vhodnih podatkov le končno korakov;    - Korektnost: rezultati ustrezajo nalogi;    - Splošnost: algoritem je izvedljiv za vse nabore vhodnih podatkov;    - Odvisnost od stroja:    - Omejimo se na eno procesorski računalnik (znanje bo uporabno tudi na HPC)    - Turingov stroj  7   3. Podatkovne strukture in algoritmi  3. 1. Algoritem in psevdokoda  ■ Psevdokoda- **Opis (Psevdkoda)** _Zapis abstraktne podatkovne strukture ali algoritma, neodvisen od programske implementacije (od programskega jezika)._- Podaja    - Vhodne podatke    - Rezultate    - Postopek do izbranega nivoja     8   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  3.2. Podatkovne strukture■ Opis podatkovne strukture■ Vrste podatkovnih struktur■ Podatkovna struktura Sklad■ Podatkovna struktura Seznam■ Podatkovna struktura Vrsta■ Podatkovna struktura Graf■ Primer uporabe podatkovne strukture: sprehod po grafu v širino 9   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Opis podatkovne strukture**Opis (Podatkovna struktura)** _Podatkovna struktura je način organizacije podatkov v računalniku._- Podatkovna struktura je opis    - Shranjevanja sestavljenih podatkov    - Osnovnih operacij na teh podatkih: dostop, manipulacija- Namen vpeljave podatkovnih struktur je:    - Ločitev opisa podatkov od konkretne implementacije v programskem jeziku;    - Omogoča univerzalne študije lastnosti: korektnost    - Določanje zahtevnosti algoritmov        - Poznamo    - Primitivni tipi: char, int, ...    - Sestavljeni tipi: array, ...    - Abstraktne podatkovne strukture: sklad, vrsta, .... 10   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Vrste podatkovnih struktur- Primitivni tipi    - Obstajajo: Logični (binarni), Char, Float, Double, Integer, Enumerated;    - Namen: Predstavitev števil- Sestavljeni:    - Obstajajo: Array, Struct,Union, ...    - Namen: Predstavitev polj podatkov (matrik, ...)- Abstraktni podatkovni tipi - za nas pomembni abstraktni tipi    - Seznam (List)    - Vrsta (Queue)    - Sklad (Stack)    - Graf (Graph)    - Namen: predstavitev kompleksnih podatkov      11   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Podatkovna struktura Sklad- Uporaba:    - modeli procesorjev: Von Neumanovi procesor    - „Reverse Polish notion “ RPN 12   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Podatkovna struktura Vrsta (ang. queue)- Uporaba    - Čakalne vrste    - Sprehodi po grafih         13   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Podatkovna struktura Graf (ang. graph)- Oznaka $ G = (V ,E)$    - Vozlišča $V$:  oznake z naravnimi števili    - Povezave $E=\{(u,v): u,v\in V\}$         - Uporaba    - Predstavitev omrežja    - Podatkovna struktura optimizacijskih algoritmov     14   3. Podatkovne strukture in algoritmi  3.2. Podatkovne strukture  ■ Primer uporabe podatkovne strukture: sprehod po grafu v širino- Teoretična analiza: algoritem je korekten = (obišče vsa vozlišča)- Neodvisno od implementacije- Uvedba novih osnovnih operacij za analizo zahtevnosti- Graf $G=(E, V)$    $E=\{1,2,3,4,5\}$     $V=\{(12),(13),(23),(24),(34),(35),(45)\}$         15   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  3.3. Računska in prostorska zahtevnost algoritma■ Opis računske in prostorske zahtevnosti algoritma  ■ Velikost vhodnih podatkov ■ Definicija razredov zahtevnosti ■ Razredi zahtevnosti – seznam ■ Časovna in prostorska (spominska) zahtevnost ■ Izvedba analize zahtevnosti algoritma ■ Primer: razcep simetrične matrike ■ Zahtevnost algoritma - opažanja  16   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Opis računske in prostorske zahtevnosti algoritma - Zakaj:     - Bistveno za praktično uporabnost algoritmov;    - Algoritem „sestopanje“ reši vsak problem, a prepočasi;- Namen:    - Izvedba analize konkretnega algoritma    - Osnovni razredi zahtevnosti    - Orientacija med znanimi algoritmi        - Tipi zahtevnosti    - **Najslabša (angl: worst case) zahtevnost**: število korakov, ki za noben nabor vhodnih podatkov ne bo preseženo;    - **Povprečna zahtevnost (angl: average case)**: povprečno število korakov za pričakovane nabore vhodnih podatkov, torej število, okoli katerega bo največ realnih izidov. Izkaže se, da je lahko med najslabšo in povprečno zahtevnostjo velika in bistvena razlika.   17   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Velikost vhodnih podatkov- Velikost vhodnih podatkov v analizo zahtevnosti algoritma- Odvisno od tipa podatkov in algoritma- Tipi vhodnih podatkov in merjenje      Tip podatka    Velikost    Primer algoritma         Število $n$    $\log_2(n)$    Razcep na praštevila        Seznam $L$     $|L|$    Urejanje        Matrika $A$    $|A_1|$    Inverz        Graf $G=(V,E)$     $\max(|V|, |E|)$     Največje vpeto drevo   18   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Definicija razredov zahtevnosti- Zanima nas zahtevnost za velike količine vhodnih podatkov- **Definicija** Naj bosta $f,g:ℕ\to ℝ_+$ nenegativni funkciji na pozitivnih naravnih številih. Funkcija $f$ je v razredu $O(g(n))$, če obstajata konstanti $C_1>0$ in $N_1>0$ tako, da velja$$ f(n)\leq C_1 g(n) \mbox{ za vse } n>N_1. $$Funkcija $f$ je v razredu $o(g(n))$, če velja$$ \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.  $$- Opazimo:    - Veliki $O$ pomeni, da funkcija $f$ narašča enako hitro kot predstavnik razreda $g$    - Mali $o$ pomeni, da funkcija $f$ narašča počasneje kot predstavnik razreda $g$ 19   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Časovna in prostorska (spominska) zahtevnost- Časovna zahtevnost    - Oznaka $𝑇(𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑒𝑚)$ [število osnovnih operacij = ciklov]    - Osnovne operacije: $+, -, *, /, \ldots$ - odvisno od strojne opreme    - Razmerje med $𝑇(𝑜𝑝)$ in $𝑇(𝑝𝑟𝑜𝑐)$;        - Python primer: koren            - **Definicija:** _Časovna zahtevnost algoritma je število osnovnih operacij v odvisnosti od velikosti vhodnih podatkov._            - Prostorska (spominska) zahtevnost    - Oznaka $𝑀(𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑒𝑚)$ [število osnovnih spominskih enot ]    - Osnovne spominske enote: bajt ali spomin za eno npr. decimalno število        - Python primer: kasneje Cholesky            - **Definicija:** _Prostorska zahtevnost algoritma je število osnovnih spominskih enot v odvisnosti od velikosti vhodnih podatkov._     20   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Razredi zahtevnosti – seznam      Ime    Razred    Opomba        Konstantni    $O(1)$             Log log    $O(\log(\log(n))$             Log    $O(\log(n))$            Sublinearen    $O(n^c)$, $c            Linearen    $O(n)$            N Log n    $O(n\log(n))$    Zelo uporabno        Kvadratični    $O(n^2)$    Uporabno        Kubični    $O(n^3)$            Polinomski    $O(n^k)$, $k\geq 1$    Meja uporabnosti        Eksponentni    $O(c^n)$, $c>1$    Neuporabno        Fakultetni    $O(n!)$       21   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Razredi zahtevnosti - grafiRazredi naraščanja zahtevnosti povedo, da močnejša strojna oprema ni rešitev, ker čas izvajanja ni praktično dostopen; 22<jupyter_code>## Time complexity of slected classes
import numpy as np
import matplotlib.pyplot as plt


fig, ax = plt.subplots(figsize=(8, 6))

n_max = 12
n_lst = np.arange(n_max)+1
lin10n_lst = [10*n for n in n_lst]
lin20n_lst = [20*n for n in n_lst]
nlogn_lst = [n*np.log(n) for n in n_lst]
quadr_lst = [n**2 for n in n_lst]
qubic_lst = [n**3 for n in n_lst]
exp_lst = [2**n for n in n_lst]

ax.plot(n_lst, lin10n_lst, label='$10 n$')
ax.plot(n_lst, lin20n_lst, label='$20 n$')
ax.plot(n_lst, nlogn_lst, label='$n \log(n)$')
ax.plot(n_lst, quadr_lst, label='$n^2$')
ax.plot(n_lst, qubic_lst, label='$n^3$')
ax.plot(n_lst, exp_lst, label='$2^n$')
plt.legend()
plt.show


#<img src="https://raw.githubusercontent.com/andrejkk/ORvTK_SlidesImgs/master/footer_full.jpg"><jupyter_output><empty_output><jupyter_text>3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Izvedba analize zahtevnosti algoritma: najslabša- Postopek teoretične analize zahtevnosti algoritma    1. Določitev merjenja velikosti vhodnih podatkov;    2. Določitev osnovnih operacij in njihovih zahtevnosti;    3. Analiza psevdokode po korakih    4. Seštevanje zahtevnosti    5. Analiza vodilnih členov in uvrstitev algoritma v razred zahtevnosti- Merjenje na podlagi implementacije – merjenje časa na podlagi implementacije    - Merjenje časa izvajanja na izbranih velikosti podatkov    - Analiza primerjave z osnovno operacijo    - Prileganje modelov- Rezultat analize je uvrstitev algoritma v zahtevnostni razred;- Je osnova za odločitev glede praktične uporabnosti algoritma 23   3. Podatkovne strukture in algoritmi  3.3. Računska in prostorska zahtevnost algoritma  ■ Primer: razcep simetrične matrike- Primer: algoritem Choleskega za razcep matrike $A = V.V^\top$- Časovna zahtevnost $n^3/3 + O(n^2)$- Prostorska zahtevnost $n^2/2 + O(n)$- Ocenjena zahtevnost korena:    $c = O(1)$, $c=1,037$  - Matlab: linearno, glejte sliko  - Python: glejte kodo in sliko naslednje celice 24<jupyter_code># Zahtevnost kvadratnega korena - merjenje konstante c


import numpy as np
from timeit import default_timer as timer
import matplotlib.pyplot as plt


p_num = 100
N = 1000000000000000
dN = int(N/p_num)

# One operation time
y = np.sqrt(2)
start = timer()
y = 1 + 1
end = timer()
op_time = end - start

x_lst = range(1, N, dN)
time_lst = np.zeros(p_num)
n_count = 0
for x in x_lst:
    start = timer()
    y = np.sqrt(x)
    end = timer()
    time_lst[n_count] = (end - start) / op_time
    n_count += 1

fig, ax = plt.subplots(figsize=(6, 6))
ax.plot(x_lst, time_lst, label='')
plt.show()

# Določitev C1 in N1: Celoten izraz

import numpy as np
import matplotlib.pyplot as plt

N = 35
n_lst = range(N)

def f(n):
    return (2.0/3)*n**3 + n**2 + (c-5.0/3)

    
c = 1 
C1 = 1
f_lst = [f(n) for n in n_lst]
g_lst = [C1*n**3 for n in n_lst]
    
fig, ax = plt.subplots(figsize=(6, 6))
ax.plot(n_lst, f_lst, label='f')
ax.plot(n_lst, g_lst, label='g')
plt.legend()
plt.show()

# Določitev C1 in N1: celoten izraz

import numpy as np
import matplotlib.pyplot as plt

N = 35
n_lst = range(N)

def f(n):
    return n**2 + (c-5.0/3)

    
c = 1 
C1 = 2
f_lst = [f(n) for n in n_lst]
g_lst = [C1*n**2 for n in n_lst]
    
fig, ax = plt.subplots(figsize=(6, 6))
ax.plot(n_lst, f_lst, label='f')
ax.plot(n_lst, g_lst, label='g')
plt.legend()
plt.show()<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup