Naslov predmeta: Algoritmi in podatkovne strukture I – RI-UNI (Bolonja) ter RM, 2. letnik

Predavatelj: prof. dr. Igor Kononenko
Asistenti: dr. Petar Vračar, dr. Bojan Žunkovič

Namen predmeta:

  1. Izpopolniti in utrditi znanje iz programiranja (predvsem rekruzije)
  2. Naučiti se načrtovati algoritme in analizirati njihovo časovno zahtevnost
  3. Podati osnovne abstraktne podatkovne tipe in operacije na njih
  4. Spoznati osnovne operacije na dinamičnih podatkovnih strukturah: seznamih, drevesih in grafih

Okvirna vsebina:

  • Uvod:
    • Pregled predmeta
    • Rekurzija in iteracija (predavano vnaprej zaradi vaj)
    • Časovna zahtevnost algoritmov (asimptotična in dejanski čas)
  • Osnovni abstraktni podatkovni tipi in njihove implementacije:
    • ADT Seznam
    • ADT Množica
    • ADT Sklad
    • ADT Vrsta
  • Rekurzija-iteracija (predavano že prej zaradi vaj)
  • Reševanje problemov z algoritmi
  • Reševanje problemov
  • Pregled preiskovalnih algoritmov
  • Deli in vladaj
  • Strategije iskanja optimalne rešitve
  • Strategije iskanja približne rešitve
  • Stohastični preiskovalni algoritmi
  • Razvoj algoritmov
  • ADT preslikava, zgoščene tabele; preskočni seznami
  • Drevesa:
    • Drevo kot abstraktni podatkovni tip
    • Binarna drevesa, primer izrazna drevesa (tudi kontekstno neodvisne gramatike)
    • ADT slovar
    • Dvojiška iskalna drevesa
    • Rdeče-črna drevesa
    • AVL drevesa
    • B-drevesa
    • ADT prioritetna vrsta; kopica
    • Napredno sortiranje: heapsort
    • ADT disjunktne množice
  • Graf:
    • ADT graf
    • Kritična pot
    • Drevo najkrajših poti
    • Minimalno vpeto drevo
  • Dokazovanje pravilnosti programov:
    • Zančna invarianta
    • Parcialna in totalna pravilnost

VAJE

Študenti preko e-učilnice sproti rešujejo ob rokih objavljene spletne kolokvije, ki se točkujejo. Vsak študent mora doseči najmanj 50% pri reševanju spletnih kolokvijev, da lahko dobi oceno iz vaj.

V okviru laboratorijskih vaj vsak študent samostojno izdela 2 seminarski nalogi, ki jih oddaja ob rokih preko učilnice ter zagovarja v dveh rokih na laboratorijskih vajah in zagovori seminarskih nalog se ocenjujejo.

Pri oddajanju seminarskih nalog preko učilnice se programska koda navzkrižno preverja glede prepisovanja. Odkriti prepisovalci (tako avtorji kode kot tisti, ki so kodo prepisali) se ocenijo negativno s prepovedjo opravljanja vaj in izpita v tekočem šolskem letu ter prijavijo disciplinski komisiji FRI, ki kršitelje ustrezno kaznuje (od prepovedi opravljanja vseh izpitov 6-12 mesecev do izključitve iz FRI).

Uspešno (ocena vsake seminarske naloge najmanj 50%) in pravočasno (do postavljenih rokov) zagovarjane seminarske naloge so pogoj za pristop k opravljanju izpita. Ocena seminarskih nalog se upošteva kot ocena vaj, pri čemer imata lahko seminarski nalogi različno težo. Končna ocena predmeta je povprečje ocene iz vaj in ocene iz izpita. Pri tem morata biti tako ocena vaj in ocena iz izpita pozitivni.

Ocena iz vaj velja samo tekoče šolsko leto. Če študent, ki ima pozitivno ocenjene vaje, v tekočem šolskem letu ne opravi izpita, mu ocena iz vaj propade.

IZPIT:

Izpit je sestavljen iz pisnega in morebitnega ustnega dela. Na pisnem izpitu je od literature dovoljen en A4 list napisan lastnoročno z navadnim svinčnikom (da se lahko radira) in podpisan s kemičnim svinčnikom z imenom in priimkom ter vpisno številko (fotokopije in printi niso dovoljeni). Ta list se odda skupaj s pisnim izdelkom. Na ustnem izpitu lahko študent popravi ali pokvari oceno pisnega izpita.

Ocena vaj in ocena izpita morata biti pozitivni. Končna ocena predmeta je povprečje ocene iz vaj in ocene iz izpita.

Osnovna literatura:

Igor Kononenko, Marko Robnik Šikonja, Zoran Bosnić: Programiranje in algoritmi, Založba FE in FRI, 2008.

Pomožna literatura:

  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Data Structures and Algorithms, Addison Wesley, 1983.
  • J.Kozak: Podatkovne strukture in algoritmi, DMFA Slovenije, Ljubljana, 1986.
  • Thomas H. Cormen, Stein Clifford, Charles E. Leiserson, Robert L. Rivest: Introduction to Algorithms, second edition. The MIT Press, 2001.
  • N.Wirth: Računalniško programiranje 1. in 2. del, DMFA, Ljubljana, 1989.
  • Robert Sedgewick: Bundle of Algorithms in Java: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms. Addison Wesley, 2003.