Кафедра математической логики и теории алгоритмов

Алгоритмы: построение и анализ

Полугодовой курс для магистрантов первого года программы «Цифровые технологии и искусственный интеллект» (осень 2022)

Лектор: Н.К. Верещагин

Вторник 12:30 — 14:05 онлайн на платформе Zoom (https://us06web.zoom.us/j/86758420576?pwd=ckFrMWUvKzNwL01Oa3N0NU9ZNyt1dz09), начиная со 2 сентября.

Контакты: nikolay.vereshchagin@math.msu.ru | Группа в Телеграм | Записи лекций | Записи на доске

Новости:

Экзамен 24 января переносится на вторую половину дня (начиная с 14:30). Просьба ко всем заново записаться в таблицу для сдачи экзамена  https://docs.google.com/spreadsheets/d/1tPEAzd2IGjCSgQFja69fa28shcA05g8b7-6IBMmvK8I/edit#gid=0
Лекция 11 октября не состоится. Следующая лекция — 18 октября.
Начиная с 27 сентября лекции перенесены на вторник 12:30-14:05

Краткое описание курса:

Методы построения быстрых алгоритмов: алгоритмы сортировки, динамическое программирование, потоки в сетях, жадные алгоримты, амортизационный анализ, строковые алгоритмы.

Лекции

Лекции читаются по вторникам 12:30–14:05 онлайн на платформе Zoom (https://us06web.zoom.us/j/86758420576?pwd=ckFrMWUvKzNwL01Oa3N0NU9ZNyt1dz09).

Домашние задания

После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF Н.К. Верещагину nikolay.vereshchagin@math.msu.ru)  не позже дедлайна, указанного перед самим заданием. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).

Экзамен

В конце семестра будет устный экзамен. В билете будет два теоретических вопроса, каждый из которых оценивается в 0.5 балла.Программа экзамена

Досрочный экзамен состоится 14 декабря (Самородова, Гелиаскарова, Хазиев), а обычный экзамен будет 24 января. Для сдачи экзамена неолходимо заранее записаться в следующие таблицы: 14 декабря24 января. Подключившись к конференции за 30 мин. до того времени, в которое записались, Вы получите 
один вопрос на теорему с доказательством или анализ некоторого алгоритма.
 На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками. 
После ответа на этот вопрос Вы получите второй вопрос, в котором доказывать ничего не надо (на определение или формулировку утверждения).
 На этот вопрос надо отвечать сразу. Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса. Ссылка для подключения: https://us06web.zoom.us/j/86791560853?pwd=UXNUczBHNWdrbG81RHlKTlozaEZqdz09

Итоговая оценка

Оценка за домашние задания и оценка за экзамен входят в итоговую оценку с коэффициентами 0.5, 0.5 соответственно.  Итоговая оценка выставляется по следующему правилу:

отлично — итоговоя оценка не меньше 80%,
хорошо — 60%,
удовлетворительно — 40%.
Зачет — 50%.

Таблица оценок (домашние задания, экзамен, итоговая оценка)

Литература

  1. Кормен, Лейзерсон, Ривест. Алгоритмы: построение и анализ. Москва, МЦНМО 2001.
  2. Китаев, Вялый, Шень. Классические и квантовые вычисления. Москва, МЦНМО 1999.