Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.

Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов? Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.

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

На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун. Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.

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

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

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

Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.

В этом курсе мы познакомимся с замечательной теорией NP-полных задач. Проблема (не)равенства классов P и NP — одна из «задач тысячелетия», за каждую из которых объявлен приз в миллион долларов. Мы разберемся в определении класса NP и научимся доказывать NP-полноту различных комбинаторных задач (классические теоремы Кука–Левина и Карпа). Особое внимание уделим задаче выполнимости булевых формул SAT. Мы поиграем с программами, решающими эту задачу, разберем какие алгоритмы они используют, как результатом их работы может быть доказательство, допускающее автоматическую проверку. Научимся сводить логические головоломки и математические задачи к SAT, поговорим о судоку, задачах теории Рамсея, недавнем продвижении в задаче о хроматическом числе плоскости и о «самом большом математическом доказательстве».

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