Diskretne strukture i algoritmi

 

Naziv kolegija:
Diskretne strukture i algoritmi
Šifra ISVU:
85098
Šifra MOZVAG:
IZN103
ECTS:
5
Jezik izvođenja:
hrvatski
Preduvjeti upisa:
Odsjek:
ODSJEK ZA INFORMACIJSKE ZNANOSTI

Studij
Godina
Semestar
Status
INFORMATOLOGIJA - PREDDIPLOMSKI (jednopredmetni studij)
1.g.
ljetni
izborni

Nastavnik
Nositelj
P
V
S
Galić, Silvija
15
30
15

 

Ciljevi i zadaci:

Osnovni cilj kolegija je upoznati studente s diskretnim matematičkim strukturama koje su neophodne za shvaćanje i recepciju kvantitativnih aspekata znanja u informacijskim znanostima. Cilj kolegija je kod studenata razviti sposobnost izražavanja matematičkim jezikom kao i razviti apstraktno mišljenje i logičko rasuđivanje. Studenti će se pripremiti na algoritamski način razmišljanja kako bi mogli pratiti brzi razvoj i prodornost informacijsko-komunikacijske tehnologije te će im se pružiti znanje na temelju kojega će moći samostalno ili timski rješavati cjelovite probleme vezane uz primjenu algoritama u informacijskim znanostima.

Ishodi učenja:

Po završetku nastave iz navedenog kolegija student će moći:

  • upoznati osnovne ideje i metode teorije grafova na nizu ilustracija
  • razlikovati jednostavne i složene vrste algoritama i njihove primjene
  • objasniti utjecaj strukture podataka na izvedbu i brzinu algoritama
  • rješavati raznorodne probleme vezane uz primjenu pojedinih algoritama

Sadržaj predmeta:

Studenti će se upoznati sa diskretnim strukturama – apstraktnim matematičkim konačnim strukturama i mogućnostima njihove primjene u informacijskim znanostima. Na predavanjima će se obraditi odabrana poglavlja teorije grafova te će se predstaviti najpoznatiji algoritmi i njihove primjene.

Tijekom kolegija obradit će se sljedeće teme: Relacije na skupovima (podskup, pravi podskup, jednakost skupova); Partitivni skup; Operacije na skupovima (unija, presjek, razlika, komplement); Vennovi dijagrami; Skupovi brojeva; Kompleksni brojevi; Relacije, binarne relacije; Matrica incidencije; Funkcije; Relacija ekvivalencije; Kongruencije; Operacije s kongruencijama; Primjena kongruencije na International Standard Book Number; Primjena kongruencija u kriptografiji; Rekurzivno zadani nizovi; Fibonaccijev niz; Homogene rekurzivne relacije; Karakteristični polinom; Binomni teorem; Euklidov algoritam; Hornerova shema; Složenost algoritma; Pretraživanje i sortiranje; Slijedno i binarno pretraživanje; Sortiranje umetanjem; Mjehuričasto sortiranje; Sortiranje spajanjem; Quicksort; Grupa; Komutativna (Abelova) grupa; Izomorfizam grupa; Prsteni i polja; Polje realnih brojeva; Vektorski prostor matrica; Primjena grupa u teoriji kodiranja; Definicija grafa i osnovna svojstva grafova; Stupanj vrha, višestruki bridovi, pseudograf; Podgraf; Specijalni grafovi: potpuni graf, bipartitni graf, potpuni bipartitni graf; Regularni grafovi; Izomorfizam grafova; Šetnja, zatvorena šetnja, staza u grafu; Eulerova tura kao zatvorena Eulerova staza i Eulerov graf; Povezani grafovi; Problem  Koeningsberških mostova; Hamiltonov ciklus; Hamiltonov graf; Matrica incidencije i matrica susjedstva; Algoritam za nalaženje Eulerove staze i ciklusa; Problem deadlockova; Težinski graf; Najkraći put između dva vrha u težinskom grafu; Primjene težinskih grafova; Problem trgovačkog putnika; Dijkstrin algoritam; Floyd-Warshallov algoritam; Problem kineskog poštara; Eulerizacija grafa; Stablo; Svojstva stabla; Binarno stablo; Algoritam sortiranja; Minimalno razapinjuće stablo; Razapinjući podgraf; Težina stabla; Kruskalov algoritam; Primov algoritam; Pretraživanje stabla; Prolasci grafom i stablom; Usmjereni graf; Usmjerena šetnja, usmjereni put; Metoda kritičnog puta - CPM, PERT; Problem četiri boje; Bojenje vrhova i bridova grafa; Kromatski broj grafa; Klike i broj klike.

