• Algoritem je postopek, ki nam korak za korakom pove, kako rešiti dani problem
• Za dani problem v splošnem obstaja veliko algoritmov, ki določijo postopek, s katerim rešimo problem

• Npr. obstaja veliko algoritmov za izračun produkta dveh števil:

  • Tabela poštevanke (primerno le za majhna števila)
  • Pisno množenje
  • Množenje z uporabo logaritmov.
  • Uporaba računala.
  • Uporaba postopkov vgrajenih v računalnik.
  • Leibnitzov "računalnik"
  • ...

• navodilo, kako opraviti določen postopek
• KAJ storiti, KAKO to storiti
• Končno zaporedje ukazov, ki, če jih ubogamo, opravijo neko nalogo

• ima podatke
• vrne rezultat (število, risba na zaslonu, izdelan izdelek, ...)
• je natančno določen
• se vedno konča
• mogoče ga je opraviti

• Kako zasnovati algoritem

  • metode, strategije

• Kako preveriti algoritem

  • dokaz pravilnosti

• Kako analizirati algoritem

  • prostorska in časovna zahtevnost

• Kako izraziti algoritem

  • enoličnost, komu je namenjen, kaj so osnovna navodila, komentarji

• Metode za razvoj

  • Deli in vladaj
  • Požrešna metoda
  • Sestopanje
  • Dinamično programiranje
  • Razveji in omeji

• Glede na tip problema

  • Algoritmi za sortiranje/urejanje
  • Algoritmi nad grafi
  • Numerični algoritmi
  • Iskalni algoritmi
• …

• Podatkovna struktura je sistematični način kako organizirati skupino podatkov.
• Za vsako podatkovno strukturo potrebujemo postopke za vstavljanje, brisanje, iskanje in podobno.
• Določene strukture so predstavljene v programskih jezikih (npr. seznam, nabor, slovar … v Pythonu), določene so na voljo kot razširitve jezika (v standardnih knjižnicah in modulih)
• Za določene (npr. iskalno dvojiško drevo …) bomo sestavili predstavitev (v obliki razreda v Pythonu)

• Je vreča, kamor shranjujemo podatke
• Vanjo dajemo in iz nje jemljemo
• Glede na značilnosti tega kakšen podatek dobimo iz vreče (in tudi glede na to kaj mora vreča početi, da nam tak podatek vrne) ločimo različne PS.

• Ko pišemo programe, nam je vseeno, kako je v pomnilniku računalnika npr. zares predstavljen niz (npr. String v p.j. java, ali str v jeziku Python)– le deklariramo spremenljivko tipa String (ali v Pythonu v neko spremenljivko pač shranimo niz) ... in uporabljamo dovoljene operacije.
• Prav tako npr. ne vemo, kako je prestavljen objekt Button v p.j. Delphi. Poznamo le dovoljene operacije nad njim.
• Abstraktni podatkovni tip je podatkovni tip, katerega predstavitev je skrita in ne vpliva na kodo programa
• Z "odstranitvijo" vedenja o dejanski predstavitvi laže pišemo predvsem večje programe.
• neodvisnost od dejanske predstavitveKAJ je struktura in ne KAKO jo predstaviti

• Sklad

  • Iz vreče vedno potegnemo tisti podatek, ki je najmanj časa v vreči

• vrsta

  • Iz vreče vedno potegnemo tisti podatek, ki je najdalj časa v vreči

• Drevo

  • Podatki so urejeni po hierarhiji (nadrejeni/podrejeni)
  • Vedno dobimo le glavnega

• Seznam

  • Podatke dobivamo iz vreče glede na indekse

• Enostavni verižni seznam

  • Vsak podatek ve, kje je njegov naslednik (in nič več)
• ...

• Za dani problem imamo več algoritmov – kateri je "najboljši"?
• Koliko časa dani algoritem zahteva?

• Koliko prostora (pomnilnika) dani algoritem zahteva?

  • Zanima nas dodaten prostor (poleg tistega, ki ga potrebujemo za podatke in rezultat)

    • Slednje tako ali tako potrebujejo vsi algoritmi

  • Čeprav pogosto zanemarjeno, pa je količina dodatnega pomnilnika pogosto zelo pomembna

    • Največ računalnikov ima zelo omejen prostor (računalniki v hišnih napravah, avtomobilih, strojih ...)
