Курс находится на модерации. Данные могут быть неактуальны.
Тип обучения
Тип обучения
Курс
Зач. единицы
Зач. единицы
5
Сертификат
Сертификат
1 800 ₽ для получения

Стоимость курса

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

Вас будут обучать

Кандидат физико-математических наук Должность: Преподаватель кафедры дискретной математики МФТИ
Научные интересы: сложность вычислений и описаний, теория игр, пространственная экономика, сложные сети. Образование С 1990 по 2001 годы учился в Московской гимназии на Юго-Западе №1543, с 1995 года неоднократно участвовал и побеждал в олимпиадах различного уровня по математике, физике, химии и проч. Высшие результаты: второе место на Московской математической олимпиаде 1999 и 2001 годов, второе место на Всероссийской олимпиаде по математике 1999 года. В 2001 году поступил на механико-математический факультет МГУ, с 2003 года на кафедре математической логики и теории алгоритмов, в 2006 году завершил обучение с красным дипломом, защитив работу по теме «Экстракторы и эффективный вариант теоремы Мучника». В 2001 году поступил в Независимый Московский Университет, который также успешно закончил в 2006 году. В 2006–2008 годах обучался в Российской экономической школе по программе «магистр экономики», закончив её с особым отличием. Профессиональный опыт В 2006–2009 годах обучался в очной аспирантуре мехмата МГУ на кафедре матлогики и теории алгоритмов. Готовится к защите кандидатская диссертация по теме «Комбинаторные методы в теории колмогоровской сложности с ограничением на ресурсы» С 2007 года преподаю в МФТИ на факультете ИВТ. Курсы: теория игр, математическая логика и теория алгоритмов, сложность вычислений, криптография, методы оптимизации. С 2007 года веду семинары в РЭШ по курсам микроэкономики 1–5, пространственной экономики, теории международной торговли, теории аукционов, теории контрактов, экономике общественного сектора. Выступал на многих российских и международных конференциях по математике, экономике и computer science.

Образовательная организация

Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира.

Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.

Основой образования в МФТИ является уникальная «система Физтеха», сформулированная Петром Капицей: кропотливый отбор одаренных и склонных к творческой работе абитуриентов; участие в обучении ведущих научных работников; индивидуальный подход к отдельным студентам с целью развития их творческих задатков; воспитание с первых шагов в атмосфере технических исследований и конструктивного творчества с использованием потенциала лучших лабораторий страны.

Среди выпускников МФТИ — нобелевские лауреаты Андрей Гейм и Константин Новоселов, основатель компании ABBYY Давид Ян, один из авторов архитектурных принципов построения вычислительных комплексов Борис Бабаян.

Новый элемент системы российского образования — открытые онлайн-курсы — cможет перезачесть любой университет. Мы делаем это реальной практикой, расширяя границы образования для каждого студента. Полный набор курсов от ведущих университетов. Мы ведём системную работу по созданию курсов для базовой части всех направлений подготовки, обеспечивая удобное и выгодное для любого университета встраивание курса в свои образовательные программы
«Открытое образование» – это образовательная платформа, предлагающая массовые онлайн-курсы ведущих российских вузов, которые объединили свои усилия, чтобы предоставить возможность каждому получить качественное высшее образование.

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

Программа курса

Неделя 1

Основные модели вычислений и измерение сложности задач

Неделя 2

Классы P, NP и coNP, проблема равенства P и NP

Недели 3 и 4

Полиномиальная сводимость, NP-полнота

Неделя 5

Вычисления на полиномиальной памяти, класс PSPACE

Недели 6 и 7

Вычисления на логарифмической памяти, классы L и NL

Недели 8 и 9

Вероятностные вычисления

Неделя 10

Дерандомизация вероятностных алгоритмов

Неделя 11

Интерактивные протоколы

Неделя 12

Основания криптографии

Рейтинг курса

3.3
рейтинг
0
0
0
0
0
обновлено 26.11.2023 01:06
Сложность вычислений

Сложность вычислений

Оставить отзыв
Поделиться курсом с друзьями