RUS  ENG
Полная версия
ВИДЕОТЕКА



Случайно существующие объекты (вероятностные доказательства существования). Занятие 1

М. А. Раскин



Аннотация: Иногда мы хотим доказать, что какой-нибудь объект существует. Разумеется, можно медленно и методично объект построить. Но это что-то делать надо, а хочется получить кое-что задаром. Поэтому мы просто возьмём случайный объект и заметим, что он подходит с ненулевой вероятностью. Это позволяет избежать занудной конструкции. Заодно можно спрятать в доказательстве незаметную ошибку.
Для понимания курса нужно будет знать определение независимых событий. Понимать, что это такое, не обязательно, всё равно в ходе курса такое понимание (или только его иллюзию?) можно будет утратить.
Примерная программа курса
  • Построим что-нибудь. Нижняя оценка на число Рамсея. Раскраски таблиц с одноцветными прямоугольниками и без.
  • Ожидания и реальность: вероятность больших отклонений, разные оценки и их применимость.
  • Графы-экспандеры.
  • Мошенничество и никакой ловкости рук: почему важно следить за независимостью.
  • Буквоедские изыскания: почему «несжимаемый» файл очень легко породить случайно и доказуемо совершенно невозможно совсем неслучайно.
  • Применение жути в мирных целях: формулировка и применение леммы Ловаша о локальной зависимости.


Website: https://www.mccme.ru/dubna/2017/courses/raskin2.html
Цикл лекций


© МИАН, 2024