• V splošnem je tako časovna kot prostorska zahtevnost odvisna od podatkov za dani algoritem (tipično od "velikosti" vhodnih podatkov).

• Izmišljeni profil dveh algoritmov za urejanje:

• Kateri algoritem je hitrejši?

  • Noben! Eden pri eni, drugi pri drugi količini podatkov
• Čas potreben za alg. B raste počasneje kot čas potreben za algoritem A. Zato rečemo, da je algoritem B boljši.

• Čas meriti v sekundah izvajanja programa?

  • + enostavno

  • – odvisno od jezika, prevajalnika in procesorja.

    • Nemogoče primerjati različne algoritme (razen, če bi imeli možnost izvesti vse na istem računalniku, z istim jezikom, z istim prevajalnikom)

• Šteti karakteristične operacije?

  • (npr. aritmetične operacije v matematičnih algoritmih, primerjave v iskalnih algoritmih, ...)
  • + odvisno le od algoritma, nič od strojne opreme, učinkovitosti prevajalnika, izbranega jezika, uspešnosti kodiranja, meri dejansko učinkovitost algoritma
  • - običajno zapleteno

• T(n) = 5n – 2n + 20

  • Formula, ki nam pove, kako se spreminja čas (število karakterističnih operacij) v odvisnosti od velikosti problema

  • Če rešujemo problem velikosti n, bomo potrebovali 5n – 2n + 20 karakterističnih operacij

    • 500 za problem velikosti 10
    • 7980 za problem velikosti 20
    • ...

• Na računalniku A algoritem X reši problem velikosti n v treh minutah
• Isti program, a z 10x več podatki, izvedemo na istem računalniku. Kaj lahko napovemo glede časa izvajanja?
• Isti program z istimi podatki izvedemo na 1000x hitrejšem računalniku. Kaj lahko napovemo glede časa izvajanja?
• Na računalniku B algoritem Y reši isti problem velikosti n v dveh minutah. Je računalnik B hitrejši od računalnika A? Je algoritem X slabši od algoritma Y?
• Na računalniku A izvedemo algoritem X na n podatkih. Izvajanje traja dve uri. Na računalniku A izvedemo algoritem Y na n podatkih. Izvajanje traja dve uri in pol. Je algoritem X boljši od algoritma Y? Kaj se bo zgodilo, če zgodbo ponovimo na problemu s 100x več podatki?

• Z merjenjem časa dejansko ne zvemo nič!

• Težja
• Natančnejša od meritev
• Da nam RAZUMEVANJE, zakaj določen algoritem potrebuje ta čas
• Vidimo “kritične” dele
• Pogosto iz analize dobimo ideje za izboljšave

• količina sredstev, ki jih potrebujemo za rešitev problema

  • Časovna: Število karakterističnih operacij
  • Prostorska: Število dodatnih spremenljivk (če smo natančnejši – število zlogov pomnilnika)
• odvisnost od obsežnosti (velikosti) problema
• kaj meriti

• pogosto le ocenimo zahtevnost

  • Točna funkcija nas NE zanima

  • Zanima nas rast

    • Kaj se zgodi, če velikost reševanega problema povečujemo
  • T1(n) = 5n – 2n + 20
  • T2(n) = n/100 + 5n + 20
  • T3(n) = 1000000 n - 5000n + 1

  • ZA dovolj velike n se T1, T2, T3 obnašajo podobno

    • enako rastejo
    • kot n

• red velikosti

  • O notacija
  • O(n)

• Algoritem zahtevnosti O(log n) je boljši kot algoritem zahtevnosti O(n), ker je log n za vse vrednosti n od nekje naprej (od dovolj velikega n) zagotovo manjše kot n. O(log n) pomeni počasnejšo rast kot O(n).
• Kompleksnost O(X) pomeni “reda X”, t.j., rast sorazmerno z X. X označuje red rasti, kjer zanemarimo počasneje rastoče člene in konstantne faktorje.

