Análise da complexidade computacional de problemas de estatística descritiva com entradas intervalares.

Abstract

Statistics in a fundamental tool for all scientific areas. Descriptive Statistics are used to analyze data. The main problem in this area is related to sample values, which are typically error prone due to the experimental processes used to obtain these values. One of the aims of this thesis is to suggest a representation form to sample values that takes these errors into account by using intervals. There are already approaches to calculate values of dispersion, variance, covariance and correlation coefficient using intervals, but the interval computation of dispersion measures gives always overestimated intervals (with wide amplitude) as results. Moreover, if better solutions are needed, by using the interval image representation, calculating such measures turns out to be an NP-hard problem. The main aim of this thesis is to analyze the computational complexity of the descriptive statistics measures using intervals as input values. More concretely this work presents: i) definitions of central trend, dispersion and separatriz using intervals; ii) investigation of the complexity of problems related to the calculation of central trend measures mean, median and moda, of the dispersion measures amplitude, variance, standard deviation. variance coefficient, covariance, correlation coefficient and separatriz; and iii) interval representation of real values such that guarante the quality of the approximation in the result intervals calculated using interval extension does not occur. First, an interval approach to statistics measures is presented, and then algorithms to compute the above described measures are proposed. Such algorithms are based on the interval arithmetics defined by Moore, on interval extension, and were designed to execute in ambients like IntLab and Interval Maple. By analyzing the computational complexity of these algorithms, we conclude that all defined measures are in the P class of complexity. This means that there are polynomial time algorithms that calculate the resulting intervals of the main descriptive statistical measures with interval input values with quality of the approximation. The impact of this result is to make Interval Descriptive Statistics feasible.