Тип: курс обязательный
Лектор: Гасанов Эльяр Эльдарович, Калачев Глеб Вячеславович, Алексеев Дмитрий Владимирович
Для: аспирантов 1 года обучения
Время: ср 20:10
Понятие алгоритма и вычислимой функции, перечислимого и разрешимого множества.
Универсальная вычислимая функция. Существование перечислимого неразрешимого множества. Алгоритмические проблемы.
Определение вычислимости в теоретико-множественных терминах (например, вычислимость по Тьюрингу). Тезис Тьюринга-Чёрча.
Сложность вычисления. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи выполнимости булевых формул (3-выполнимость)
Понятие алгоритма и вычислимой функции, перечислимого и разрешимого множества.
Универсальная вычислимая функция. Существование перечислимого неразрешимого множества. Алгоритмические проблемы.
Определение вычислимости в теоретико-множественных терминах (например, вычислимость по Тьюрингу). Тезис Тьюринга-Чёрча.
Сложность вычисления. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи выполнимости булевых формул (3-выполнимость)
Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования, теоремы о сильной/слабой двойственности.
Задачи целочисленного линейного программирования (ЦЛП). Метод ветвей и границ, метод Гомори. Примеры и решение Задачи ЦЛП: Транспортная задача. Задача о назначениях, венгерский алгоритм. Задача коммивояжера.
Задача распределения ресурсов. Принцип выравнивания Гермейера.
Метод динамического программирования. Принцип Беллмана. Примеры задач. Алгоритмы Нидлмана-Вунша и Смита-Ватермана
Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм нахождения максимального потока. Теорема о целочисленности. Теорема Кенига-Эгервари. Теорема Холла. Теорема Дилуорса.
Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
Динамическая модель Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
Теоремы о неподвижных точках (Брауэра, Какутани). Модель Вальраса. Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи допол
Материалы:
[1] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — 4-е изд., исправленное. — М.: МЦНМО, 2012. — 160 c.
[2] Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. - М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 368 с.
[3] Гери М., Джонсон Д., Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982, 416с.
[4] Кострикин А.И. Введение в алгебру, ч. 3, Основные структуры , 3 изд., М:ФИЗМАТЛИТ, 2004
[5] Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел, Изд-во Моск. ун-та, 1984, 152 стр.
[6] Коблиц Н., Курс теории чисел и криптографии, М.: Науч. изд-во ТВП, 2001, 254 с.
[7] Ван-дер-Варден Б.Л., Алгебра, М.: Мир, 1976. - 648 с.
[8] Винберг Э.Б., Курс алгебры, М.: Изд-во «Факториал Пресс», 2001. 544c.
[9] Бунина Е.И., Лекции по алгебре, 3 сем., 2016–2017 уч. год. Лекция 17 (электронное издание)
[10] http://halgebra.math.msu.su/wiki/lib/exe/fetch.php/staff:lecture17.pdf
[11] Виноградов И.М. Основы теории чисел, М.-Л., Гостехиздат, 1952. 180 с.
[12] Нестеренко Ю.В., Теория чисел, – М.: Академия, 2008. 272с.