Preskoči na glavno vsebino

Algoritmi in podatkovne strukture 1

2023/2024
Program:
Interdisciplinarni univerzitetni študijski program 1. stopnje Računalništvo in matematika
Letnik:
2 letnik
Semester:
prvi
Vrsta:
obvezni
ECTS:
6
Jezik:
slovenski
Nosilec predmeta:

Tomaž Hočevar

Ure na teden – 1. semester:
Predavanja
3
Seminar
0
Vaje
0
Laboratorij
2
Vsebina

Predavanja:

  • modeli računanja, računska zahtevnost
  • urejanje
  • abstraktni podatkovni tipi
  • drevesne strukture
  • požrešni algoritmi
  • grafi, minimalna vpeta drevesa
  • najkrajše poti
  • deli in vladaj
  • dinamično programiranje
  • računska geometrija
  • reševanje težkih problemov

Sprotno delo (vaje in domače naloge):
Na vajah bodo študenti utrjevali snov, ki so jo obravnavali na predavanjih, tako da jo bodo uporabili pri reševanju praktičnih problemov. Pri tem bodo poudarki na samostojnem delu študentov ob pomoči asistentov. Na vajah bodo študenti implementirali rešitve kratkih nalog, s katerimi bodo opravili sprotno delo in pridobili pravico pristopa k izpitu.

Temeljni literatura in viri

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.
Sedgewick R. & Wayne K. (2011). Algorithms fourth edition. Addison-Wesley.
Aho A. V. Hopcroft J. E. & Ullman J. D. (1983). Data structures and algorithms. Addison-Wesley.
Kononenko, I., Robnik Šikonja, M., & Bosnić, Z. (2008). Programiranje in algoritmi. Fakulteta za računalništvo in informatiko.

Cilji in kompetence

Cilj predmeta je spoznavanje osnovnih principov načrtovanja in analize algoritmov in podatkovnih struktur. Pri tem študenti razvijajo svoje zmožnosti analitičnega in kritičnega razmišljanja. V povezavi z obstoječim znanjem programiranja osvojijo potrebno znanje za učinkovito reševanje tehničnih in znanstvenih problemov v računalništvu in informatiki.

Predvideni študijski rezultati

Po uspešno zaključenem predmetu naj bi bili študenti zmožni:

  • Uporabiti osnovne podatkovne strukture in algoritme v razvoju programov.
  • Prilagoditi znane algoritme in podatkovne strukture za reševanje podobnih problemov.
  • Razlikovati med različno učinkovitimi rešitvami istega problema.
  • Načrtovati učinkovite rešitve zastavljenega problema z uporabo primernih podatkovnih struktur in algoritmov.
  • Utemeljiti in zagotoviti pravilnost ter učinkovitost razvitega algoritma.
  • Uporabiti naučene algoritmične koncepte v poljubnem programskem jeziku.
Metode poučevanja in učenja

Predavanja, vaje, domače naloge. Poudarek je na sprotnem študiju in na samostojnem delu.

Načini ocenjevanja

Sprotno preverjanje (vaje, domače naloge)
Končno preverjanje (pisni in ustni izpit)
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Reference nosilca

Hočevar, T., Brodnik, A., & Munro, J. I. (2018). Sosednost vozlišč v hipergrafih. Elektrotehniski Vestnik, 85(5), 224-228
Hočevar, T. (2018). Counting small patterns in networks
Hočevar, T., & Demšar, J. (2017). Combinatorial algorithm for counting small induced graphs and orbits. PloS one, 12(2)
Hočevar, T., & Demšar, J. (2016). Computation of graphlet orbits for nodes and edges in sparse graphs. Journal of Statistical Software, 71, 1-24
Hočevar, T., & Demšar, J. (2014). A combinatorial approach to graphlet counting. Bioinformatics, 30(4), 559-565