prikaz prve stranice dokumenta Vremenska složenost algoritama
Access restricted to students and staff of home institution
master's thesis
Vremenska složenost algoritama
2017. urn:nbn:hr:166:926883
Andrijić, Jelena
University of Split
Faculty of Science
Department of Mathematics

Cite this document

Andrijić, J. (2017). Vremenska složenost algoritama (Master's thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, Jelena. "Vremenska složenost algoritama." Master's thesis, University of Split, Faculty of Science, 2017. https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, Jelena. "Vremenska složenost algoritama." Master's thesis, University of Split, Faculty of Science, 2017. https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić, J. (2017). 'Vremenska složenost algoritama', Master's thesis, University of Split, Faculty of Science, accessed 16 November 2024, https://urn.nsk.hr/urn:nbn:hr:166:926883

Andrijić J. Vremenska složenost algoritama [Master's thesis]. Split: University of Split, Faculty of Science; 2017 [cited 2024 November 16] Available at: https://urn.nsk.hr/urn:nbn:hr:166:926883

J. Andrijić, "Vremenska složenost algoritama", Master's thesis, University of Split, Faculty of Science, Split, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:166:926883

Please login to the repository to save this object to your list.
Metadata
TitleVremenska složenost algoritama
Title (english)Time complexity of algorithms
AuthorJelena Andrijić
MentorJurica Perić (mentor)
Committee memberJurica Perić (predsjednik povjerenstva)
Committee memberMilica Klaričić Bakula (član povjerenstva)
Committee memberMarija Bliznac Trebješanin (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Mathematics)
Split
Defense date and country2017-09-06, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Languagecroatian
URN:NBNurn:nbn:hr:166:926883
Study programmeTitle: Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching
Course: major in computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2018-05-18 17:24:44