Algoritmi i strukture podataka
ID: 0390nosilac predmeta: Bengin Č. Aleksandar
nivo studija: master akademske studije
ESPB: 6
oblik završnog ispita: pismeni
katedra: mašinstvo i informacione tehnologije
cilj
• Osnove dizajna i analize algoritama,• Razumevanje koncepta apstraktnih tipova podataka i njihove implementacije,
• Upoznavanje sa osnovnim i složenijim strukturama podataka,
• Predstavljanje standardnih algoritama koji se koriste za rešavanje problema pretraživanja, sortiranja i optimizacije.
ishod
Posle uspešnog odlušanog programa koji je predviđen ovim predmetom student može:• da prepozna i odabere odgovarajuću strukturu podataka za podatke koje treba obrađivati,
• da odabere najbrži, najefikasniji ili najtačniji algoritam za odgovarajući problem,
• da odabere algoritam iz klase iterativnih ili rekurzivnih algoritama.
sadržaj teorijske nastave
Definicije algoritma. Analiza algoritama. Zapis algoritama. Pojam apstraktnog tipa podataka. Elementi od kojih se grade strukture podataka.Lista. Stek. Red.
Stabla. Binarna stabla. Binarno stablo za pretraživanje. Binarni hip.
Skup. Rečnik. Heširanje.
Redovi prioriteta. Preslikavanje. Relacija.
Sortiranje zamenom elemenata. Sortiranje umetanjem. Rekurzivni algoritmi za sortiranje. Sortiranje pomoću binarnog stabla.
Sekvencijalno pretraživanje. Binarno pretraživanje. Pretraživanje pomoću binarnog stabla. Crveno-crno stablo.
Osnovni pojmovi. Usmereni i neusmereni grafovi. Petraga u dubinu i širinu. Primene pretrage u dubinu i širinu.
Zavadi pa vladaj. Hanojske kule. Sortiranje sažimanjem. Brzo sortiranje. Traženje elementa u listi. Množenje velikih celih brojeva. Fibonačijevi brojevi. Binomni koeficijenti. Najduži zajednički podniz. Triangulacija poligona. Određivanje šanse za pobedu u takmičenju. Problem ranca. Problem vraćanje kusura. Problem bojenja atlasa. Optimalno sžimanje sortiranih lista. Problem ranca. Problem rasporeda časova. Problem n kraljica. Problem trgovačkog putnika. Problem stabilnih brakova.
sadržaj praktične nastave
Sastoji se iz auditornih, laboratorijskih vežbi koje prate sadržaj predmeta.resursi
Neophodan softver za ovaj predmet je pod GNU licencom - besplatan je. Ukoliko koristite LINUX neophodni S/C++ Vam je odmah dostupna. Ukoliko koristite drugi operativni sistem S/C++ možete preuzeti sa odgovarajuće WEB lokacije (vidi URL) ili na samom URL-u. Za pokretanje neophodnog softvera dovoljno je posedovati najjednostavniji PC računar.fond časova
ukupan fond časova: 75aktivna nastava (teorijska)
novo gradivo: 20razrada i primeri (rekapitulacija): 0
aktivna nastava (praktična)
auditorne vežbe: 6laboratorijske vežbe: 13
računski zadaci: 0
seminarski rad: 15
projekat: 3
konsultacije: 0
diskusija/radionica: 3
studijski istraživački rad: 0
provera znanja
pregled i ocena računskih zadataka: 0pregled i ocena laboratorijskih izveštaja: 0
pregled i ocena seminarskih radova: 3
pregled i ocena projekta: 3
kolokvijum sa ocenjivanjem: 0
test sa ocenjivanjem: 4
završni ispit: 5
Preuzeto sa www.mas.bg.ac.rs
