PMIE10: Strukture podataka i algoritmi (79282)

6 ECTS
	30 P + 30 PK
	0% primjene e-učenja
	Odjel za informatiku (Sceduly)

Nositelji: Divna Krpan
Suradnici:

Ciljevi predmeta

Razumjeti, usvojiti i naučiti koncepte algoritama i struktura podataka

Razumjeti, usvojiti i naučiti primjenu i implementaciju algoritama, apstraktnih tipova i struktura podataka, razumijevanje i primjena jednostavnih i složenih algoritama za sortiranje

Uvjeti (kompetencije) za upis predmeta

Položen kolegij: Programiranje I

Kompetencije: poznavanje osnova OOP i programskog jezika C#

Očekivani ishodi učenja

1. klasificirati osnovne strukture podataka

2. klasificirati osnovne vrste algoritama

3. analizirati složenost postojećih algoritama

4. usporediti algoritme

5. izraditi linijske i razgranate strukture podataka

6. primijeniti algoritme i strukture podataka

7. nadograditi postojeće strukture podataka (klase)

Sadržaj predmeta

1. P: Uvodno predavanje. Pregled kolegija. Pojam apstraktnog podatka, pojam strukture podataka i algoritma. Pregled struktura podataka.

V: Ulazni test. Ponavljanje sintakse i programskih koncepata.

2. P: Algoritmi, analiza složenosti algoritama.

V: Izrada jednostavnih linijskih struktura podataka.

3. P: Linijske strukture podataka. Upoznavanje s kolekcijom postojećih struktura u programskom jeziku. Skupovi.

V: Primjena stoga i reda.

4. P: Rječnik (Dictionary). Raspršeno adresiranje (Hashtable).

V: Rješavanje zadataka sa strukturama Dictionary i Hashtable. Primjena tehnika za rješavanje kolizije.

5. P: Jednostruke vezane liste. Dvostruke vezane liste. Preskočne liste (skip list).

V: Osnovne operacije s vezanim listama.

6. P: Algoritmi sortiranja.

V: Primjena algoritama sortiranja. Usporedba vremena izvršavanja.

7. P: Algoritmi sortiranja – primjena i način implementacije. Priprema za kolokvij.

V: 1. kolokvij

8. P: Razgranate strukture. Binarna stabla. Binarna uređena stabla.

V: Dodavanje i brisanje čvorova iz binarnog uređenog stabla.

9. P: Balansirana stabla. Samobalansirajuća stabla.

V: Primjena rotacija. Visina stabla.

10. P: Red prioriteta. Struktura gomile (Heap). Heapsort.

V: Izrada reda prioriteta. Primjena Heapsorta.

11. P: Grafovi. Načini implementacije grafova. Minimalno razapinjuće stablo.

V: Implementacija grafa. Operacije s grafovima.

12. P: Načini obilaska grafova (pretraga po dubini, pretraga po širini).

V: Primjena pretraga.

13. P: Putovi u grafu. Najkraći put u grafu (Dijkstra, Floyd Warshall).

V: Izrada primjera s traženjem najkraćeg puta i usporedba.

14. P: Uvod u dinamičko programiranje.

V: Primjena dinamičkog programiranja.

15. P: Ponavljanje i priprema za drugi kolokvij.

V: 2. kolokvij

Vrste izvođenja nastave

- Predavanja
- Vježbe
- Samostalni zadaci

Obveze studenata

Pohađanje nastave, aktivno sudjelovanje u nastavnom procesu, kolokviji, pismeni ispit, usmeni ispit

Praćenje rada studenata (ECTS)

- Pohađanje nastave (1)
- Praktični rad (1)
- Usmeni ispit (2)
- Pismeni ispit (2)

Ocjenjivanje i vrjednovanje rada studenata

Pismeni dio ispita: tijekom semestra pišu se dva kolokkvija koji se ocjenjuju ocjenama od 0-5, a konačna ocjena pismenog predstavlja zbroj 40% ocjene prvog kolokvija i 60% ocjene drugog kolokvija. Studenti koji ne polože neki od kolokvija na ispitu pišu samo onaj dio gradiva kojeg nisu položili.

Usmeni dio ispita obavezan je za sve studente, te iznosi 20% konačne ocjene.

Obvezna literatura

Griffiths, I., Adams, M., & Liberty, J. (2010). Programming C# 4.0: O'Reilly Media, Inc.

Robert Manger, Miljenko Marušić: Strukture podataka i algoritmi, skripta - 2. izdanje, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2003

Nastavni materijali (bilješke s predavanja i vježbi) dostupni u sustavu e-učenja

Izborna literatura

Robert Manger, Strukture podataka i algoritmi, Element, Zagreb, 2014.

S. S. Skiena: The Algorithm Design Manual, Springer-Verlag, 2008

Robert Sedgewick: Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, Addison-Wesley Professional, 2001.

M. McMillan: Data Structures and Algorithms Using C#, Cambridge, 2007.

Načini praćenja kvalitete

Razgovor sa studentima, studentska evaluacija primjenom anonimne ankete, uspjeh studenata na ispitu, samoprocjena.

Izvedba

Sveučilišni prijediplomski studij
• Fizika (izborni 5. sem.)
• Informatika (obvezni 3. sem.)
• Informatika i tehnika (obvezni 3. sem.)
• Matematika; smjer: Matematički (obvezni 3. sem.)
• Matematika; smjer: Računarski (obvezni 3. sem.)
• Matematika i informatika (obvezni 3. sem.)
Sveučilišni diplomski studij
• Fizika; smjer: Fizika okoliša (izborni 1. i 3. sem.)
• Fizika; smjer: Računarska fizika (izborni 1. i 3. sem.)

Napomene:
Vrste nastave (tip): (P) Predavanja; (S) Seminari; (A) Auditorne vježbe; (PK) Vježbe u praktikumu; (L) Laboratorijske vježbe; (M) Metodičke vježbe; (TJ) Vježbe tjelesnog odgoja; (T) Terenske vježbe.
Prije početka nastave moguće su rošade izvođača nastave u svrhu optimizacije opterećenja. Prikazana je testna verzija automatskog generiranja informacija.