Vrste izvođenja nastave:

predavanja, seminari i radionice, vježbe

Povezivanje ishoda učenja, nastavnih metoda i procjena ishoda učenja:

NASTAVNA METODA AKTIVNOST STUDENTA ISHOD UČENJA
 
METODA PROCJENE
predavanja slušanje predavanja i sudjelovanje u raspravama upoznati osnovne ideje i metode teorije grafova na nizu ilustracija pismeni ispit
seminarsko izlaganje i radionice sustavno opažanje, slušanje izlaganja, analiza literature razlikovati jednostavne i složene vrste algoritama i njihove primjene seminarski rad
praktični rad na vježbama rješavanje problemskih zadataka objasniti utjecaj strukture podataka na izvedbu i brzinu algoritama pohađanje nastave i aktivnost studenata u nastavi
praktični rad na vježbama rješavanje problemskih zadataka rješavati raznorodne probleme vezane uz primjenu pojedinih algoritama pohađanje nastave i aktivnost studenata u nastavi

 

 

Obveze i praćenje rada studenta:

Pohađanje nastave, Seminarski rad, Pismeni ispit, Usmeno izlaganje

Način vrednovanja i ocjenjivanja:

usmeno i pismeno

Elementi praćenja i provjeravanja:

Element
Opterećenje u ECTS
Udio u ocjeni
Pohađanje nastave 1,5 0%
Seminarski rad 1,3 30%
Pismeni ispit 2 60%
Usmeno izlaganje 0,2 10%

 

Način oblikovanja konačne ocjene:

Iz svih elemenata praćenja i provjeravanja student može ostvariti maksimalno 100 ocjenskih bodova, što čini 100% ocjene. Za prolaznu ocjenu student treba ostvariti minimalno 60 ocjenskih bodova ili 60% ocjene.

Skala je ocjenjivanja sljedeća: 60% - 69,9%  = dovoljan (2), 70% - 79,9%  = dobar (3), 80% - 89,9%   = vrlo dobar (4), 90% - 100% = izvrstan (5).

 

Primjer izračunavanja ocjene:

Ostale informacije relevantne za praćenje i vrednovanje studenta:

Studenti su obvezni pohađati 70 % održanih nastavnih sati. Ako student ima 5 ili više izostanaka (jedan izostanak iznosi 2 nastavna sata), neće dobiti potpis, kao ni ukoliko ukupno ostvari manje od 40% ocjene.

 

 

Obavezna literatura:

  1. Divjak, B.; Lovrenčić, A. Diskretne strukture s teorijom grafova. Varaždin: TIVA-FOI, 2005.
  2. Goodaire, E. G.; Parmenter, M. M. Discrete Mathematics with Graph Theory. New York: Prentice Hall, 2002.

Dopunska literatura:

  1. Discrete Discoveries. URL: http://mathforum.org/workshops/sum96/discrete/toc.html
    2. Graph Theory Resources. URL: http://www.graphtheory.com/
  2. Math Archives: Discrete Mathematics. URL: http://archives.math.utk.edu/topics/discreteMath.html

 

Načini praćenja kvalitete koji osiguravaju razvoj znanja, vještina i kompetencija:

  • Provedba jedinstvene sveučilišne ankete među studentima za ocjenjivanje nastavnika koju utvrđuje Senat Sveučilišta
  • Praćenje i analiza kvalitete izvedbe nastave u skladu s Pravilnikom o studiranju i Pravilnikom o unaprjeđivanju i osiguranju kvalitete obrazovanja Sveučilišta.

Ostale informacije: