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

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

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

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

Пятница 9:00–10:35 онлайн на платформе Zoom (https://us06web.zoom.us/j/86758420576?pwd=ckFrMWUvKzNwL01Oa3N0NU9ZNyt1dz09), начиная со 2 сентбря.

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

 

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

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

Лекции

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

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

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

Экзамен

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

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

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

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

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

Литература

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