Пятница 14 октября, 18-00, ауд. 106

Пятница, 14 октября, ауд. 106. Начало в 18:00.

Докладчик: А.О. Слисенко (University Paris East Créteil).

Тема: On Entropy in Computations.


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. In this talk 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. Доклад будет на русском языке.