FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2019/2020
semestar:
5. semestar

2019/2020

6ECTSa

Preddiplomski

Informacijski/Poslovni sustavi v1.1

Program Obavezan
Informacijski sustavi IS Ne
Poslovni sustavi PS Ne
5. semestar
3. nastavna godina

Algoritmi npp:72614

Engleski naziv

Algorithms

Katedra

Katedra za teorijske i primijenjene osnove informacijskih znanosti

Kategorija ("boja")

RI

Cilj kolegija

Ovaj predmet studentima daje metode izgradnje algoritama, kao i značajnije primjere gotovih algoritama, koji su važni kako kao primjeri korištenja standardnih metoda izgradnje algoritama, tako i kao gotova rješenja važnijih problema, koji se često susreću u programerskoj praksi.

Nastava

Predavanje
30sati
Laboratorijske vježbe
30sati

Ishodi učenja predmeta

  • izabrati između nekoliko ponuđenih programskih rješenja zadanog rješenja ono koje je najbolje prema kriterijima ocjene kvalitete programskog rješenja
  • koristiti različite izvore te u njima tražiti rješenja svog problema, te je (vidi ishod) u stanju kritički ocijeniti njihovu kvalitetu i izabrati onaj koji mu je najbolji.
  • poznati kritičan broj gotovih algoritama te ih može primijeniti u istoj situaciji ili ih metodom analogije prilagoditi za sličnu situaciju.
  • primijeniti metode izrade algoritama i pomoću njih izgraditi algoritam za zadani problem
  • procijeniti složenost zadanog problema i ocijeniti kvalitetu dobijenog programskog rješenja

Ishodi učenja programa

  • analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT
  • pratiti stručnu literaturu na hrvatskom i stranom jeziku, pripremiti i samostalno održati prezentacije na hrvatskom i stranom jeziku stručnoj i općoj publici, te kritičku evaluaciju prezentirane stručne temepratiti stručnu literaturu na hrvatskom i stranom jeziku, pripremiti i samostalno održati prezentacije na hrvatskom i stranom jeziku stručnoj i općoj publici, te kritičku evaluaciju prezentirane stručne teme
  • razumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanjarazumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
  • razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava
  • razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama

Sadržaj predavanja

  • Uvod. Matematičke osnove.
    Programiranje i programski jezici. Problemi. Zadavanje problema. Intuitivni pojam algoritma. Svojstva algoritma. Vremenska i prostorna složenost algoritma. Definicija algoritma kao rješenja optimizacijskog problema i problema odlučivanja. Asimptotske ocjene složenosti algoritma (notacije O, o, Ω, ω i Θ). Propozicije vezane uz asimptotske osnove složenosti algoritama. Važniji redovi brojeva. Faktorijeli. Stirlingova formula. Binomni koeficijenti. Binomni poučak. Matematička indukcija.
  • Matematičke osnove (cont.)
    Rekurzivne jednadžbe. Homogene linearne rekurzivne jednadžbe. Rješavanje rekurzivnih jednadžbi pomoću karakteristične jednadžbe - homogeni slučaj. Rješavanje rekurzivnih jednadžbi pomoću karakteristične jednadžbe - nehomogeni slučaj. Neki slučajevi nelinearni rekurzivnih jednadžbi i njihovo rješavanje. Rekurzivni računalni programi Izračunavanje složenosti rekurzivnih programa.
  • Metode izgradnje algoritama. Metoda pohlepe
    Definicija metode pohlepe. Dokazivanje korektnosti pohlepnog algoritma za dani problem. Problem realnog ranca (problem skladištenja rasutog tereta), dokaz korektnosti i ocjena složenosti. Dokaz da pohlepni algoritam ne daje optimalno rješenje problema cjelobrojnog ranca. Huffmanov algoritam optimalnog spajanja datoteka, dokaz korektnosti i ocjena složenosti. Problem dostupnosti datoteka na sekvencijalnom mediju u minimalnom vremenu, dokaz korektnosti i ocjena složenosti.
  • Metode izgradnje algoritama. Metoda podijeli pa ovladaj.
    Metoda podijeli pa ovladaj. Metoda smanji pa ovladaj. Rekurzivne jednadžbe koje nastaju pri izračunu složenosti algoritama temeljenih na metodi podijeli pa ovladaj. Rješavanje Josephusovog problema metodom smanji pa ovladaj i ocjena složenosti Pronalaženje maksimuma metodom podijeli pa ovladaj i ocjena složenosti Rješavanje problema udaljenosti dvije točke u ravnini metodom podijeli pa ovladaj i ocjena složenosti.
  • Metode izgradnje algoritama. Metoda pretraživanja s vraćanjem
    Opis backtracking metode. Stablo prostora stanja problema. Pretraživanje prvo u dubinu i prvo u širinu Pretraživanje prvo u dubinu rekurzivno i pomoću stoga. Problem kraljica i ocjena složenosti.
  • Metode izgradnje algoritama. Metoda pretraživanja s vraćanjem (cont.)
    Problem 0-1 ranca, ocjena složenosti. Poboljšanje algoritma za problem 0-1 ranca. Rješavanje problema sume podskupova metodom pretraživanja s vraćanjem. Ocjena složenosti. Poboljšanje algoritma za pronalaženje sume podskupova
  • Metode izgradnje algoritama. Metoda grananja i ograničenja
    Metoda grananja i ograničenja. LC pretraživanje stabla prostora stanja problema. Problem skakača na šahovskoj ploči. Rješenje metodom pretraživanja s vraćanjem i metodom grananja i ograničenja. Problem 0-1 ranca. Rješenje metodom grananja i ograničenja. Ocjena složenosti.
  • Metode izgradnje algoritama. Metoda dinamičkog programiranja
    Opis metode dinamičkog programiranja. Uvjet optimalnosti. Eliminacija višestrukog izračunavanja istih podproblema. Koraci izgradnje programskog rješenja metodom dinamičkog programiranja Problem cjelobrojnog ranca. Dokaz zadovoljenja principa optimalnosti. Ocjena složenosti
  • Metode izgradnje algoritama. Metoda dinamičkor programiranja (cont.)
    Problem proizvodnih traka. Dokaz zadovoljenja uvjeta optimalnosti. Ocjena složenosti Problem optimalnog množenja niza matrica. Dokaz zadovoljenja uvjeta optimalnosti. Algoritam za određivanje optimalnog redosljeda množenja matrica dinamičkim programiranjem. Ocjena složenosti. Problem optimalnog binarnog stabla pretraživanja. Dokaz zadovoljena principa optimanlosti. Ocjena složenosti.
  • Algoritmi na grafovima
    Apstraktni tip podataka matematički graf. Usmjereni i neusmjereni grafovi. Implementacija grafa pomoćumatrice susjednosti. Implementacija grafa pomoću ortogonalne liste. Pretraživanja grafa prvo u širinu i prvo u dubinu.
  • Algoritmi na grafovima (cont.)
    Razapinjuće stablo grafa. Kruskalov i Primov algoritam za minimalno razapinjuće stablo grafa. Izračun složenosti za algoritme za minimalno razapinjuće stablo grafa. Dijkstrin algoritam. Složenost Dijkstrinog algoritma. Eulerovi putevi i ciklusi u grafu. Algoritam za nalaženje Eulerovih ciklusa i složenost.
  • Algoritmi na grafovima (cont.)
    Topološko sortiranje Maksimalni protok u grafu. Ford-Fulkersonov algoritam i njegova složenost. Hamiltonovi ciklusi Problem trgovačkog putnika. Algoritam za bojenje vrhova grafa i njegova složenost. Pokrivač vrhova grafa, algoritam i složenost.
  • Numerički algoritmi
    Metode pronalaženja nul-točaka funkcije. Metoda bisekcije. Newtonova metoda tangente. Metoda sekante Hornerov algoritam za izračunavanje vrijednosti polinoma. Dijeljenje polinoma Euklidov algoritam za najveći zajednički djelitelj dvaju prirodnih brojeva.
  • Numerički algoritmi (cont.)
    Numerička integracija. Trapezna formula. Simpsonova formula. Uopćena trapezna i Simpsonova formula. Rombergov algoritam.
  • NP-teški i NP-potpuni problemi
    Definicija klasa NP-teških i NP-potpunih problema. Cookov teorem. SAT i 3SAT problem. Dokaz NP-potpunosti nekih problema. Problem particije skupa brojeva. Problem maksimalne klike grafa. Problem pokrivača vrhova grafa. Problem Hamiltonovih ciklusa. Problem particije skupa. NP-teški problemi rasporeda. Problem 0-1 ranca.

Sadržaj seminara/vježbi

  • Uvod
    Osnovni algoritmi pretraživanja i sortiranja
  • Rekurzija
    Korištenje rekurzije za rješavanje problema. Ocjena složenosti rekurzivnih programa
  • Pohlepni algoritmi
    Primjeri algoritama temeljenih na metodi pohlepe. Dokaz korektnosti.
  • Pohlepni algoritmi (cont.)
    Primjeri algoritama temeljenih na metodi pohlepe. Dokaz korektnosti.
  • Programski zadatak 1
    Studenti samostalno rješavaju programski zadatak.
  • Podijeli pa ovladaj
    Primjeri algoritama temeljeni na metodi podijeli pa ovladaj
  • Podijeli pa ovladaj (cont.)
    Primjeri algoritama temeljeni na metodi podijeli pa ovladaj
  • Programski zadatak 2
    Studenti samostalno rješavaju programski zadatak
  • Pretraživanje s vraćanjem
    Primjeri algoritam temeljeni na metodi pretraživanja s vraćanjem (backtracking)
  • Metoda grananja i ograničenja
    Primjeri algoritama temeljeni na metodi grananja i ograničenja (banch and bound)
  • Programski zadatak 3
    Studenti samostalno rješavaju programski zadatak
  • Dinamičko programiranje
    Primjeri algoritama temeljeni na metodi dinamičkog programiranja
  • Dinamičko programiranje (cont.)
    Primjeri algoritama temeljeni na metodi dinamičkog programiranja
  • Programski zadatak 4
    Studenti samostalno rješavaju programski zadatak.

Alati koji se koriste na predmetu

  • DEV-C++
    Open-source C++ programming environment Bloodshed DEV-C++

Osnovna literatura

  • Cormen, T. et al., Introduction to Algorithms. MIT Press, Cambridge, 2001.
  • Levitin, Anany V., Introduction to the design and analysis of algorithms. 2nd ed., Addison-Wesley, Boston, 2007.

Dopunska literatura

  • Skiena, S. S. The Algorithm Design Manual. 2nd ed. London, Springer, 2008.
  • Sedgewick, R. Algorithms in C++. Vol 1, parts 1-4: Fundamentals data structers, sorting, searching. 3rd ed. Boston, Addison-Wesley, 2008.
  • Sedgewick, R. Algorithms in C++. Vol 2, part 5: Graph algorithms. 3rd ed. Boston, Addison-Wesley, 2002.

Preduvjeti

  • Matematika 1
    Cilj predmeta Matematika I je upoznavanje studenata s osnovnim pojmovima diskretne matematike (kao što su matematički modeli, matematička logika te skupovi i relacije) i linearne algebre (matrice, determinante, sustavi linearnih jednadžbi i nejednadžbi) koji su neophodni za prihvaćanje kvantitativnih aspekata znanja u informacijskim i organizacijskim znanostima te priprema studenata za logičko razmišljanje u znanosti i poslovanju. Predmet ima i generičke ciljeve kao što su timski rad, prezentacijske vještine (usmeno i pismeno izražavanje), razumijevanje modela, upotreba literature i razvoj ICT vještina, te posebno strategije rješavanja problemskih zadataka. Nadalje, koncepcija rada omogućava razvoj vještina apstrakcije kod studenata
  • Programiranje 2
    Kolegij se nastavlja na Programiranje I s kojim predstavlja cjelinu. Po završetku, studenti trebaju biti sposobni oblikovati, kodirati, testirati, ispravljati i dokumentirati programska, prije svega objektno orijentirana rješenja problema algoritamskog tipa. Ciljna razina složenosti programa jesu programi koji rade s više datoteka i više klasa
  • Strukture podataka
    Cilj kolegija Modeliranje poslovnih pravila je upoznavanje studenata s osnovnim teorijskim postavkama i praktičnim metodama i postupcima konceptualnog i formalnog oblikovanja i implementacije poslovnih pravila i sustava poslovnih pravila, u kontekstu suvremenih alata za razvoj informacijskih sustava, kako klasičnih, tako i suvremenih (sustavi ontologija, sustavi baza znanja i sustavi semantičkog Weba).

Slični predmeti

  • Algoritmi i strukture podataka, Fakultet elektrotehnike i računarstva, Sveučilište uu Zagrebu
  • Strukture podataka i algoritmi, Prirodoslovno matematički fakultet – matematički odjel, Sveučilište u Zagrebu
  • Algoritmi i strukture podataka, Odjel za fiziku, Sveučilište Josipa Juraja Strossmayera u Osijeku
  • Algoritmi i strukture podataka, Elektrotehnički fakultet Osijek, Sveučilište Josipa Juraja Strossmayera u Osijeku
Nastavnik Oblik nastave Tjedana Sati tjedno Grupa
Konecki Mladen Laboratorijske vježbe 15 2 5
Lovrenčić Alen Predavanje 15 2 1
Izvanredni rok
Datum: 18.11.2019.
Vrijeme: 16:00
Napomena:
Izvanredni rok
Datum: 24.04.2020.
Vrijeme: 16:00
Napomena:

Algoritmi - Redovni studenti

Studij: Informacijski/Poslovni sustavi
Akademska godina: 2019/2020

Praćenje rada studenata

Elementi praćenjaBodova
Prisustvovanje nastavi0
Aktivnost na nastavi40
Domaće zadaće (Seminari)30
Kolokviji30
ZBROJ100


Bodovna skala ocjena

OdDoOcjena
0 49 nedovoljan (1)
50 60 dovoljan (2)
61 75 dobar (3)
76 90 vrlo dobar (4)
91 100 odličan (5)



Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
Kolokvij 1 + 100.0 80.0 90 +
Kolokvij 2 + 20.0 100.0 90 +


Opis elemenata praćenja - Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Prisustvovanje nastavi 0 0 Prisustvovanje na predavanjima se ne evidentira. Na svim laboratorijskim vježbama (seminarima) provjerava se prisustvovanje. Kako bi student stekao uvjete za potpis, može izostati s najviše 3 laboratorijske vježbe. 3 Kako su dozvoljena 3 izostanka sa laboratorijskih vježbi, nadoknade nisu potrebne. Posljednji tjedan nastave
Aktivnost na nastavi 40 0 Na predavanjima se ne prati aktivnost studenata. Studenti tijekom laboratorijskih vježbi rješavaju zadatke. Tijekom semestra na 4 se laboratorijske vježbe studentima zadaje zadatak koji trebaju rješiti. Svaki zadatak donosi 0-10 bodova.
Domaće zadaće (Seminari) 30 0 Svaki je student dužan tijekom semestra izaditi jedan seminarski rad. Temu seminarskog rada student je dužan predložiti predmetnom nastavniku, koji temu odobrava.
0 Svaki je student dužan izraditi seminarski rad. Zadnji dan 3. međuispitnog razdoblja
Kolokviji 30 0 Tijekom semestra studenti polažu 2 kolokvija na kojima dobivaju 3 zadatka koja pismeno rješavaju. Svaki kolokvij donosi 0-15 bodova. Na oba kolokvija studenti mogu ostvariti ukupno 30 bodova. 0 Prisustvovanje na kolokvijima nije obavezno, pa stoga ne postoje nadoknade kolokvija.


Opis elemenata praćenja - Ispit

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Pismeni dio ispita 4 Pismeni dio ispita sastoji se od 4 zadatka od kojih student da bi prošao na usmeni dio ispita treba ostvariti 2 boda. Bodovna skala ocjena s pismenog dijela ispita je

2 - dovoljan
2,5-3 - dobar
3,5 - vrlo dobar
4 - izvrstan
2
Usmeni dio ispita Na usmenom dijelu ispita nastavnik daje konačnu ocjenu iz predmeta.


Algoritmi - Izvanredni studenti

Studij: Informacijski/Poslovni sustavi
Akademska godina: 2019/2020

Praćenje rada studenata

