Matematička analiza algoritama

Opis predmeta

Metode diskretne matematike za analizu računalnih algoritama: rekurzivne relacije, funkcije izvodnice, aproksimacije asimptotskim razvojima i analitička kombinatorika. Primjene za analizu osnovnih algoritama kombinatoričkih struktura (stabla, permutacije, stringovi, riječi).

Ishodi učenja

  1. Analizirati klasične računalne algoritme
  2. Primijeniti rekurzivne relacije za analizu algoritama
  3. Primijeniti funkcije izvodnice za analizu algoritama
  4. Primijeniti aproksimacije korištenjem asimptotskih razvoja za analizu algoritama
  5. Primijeniti analitičku kombinatoriku za analizu algoritama

Oblici nastave

Predavanja

Predavanja se održavaju u dva ciklusa, 3 sata tjedno.

Samostalni zadaci

Svaki će student trebati riješiti samostalne zadatke.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Domaće zadaće 0 % 10 % 0 % 0 %
Međuispit: Pismeni 0 % 45 % 0 %
Završni ispit: Pismeni 0 % 45 %
Ispit: Pismeni 0 % 100 %

Tjedni plan nastave

  1. Nelinearne rekurzivne relacije prvog reda
  2. Metode: zamijene varijabli. repertoara. izvlačenja. perturbacije
  3. Binarne i opće "podijeli pa vladaj" rekurzije
  4. Obične i eksponencijalne funkcije izvodnice
  5. Rješavanje rekurzivnih relacija pomoću funkcija izvodnica
  6. Razvoj funkcija izvodnica
  7. Funkcionalne jednadžbe za funkcije izvodnice
  8. Međuispit
  9. Oznake. definicija. osnovna svojstva O-notacije
  10. Asimptotske aproksimacije za konačne sume. Aproksimacija sume pomoću integrala
  11. Primjeri za Ramanujanovu i binomnu razdiobu
  12. Simbolička metoda za neoznačene kombinatorne klase
  13. Simbolička metoda za označene kombinatorne klase
  14. Primjene za najvažnije kombinatorne strukture
  15. Završni ispit

Studijski programi

Sveučilišni diplomski
Audiotehnologije i elektroakustika (profil)
Slobodni izborni predmeti (1. semestar)
Automatika i robotika (profil)
Slobodni izborni predmeti (1. semestar)
Elektroenergetika (profil)
Slobodni izborni predmeti (1. semestar)
Elektroničko i računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar)
Elektronika (profil)
Slobodni izborni predmeti (1. semestar)
Elektrostrojarstvo i automatizacija (profil)
Slobodni izborni predmeti (1. semestar)
Informacijsko i komunikacijsko inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar)
Komunikacijske i svemirske tehnologije (profil)
Slobodni izborni predmeti (1. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Izborni predmet profila (1. semestar)
Računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar)
Računalno modeliranje u inženjerstvu (profil)
Slobodni izborni predmeti (1. semestar)
Računarska znanost (profil)
Slobodni zborni predmeti (1. semestar)
Znanost o mrežama (profil)
Slobodni izborni predmeti (1. semestar)
Znanost o podacima (profil)
Slobodni izborni predmeti (1. semestar)

Literatura

(.), R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms,
(.), R. Sedgewick, K. Wayne: Algorithms,
(.), T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms,
(.), R. Sedgewick, P. Flajolet: Analytic Combinatorics,
(.), D. Knuth: The Art of Computer Programming,

Za studente

Izvedba

ID 222645
  Zimski semestar
5 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja

Ocjenjivanje

85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan