Učni načrt predmeta

Predmet:
Programiranje, podatkovne strukture in algoritmi
Course:
Programming, Data Structures and Algorithms
Študijski program in stopnja /
Study programme and level		 Študijska smer /
Study field		 Letnik /
Academic year		 Semester /
Semester
Informacijske in komunikacijske tehnologije, 2. stopnja / 1 1
Information and Communication Technologies, 2nd cycle / 1 1
Vrsta predmeta / Course type
Obvezni / Mandatory
Univerzitetna koda predmeta / University course code:
IKT2-693
Predavanja
Lectures		 Seminar
Seminar		 Vaje
Tutorial		 Klinične vaje
work		 Druge oblike
študija		 Samost. delo
Individ. work		 ECTS
30 30 30 210 10

*Navedena porazdelitev ur velja, če je vpisanih vsaj 15 študentov. Drugače se obseg izvedbe kontaktnih ur sorazmerno zmanjša in prenese v samostojno delo. / This distribution of hours is valid if at least 15 students are enrolled. Otherwise the contact hours are linearly reduced and transfered to individual work.

Nosilec predmeta / Course leader:
izr. prof. dr. Gregor Papa
Sodelavci / Lecturers:
doc. dr. Anton Biasizzo , prof. dr. Janez Demšar
Jeziki / Languages:
Predavanja / Lectures:
slovenščina, angleščina / Slovenian, English
Vaje / Tutorial:
Pogoji za vključitev v delo oz. za opravljanje študijskih obveznosti:
Prerequisites:

Zaključen študijski program prve stopnje s področja naravoslovja, tehnike ali računalništva.

Student must complete first-cycle study programmes in natural sciences, technical disciplines or computer science.

Vsebina:
Content (Syllabus outline):

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

Analiza algoritmov: računska zahtevnost algoritmov deli in vladaj, amortizirana analiza algoritmov.

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, dvojiška drevesa, operacije v drevesih, iskalna drevesa, uravnotežena drevesa, samonastavljiva drevesa, B-drevesa, uporaba dreves.

Razpršene tabele: funkcija razprševanja, trčenja, popolno razprševanje, univerzalno razprševanje.

Vrste in prednostne vrste: model vrste, uporaba vrst, prednostne vrste, dvojiška kopica, leve kopice, izmaknjene kopice, binomske prioritetne vrste, uporaba prednostnih vrst.

Grafi: definicija grafov, usmerjeni in neusmerjeni grafi, predstavitev grafov, problem najkrajše poti, določanje najmanjšega vpetega drevesa, določanje pretoka v omrežju, 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.

Introduction: mathematical fundamentals, models of computation, and programming techniques, overview of the programming languages and selected programming language.

Algorithm analysis: computational complexity of divide and conquer algorithms, amortized analysis of algorithms.

Lists and stacks: linked list, double linked list, circular list, basic operations on lists, stack model, stack implementation, applications, reverse polish notation.

Trees: definition of tree, binary trees, operations on trees, search tree, balanced trees, self-adjusting trees, B-trees, applications of trees.

Hash tables: hash functions, colisions, perfect hashing, universal hashing.

Queues and priority queues: queue model, queue applications, priority queues, binary heaps, leftist heaps, skew heaps, binomial queues, applications of priority queues.

Graphs: graph definition, directed and undirected graph, graph representation of graphs, shortestpath problem, minimum spanning tree, network flow problem, depth-first search, NPcompleteness.

Algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, backtracking algorithms.

Practical examples: computer communications, embedded applications, massive data storages.

Temeljna literatura in viri / Readings:

Izbrana poglavja iz naslednjih knjig: / Selected chapters from the following books:
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.

Cilji in kompetence:
Objectives and competences:

Cilj predmeta je nadgraditi znanje programiranja ter pridobiti poglobljeno znanje s področja načrtovanja algoritmov, analize algoritmov in uporabe zahtevnejših podatkovnih struktur.

Kompetence študenta z uspešno zaključenim predmetom bodo vključevale poglobljeno znanje programiranja v izbranem programskem jeziku, poznavanje zahtevnejših podatkovnih struktur in algoritmov, zmožnost uporabe obstoječih algoritmov pri reševanju problemov.

The goal of the course is to upgrade the knowledge of the programming and to gain deeper knowledge of algorithm design techniques, algorithm analysis, and use of advanced data structures.

The competences of the students completing this course successfully would include the in-depth programming knowledge in selected programming language, the knowledge of advanced data structures and algorithms, the ability to reuse the existing algorithms in problem solving.

Predvideni študijski rezultati:
Intendeded learning outcomes:

Študenti bodo z uspešno opravljenimi obveznostmi tega predmeta pridobili:
- poglobljeno znanje izbranega programskega jezika,
- poznavanje zahtevnejših podatkovnih struktur in algoritmov ter njihovih značilnosti,
- sposobnost snovanja novih podatkovnih struktur in algoritmov za specifične probleme,
- sposobnost analize in vrednotenja razvitih podatkovnih struktur in algoritmov.

Students successfully completing this course will acquire:
- In-depth knowledge of the selected programming language,
- Knowledge of the advanced data structures and algorithms and their characteristics,
- Ability to develop new data structures and algorithms for specific problem,
- Ability to perform the analysis and validation of the developed algorithms and data structures.

Metode poučevanja in učenja:
Learning and teaching methods:

Predavanja, seminar, konzultacije, individualno delo.

Lectures, seminar, consultations, individual work.

Načini ocenjevanja:
Delež v % / Weight in %
Assesment:
Seminarska naloga
50 %
Seminar work
Ustni zagovor seminarske naloge
50 %
Oral defense of seminar work
Reference nosilca / Lecturer's references:
1. RAUT, Gopal, BIASIZZO, Anton, DHAKAD, Narendra, GUPTA, Neha, PAPA, Gregor, VISHVAKARMA, Santosh Kumar. Data multiplexed and hardware reused architecture for deep neural network accelerator. Neurocomputing. [Print ed.]. 2022, vol. 486, str. 147-159, graf. prikazi, tabele. ISSN 0925-2312. https://dirros.openscience.si/IzpisGradiva.php?id=14652, DOI: 10.1016/j.neucom.2021.11.018
2. BIASIZZO, Anton, KOROUŠIĆ-SELJAK, Barbara, VALENČIČ, Eva, PAVLIN, Marko, SANTO-ZARNIK, Marina, BLAŽICA, Bojan, O'KELLY, Damian, PAPA, Gregor. An open-source approach to solving the problem of accurate food-intake monitoring. IEEE access. 2021, vol. 9, str. 162835-162846. ISSN 2169-3536. DOI: 10.1109/ACCESS.2021.3128995
3. MEHRA, Sumiran, RAUT, Gopal, DAS, Ribhu, VISHVAKARMA, Santosh Kumar, BIASIZZO, Anton. An empirical evaluation of enhanced performance softmax function in deep learning. IEEE access. [in press] 2023, 13 str. ISSN 2169-3536. DOI: 10.1109/ACCESS.2023.3265327.
4. PETELIN, Gašper, HRIBAR, Rok, PAPA, Gregor. Models for forecasting the traffic flow within the city of Ljubljana. European transport research review. [Online ed.]. 2023, vol. 15, article no. 30, str. 1-20, ilustr. ISSN 1866-8887
5. PAPA, Gregor, SANTO-ZARNIK, Marina, VUKAŠINOVIĆ, Vida. Electric-bus routes in hilly urban areas : overview and challenges. Renewable & sustainable energy reviews : an international journal. [Print ed.]. 2022, vol. 165, str. 112555-1-112555-19. ISSN 1364-0321