MPŠ
MPŠ MP&Scaron MP&Scaron MP&Scaron Avtorji

Mednarodna
podiplomska šola
Jožefa Stefana

Jamova 39
SI-1000 Ljubljana
Slovenija

Tel: (01) 477 31 00
Faks: (01) 477 31 10
E-pošta: info@mps.si

Išči

Opis predmeta

Programiranje, podatkovne strukture in algoritmi

Programi:

Informacijske in komunikacijske tehnologije, 2. stopnja

Sodelavci:

doc. dr. Anton Biasizzo
prof. dr. Janez Demšar

Cilji:

Cilj predmeta je seznaniti študenta s programskimi jeziki, metodami programiranja, osnovnimi algoritmi in podatkovnimi strukturami ter analizo zahtevnosti algoritmov.
Kompetence študenta z uspešno zaključenim predmetom bodo vključevale osnovno znanje programiranja v izbranem programskem jeziku, poznavanje najbolj razširjenih podatkovnih struktur in algoritmov, zmožnost uporabe obstoječih algoritmov pri reševanju problemov.

Vsebina:

Uvod: matematične osnove, modeli računanja in tehnike programiranja, pregled programskih jezikov in osnove izbranega programskega jezika

Seznami in skladi: Seznami, dvosmerno povezani seznami, krožni seznami, osnovne operacije nad seznami, model sklada, izvedbe sklada, uporaba sklada, obrnjeni poljski zapis.

Drevesa: Definicija drevesa, izvedbe dreves, dvojiška drevesa, operacije v drevesih, iskalna drevesa, uravnotežena drevesa, operacije v uravnoteženih drevesih, B-drevesa, uporaba dreves.

Vrste in prednostne vrste: model vrste, izvedba vrste, uporaba vrst, prednostne vrste, preprosta izvedba prednostne vrste, dvojiška kopica, uporaba prednostnih vrst.

Sortiranje: sortiranje z vstavljanjem, Shellsort, sortiranje z mehurčki, sortiranje s kopico, zlivanje, hitro sortiranje, analiza postopkov sortiranja

Grafi: definicija grafov, usmerjeni in neusmerjeni grafi, predstavitev grafov, problem najkrajše poti, določanje najmanjšega vpetega drevesa, iskanje v globino, NP-polni problemi.

Tehnike načrtovanja algoritmov, požrešna metoda, deli in vladaj, dinamično programiranje, sestopanje.

Praktični primeri: računalniške komunikacije, vgradne aplikacije, velika podatkovja in podobno.

Temeljna literatura in viri:

Izbrana poglavja iz naslednjih knjig:

• M. A. Weiss, Data Structures and Algorithm Analysis in C++. Addison-Wesley, 2013. ISBN 978-0-132-84737-7
• R. Sedgewick, and K. Wayne, Algorithms. Addison-Wesley, 2011. ISBN 978-0-321-57351-3
• D. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, 1997. ISBN 0-201-89683-4
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press and McGraw-Hill, 2009. ISBN 0-262-03384-4

Izbrane reference nosilca:

• A. Biasizzo and F. Novak, “Hardware accelerated compression of LIDAR data using FPGA devices”, Sensors, vol. 13, no. 5, pp. 6405-6422, 2013.
• U. Legat, A. Biasizzo, and F. Novak, “SEU recovery mechanism for SRAM-based FPGAs”, IEEE trans. on nuclear science, vol. 59, no 5, pp. 2562-2571, 2012.
• U. Legat, A. Biasizzo, and F. Novak, “A compact AES core with on-line error-detection for FPGA applications with modest hardware resources”, Microprocessors and microsystems, vol. 34, no. 4, pp. 405-416, 2011.
• F. Novak and A. Biasizzo, “Academic network for microelectronic test education”, International Journal of Engineering Education, vol. 23, no. 6, pp. 1245-1253, 2007.
• F. Novak and A. Biasizzo, “Security extension for IEEE Std 1149.1”, Journal of electronic testing, vol. 22, no. 3, pp. 301-303, 2006.

Načini preverjanja znanja:

Seminarska naloga
Ustni zagovor seminarske naloge

Obveznosti študentov:

Seminarska naloga in ustni zagovor seminarske naloge.

Zunanje povezave: