Исходные понятия. Длина описания задачи. Кодирование описания. Число бит информации, необходимых для формулировки задачи. Время решения, или число арифметических операций, требуемых для решения задачи. Водораздел между полиномиальными и переборными алгоритмами.
2. Задачи распознавания и оптимизации
Роль задач распознавания в теории алгоритмов. Сводимость оптимизации к распознаванию — почти всегда. Задача о простоте числа. О труднорешаемости задачи разложения на множители составного числа.
3. P- и NP-задачи
Определение классов P и NP. Совпадает ли P с NP или не совпадает — вопрос на миллион долларов. Феноменальный прорыв в изучении труднорешаемых задач в связи с открытием NP-класса.
4. Машины Тьюринга
Машина Тьюринга как универсальный вычислительный прибор. Контраст примитивности устройства с фантастическими возможностями. Тезис Тьюринга. Задача Тьюринга как универсальная переборная (NP-полная) задача.
5. Опорные комбинаторные задачи
Джентльменский набор комбинаторных задач. Минимальное остовное дерево (МОД). Задача коммивояжера. Задачи: клика, изоморфизм графов, паросочетание, рюкзак, целочисленное линейное программирование (ЦЛП), транспортная задача. В двух словах о непрерывной задаче линейного программирования. Логические задача ВЫПОЛНИМОСТЬ.
6. Теорема Кука
Теорема Кука устанавливает NP-полноту задачи ВЫПОЛНИМОСТЬ, трансформируя проблематику в область задач, которые можно «пощупать».
Лекции читает Опойцев Валерий Иванович, доктор физико-математических наук, профессор МФТИ, гл. н. с. ИПУ РАН. oschool.ru
Идеальный газ. Уравнение состояния газа. Взаимосвязь давления, температуры и объёма. Механизмы рождения макропараметров в рамках «молекулярного бильярда». Первое начало термодинамики как закон сохранения энергии. Вывод уравнения Бернулли. Энтропия и второе начало термодинамики. Тепловые машины и цикл Карно. Энтропия информационная. Энтропия как неопределённость. Аксиоматический подход к определению энтропии. Принцип максимума энтропии. Подход статистической физики за пределами термодинамики.
На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун. Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.
Мультфильм рассказывает об использовании идеи биологической эволюции в задачах искусственного интеллекта, истории эволюционных алгоритмов и принципах их работы. Все это подробно изучается на магистерской программе Университета Иннополис «Робототехника». Историю об эволюционных алгоритмах нам помог рассказать доцент, руководитель Лаборатории искусственного интеллекта в разработке игр Университета Иннополис Джозеф Браун.
В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.
Теория сложности вычислений — бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы. Поэтому знакомство с основами теории сложности, безусловно, полезно любому, кто собирается серьезно заниматься практическим программированием или теоретическими исследованиями.
В 1958 году в Докладах Академии Наук вышла заметка А. Н. Колмогорова об энтропии как новом инварианте преобразований, сохраняющих меру. Вместе с двумя более ранними заметками, в которых заложены основы того, что потом было названо КАМ-теорией, эти работы полностью изменили облик и место в математике теории динамических систем. Это открытие привело серьезному прогрессу в нескольких областях математики, однако, как ни странно, некоторые идеи, близко лежащие к колмогоровским, не были развиты и даже замечены. Энтропия является одним из целой серии инвариантов, которые возникают при рассмотрении динамики метрических пространств с мерой. Изучение динамики метрик полезно и в других вопросах комбинаторики и теории случайных процессов.
Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.
Какова история создания машины Тьюринга? Как она повлияла на развитие идей, лежащих в основе ряда современных технологий? Какие проблемы существуют в теории вычислительной сложности? И как математика рассматривает понятие случайность? Об идее универсальной машины, проблеме перебора и случайности рассказывает кандидат физико-математических наук Александр Шень.
Выпуклость и неравенства. Неравенство Иенсена. Метод математической индукции. Среднее арифметическое больше среднего геометрического. Приёмы доказательств. Использование производных. О монгольском неравенстве. Метод интервалов. Неравенство с логарифмами.
Теория функций и функциональный анализ – уникальная дисциплина второго круга математического образования, осваивая которую человек вдруг понимает, что ещё вчера за деревьями леса не видел. Это другой этаж мышления, виденья, понимания. Чтобы днём увидеть звёзды, надо опуститься в глубокий колодец. В основе изложения лежит стандартный скелет: метрические, нормированные и топологические пространства; теория меры, интеграл Лебега; компактные и предкомпактные множества; линейные операторы в банаховых и гильбертовых пространствах; спектральная теория; обобщённые функции; элементы нелинейного анализа.