Краткое описание курса:
Логика высказываний и логика предикатов. Начала сложности вычислений: время и память алгоритмов, полиномиальные алгоритмы, сведение задач по Карпу, классы P и NP.
Лекции
Лекции читаются он-лайн на платформе Zoom https://us06web.zoom.us/j/89232018333?pwd=TzJmdUh2OUFhM09wdnludVhtazRQdz09. В конце каждой лекции дается тест состоящий и нескольких простых задач. Цель теста — добиться, чтобы студенты внимательно слушали лекции. За тесты выставляется оценка, равная доле правильных ответов.
Домашние задания
После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF Н.К. Верещагину nikolay.vereshchagin@math.msu.ru) не позже дедлайна, указанного перед самим заданием. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).
Экзамен
В конце семестра будет устный экзамен. В билете будет два теоретических вопроса, каждый из которых оценивается в 0.5 балла. Программа экзамена
Экзамен состоится 30 июня с 9:00. Для сдачи экзамена небоходимо заранее записаться в следующую таблицу.
Подключившись к конференции (https://us06web.zoom.us/j/89232018333?pwd=TzJmdUh2OUFhM09wdnludVhtazRQdz09) в то время, в которое записались, Вы получите
один вопрос на теорему с доказательством.
На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками.
После ответа на этот вопрос Вы получите второй вопрос на определение.
На этот вопрос надо отвечать сразу. Для уточнения оценки
преподаватель может задавать дополнительные вопросы на знание определений и
основных фактов курса.
Итоговая оценка
Оценка за тесты, оценка за домашние задания и оценка за экзамен входят в итоговую оценку с коэффициентами 0.3, 0.3, 0.4, соответственно. Итоговая оценка выставляется по следующему правилу:
отлично — итоговая оценка нее меньше 80%,
хорошо — 60%,
удовлетворительно — 40%.
Зачет — 50%.
Таблица оценок (тесты, домашние задания, экзамен, итоговая оценка)
Литература
- Верещагин, Шень. Языки и исчисления. Москва, МЦНМО 2008.
- Кормен, Лейзерсон, Ривест. Алгоритмы: построение и анализ. Москва, МЦНМО 2001.
- Китаев, Вялый, Шень. Классические и квантовые вычисления. Москва, МЦНМО 1999.