• Običajno so algoritmi taki, da se čas izvajanja lahko zelo razlikuje, če so podatki

  • "idealni"
  • "običajni"
  • "zlobni"

• Npr. bisekcija

  • Če iščemo ravno srednji podatek – idealni podatki – algoritem se takoj zaključi
  • Če iščemo podatek, ki ga ni – "zlobni" podatki – največ dela

• Zato: časovna zahtevnost v najboljšem primeru, najslabšem primeru in pričakovana časovna zahtevnost

  • Minimalna
  • Pričakovana
  • Maksimalna

• Najboljši primer ni, da vzamemo velikost problema 1, ...

  • Še vedno: zahtevnost v odvisnosti od velikosti problema, le vzamemo "idealne" ("zlobne", "običajne") podatke

• Celotna zgodba velja tudi za prostorsko zahtevnost
• Zanima nas količina dodatnega prostora (spremenljivk ...)
• Pogosto so problemi taki, da se, če želimo zmanjšati časovno zahtevnost, poveča prostorska zahtevnost in obratno.

• Uredi n števil v tabeli

  • Velikost problema: koliko števil imamo

• Na farmi zajcev ugotovi, kateri zajec je najtežji

  • Velikost problema: koliko zajcev imamo

• Razvrsti dijake v ravno vrsto

  • Velikost problema: število dijakov

• S pisnim množenjem zmnoži dve števili

  • Velikost problema: število števk obeh števil

• Sliki spremeni ločljivost

  • Velikost problema: število pikslov slike

• Izračunati b

• Enostavni algoritem:

  • Denimo, da izvajalec (v naši zgodbi beri programski jezik) ne pozna b**n ali pow(b, n) ali podobnega “direktnega” ukaza

1. Naj bo p enak 1.
2. Za i = 1, …, n, ponavljaj:
množi p z b.
3. Končaj z odgovorom p.

def poten (b, n):
 ''' Vrne b^n (kjer je n ne-negativen) '''
 p = 1.0;
 for i in range(1, n + 1):
   p = p * b;
 return p

• Štetje množenj (najbolj karakteristična operacija)
• Množenj je n

• Ideja: b = b b. Če poznamo b, lahko b izračunamo le z enim dodatnim množenjem!
• b = b * b = b * (b) = b * b * (b) =
• b * b * (b) = b * b * (b) =
• b * b * b * (b) = b * b * b * (b) =
• b * b * b * (b) = b * b * b * b * (b)
• Ko je eksponent lih – računamo del pred oklepajem
• Na vsakem koraku podvojimo

1. Postavi p na 1, q na b in m na n.
2. Dokler je m > 0, ponavljaj:
2.1. Če je m lih, množi p s q.
2.2. Razpolovi m
(morebitni ostanek zavrzi).
2.3. Množi q s samim seboj.
3. Končaj z odgovorom p.

def poten2(b, n):
    ''' Vrne b**n (kjer je n ne-negativen) '''
    p = 1
    q = b # ustrezna potenca b-ja
    m = n
    while m > 0:
        if m % 2 != 0: # liha potenca
            p = p * q # del pred oklepajem
        m = m // 2
        q = q * q # podvojimo
    return p

