Ustni Izpit

V programiranju so funkcije višjega reda funkcije, ki sprejmejo neko drugo funkcijo kot argument in/ali vrnejo funkcijo kot rezultat. Primeri takih funkcijo so funkcije map, filter.

Primer uporabe bi bil

map(lambda x: x**2, [1, 2, 3])

Funkcija map sprejme funkcijo (v našem primeru \( x^{2} \))

Primeri funckije višjega so tudi dekoratorji - to so funckije, ki zaobjamejo druge funckije.

def home_decorator(fja):

        def notranja_fja():
                print("Pred funkcijo")
                fja()
                print("Po funkciji")

        return notranja_fja

def uporabljena_fja():
        print("znotraj fja")

uporabljena_fja = home_decorator(uporabljena_fja)

#oz. drugače

@home_decorator
uporabljena_fja()

Rekurzivna funkcija je funkcija, ki kliče samo sebe. Ključen je robni pogoj.

Tako npr. se obračanje seznama s v os dogaja, dokler je len(s) < 1.

Poznamo dve možni rekurziji: glava - rep ali pa bisekcija. Glava rep je ima zahtevnost \( O(n ^2) \), saj vsakič ustvarimo nov seznam (\( O(n) \)) in to naredimo \( n \)-krat.

Pri preiskovanju naletimo na urejeno četverico (S, s, G, \( \sigma \)).

S je množica vseh rešitev (tudi delnih), te rešitve imenujemo tudi stanja. \( s \in S \) je začetno stanje, \( G \subset S \) je množica vseh končnih stanje, tj. pravih rešitev.

\( \sigma: S \to P(S) \) je funkcija, ki tvori množico naslednikov \( \theta \subset S \) za podano stanje \( q \in S \). Funkcija \( \sigma \) ima nekatere lastnosti:

• z njenim iteriranjem na začetnem stanju \( s \) dobimo vsa stanja iz \( S \) in
• stanja se nikoli ne ponovijo: vsako stanje se pojavi le enkrat.

Funkcija \( \sigma \) ustvari t.i. preiskovalno drevo. Notranja vozlišča so tista, ki so že razvejana s to funkcijo, medtem ko so končna vozlišča tista, ki še niso razvejana. Množici končni vozlišč rečemo preiskovalna fronta oz. odprti seznam.

Če smo neinformirani of preiskovalnem drevesu lahko iščemo ali v globino ali pa v širino.

Ko ugotovimo, da naša vaje drevesa, več ne reši danega problema, prekinemo preiskovanje dane veje in se reče, da sestopimo.

je iskanje števila v urejenem seznamu.

Pri bisekciji imamo urejen seznam \( x \) in pa poizvedbo \( e \), ki je potencialno element seznama \( x \). To sta vhoda, potem pa imamo 2 možna rezultata: indeks \( e \) v \( x \), ali pa None, če \( e \not \in x \).

Poznamo več vrst zahtevnosti, ki nam pove, koliko virov je potrebnih za njegovo izvedbo: časovno, prostorsko in drugo (komunikacija, naključnost ali energija).

Računska zahtevnost algoritma nam pove najmanjšo računsko zahtevnost za njegovo reševanje (torej je lahko tudi več kot izračun).

Zahtevnost je odvisna od velikost vhodnih podatkov (npr. pri seznamu imamo dolžino \( n \) seznama \( x \)).

Definiramo funkcijo \( T: \mathbb{N} \to \mathbb{R}^+_0 \), kjer je \( T(n) \) čas potreben za izvedbo logaritma.

Ker se računalniki množično razlikujejo med sabo, za čas lažje definirati število ključnih operacij, kako definirati čas (procesorki, realen, itd) in zato razbijemo \( T(n) = C \cdot t(n) \), kjer je \( C > 0 \) odvisna od strojne opreme in \( t(n) \), ki je odvisna od algoritma.

Pogosto se ukvarjamo z asimptotično zahtevnostjo, ki opisuje porabo virov algoritma pri zelo velikih \( n \), saj je za majhne \( n \) rešitev trivialna.

Zgornjo mejo asimptotične zahtevnosti opisujemo s t.i. notacijo z velikim O-jem.

Notacija z velikim O je definirana kot: naj bosta \( T(n), f(n) > 0 \). Rečemo, da ima \( T(n) \) kompleksnost reda \( f(n) \), če \( T(n) \) raste počasneje kot \( cf(n) \) za \( c > 0 \) in \( n > n_0 \, n_0 \in \mathbb{N} \) oz.

\[ T(n) \in O(f(n)) \iff \exists n_0 \in \mathbb{N}, c >0 \forall n \in \mathbb{N}, n \ge n_0: T(n) \le c f(n) \]

Pri kakršnem koli urejanju je vhod seznam dolžine \( n \) x, ki je neurejen in rezultat je seznam y z elementi seznama \( x \), ki so urejeni v naraščajočem vrstnem redu.

Če računamo Fibonaccijevo zaporedje rekurzivno, imamo funkcijo, ki za vsak naslednji člen izračuna od začetka (torej do 1). Namesto tega lahko uporabimo memoizacijo, pri kateri s pomočjo slovarja shranimo pretekle vrednosti funkcije. To ponavadi naredimo s slovarji.

Možnost 1 je, da definiramo funkcijo višjega reda, ki shrani vrednosti funkcije f v cache, vendar namesto nove funkcije g, ki ne prestreže rekurzivnih klicev f, naredimo f = memo(f).

