01a_asp-uvod.pdf

Čas 1.1 - Uvod Obaveze studenata • Predispitne obaveze: – test sa vežbi - 20 poena – test sa predavanja - 10 poena • Završni ispit: – praktični ispit - 30 poena (prag 15 poena) – usmeni ispit - 40 poena (prag 20 poena)

Literatura • Filip Marić, Vesna Marinković, Mladen Nikolić: Algoritmi i strukture podataka, beleške sa predavanja i vežbi • Miodrag Živković: Algoritmi • Miodrag Živkokvić, Vesna Marinković: Algoritmi i strukture podataka, skripta • Predrag Janičić, Filip Marić: Programiranje 2, skripta • Thomas H. Cormen. Charles E. Leiserson. Ronald L. Rivest. Clifford Stein. Introduction to Algorithms. Third Edition. The MIT Press. • Steven S. Skiena. The Algorithm Design Manual, Springer. • onlajn literatura (petlja.org, geeksforgeeks.org, . . . )

Preduslovi • Nema formalnih preduslova, ali se podrazumeva da ste savladali u potpunosti gradivo koje se predaje na P1/P2, kao i elementarne pojmove diskretne matematike (koji se pokrivaju i u srednjim školama). Potrebno je, na primer, da umete da rešite sve naredne zadatke. – Navesti bar jedan algoritam čije vreme izvršavanja zadovoljava rekurentnu jednačinu T (n) = 2T (n/2) + O(n), T (1) = O(1). Koja je rezultujuća složenost? – Opisati i implementirati korak particionisanja kod algoritma QuickSort. – Definisati strukturu čvora dvostruko povezane liste i funkciju koja briše takvu listu (poznat je pokazivač na njen prvi član). – Navesti primer niza od k elemenata za koji se algoritam umetanja jednog po jednog čvora u nebalansirano pretraživačko binarno stablo izvršava najsporije. Koja je složenost umetanja svih elemenata u tom slučaju?

1

– Definisati rekurzivnu funkciju koja izračunava 1 + ... + n. Kolika je vrednost tog zbira? – Indukcijom dokaži da je 1 + 3 + ... + (2k + 1) = (k + 1)2 . – Ukloni rekurziju iz naredne funkcije koja određuje koliko se kvadrata može iseći od pravougaonika dimenzije a × b, ako se u svakom koraku iseca kvadrat manje dimenzije. int brojKvadrata(int a, int b) { if (b == 0) return 0; return a / b + brojKvadrata(b, a % b); }

Pojam algoritma i strukture podataka Kao što sam naziv kursa govori, ključne teme ovog kursa predstavljaju algoritmi i strukture podataka. • Niklaus Wirth (tvorac Pascal-a): algoritmi + strukture podataka = programi • Algoritmi su sredstva za rešavanje precizno definisanih računskih problema. Npr. problem neopadajućeg sortiranja niza brojeva se može definisati na sledeći način: – Ulaz: niz brojeva (a0 , a1 , . . . , an−1 ) – Izlaz: permutacija (a00 , a01 , . . . , a0n−1 ) ulaznog niza takva da je a00 ≤ a01 ≤ . . . ≤ a0n−1 . • Veoma neformalno: algoritam je precizno definisana procedura izračunavanja tj. niz koraka izračunavanja, koja, polazeći od neke vrednosti (ili niza vrednosti, skupa vrednosti, itd.) kao ulaza proizvodi neku vrednost (ili niz vrednosti, skup vrednosti itd.) kao izlaz. • Strukture podataka predstavljaju načine organizacije i skladištenja podataka koji omogućavaju efikasan pristup željenim podacima i njihovu efikasnu modifikaciju. Strukture podataka sačinjavaju kolekcije vrednosti podataka, veze između njih i funkcije i operacije koje se mogu primeniti nad tim podacima.

Načini opisa algoritama Neki od najčešće korišćenih mehanizama za opis algoritama su sledeći: • programski kôd • pseudo-kôd

2

• blok dijagrami toka • scratch/blockly dijagrami • ...

Formalne definicije algoritama Postoje precizne definicije pojma algoritma (nastale 1930-ih kada su se logičari bavili pitanjem šta se može, a šta ne može izračunati praćenjem precizno definisanih postupaka). • • • • •

URM mašine Tjuringove mašine Gedelove rekurzivne funkcije Čerčov lambda račun ...

3