Ispit Flashcards
Šta je to struktura podataka?
Struktura podataka – “statički” aspekt nekog programa (ono sa čime se radi) skupina varijabli u nekom programu i veza između njih.
Šta je to algoritam?
Algoritam – “dinamički” aspekt programa (ono što se radi) konačni niz instrukcija, od kojih svaka ima jasno značenje i može biti izvršena u realnom vremenu.
Šta je to program?
program - opis algoritma koji u nekom programskom jeziku jednoznačno određuje što računalo treba napraviti
Šta predstavlja programiranje?
programiranje - naučiti sintaksu nekog proceduralnog jezika i steći osnovna intuitivna znanja glede algoritmizacije problema opisanog riječima
algoritmi + strukture podataka = programi (Wirth)
Za šta ih koristimo?
kako osmisliti algoritme? kako strukturirati podatke? kako formulirati algoritme? kako verificirati korektnost algoritama? kako analizirati algoritme? kako provjeriti (testirati) program?
Koja je svrha analize algoritma?
svrha
intelektualna razonoda
predviđanje vremena izračuna
pronalaženje učinkovitijih algoritama
pretpostavke:
sekvencijalno jednoprocesorsko računalo
fiksno vrijeme dohvata sadržaja memorijske lokacije
vrijeme obavljanja operacija (aritmetičke, logičke, pridruživanje, poziv funkcije) je ograničeno nekom konstantom kao gornjom granicom
Koji je izbor skupova podataka za iscrpno testiranje algoritma:
ponašanje u najboljem slučaju (best case scenario)
ponašanje u najgorem slučaju (worst case scenario)
prosječno (tipično) ponašanje
Šta predstavlja “a priori”?
Tajanje izvođenja algoritma (u najgorem slučaju) kao vrijednost funkcije nekih relevantnih argumenata (npr. broja podataka)
Šta predstavlja “a posteriori”?
Statistika dobivena mjerenjem na računalu
Zašto proračunavamo algoritme?
Teorijska vrijednost:
Jezgra računarstva
Praktična primjena:
Korištenje pri rješavanju problema
Navesti strategije oblikovanja algoritma
Korištenje (računalne) sile Podijeli pa vladaj Smanji pa vladaj Transformiraj pa vladaj Balansiranje između zauzimanja prostora i vremena izvršavanja Pohlepni pristup Dinamičko programiranje Iteracijski napredak Unatražno praćenje
Navesti klase problema
Sortiranja Pretraživanja Procesuiranje stringova (alfanumeričkih nizova) Problemi grafova Kombinatorni problemi Geometrijski problemi Numerički problemi
Navesti primjere algoritma sortiranja
- Selection sort
- Bubble sort
- Heap sort
- Merge sort
- Quick sort
- Insertion sortt
Primjeri algoritama traženja:
Sekvencijalno traženje
Binarno traženje
Neformalna definicija grafa glasi:
Neformalna definicija: graf je skup čvorova od kojih su neki povezani vezama koje nazivamo bridovima.
Primjeni algoritama grafa:
Prolazak kroz graf
Topološko sortiranje
Predsnosti i nedostaci korištenja strategije (računalne sile)?
Prednosti korištenja strategije (računalne) sile:
Jednostavno oblikovanje algoritma
Mogućnost česte primjene
Lako razumljivi algoritmi
Nedostatci:
Često vrlo neefikasni algoritmi
Spori algoritmi
Primjeri kod kojih se koristi strategija podijeli i vladaj:
Merge i quick sort
Binarno traženje
Množenje velikih cijelih brojeva
Množenje velikih matrica
Primjeri strategija: smanji i vladaj
Reduciranje instance problema prema manjim instancama istog problema
Rješavanje manjih instanci
Proširivanje rješenja manje instance kao rješenja glavnog problema.
Primjer: Euklidov algoritam
Primjeri strategija: smanji i vladaj
Primjeri strategija: transformiraj pa vladaj
Ova skupina metoda rješava problem transformacijama. Ovo je moguće napraviti na 3 načina:
Pojednostavljivanjem instance problema
Drugačijom reprezentacijom instance problema.
Reduciranjem problema njegovim transformiranjem u problem kojeg je lakše riješiti.
Primjeri primjene strategije transformiraj i vladaj
Mnoge probleme kod primjeni listi je moguće jednostavnije riješiti sortiranjem liste – npr. pretraživanje liste: nakon što sortiramo listu možemo primjeniti algoritam binarnog traženja.
Gaussovim transformacijama sustav jednadžbi transformiramo u jednostavno rješivu ekvivalentnu instancu problema.
Primjeri strategija: dinamičko programiranje
Dinamičko programiranje obuhvaća grupu formalnih (razrađenih i usvojenih) postupaka optimalizacije kod kojih se obimni i/ili teško obradivi problemi (sustavi u cjelini) dijele u niz manjih lako obradivih problema (komponente sustava). Rješenja se potom dobivaju koračnim postupkom, pri čemu se u svakom koraku (k) optimalizacije uzimaju u obzir optimalna rješenja prethodnog koraka (k–1).