Lepša rešitev je z dekoratorjem, ki obleče našo funkcijo s funkcijo memo.

Dinamično programiranje je optimizacijski algoritem, ki uporablja memoizacijo ter deli in vladaj, da najdemo optimalno rešitev problema.

Torej ponavljajočih problemov ne rešujemo znova, ampak jih memoiziramo.

Velja načelo optimalnosti: optimalna rešitev je sestavljena iz optimalnih rešitev podproblemov.

Recept za sestavljanje rešitev imenujemo Bellmanova enačba.

Niz znakov, ki določa iskalni vzorec.

Sestavljeni so iz črk podane abecede ter treh regularnih operatorjev: stik (ab), unija ( a ali b ) in iteracija (ponovitve a).

Hevristično programiranje je programiranje, ki se ne osredotoča na racionalno, logično, optimalno rešitev, ampak rešitev, ki je “good enough” in zadosti hiter.

Prostor možnih rešitev delimo na usmerjene/informirane, ki upoštevajo cene rešitev in pa neusmerjene/neinformirane, ki tega ne naredijo.

Preiskovalne strategije primerjamo s kriteriji: popolnost (ang. completeness) - vedno najde rešitev, optimalnost (ang. optimality) - vedno najde optimalno rešitev ter časovna/prostorska zahtevnost.

Parametri prostora stanj, ki vplivajo na zahtevnost so:

1. velikost prostora stanj
2. b, stopnja razvejanosti
3. d, najmanjša razdalja med začetnim stanje in rešitvijo
4. m, dolžina najdaljše poti v prostoru stanj

Če imamo problem P, lahko uporabimo različne pristope za preiskovanje možnih rešitev. Najpogostejši so iskanje v globino, širino, iterativno poglabljanje, najprej najboljši, A*

Pri hevristiki imamo pogled naprej. Če imamo trenutno ceno \( g(s) = c(s_0, s) \), kjer je \( s_0 \) začetno stanje in c je razdalja med \( s \) in \( s_0 \).

Hevristika je funkcija \( h: S \to \mathbb{R} \), ki oceni dolžino(ceno) poti do cilja: \( h(s) \approx c(s, s_{G}) \), kjer je S prostor stanj in G rešitev.

Pri hevristiki imamo dve komponenti: znano ceno delne rešitve do trenutne točke \( g(s) \) in ceno rešitve \( h(s) \) od trenutnega do končnega stanja.

Hevristika je sprejemljiva, če velja \( h(s) \le c(s, s_G) \). Ekstremna primera sta \( h(s) = 0 \) je neuporabna hevristika, A* postane najprej najboljši, \( h(s) = c(s, S_G) \), ki je super, vendar predraga za izračunati. Dobra hevristika je tista, kjer je razlika \( c(s, S_G) - h(s) \) čim manjša.

Je podatkovna struktura, kar je format za organiziranje, upravljanje in shranjevanje podatkov. Prav tako podatkovna struktura omogoča učinkovit dostop do podatkov ter njihovo učinkovito spreminjanje.

Funkcija doda podatek na konec vrste in jemlje podatek iz začetka vrsta ai. queue FIFO in je uporabna pri iskanju v širino ali kot medpomnilnik.

Primer s seznamom \( s \) dolžine \( l \). Imamo tri podatkovne elemente: seznam \( s \), \( z \) je indeks prvega elementa v vrsti in \( k \) je prvi indeks prve proste lokacije.

Dodamo element preko s[k] = x in \( k = k+1 \). Če je bil \( k = l -1 \), je \( k=0 \) in računamo po modulu \( l \).

Vzamemo element s[z] in \( z = z+1 \) in spet računamo po modulu \( l \).

Če je \( z = k \) imamo prazen seznam in če \( (k + 1) - z = 0 \) imamo poln seznam, vendar če imamo krožen seznam veljata neenakosti \( z > k, \, z < k \)

Ali prioritetna vrsta (ang. priority queue). Dodamo podatek s pridruženo numerično prioriteto, in jemljemo podatek z najvišjo prioriteto. Uporabno je pri računanju minimuma, maksimuma, mediane ali drugih kvartilov.

Če imamo urejen seznam po padajoči prioriteti, je jemanje elementa z najvišjo prioriteto \( O(1) \) in dodamo element z bisekcijo \( O(\log n) \) ali vrivanje \( O(n) \).

Če imamo neurejen seznam je jemanje elementa z najvišjo prioriteto \( O(n) \) in dodamo vedno na konec seznam \( O(1) \).

Kopica je dvojiško drevo in element v korenu ima najvišjo prioriteto. Če vzamemo element z najvišjo prioriteto, vzamemo koren, zahtevnost \( O(1) \), če dodamo element, ga dodamo v prvo prosto vozlišče in popravimo kopico.

Če damo drevo v seznam, je koren prvi element seznama s[0], levi potomec je s[2i + 1] in desni potomec s[2i + 2]. Prednik vozlišča s[i] je s[(i - 1)//2] Zahtevnost časovna je \( O(\log n) \)

Iskalno drevo shranjuje iskalne ključe. Mora biti zmožen dodati nov ključ in iskat ključ ter ugotoviti ali je v drevesu.

Drevo je lahko globine \( \log_2 n < d < n \), kjer je \( n \) število vozlišč. Če je \( d = n \) je izrojeno.

Glavna lastnost iskalnega dvojiškega drevesa je to, da so vsi potomci na levi manjši od prednika in vsi potomci na desni večji od prednika.

časovne zahtevnosti: