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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Лекция 1)
(→‎Лекция 1. Вводная)
Строка 1: Строка 1:
 
== Лекция 1. Вводная ==
 
== Лекция 1. Вводная ==
−
Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]''' и '''[[Класс DTIME |DTIME]]'''.  
+
Курс начинается с введения понятий '''[[Класс DSPACE |DSPACE]]''' и '''[[Класс DTIME |DTIME]]'''.
  
−
Через эти классы будет дано определение нескольким сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
+
'''DTIME'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Time(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.
 +
 
 +
'''DSPACE'''(''f''(''n'')) = <tex>\{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.
 +
 
 +
 
 +
 
 +
Через эти классы будет дано определение многим сложностным классам, в том числе '''[[P]]''' и '''[[NP]]'''.
  
 
*[[Теорема о емкостной иерархии]]
 
*[[Теорема о емкостной иерархии]]

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

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

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

DTIME(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Time(m,x) \le f(|x|) \}[/math], где [math]|x|[/math] — длина входа [math]x[/math].

DSPACE(f(n)) = [math]\{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Space(m,x) \le f(|x|) \}[/math], где [math]|x|[/math] — длина входа [math]x[/math].


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

Практика 1

Лекция 2

Практика 2

Лекция 3

Практика 3

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

Лекция 5

Лекция 6

Практика 6

Лекция 7

Практика 7

Лекция 8

Практика 8

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_сложности_(старая_трешовая_версия)&oldid=1355»