План лекций: Доказуемость и недоказуемость (почему некоторые утверждения нельзя ни доказать, ни опровергнуть?); Вычислимые функции (почему некоторые функции нельзя вычислить на компьютере?); Сложность алгоритмов; Формальные языки и исчисления.

Какова история создания машины Тьюринга? Как она повлияла на развитие идей, лежащих в основе ряда современных технологий? Какие проблемы существуют в теории вычислительной сложности? И как математика рассматривает понятие случайность? Об идее универсальной машины, проблеме перебора и случайности рассказывает кандидат физико-математических наук Александр Шень.

Представьте себе, что на стол высыпана кучка совершенно одинаковых по виду монет, но вам сказали, что одна из этих монет — фальшивая. Она отличается от остальных монет по весу, но вам не сообщили, легче она или тяжелее. В вашем распоряжении имеются чашечные весы без гирь. Как нужно действовать, чтобы выделить эту монету и выяснить её тип (то есть узнать, легче она или тяжелее) за минимальное число взвешиваний?

Природа статистических законов вызывала споры с самого рождения теории вероятностей и продолжает их вызывать. Эти философские споры привели к рождению интересной математической теории: алгоритмической теории вероятностей и информации, которая — в отличие от классической — пытается дать определение индивидуального случайного объекта. Мы обсудим основные понятия этой теории и их связь с основаниями и парадоксами теории вероятностей. Об этом в публичной лекции математика Александра Шеня, кандидата физико-математических наук, старшего научный сотрудник Лаборатории теории передачи информации и управления ИППИ РАН.

Четыре тысячи лет назад жители Вавилонии изобрели умножение. А в марте этого года математики усовершенствовали его. 18 марта 2019 два исследователя описали самый быстрый из известных методов перемножения двух очень больших чисел. Работа отмечает кульминацию давнишнего поиска наиболее эффективной процедуры выполнения одной из базовых операций математики. «Все думают, что метод умножения, который они учили в школе, наилучший, но на самом деле в этой области идут активные исследования», — говорит Йорис ван дер Хувен, математик из Французского национального центра научных исследований, один из соавторов работы.

Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. В виде проблемы она была сформулирована в 1852 году — и доказана в 1976-м лишь с помощью компьютера. Такое решение не всем понравилось, и некоторые до сих пор ждут доказательства, которое можно проверить без компьютера. Другие (как великий математик Владимир Воеводский) — наоборот, стали развивать автоматическую проверку правильности доказательств на компьютере… В курсе мы разберем доказательство теоремы о четырёх красках (это простая комбинаторика, доступная любому школьнику), а также обсудим сегодняшнее использование компьютера в математике (надо примерно знать, что такое компьютер).

В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция.

О сложности вычислений и квантовых компьютерах рассказывает Александр Ханиевич Шень — кандидат физико-математических наук, научный сотрудник Института проблем передачи информации РАН (Москва) и LIF CNRS — Лаборатории информатики Национального центра научных исследований Франции (Марсель). Лекция была прочитана 23 апреля 2009 года в Москве, в ФИАНе.

Составленная из нулей и единиц цепочка 100010111011110100000111 выглядит более случайной, чем цепочка 010101010101010101010101. Возможно ли разделить все цепочки нулей и единиц на случайный и не случайные? Для конечных цепочек эта задача вряд ли осуществима. Однако можно пытаться решать её для бесконечных цепочек, т.е. для последовательностей. Иными словами, можно пытаться найти строгое математическое определение для понятия «случайная последовательностей нулей и единиц».

«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы — предложены в качестве задач. Будут приведены и примеры т.н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.