Algoritmi in podatkovne strukture 1

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

Igor Kononenko

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

predavanja:
Iteracija in rekurzija
Reševanje problemov in algoritmi
Analiza časovne zahtevnosti algoritmov
Abstraktni podatkovni tip, ADT seznam
Osnovni abstraktni podatkovni tipi: množica, vrsta, sklad, preslikava
Zgoščene tabele
Abstraktni podatkovni tip drevo, primer: Izrazna drevesa
Abstraktni podatkovni tip slovar, Iskalna drevesa: binarna, rdeče-črna
Iskalna drevesa: AVL, B-drevesa
Abstraktna podatkovna tipa prioritetna vrsta (kopica) disjunktne množice
Abstraktna podatkovna tipa graf in usmerjeni graf
Iskanje najdaljših poti z dinamičnim programiranjem (kritična pot)
Iskanje najkrajših poti v usmerjenem grafu (algoritem Dijkstra)
Minimalno vpeto drevo v neusmerjenem grafu, Primov in Kruskalov algoritem.
Dokazovanje parcialne in totalne pravilnosti programov
vaje:
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 več manjših programov (tudi kot domače naloge) ter obsežnejše programe v obliki seminarskih nalog, ki jih bodo zagovarjali na vajah in s tem dobili oceno iz vaj.
domače naloge:
Namen domačih nalog je ponuditi študentom priložnost za reševanje preprostejših problemov s samostojnim razvojem krajših programov in jih s tem spodbuditi k sprotnemu študiju.

Temeljni literatura in viri

I. Kononenko in sod.: Programiranje in algoritmi, Založba FE in FRI, 2008.
Pomožna literatura:
I.Kononenko in M. Robnik-Šikonja: Algoritmi in podatkovne strukture 1, Založba FE in FRI, 2003.
A.V.Aho, J.E.Hopcroft, J.D.Ullman: Data Structures and Algorithms, Addison Wesley, 1983.
Thomas H. Cormen, Stein Clifford, Charles E. Leiserson, Robert L. Rivest: Introduction to Algorithms, second edition. The MIT Press, 2001.

Cilji in kompetence

Cilj predmeta je spoznavanje osnovnih principov načrtovanja in analize algoritmov na osnovnih in dinamičnih podatkovnih strukturah.
Kompetence:
Zmožnost kritičnega, analitičnega in sintetičnega razmišljanja. Zmožnost razumevanja in reševanja profesionalnih problemov iz računalništva in informatike. .). Zmožnost uporabiti pridobljenega znanja za reševanje tehničnih in znanstvenih problemov v računalništvu in informatiki, zmožnost nadgrajevanja pridobljenega znanja. Osnovne veščine iz računalništva in infromatike, ki vključujejo teoretične veščine, praktično znanje in veščine, ki so bistvene za področje računalništva in informatike. . Osnovne veščine iz računalništva in infromatike, ki omogočajo nadaljevanje študija na 2. stopnji.

Predvideni študijski rezultati

Z uspešno zaključenim predmetom bo študent:

  • sposobnen samostojnega razvoja programov, uporabe osnovnih podatkovnih struktur in algoritmov, sposoben samostojnega načrtovanja podatkovnih struktur in algoritmov.
  • lahko uporabil principe programiranja in načrtovanja podatkovnih struktur in algoritmov za razvoj obsežnih programskih sistemov.
  • prilagodil znane algoritme za reševanje podobnih problemov iz preiskovanja seznamov, dreves in grafov
  • razlikoval med različno učinkovitimi algoritmi za reševanje istega problema
  • zmožen načrtovanja rešitve različnih problemov s programi in algoritmi in zmožen uporabe naučenih principov pri programiranju v poljubnem programskem jeziku.
Metode poučevanja in učenja

Predavanja, domače naloge, seminarski način dela pri vajah. Poseben poudarek je na sprotnem študiju in na samostojnem delu pri domačih nalogah, vajah in seminarjih.

Načini ocenjevanja

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

Reference nosilca

KONONENKO, Igor, KUKAR, Matjaž. Machine learning and data mining : introduction to principles and algorithms. Chichester: Horwood Publishing, cop. 2007. XIX, 454 str., ilustr. ISBN 1-904275-21-4. ISBN 978-1-904275-21-3. [COBISS-SI-ID 5961556]
ŠTRUMBELJ, Erik, KONONENKO, Igor. An efficient explanation of individual classifications using game theory. Journal of machine learning research, ISSN 1532-4435. [Print ed.], Jan. 2010, vol. 11, no. [1], str. 1-18, ilustr. [COBISS-SI-ID 7543636]
ROBNIK ŠIKONJA, Marko, KONONENKO, Igor. Theoretical and empirical analysis of ReliefF and RReliefF. Machine learning, ISSN 0885-6125. [Print ed.], 2003, vol. 53, str. 23-69, graf. prikazi. [COBISS-SI-ID 3813460]
KONONENKO, Igor, BRATKO, Ivan. Information-based evaluation criterion for classifier's performance. Machine learning, ISSN 0885-6125. [Print ed.], 1991, vol. 6, no. 1, str. 67-80. [COBISS-SI-ID 7717972]
KONONENKO, Igor. Machine learning for medical diagnosis : history, state of the art and perspective. Artificial intelligence in medicine, ISSN 0933-3657. [Print ed.], 2001, vol. 23, no. 1, str. 89-109. [COBISS-SI-ID 2545236]