prikaz prve stranice dokumenta Vremenska složenost algoritama
Pristup korisnicima matične ustanove
diplomski rad
Vremenska složenost algoritama
Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2017. urn:nbn:hr:166:926883
Andrijić, Jelena
Sveučilište u Splitu
Prirodoslovno-matematički fakultet
Odjel za matematiku

Institucijski repozitorij: repozitorij.pmfst.unist.hr

Citirajte ovaj rad

Andrijić, J. (2017). Vremenska složenost algoritama (Diplomski rad). Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, Jelena. "Vremenska složenost algoritama." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, Jelena. "Vremenska složenost algoritama." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, J. (2017). 'Vremenska složenost algoritama', Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, citirano: 04.11.2024., https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić J. Vremenska složenost algoritama [Diplomski rad]. Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet; 2017 [pristupljeno 04.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:926883

J. Andrijić, "Vremenska složenost algoritama", Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, Split, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:926883

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:166:926883
Podaci o radu
NaslovVremenska složenost algoritama
Naslov (engleski)Time complexity of algorithms
AutorJelena Andrijić
MentorJurica Perić (mentor)
Član povjerenstvaJurica Perić (predsjednik povjerenstva)
Član povjerenstvaMilica Klaričić Bakula (član povjerenstva)
Član povjerenstvaMarija Bliznac Trebješanin (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Splitu
Prirodoslovno-matematički fakultet
(Odjel za matematiku)
Split
Datum i država obrane2017-09-06, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom radu glavna je tema vremenska složenost algoritama. U prvom poglavlju navedene su definicije vezane za Turingov stroj (više verzija, s ciljem kasnije analize složenosti i utvrđivanja njihove ekvivalencije), riječi i jezike u istom kontekstu te kodiranje Turingovih strojeva. Naglavedeno je što su parcijalno rekurzivne funkcije te Turing-izračunljive funkcije s ciljem nadogradnje na te pojmove u sljedećem poglavlju. Drugo poglavlje nadovezuje se na Turingov stroj dajući vremenske složenosti raznih verzija stroja, posvećuje se više konceptu univerzalnog Turngovog stroja. Nadalje analizira klase vremenske složenosti s naglaskom na klase P i NP, takoder navodeći karakteristične primjere za svaku klasu.
Sažetak (engleski)
The main topic of this master’s thesis is time complexity of algorithms and Turing machines. In the first chapter we give some basic thesis which will be needed in second chapter, some of which are: definitions of deterministic Turing machine, nondeterministic Turing machine, multitape Turing machine and universal Turing machine, properties of such machines, relations between them and partial functions computed by Turing machines. We also give definitions of primitive recursive functions, recursive functions and theorems about them. In the second chapter we introduce O notation and the notion of computational time complexity. Reduction theorems for Turing machines in terms of time complexity are presented as well as several illustrative examples. In the end of this chapter we introduce PTIME and NPTIME classes and we give basic relations between them, together with examples of each of classes.
Ključne riječi
Jezikhrvatski
URN:NBNurn:nbn:hr:166:926883
Studijski programNaziv: Matematika; smjerovi: teorijski, računarski, nastavnički
Smjer: računarski
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaPristup korisnicima matične ustanove
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-05-18 17:24:44