Алгоритмы и структуры данных 2 2018/2019

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Лектор: С. Объедков

Расписание лекций:
понедельник 12:10 – 13:30, ауд. 622
пятница 10:30 – 11:50, ауд. 622

Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324

Ассистент: Игорь Минеев

Лекции

  1. 7 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
  2. 10 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Теорема Кука – Левина.
  3. 14 сентября. NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе.
  4. 17 сентября. Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск.

Оценки

Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен

Аудиторная работа

Оценка за аудиторную работу складывается из следующих частей: 3 балла за контрольную работу в середине модуля, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование. За каждый набор задач и каждое задание на программирование можно получить 1 балл. Дробные оценки не предусмотрены.

Задания на программирование

  1. Конечные автоматы: контест до 30 сентября.

Наборы задач

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

  1. P и NP
  2. Полиномиальные сведения и NP-полные задачи

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

Первое домашнее задание: контест до 23:59 30 сентября.

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_2_2018/2019&oldid=29196»