Математическая логика

все курсы

Курс находится на модерации. Данные могут быть неактуальны.

3.5

13 недель

Тип обучения

Курс

Зач. единицы

Сертификат

1 800 ₽ для получения

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

бесплатно

нет рассрочки

Основное достижение теории вычислимости заключается в существование задач, которые в принципе нельзя решить компьютерной программой. Более того, подобные задачи возникают в алгебре, комбинаторике слов и других разделах математики, с теорией вычислимости напрямую не связанных. Теория вычислимости тесно переплетается и с математической логикой, особенно с логикой доказательств. Ещё Лейбниц предполагал, что любое рассуждение можно в конечном счёте заменить вычислением. Знаменитая теорема Гёделя о неполноте арифметики в некотором смысле делает невозможным реализацию идеи Лейбница. Теория вычислимости высвечивает глубинные причины этого явления. В курс также включены два раздела, более близкие к практике. Первый – это лямбда-исчисление, альтернативный способ формализации, что такое программа. Эта наука закладывает основы функционального программирования. Второй – это теория сложности вычислений. На практике неважно, даст ли программа ответ в принципе. Важно, даст ли она его за приемлемое время. В этой теории возникает одна из ключевых открытых проблем современности: равны ли классы P и NP. Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.

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

Мусатов Даниил Владимирович

курсов

Кандидат физико-математических наук Должность: Преподаватель кафедры дискретной математики МФТИ

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

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

Московский физико-технический институт

1 отзыв

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

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

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

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

Открытое образование

3.7

31 отзыв

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

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

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

Множества и их мощности. Счётные и несчётные множества. Диагональный метод Кантора.
Абстрактное понятие алгоритма. Машины Тьюринга. Счётность множества всех алгоритмов.
Вычислимые функции. Разрешимые и перечислимые множества. Существование невычислимых функций и неразрешимых множеств из соображений мощности.
Неразрешимость проблем самоприменимости и остановки. Теорема Успенского-Райса.
Понятие m-сводимости. Построение неперечислимого множества, дополнение к которому также неперечислимо.
Алгоритмически неразрешимые задачи в комбинаторике и алгебре.
Теорема Клини о неподвижной точке. Существование в любом языке программирования программы, печатающей собственный текст.
Понятие формальной системы доказательств. Аксиомы формальной арифметики.
Теорема Гёделя о неполноте. Существование принципиально непознаваемой программы.
Лямбда-исчисление: синтаксис, приведение к нормальной форме, нумералы Чёрча, реализация простейших функций.
Лямбда-исчисление: комбинатор неподвижной точки и рекурсивное программирование.
Основы теории сложности вычислений: измерение времени работы программы. Классы P и NP. Проблема перебора (равны ли классы P и NP). NP-полные задачи.