Теория сложности (старая трешовая версия) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лекция 1)
Строка 1: Строка 1:
== Лекция 1 ==
+
== Лекция 1. Вводная ==
*[[Класс DSPACE]]
+
Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]''' и '''[[Класс DTIME |DTIME]]'''.
*[[Класс DTIME]]
+
 
 +
Через эти классы будет дано определение нескольким сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
 +
 
 
*[[Теорема о емкостной иерархии]]
 
*[[Теорема о емкостной иерархии]]
 
*[[Теорема о временной иерархии]]
 
*[[Теорема о временной иерархии]]
 +
*[[Класс co-NP]]
 
*[[Сведение по Карпу]]
 
*[[Сведение по Карпу]]
 
*[[Сведение по Куку]]
 
*[[Сведение по Куку]]
*[[Класс P]]
 
*[[Класс NP]]
 
*[[Класс coNP]]
 
  
 
== Практика 1 ==
 
== Практика 1 ==

Версия 18:19, 2 июня 2010

Лекция 1. Вводная

Курс начинается с введения понятий DSPACE и DTIME.

Через эти классы будет дано определение нескольким сложностным классам, в том числе P и NP.

Практика 1

Лекция 2

Практика 2

Лекция 3

Практика 3

Практика, которой на самом деле не было

Лекция 5

Лекция 6

Практика 6

Лекция 7

Практика 7

Лекция 8

Практика 8

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13