Успенский В.А.

М.: МЦНМО, 2006.— 48 с.В брошюре рассматривается четыре разных подхода к этому понятию, основанных на характерных свойствах случайных последовательностей: частотоустойчивость, хаотичность, типичность и непредсказуемость. Вводятся важнейшие в теории алгоритмов понятия перечислимости, вычислимости, энтропии и колмогоровской сложности. С их помощью и можно попытаться ответить на вопрос, с которым не ...

Брошюра написана по материалам лекции, прочитанной автором 23 июля 2005 года в летней школе «Современная математика» в Дубне. Она посвящена формализации такого интуитивно ясного термина, как «случайность». В брошюре рассматривается четыре разных подхода к этому понятию, основанных на характерных свойствах случайных последовательностей: частотоустойчивость, хаотичность, типичность и непредсказуемос...

Предисловие.обозначения и терминология.введение.предварительные понятия теории алгоритмов: конструктивные объекты и их ансамбли, локальные свойства и локальные действия.Общее понятие алгоритма как самостоятельное (отдельное) понятие.Представительные вычислительные модели.Общее понятие исчисления как самостоятельное.(отдельное) понятие.Представительные порождающие модели.Выяснение связей между алго...

От автора Книга написана по материалам одной из секций школьного математического кружка при МГУ. В предлагаемую книгу вошли три темы: задачи о многоцветной раскраске карт, задачи из теории чисел, решаемые с помощью арифметики вычетов, и задачи из теории вероятностей, связанные с так называемыми случайными блужданиями. Для чтения первых двух разделов достаточно знания математики в объеме 8 классов ...

Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А.Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмическ...

В книге дается обзор важнейших достижений теории алгоритмов за последние полвека, т.е. с момента зарождения этой теории. Излагаются в систематизированном виде основные открытия, связанные с понятием алгоритма, приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Рассматривается влияние теории алгоритмов на алгоритмическую практику.Для специалистов по м...