7 novembre 2011
Anatol Slissenko (LACL)This is an attempt to grope for quantitative measures of information structure of runs of algorithms. The prospective goal, likely long-term, is on the one hand, to introduce smoothness and information convergence or information capacity of algorithms with the hope to prove lower bounds on complexity for such algorithms (all practical algorithms intuitively look smooth), and on the other hand, to try to find new ideas for designing efficient algorithms. I start with adapting classical notions of epsilon-entropy of compacts and probabilistic entropy. Though they are not sufficient to reach the goal, they give some ideas how to go further.