Algoritmi i strukture podataka

Opis predmeta

Nastavljajući na gradivo usvojeno na predmetu Programiranje i programsko inženjerstvo, obrađuju se najšire primjenjivani algoritmi i strukture podataka. Nakon dinamičkog alociranja memorije, primjera dodjele memorije i mehanizma poziva funkcija, uvodi se pojam složenosti algoritma. Objašnjava se i ilustrira rekurzija. Nastavlja se s tehnikama pretraživanja te potom slijede svi važniji algoritmi sortiranja. Uvode se dinamičke strukture podataka: jednostruke i višestruko povezane liste. Grade se osnovne strukture podataka poput stoga i reda. Zatim se uvodi tehnika raspršenog adresiranja, binarna stabla te gomila kao posebni slučaj binarnog stabla. Uporaba gomile kao prioritetnog reda se pokazuje na primjeru heap sorta.

Opće kompetencije

Studenti će biti osposobljeni za pisanje računalnih algoritama koji koriste naprednije strukture podataka, koristeći osnove objektno orijentirane programske paradigme u programskom jeziku C.

Ishodi učenja

  1. opisati upotrebu različitih podatkovnih struktura
  2. prepoznati složenost operacija i algoritama
  3. primijeniti odgovarajuće podatkovne strukture i algoritme pri rješavanju konkretnih problema
  4. razviti računalne programe u kojima će biti implementirane odgovarajuće podatkovne strukture i algoritmi
  5. ocijeniti složenost algoritama i računalnih programa
  6. identificirati odgovarajuće podatkovne strukture i algoritme pri rješavanju konkretnih problema

Oblici nastave

Predavanja

Nastava je organizirana u dva ciklusa ukupnog trajanja 15 tjedana, u što su uračunata dva tjedna za međuispite. Predavanja traju četiri sata tjedno, a podijeljena su u dva dana, dakle 2+2 sata.

Provjere znanja

Provjera znanja provodi se putem međuispita i završnog ispita.

Laboratorijske vježbe

Organiziraju se dvije do tri laboratorijske vježbe.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Napomena / komentar Udio u ocjeni
Laboratorijske vježbe 0 % 30 % 0 % 30 %
Međuispit: Pismeni 40 % 30 % 0 %
Završni ispit: Pismeni 50 % 40 %
Ispit: Pismeni 50 % 70 %
Napomena / komentar

Na kontinuiranom praćenju potrebno je prikupiti barem 35 bodova zajedno iz međuispita i završnog ispita.

Tjedni plan nastave

  1. Uvod. Rekapitulacija elementarnih struktura podataka. Dodjela memorije.
  2. Mehanizam poziva funkcija. Definicija algoritma. Složenost algoritama.
  3. Pretraživanje: slijedno, po blokovima, binarno.
  4. Rekurzija.
  5. Primjeri rekurzije, vježbe.
  6. Sortiranje biranjem, mjehuričasto sortiranje, sortiranje umetanjem, Shellov sort, mergesort, quick sort.
  7. Jednostruko povezana lista. Višestruko povezana lista.
  8. Međuispit
  9. Međuispit
  10. Stog. Red.
  11. Raspršeno adresiranje.
  12. Primjeri raspršenog adresiranja.
  13. Osnovni pojmovi iz grafova. Stabla.
  14. Gomila.
  15. Heap sort.

Studijski programi

Sveučilišni preddiplomski
Elektrotehnika i informacijska tehnologija i Računarstvo (studij)
(2. semestar)

Za upis predmeta treba položiti predmete

Literatura

Adam Drozdek (2000.), Data Structures and Algorithms in C++, Course Technology
M. A. Weiss (1996.), Data Structures and Algorithm Analysis in C (2nd Edition), Addison Wesley
R. Sedgewick (2001.), Algorithms in C: Fundamentals, Data Structures, Sorting, Searching and Graph Algorithms in C, Addison Wesley
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009.), Rent eTextbook Buying Options Add To Cart - hardcover Add To Cart - paperback Add To Cart - eBook Hardcover | $94.00 Text | £69.95 | ISBN: 9780262033848 | 1312 pp. | 8 x 9 in | 235 b&w illus.| July 2009 Paperback | $74.00 Text | £44.95 | ISBN: 9780262533058 | 1312 pp. | 8 x 9 in | 235 b&w illus.| July 2009 eBook | $94.00 Text | ISBN: 9780262259460 | 1312 pp. | 235 b&w illus.| July 2009 About MIT Press eBooks Paperback not for sale in the US or Canada. Look Inside Index Preface Sample Chapter Essential Info Table of Contents Supplemental Content Author Errata Page Khan Academy Course Instructor Resources Digital Exam/Desk Copy Print Exam/Desk Copy Ancillary Material Introduction to Algorithms, Third Edition, MIT Press

Predavanja

Laboratorijske vježbe

Izvedba

ID 21008
  Ljetni semestar
6 ECTS
R1 Engleski jezik
R1 E-učenje
60 Predavanja
0 Auditorne vježbe
15 Laboratorijske vježbe

Ocjenjivanje

90 izvrstan
80 vrlo dobar
66 dobar
50 dovoljan