Алгоритмы и структуры данных 2 2017/2018: различия между версиями
Перейти к навигации
Перейти к поиску
Aumnov (обсуждение | вклад) Нет описания правки |
.obj (обсуждение | вклад) Нет описания правки |
||
| Строка 9: | Строка 9: | ||
понедельник 18:00 – 20:00, к. 324<br /> | понедельник 18:00 – 20:00, к. 324<br /> | ||
четверг 16:30 – 18:00, к. 324 | четверг 16:30 – 18:00, к. 324 | ||
= Лекции = | |||
* '''5 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов. | |||
== Страницы групп == | == Страницы групп == | ||
[[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | [[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | ||
Версия от 14:03, 5 сентября 2017
Лектор: С. Объедков
Расписание лекций:
вторник 15:10 – 16:30, ауд. 622
пятница 10:30 – 11:50, ауд. 509
Дополнительная лекция — суббота 23 сентября 12:10 – 13:30, ауд. 622.
Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324
Лекции
- 5 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.