Elementi praćenjaBodova
Prisustvovanje nastavi0
Aktivnost na nastavi40
Domaće zadaće (Seminari)30
Kolokviji30
ZBROJ100


Bodovna skala ocjena

OdDoOcjena
0 49 nedovoljan (1)
50 60 dovoljan (2)
61 75 dobar (3)
76 90 vrlo dobar (4)
91 100 odličan (5)



Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
Kolokvij 1 + 100.0 80.0 90 +
Kolokvij 2 + 20.0 100.0 90 +


Opis elemenata praćenja - Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Prisustvovanje nastavi 0 0 Prisustvovanje na predavanjima se ne evidentira. Na svim laboratorijskim vježbama (seminarima) provjerava se prisustvovanje. Kako bi student stekao uvjete za potpis, može izostati s najviše 3 laboratorijske vježbe. 3 Kako su dozvoljena 3 izostanka sa laboratorijskih vježbi, nadoknade nisu potrebne. Posljednji tjedan nastave
Aktivnost na nastavi 40 0 Na predavanjima se ne prati aktivnost studenata. Studenti tijekom laboratorijskih vježbi rješavaju zadatke. Tijekom semestra na 4 se laboratorijske vježbe studentima zadaje zadatak koji trebaju rješiti. Svaki zadatak donosi 0-10 bodova.
Domaće zadaće (Seminari) 30 0 Svaki je student dužan tijekom semestra izaditi jedan seminarski rad. Temu seminarskog rada student je dužan predložiti predmetnom nastavniku, koji temu odobrava.
0 Svaki je student dužan izraditi seminarski rad. Zadnji dan 3. međuispitnog razdoblja
Kolokviji 30 0 Tijekom semestra studenti polažu 2 kolokvija na kojima dobivaju 3 zadatka koja pismeno rješavaju. Svaki kolokvij donosi 0-15 bodova. Na oba kolokvija studenti mogu ostvariti ukupno 30 bodova. 0 Prisustvovanje na kolokvijima nije obavezno, pa stoga ne postoje nadoknade kolokvija.


Opis elemenata praćenja - Ispit

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Pismeni dio ispita 4 Pismeni dio ispita sastoji se od 4 zadatka od kojih student da bi prošao na usmeni dio ispita treba ostvariti 2 boda. Bodovna skala ocjena s pismenog dijela ispita je

2 - dovoljan
2,5-3 - dobar
3,5 - vrlo dobar
4 - izvrstan
2
Usmeni dio ispita Na usmenom dijelu ispita nastavnik određuje konačnu ocjenu iz predmeta.


Alternativni način polaganja predmeta:

Studenti koji ne ostvare dovoljan broj bodova kroz kontinuirano praćenje tijekom semestra imaju dvije mogućnosti za polaganje predmeta:

1. Izlazak na ispit koji se sastoji od:

a.  Pismenog dijela ispita
b.  Usmenog dijela ispita

Polaganje predmeta pisanjem 3 seminarska rada. U tom slučaju student dobija 3 teme koje treba obraditi od predmetnog nastavnika. Student je dužan izraditi 3 seminarska rada do najkasnije tjedan dana prije ispitnog roka u rujnu u nastavnoj godini u kojoj su odslušali predmet.   

Za izvanredne studente:

Izvanredni studenti nisu dužni pohađati nastavu iz predmeta Algoritmi, no mogu, ako to žele, pohađati nastavu i sudjelovati u kontinuiranom praćenju zajedno s redovitim studentima
Ako ne mogu pohađati nastavu, izvanredni studenti mogui polagati predmet na dva načina:

1. Pisanjem triju seminarskih radova čije teme određuje predmetni nastavnik. Seminarske su radove dužni predati najkasnije tjedan dana prije ispitnog roka u rujnu u nastavnoj godini u kojoj su odslušali predmet
2. Klasičnim ispitom koji se sastoji od

i.  Pismenog dijela ispita
ii. Usmenog dijela ispita

Predavanje Seminar Auditorne vježbe Laboratorijske vježbe Vježbe (jezici, tzk) Ispit Kolokviji Nadoknade Demonstrature
Copyright © 2015 FOI Varaždin. All Rights Reserved. Sva prava pridržana.
Povratak na vrh