Математическая логика, теория алгоритмов и сложность вычислений
Полугодовой курс для магистрантов программы «Цифровые технологии и искусственный интеллект» (весна 2022)
Лектор: Н.К. Верещагин
Вторник 12:30–14:05 он-лайн на платформе Zoom, начиная с 15 февраля.
Контакты: nikolay.vereshchagin@math.msu.ru | Канал Youtube с записями лекций | Группа в Телеграм | Ссылка на записи во время лекций
Краткое описание курса:
Начала сложности вычислений: время и память алгоритмов, полиномиальные алгоритмы, сведение задач по Карпу, классы P и NP. Методы построения быстрых алгоритмов: алгоритмы сортировки, динамическое программирование, потоки в сетях, жадные алгоримты, амортизационный анализ.
Лекции
Лекции читаются он-лайн на платформе Zoom https://us02web.zoom.us/j/81245827843?pwd=c2tIcDFQY0NTcUljNk9VRUdIRVZSQT09 В конце каждой лекции дается тест состоящий и нескольких простых задач. Цель теста — добиться, чтобы студенты внимательно слушали лекции. За тесты выставляется оценка, равная доле правильных ответов.
Домашние задания
После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF Н.К. Верещагину nikolay.vereshchagin@math.msu.ru) не позже дедлайна, указанного перед самим заданием. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).
Экзамен
В конце семестра будет устный экзамен. В билете будет два теоретических вопроса, каждый из которых оценивается в 0.5 балла. Программа экзамена
Экзамен состоится 15 июня с 9:00. Для сдачи экзамена небоходимо заранее записаться в следующую таблицу https://docs.google.com/spreadsheets/d/1Igtb7Zbe_uBtZYqrh3I-CrIicUv1tcCO2Vsj8uq9jcw/edit?usp=sharing.
Подключившись к конференции (https://us02web.zoom.us/j/87940265263?pwd=cC9pVS9YTWVFdTBpRmtzRXE5WU1BQT09) в то время, в которое записались, Вы получите
один вопрос на теорему с доказательством или анализ некоторого алгоритма.
На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками.
После ответа на этот вопрос Вы получите второй вопрос на определение.
На этот вопрос надо отвечать сразу. Для уточнения оценки
преподаватель может задавать дополнительные вопросы на знание определений и
основных фактов курса.
Итоговая оценка
Оценка за тесты, оценка за домашние задания и оценка за экзамен входят в итоговую оценку с коэффициентами 0.3, 0.3, 0.4, соответственно. Итоговая оценка выставляется по следующему правилу:
отлично — итоговоя оценка нее меньше 80%,
хорошо — 60%,
удовлетворительно — 40%.
Зачет — 50%.
Оценки за тесты: https://drive.google.com/drive/folders/1XpZOpzN2FTtNB5gQ80UbRY60NNnSRxpd?usp=sharing
Таблица оценок (тесты, домашние задания, экзамен, итоговая оценка)
Литература
- Кормен, Лейзерсон, Ривест. Алгоритмы: построение и анализ. Москва, МЦНМО 2001.
- Китаев, Вялый, Шень. Классические и квантовые вычисления. Москва, МЦНМО 1999.