Algoritmi in podatkovne strukture 2

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

Borut Robič

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

Predavanja:
Uvod: splošno o metodah razvoja algoritmov, o analizi algoritmov, o računski zahtevnosti algoritmov in problemov
Deli in vladaj: opis metode, primeri problemov in algoritmov (glejte primere v točki 12 spodaj)
Požrešna metoda: opis metode, primeri
Postopno izboljševanje: opis, primeri
Dinamično programiranje: opis, primeri
Sestopanje: opis metode, primeri
Razveji in omeji: opis metode, primeri
Linearno programiranje: opis metode, simpleksni algoritem, primeri
Izbrane višje podatkovne strukture
NP-težki računski problemi: spodnja meja časovne zahtevnosti, intuitivno o razredih P, NP in NP-težkih problemih
Metode reševanja NP-težkih problemov: hevristični algoritmi, aproksimacijski algoritmi, verjetnostni algoritmi, parametrizirani algoritmi, eksaktni eksponentni algoritmi, primeri
Primeri problemov in algoritmov: napredno urejanje &, Heapsort, Quicksort, problem izbiranja &, linearni algoritmi, matrično množenje &, Strassenov alg., diskretna Fourierova transormacija &, FFT alg., iskanje v nizih &, Knuth-Morris-Prattov algoritem, osnovni in zahtevnejši problemi in algoritmi na grafih (iskanje v grafu, topološko urejanje, maksimalni pretok &, Ford-Fulkersonov alg., najkrajše poti &, Bellman-Fordov ter Floyd-Warshallov alg.) , izbrani problemi iz računske geometrije.
Vaje: Na vajah bodo študentje utrjevali snov, podano na predavanjih. Snov bodo uporabili za reševanje praktičnih problemov, pri čemer bo poudarek na samostojnem delu ob pomoči asistentov. Implementirali bodo več manjših programov (kot domače naloge) in obsežnejše programe (kot seminarske naloge), ki jih bodo zagovarjali na vajah.
Domače in seminarske naloge:
Namen domačih in seminarskih nalog je dati študentom priložnost za reševanje raznih računskih problemov s samostojnim razvojem algoritmov in njihovim programiranjem (in jih spodbuditi k sprotnemu študiju).

Temeljni literatura in viri

B. Robič: Algoritmi (to appear, instead of 2. below)
B. Vilfan: Osnovni algoritmi, Založba FE in FRI, 2002
Dodatna literatura:
T. Cormen et al. Introduction to Algorithms, McGraw-Hill, 3rd ed., 2009
B. Robič: Aproksimacijski algoritmi, Založba FE in FRI, 2. izdaja, 2009

Cilji in kompetence

Cilj predmeta je pridobiti poglobljeno znanje s področij načrtovanja algoritmov, analize algoritmov, uporabe podatkovnih struktur, izbranih problemov in algoritmov ter ob vsem tem utrjevati in poglabljati znanje programiranja.

Predvideni študijski rezultati

Znanje in razumevanje:
Razumevanje različnih pristopov k programiranju in primernost raznih pristopov za reševanje raznih problemov,
Pregled principov in mehanizmov raznih vrst programskih jezikov,
Razumevanje načinov za opisovanje sintakse in pomena programskih jezikov ter formalno dokazovanje pravilnosti programov.
Uporaba:
Razvoj spretnosti simboličnega programiranja, programiranja v logiki in programiranja z omejitvami.
Refleksija:
Sposobnost razmišljanja o alternativnih formulacijah problemov ter pristopov k njihovemu reševanju,
Kako različni modeli računanja, paradigme programiranja in vrste jezikov spodbujajo alternativne pristope k računalniškemu reševanju problemov.
Prenosljive spretnosti - niso vezane le na en
predmet:
Razširjene spretnosti snovanja programov.

Metode poučevanja in učenja

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

Načini ocenjevanja

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

Reference nosilca

ČIBEJ, Uroš, SLIVNIK, Boštjan, ROBIČ, Borut. The complexity of static data replication in data grids. Parallel Computing, ISSN 0167-8191. [Print ed.], 2005, vol. 31, no. 8/9, str. [900]-912, ilustr. [COBISS-SI-ID 4995412]
SULISTIO, Anthony, ČIBEJ, Uroš, VENUGOPAL, Srikumar, ROBIČ, Borut, BUYYA, Rajkumar. A toolkit for modelling and simulating data Grids : an extension to GridSim. Concurrency and computation, ISSN 1532-0626. [Print ed.], Sep. 2008, vol. 20, no. 13, str. 1591-1609, ilustr. , doi: . [COBISS-SI-ID 6533716]
TROBEC, Roman, ŠTERK, Marjan, ROBIČ, Borut. Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Computers & Structures, ISSN 0045-7949. [Print ed.], 2009, vol. 87, no. 1/2, str. 81-90. [COBISS-SI-ID 21895463]
MIHELIČ, Jurij, ROBIČ, Borut. Flexible-attribute problems. Computational optimization and applications, ISSN 0926-6003. [Print ed.], 2010, vol. 47, no. 3, str. 553-566, ilustr. [COBISS-SI-ID 7087700]
MIHELIČ, Jurij, MAHJOUB, Amine, RAPINE, Christophe, ROBIČ, Borut. Two-stage flexible-choice problems under uncertainty. European journal of operational research, ISSN 0377-2217. [Print ed.], Mar. 2010, vol. 201, no. 2, str. 399-403, ilustr. [COBISS-SI-ID 7087444]