Osposobljavanje studenata za:
• razumijevanje i primjenu temeljnih znanja o analizi složenosti algoritama,
• trajno usvajanje i produbljivanje znanja iz područja dinamičke alokacije memorije, te baratanje apstraktnim tipovima podataka kao što su stog, red lista te različite vrste binarnih stabala,
• razumijevanje i primjena grupiranja podataka (engl. hashing) i hrpi (eng. heap).
očekivani ishodi učenja
Studenti će nakon uspješno savladanog predmeta moći:
• definirati temeljne pojmove vezane uz analizu složenosti algoritama,
• objasniti i realizirati postupke dodavanja, brisanja, pretraživanja elemenata u jednostruko i dvostruko vezanim listama,
• realizirati funkcije za dodavanje elemenata u stog i red, te njihovo uklanjanje,
• prepoznati primjenu apstraktnih tipova podataka u rješavanju problema,
• opisati postupke dodavanja, brisanja i pretraživanja elemenata elemenata u binarno stablo za pretraživanje,
• koristiti osnovne postupke balansiranja AVL stabala,
• primijeniti funkcije za grupiranje podataka i otvoreno adresiranje,
• opisati način rada hrpi (engl. heap).
Program je organiziran oko ideje apstrakcije podataka i definiranja apstraktnog tipa podataka. Analiziraju se izvedbe temeljnih tipova i strukture podataka: nizovi i string, stog, red, jednostruko i dvostruko vezane liste, stabla, binarna stabla i balansirana binarna stabla, hash tablice, skupovi, i grafovi. Za procesiranje ovih struktura uče se tehnike sortiranja i traženja, hashing, skupljanje memorijskog otpada i kontrola korištenja memorije. Temeljna znanja o složenosti algoritama.
preporučena literatura
Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”,(poglavlja 1-6)
dopunska literatura
Robert Sedgewick, “Algorithms in C”
jezik poduke
Hrvatski
način praćenja kvalitete i uspješnosti izvedbe svakog predmeta i/ili modula
Mišljenja studenata o kvaliteti nastave putem anketa.
Nastavnici koji podučavaju srodne predmete surađuju i zajednički vode brigu o kvaliteti nastave.
Povremeno promatranje i evaluacija nastave od strane predstojnika odsjeka/ šefa katedre, itd.
ispit (način polaganja, ispitni rokovi)
Ispit se sastoji od teoretskog i laboratorijskog dijela. Jednom kada se neki od dijelova položi, ocjena vrijedi do kraja akademske godine.
Laboratorijski dio se polaže na računalima po završetku laboratorijskih vježbi, te nakon toga na svakom ispitnom roku.
Teoretski dio se polaže pismeno i to podijeljen u dva kolokvija. Tijekom semestra bit će organiziran jedan kolokvij, a na svim ostalim rokovima studenti mogu birati koji će kolokvij polagati (mogu i oba istovremeno).
Uvjeti za pozitivnu ocjenu su: odrađene laboratorijske vježbe 100%, pozitivna ocjena iz laboratorijskih vježbi i više od 50% bodova na svakom od kolokvija.
Konačna ocjena se računa na slijedeći način:
Ocjena = 0,5*L + 0,5*T
L - ocjena iz laboratorijskih vježbi,
T – ocjena iz teoretskog dijela.
Ocjena na teoretskom djelu ispita u ovisnosti o broju bodova se formira na slijedeći način:
50% do 61% - dovoljan (2),
62% do 74% - dobar (3),
75% do 87% - vrlo dobar (4),
88% do 100% - izvrstan (5).
Ispitni rokovi: Prema kalendaru nastave.
Nastavne jedinice za Predavanja
Broj sati
1.
Uvodno predavanje o predmetu, ponavljanje osnovnih elemenata C programskog jezika (rekurzivne funkcije, strukture, pokazivači, dinamičko alociranje memorije, rad s datotekama)
2 sata
2.
Matematička pozadina analize algoritam i proračun vremena izvršavanja algoritma
2 sata
3.
Apstraktni tipovi podataka, jednostavna implementacija vezane liste i osnovnih operacija u vezanoj listi
2 sata
4.
Dvostruko vezane liste, cirkularne liste
2 sata
5.
Stog, primjena stoga (okvir stoga, balansiranje simbola), red
2 sata
6.
Stabla, binarna stabla, binarna stabla za pretraživanje
2 sata
7.
Osnovne operacije u binarnom stablu za pretraživanje
2 sata
8.
AVL stabla
2 sata
9.
Kosa i B stabla
2 sata
10.
Grupiranje podataka (engl. hashing) – osnovna ideja
2 sata
11.
Funkcije za grupiranje podataka i otvoreno adresiranje
2 sata
12.
Ponovno grupiranje i proširivo grupiranje
2 sata
13.
Hrpe (engl. heap)
2 sata
Nastavne jedinice za Laboratorijske vježbe
Broj sati
1.
Osnovne operacije u nizu struktura.
2 sata
2.
Dodavanje novog elementa na početak i kraj vezane liste, ispis vezane liste.
2 sata
3.
Pretraživanje liste i brisanje elementa iz liste.
2 sata
4.
Dodavanje novog elementa u vezanu listu ispred i iza određenog elementa.
2 sata
5.
Sortiranje vezane liste, upis i čitanje liste iz datoteke.
2 sata
6.
Zbrajanje i množenje polinoma
2 sata
7.
Simulacija stoga pomoću niza i vezane liste.
2 sata
8.
Simulacija reda pomoću niza i vezane liste.
2 sata
9.
Kreiranje nove liste koja je presjek ili unija dviju zadanih lista.
2 sata
10.
Napisati program koji pomoću vezanih listi simulira strukturu direktorija.
2 sata
11.
Unošenje novog elementa i ispis binarnog stabla.
2 sata
12.
Brisanje i pronalaženje elementa u binarnom stablu.
2 sata
13.
Formiranje AVL stabla generiranjem 15 slučajnih brojeva u opsegu od 0-100.
2 sata
Niste više prijavljeni
Istekla vam je prethodna prijava te se morate ponovno prijaviti.
Nastao je problem u radu sustava
Informacije o problemu smo pohranili i nastojat ćemo ga riješiti. Ako vas ova greška sprječava da obavite nešto važno, možete nas odmah kontaktirati na helpdesk@fesb.hr.
Vaš preglednik nije podržan
Koristite web preglednik koji nije podržan. Za puno korisničko iskustvo, preuzmite najnoviju inačicu vašeg preglednika.
