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

Abstract

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.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [M. Žugelj]
UDC: 004(043.2)
COBISS: 1538417859 Link will open in a new window
Views: 678
Downloads: 171
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Empirical analysis of the algorithm time complexity
Secondary abstract: 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.
Secondary keywords: algorithms;computational complexity;empirical computational complexity;genetic algorithms;computer science;computer and information science;master's degree;
Type (COBISS): Master's thesis/paper
Study programme: 1000471
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 68 str.
ID: 11260255