def poten3(b, n):
    ''' Vrne b**n (kjer je n ne-negativen)
        Z rekurzijo
    '''
    if n == 0:
        return 1
    if n == 1:
        return b
    p = poten3(b, n // 2) # "polovično"
    p = p * p
    if n %2 != 0: # liha potenca
       p = b * p # manjkajoči b zaradi lihosti
    return p

• Za veliko zanimivih algoritmov je štetje točnega števila operacij prezapleteno

• Da poenostavimo analizo:

  • Določimo najhitreje rastoči faktor
  • Zanemarimo počasneje rastoče faktorje (npr. n v primerjavi z n)
  • Zanemarimo konstantni faktor pri najhitreje rastočem členu (Npr. 6.2n jemljemo kot n).
• Dobljena formula je časovna zahtevnost algoritma. Poudarek je na načinu rasti časa (obnašanju kot neka znana funkcija od nekje (od neke velikosti problema) naprej), potrebnega za izvedbo.
• Podobno naredimo za prostorsko zahtevnost.

• Analiza enostavnega algoritma (štetje množenj):

  • Število množenj = n - 1
• Čas, ki ga algoritem potrebuje, je proporcionalen n.
• Časovna zahtevnost je reda n. To zapišemo kot O(n).

Nekaj značilnih časovnih zahtevnosti:

(predpostavimo, da je zahtevnost točno taka in ne le tega reda)

Denimo, da imamo na voljo 1 uro izvajanja programa na računalniku in v tem času rešimo nalogo velikosti:

• Poznamo veliko problemov za katere ne poznamo t.i. polinomskih algoritmov

• Npr.:

  • Problem trgovskega potnika (kako obiskati n mest (krožna pot), da bo prevožena pot minimalna)
  • Problem optimalnega pakiranja (kako pakirati n izdelkov v zaboje, da bomo porabili minimalno število zabojev)
  • Problem Hanoiskih stolpičev
  • ...
  • M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to NP-Completeness. W. H. Freeman, 1979.

• Mehanik popravlja avtomobile
• Za vsak avto se ve, koliko dni bo trajalo popravilo
• V kakšnem vrstnem redu jih popravljati, da bo povprečni čakalni čas najmanjši možni

• Čakalni čas lastnika:

  • Čas popravila vseh pred njim + čas popravila njegovega algoritma

• Povprečni čakalni čas

  • Vsota čakalnih časov vseh lastnikov / število lastnikov

• Ideja:

  • Preizkusimo vse možne razporeditve
  • Med njimi poiščemo najmanjšo

• Koliko je razporeditev

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1
• Permutacije
• n!
• 42! = ?

• Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n).
• Imamo problem velikosti 100.

• Koliko časa se bo izvajal na računalniku?

  • Ne vemo!
  • Denimo, da je to trajalo 5 sekund.
• Vzemimo problem velikosti 300

• Koliko časa se bo ta izvajal?

  • Ker je rast časa za ta algoritem linearna

  • 3x večji problem - 3x dlje, torej cca 15 sekund

    • V splošnem to ni nujno čisto res (ne vemo, ali smo že dosegli tisto velikost problema, ko "zanemarjeni" členi (ki jih je "pojedla" O notacija) ne delajo "zgage")

• Kaj pa problem velikosti 900?

  • Ker je rast časa za ta algoritem linearna
  • 9x večji problem - 9x dlje, torej cca 45 sekund
• Vsekakor pa od neke velikosti problema dalje zagotovo vemo, da bomo pri reševanju 5x večjega problema čakali na rešitev približno 5x dlje.

• Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost O(n).
• Imamo problem velikosti 100.

• Koliko časa se bo izvajal na računalniku?

  • Ne vemo!
  • Denimo, da je to trajalo 5 sekund.
• Vzemimo problem velikosti 300

• Koliko časa se bo ta izvajal?

  • Ker je rast časa za ta algoritem kvadratična
  • 3x večji problem - 9x (32 x) dlje, torej cca 45 sekund

• Kaj pa problem velikosti 1000?

  • Ker je rast časa za ta algoritem kvadratična
  • 10x večji problem - 100x dlje, torej cca 500 sekund

• Seveda smo pri obeh primerih HUDOOOO poenostavili
• Dva algoritma

• Dejanska čas. zahtevnost naj bo

  • T1(n) = n – 95
  • T2(n) = n / 100 + 4
• Oba O(n)
• T1(100) = 5, T2(100) = 5
• T1(300) = 205, T2(300) = 12
• T1(900) = 805, T2(900) = 13
• T1(1800) = 1705, T2(1800) = 22
• T1(3600) = 3505, T2(3600) = 40
• T1(7200) = 7105, T2(7200) = 76
• T1(14400) = 14305, T2(14400) = 148

• Če podvajamo velikost problema, se rast časa “umiri” pri podvojenem času

• Pri časovni zahtevnosti nas zanima asimptotična RAST časa v odvisnosti od velikosti problema