О ПРОЕКТЕ
ВСЕ ПРОЕКТЫ HH
Регистрация компании
Заявка на грант Повысить зарплату Поможем выбрать курс Регистрация карьериста
дистанционно, онлайн
Детали курса

Даты проведения
5 сентября 2016 — 12 декабря 2016
Город
Pоссия
Вид обучения

Видеокурс

Форма обучения
Online
Учебная нагрузка
140 часов
Тема
Науки: Физико-математические
Математика
Обучающая компания
Национальная платформа открытого образования

Базовая цена
Бесплатно!
Показать похожие курсы Найти новый курс
Мне интересно

Сохранить в избранном
Заказать звонок
Отправить вопрос
Анонс
Эдсгеру Дейкстре приписывают высказывание: «наука о вычислимости изучает компьютеры не в большей мере, чем астрономия изучает телескопы». Смысл этой фразы в том, что конкретный компьютер или конкретный язык программирования - только инструмент познания общих закономерностей, справедливых для всех вычислений. Основы этой науки заложены Тьюрингом, Гёделем, Чёрчем, Клини, Постом и другими математиками в 1930-х годах, когда вычислительных машин в современном понимании ещё не было. При этом базовые предположения в полной мере выполняются для современных компьютеров и, наверняка, будут верны для всех будущих, в том числе квантовых.

                            
Программа
  1. Множества и их мощности. Счётные и несчётные множества. Диагональный метод Кантора.
  2. Абстрактное понятие алгоритма. Машины Тьюринга. Счётность множества всех алгоритмов.
  3. Вычислимые функции. Разрешимые и перечислимые множества. Существование невычислимых функций и неразрешимых множеств из соображений мощности.
  4. Неразрешимость проблем самоприменимости и остановки. Теорема Успенского-Райса.
  5. Понятие m-сводимости. Построение неперечислимого множества, дополнение к которому также неперечислимо.
  6. Алгоритмически неразрешимые задачи в комбинаторике и алгебре.
  7. Теорема Клини о неподвижной точке. Существование в любом языке программирования программы, печатающей собственный текст.
  8. Понятие формальной системы доказательств. Аксиомы формальной арифметики.
  9. Теорема Гёделя о неполноте. Существование принципиально непознаваемой программы.
  10. Лямбда-исчисление: синтаксис, приведение к нормальной форме, нумералы Чёрча, реализация простейших функций.
  11. ...
Подробнее о программе

                        
Преподаватели
Мусатов Даниил Владимирович - Кандидат физико-математических наук.

                            
Мне интересно

Сохранить в избранном
Заказать звонок
Отправить вопрос
Обучающая компания
Национальная платформа открытого образования,
Москва, Большой Чудов переулок, дом 8, корпус 1


Схема проезда

Ассоциация «Национальная платформа открытого образования» учреждена ведущими вузами России. Основная цель деятельности Ассоциации - объединить усилия вузов и предоставить возможность каждому получить качественное высшее образование онлайн.

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

«Открытое образование» - современная образовательная платформа, предлагающая онлайн-курсы по базовым дисциплинам, изучаемым в российских университетах.