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

Теория информации — математическая дисциплина, в которой одновременно применяются методы многих разделов математики: теории вероятностей, теории алгоритмов, комбинаторики. Она занимается, в числе прочих, вопросами — как лучше всего сжать файл? Сколько информации может содержать данное сообщение? Как возможно точно передать сообщение, несмотря на помехи в канале связи? Как защитить сообщение от несанкционированного доступа? Ключевые идеи о том как решать перечисленные задачи были изложены в статье К. Шеннона «Математическая теория информации», где впервые было введено понятие энтропии (количества информации) и намечены контуры будущей теории. Мы займёмся введением в теорию сжатия дискретных данных (в отличие от непрерывных; там — своя специфика). Рассмотрим несколько алгоритмов, которые применяются в универсальных архиваторах (zip, rar). А также сделаем первые шаги (определим понятия и докажем начальные теоремы) на пути, ведущем к теоретическому обоснованию эффективности этих алгоритмов.

Теория кодирования – это отличный повод поговорить о красивых задачах из алгебры и комбинаторики, о линейной алгебре и алгебраической геометрии над конечными полями, конечных геометриях, простых группах и алгоритмах, связанных с передачей информации. Программа курса: Основные задачи теория кодирования. Коды, исправляющие ошибки. Расстояние Хемминга и неравенство треугольника. Предварительные сведения из алгебры. Строение конечных полей. Линейная алгебра над конечными полями. Линейные коды и их характеристики. Код Хемминга. Совершенные коды. Двойственный код и тождество Мак-Вильямса. Эквивалентность кодов. Методы вычисления минимального расстояния для подпространства. Циклические коды и главные идеалы. Алгеброгеометрические коды. Грассманианы и плюккеровы координаты. Грассмановы коды и минимальные расстояния. Точки на минимальной сфере. Алгоритмы декодирования. Синдромы и минимальные представители. Коды Голея. Конечные геометрии и группы Матье.

Энтропия — мера неопределённости, мера хаоса. В естественных науках это мера беспорядка системы, состоящей из многих элементов; в теории информации — мера неопределённости какого-либо опыта, процесса или испытания, которые могут иметь разные исходы (а значит, мера количества информации); в математике — мера сложности объекта или процесса. Понятие энтропии было впервые введено в 1865 году Р. Клаузиусом в термодинамике, К. Шенноном в теории информации в 1949 г., в теории стохастичпеских процессов Колмогоровым, Гельфандом и Яглом в 1956 г., в функциональном анализе и теории динамических систем Колмогоровым в 1956–1958 гг. Между мирами полной детерминированности, изучаемой классическим анализом и миром хаоса, изучаемым теорией вероятностей, ныне перекидывается мост, который связан с понятием энтропии.

Для того чтобы применить математические средства для изучения информации, потребовалось отвлечься от смысла, содержания информации. Этот подход был общим для упомянутых нами исследователей, так как чистая математика оперирует с количественными соотношениями, не вдаваясь в физическую природу тех объектов, за которыми стоят соотношения.

Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.

В 1948 году американский математик Клод Шеннон опубликовал статью «Математическая теория информации». Тогда, 70 лет назад, эта работа легла в основу современной теории информации и принесла ученому мировую славу. А математика с тех пор стала влиять на жизнь людей в реальном, а не отложенном времени. О том, где сегодня лежит граница между полезной и бесполезной математикой, мы решили спросить директора Института проблем передачи информации имени Харкевича Российской академии наук Андрея Соболевского.

Исходные понятия. Полиномиальные и экспоненциальные алгоритмы. Задачи распознавания и оптимизации. Определение классов P и NP. Совпадает ли P с NP или не совпадает — вопрос на миллион долларов. Машина Тьюринга как универсальный вычислительный прибор. Опорные комбинаторные задачи: коммивояжера, клика, изоморфизм графов, паросочетание, рюкзак, целочисленное линейное программирование (ЦЛП), транспортная задача. В двух словах о непрерывной задаче линейного программирования. Теорема Кука.

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

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