Информатика и вычислительная техника
  • формат djvu
  • размер 516,85 КБ
  • добавлен 16 февраля 2017 г.
Успенский В.А. Четыре алгоритмических лица случайности
2-е изд., исправленное. — М.: МЦНМО, 2009. — 48 с. — ISBN 978-5-94057-485-9.
Файл: отскан. страницы (b/w 600 dpi) + OCR + букмарки.
Брошюра написана по материалам лекции, прочитанной автором 23 июля 2005 года в летней школе «Современная математика» в Дубне. Она посвящена формализации такого интуитивно ясного термина, как «случайность». В брошюре рассматривается четыре разных подхода к этому понятию, основанных на характерных свойствах случайных последовательностей: частотоустойчивость, хаотичность, типичность и непредсказуемость. Вводятся важнейшие в теории алгоритмов понятия перечислимости, вычислимости, энтропии и колмогоровской сложности. С их помощью и можно попытаться ответить на вопрос, с которым не справляется классическая теория вероятностей: определить, можно ли, например, индивидуальную последовательность нулей и единиц считать случайной или нет. В последней главе проводится обобщение понятий частотоустойчивости, хаотичности, типичности и непредсказуемости на случай вычислимого распределения.
Брошюра адресована старшим школьникам и студентам младших курсов.
Предварительных знаний от читателя не потребуется, однако будет полезным знакомство с теорией алгоритмов, а для чтения последней главы — с основными понятиями теории вероятностей.
Первое издание книги вышло в 2006 г.
Оглавление:
Введение
Лицо первое: Частотоустойчивость и стохастичность
Лицо второе: Хаотичность
Лицо третье: Типичность
Лицо четвёртое: Непредсказуемость
О безостановочных стратегиях
Обобщение на вычислимые распределения вероятностей
Вычислимые меры и вычислимые распределения
Стохастичность
Хаотичность
Типичность
Непредсказуемость
О безостановочных стратегиях
История и библиография
Похожие разделы