Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Studying Informational Sensitivity of Computer Algorithms
verfasst von : Anastasia Kiktenko, Mikhail Lunkovskiy, Konstantin Nikiforov
Erschienen in: Modern Trends and Techniques in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
This study is focused on informational sensitivity of an algorithm, defined as impact of different fixed-length inputs on the value of the algorithm’s complexity function. In addition to classic worst-case complexity this characteristic provides a supplementary tool for more detailed and more “real world” approach to studying algorithms. Statistical measure of informational sensitivity is calculated based on statistical analysis of results obtained from multiple runs of the same program implementation of the algorithm in question with random inputs. This theory is illustrated by an example of algorithm that solves the travelling salesman problem by branch and bound method using the concorde package. For a sample of different input graphs with 1,000÷10,000 vertices the statistical measurements of informational sensitivity were found and confidence ranges for complexity function were constructed. It was proven that this particular algorithm is highly sensitive to fixed-size inputs by complexity function.