Алгоритмы и структуры данных 2 2018/2019 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (Новая страница: «'''Лектор:''' [http://www.hse.ru/staff/obiedkov С. Объедков] '''Расписание лекций:'''<br/> понедельник 12:10 – 13:30…») |
.obj (обсуждение | вклад) (→Аудиторная работа) |
||
Строка 21: | Строка 21: | ||
= Аудиторная работа = | = Аудиторная работа = | ||
+ | |||
+ | Оценка за аудиторную работу складывается из следующих частей: 3 балла за контрольную работу в середине модуля, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование. | ||
+ | |||
+ | ==Задания на программирование== | ||
+ | Конечные автоматы: [https://official.contest.yandex.ru/contest/8915 контест] до 30 сентября. | ||
= Домашние задания = | = Домашние задания = |
Версия 16:31, 16 сентября 2018
Лектор: С. Объедков
Расписание лекций:
понедельник 12:10 – 13:30, ауд. 622
пятница 10:30 – 11:50, ауд. 622
Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324
Ассистент: Игорь Минеев
Лекции
- 7 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
- 10 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Теорема Кука – Левина.
- 14 сентября. NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе.
Оценки
Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен
Аудиторная работа
Оценка за аудиторную работу складывается из следующих частей: 3 балла за контрольную работу в середине модуля, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование.
Задания на программирование
Конечные автоматы: контест до 30 сентября.