magistrsko delo
Marko Žugelj (Avtor), Tomaž Dobravec (Mentor)

Povzetek

Računanje časovne zahtevnosti sodi med osnovne naloge področja analize algoritmov, s katero želimo pridobiti funkcijo, ki nam za dano velikost problema napove, koliko časa se bo algoritem izvajal. Teoretična analiza je pogosto zahtevna, poleg tega ima še nekatere druge pomanjkljivosti, zato si lahko pomagamo z empirično analizo časovne zahtevnosti, na kar smo se osredotočili v tem delu. Razvili smo postopke, ki omogočajo analizo rezultatov meritev, torej podatkov, ki jih pridobimo z izvajanjem algoritmov na nalogah različnih velikosti. Analiza vrne ocenjen razred časovne zahtevnosti ter zapis funkcije v simbolični obliki. Razvili smo novo metodo za detekcijo slabih meritev, ki temelji na analizi zaporednih točk. Uvedli smo novo metriko za primerjavo algoritmov med seboj. Uporabili smo tudi nekaj novih pristopov k že znanim metodam ter vse skupaj vgradili v obstoječi sistem za avtomatsko analizo algoritmov.

Ključne besede

algoritmi;računska zahtevnost;empirična računska zahtevnost;genetski algoritmi;računalništvo;računalništvo in informatika;magisteriji;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [M. Žugelj]
UDK: 004(043.2)
COBISS: 1538417859 Povezava se bo odprla v novem oknu
Št. ogledov: 678
Št. prenosov: 171
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Empirical analysis of the algorithm time complexity
Sekundarni povzetek: Time complexity is known as one of the principal tasks of algorithm analysis; the goal is to obtain a function which - for a given size of the problem - estimates how much time the algorithm execution will take. Theoretical analysis is often cumbersome and has other drawbacks as well. Thus, the empirical analysis of time complexity can be used, which is also the primary focus of this paper. We have developed procedures that allow us analysis of measurements - i.e. data -, which we obtain by running algorithms on problems of different sizes. The analysis provides us with an estimated time complexity class and function in symbolic form. We have developed a new method for detection of bad measurements, which is based on analysis of consecutive points, and introduced new metrics for algorithm comparison. A few new approaches were intertwined together with existing methods, which was then, all together, integrated in the existing system for automatic algorithm analysis.
Sekundarne ključne besede: algorithms;computational complexity;empirical computational complexity;genetic algorithms;computer science;computer and information science;master's degree;
Vrsta dela (COBISS): Magistrsko delo/naloga
Študijski program: 1000471
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 68 str.
ID: 11260255