• 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.
• Statična podatkovna struktura je taka, katere velikost je dokončno določena ob nastanku. Npr. tabela
• Dinamična podatkovna struktura je taka, katere velikost se lahko spreminja (povečuje/zmanjšuje) – npr. povezani seznami, dvojiško drevo, ...
• Za vsako podatkovno strukturo potrebujemo postopke za vstavljanje, brisanje, iskanje in podobno.

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

• 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

• Tabela

  • Podatke dobivamo iz vreče glede na indekse

• 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

• • 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 5n2 – 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

  • Za dovolj velike se , , obnašajo podobno

    • enako rastejo
    • kot funkcija

• red velikosti

  • notacija

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

• Uredi š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

Nekaj značilnih časovnih zahtevnosti:

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

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

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

• Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost .
• 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

  • večji problem - 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" notacija) ne delajo "zgage")

• Kaj pa problem velikosti 900?

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

• Imamo algoritem, za katerega vemo, da je njegova časovna zahtevnost .
• 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
  • večji problem - () dlje, torej cca 45 sekund

• Kaj pa problem velikosti 1000?

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