Matematička analiza algoritama

Prikazani su podaci za akademsku godinu: 2023./2024.

Nositelji

Prof. dr. sc.
Andrea Aglić Aljinović

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).

Studijski programi

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

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

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
0 Seminar
0 Auditorne vježbe
0 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja

Ocjenjivanje

85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan

Sličan predmet