Stranice predmeta – Fakultet tehničkih nauka u Novom Sadu

Predmet: Primenjeni algoritmi (17.D0M31L)

Stepen i vrsta studija	Naziv
Doktorske studije	Matematika u tehnici (Godina: 1, Semestar: Letnji)
Doktorske studije	Matematika u tehnici (Godina: 1, Semestar: Letnji)

Osnovne informacije:

Kategorija	Naučno-stručni
Uža naučna oblast	Teorijska i primenjena matematika
ESPB	10

Obrazovni cilj kursa je uvođenje osnovnih koncepata teorije algoritama. Algoritmi se pojavljuju u gotovo svakoj grani informatike, kao i inženjerskim naukama, biologiji, itd. Svaki problem koji se pojavi u naučnom procesu i treba da bude rešen zahteva algoritam koji je u stanju da na osnovu datih podataka nađe rešenje. Zbog toga navedene teme imaju i teorijski i praktičan značaj.

Razumevanje koncepta algoritma, kao i njegove glavne osobine – kompleksnosti algoritma. Poznavanje nekoliko osnovnih klasa kompleksnosti sa poznatim primerima koji ih reprezentuju. Razumevanje standardnih metoda za rešavanje kompleksnih problema, kao što je korišćenje aproksimativnih i verovatnosnih algoritama.

1.Uvod.Rekurzivne funkcije. Turingove mašine i njihovi jezici. Algoritam, definicija. Kompleksnost algoritma. Vremenska i prostorna kompleksnost. 2.Klase kompleksnosti. Primeri polinomnih algoritama. Redukcije. P=NP<\eng> pitanje. NP<\eng>-kompletni problemi, primeri. Klasa coNP<\eng>. 3.Prostorna kompleksnost. Savičeva teorema. Klase L<\eng> i NL<\eng>. Klasa Pspace<\eng>, pobedničke strategije. Problemi prebrajanja. 4. Verovatnosni algoritmi i aproksimativni algoritmi. Verovatnosni algoritmi. Klase BPP<\eng>, RP<\eng> i coRP<\eng>. Derandomizacija. Mali uzorački prostori. Aproksimativni algoritmi. Klasa NPO<\eng>. Deo nastave na predmetu se odvija kroz samostalni studijski istraživački rad u oblasti primenjene matematike. Studijski istraživački rad obuhvata aktivno praćenje primarnih naučnih izvora, organizaciju i izvođenje eksperimenata i statističku obradu podataka, numeričke simulacije, eventualno pisanje rada iz oblasti primenjene matematike.

Predavanja. Mentorski rad. Predavanja se izvode kombinovano. Izlaganje teoretskog dela propraćeno je odgovarajućim primerima koji doprinose razjašnjenju teoretskog dela gradiva. Pored predavanja redovno se održavaju i konsultacije. Kroz studijski istraživački rad student, proučavajući naučne časopise i ostalu literaturu samostalno produbljuje gradivo sa predavanja. Uz rad sa nastavnikom student se osposobljava za samostalno pisanje naučnog rada.

Autori	Naziv	Godina	Izdavač	Jezik
M. Atallah<\eng>	Algorithms and theory of computation hanbook<\eng>	1999	CRC Press, London<\eng>	Engleski
U. Schöning<\eng>	Theoretische Informatik kurzgefaßt<\eng>	1995	Spektrum Akademischer Verlag GmbH, Berlin<\eng>	Nemački
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	Engleski

Predmetna aktivnost	Predispitna	Obavezna	Broj poena
Predmetna aktivnost Prisustvo na predavanjima	Predispitna Da	Obavezna Da	Broj poena 10.00
Predmetna aktivnost Seminarski rad	Predispitna Da	Obavezna Da	Broj poena 20.00
Predmetna aktivnost Usmeni deo ispita	Predispitna Ne	Obavezna Da	Broj poena 70.00

ORGANIZACIJA

DOKUMENTA

ZAPOSLENI

KONKURSI

AKREDITACIJA

KONTAKT

AKREDITACIJA

KONTAKT

Studentska služba

Predmet: Primenjeni algoritmi (17.D0M31L)

Studijski programi predmeta:

Kontakt: