Вклад участника
6 мая 2012
Теоремы о временной и ёмкостной иерархиях
Чуточку подправил читабельность
м+12
Обсуждение:Класс P
Todo №n
+1344
30 апреля 2012
29 апреля 2012
Обсуждение:Класс P
TODO
мОбсуждение:Теоремы о временной и ёмкостной иерархиях
todo
Обсуждение:Класс P
todo
Обсуждение:Теорема Махэни
todo
27 апреля 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+149
Обсуждение:Теорема Бермана — Форчуна
ToDo
+247
Обсуждение:Примеры NP-полных языков. Теорема Кука
Обязательно todo
24 апреля 2012
18 апреля 2012
15 апреля 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определение полного языка
+822
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение сложного языка
+570
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+114
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил теорему о транзитивности
+1830
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил пример сведения
+2447
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение
4 апреля 2012
Теория сложности
Добавлены темы первой волны
+1356
Заглавная страница
Разделены старая и новая версия «теории сложности»
м+181
Теория сложности
Убран редирект
-112
Теория сложности
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
Теория сложности (старая трешовая версия)
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
м
24 января 2012
Автоматы с магазинной памятью
Недетерминированный автомат с магазинной памятью
м-1
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Идиотский баг
мНеукорачивающие и контекстно-зависимые грамматики, эквивалентность
Бысрый фикс
м+1
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+44
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+18
Лемма о разрастании для КС-грамматик
Лемма о разрастании для КС-грамматик
м+27
Лемма о разрастании для КС-грамматик
Нет описания правки
мТеорема Райса-Шапиро
Тире
м+10
Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
Некоторое пояснение
+165
23 января 2012
Лемма о разрастании для КС-грамматик
Нет описания правки
м-27
Лемма о разрастании для КС-грамматик
Идиотский фиск
м-2
Вычислимые функции
Мелкий фикс (всё-таки на питоноподобном языке пишем)
мВычислимые функции
«утверждение» → «лемма»
м-7
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м+2
Удаление eps-правил из грамматики
Доказательство корректности
м+34
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м-2
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м-2
Удаление бесполезных символов из грамматики
Фикс русского
м+23
Удаление бесполезных символов из грамматики
«т.к.» → «так как»
м+6
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Фикс
м+40
Иерархия Хомского формальных грамматик
Доубирал нелепое слово «те»
м-15
Иерархия Хомского формальных грамматик
Класс 2
м-5
21 января 2012
Автоматы с eps-переходами. Eps-замыкание
Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание
м-151
Автоматы с eps-переходами. Eps-замыкание
«Определение» эквивалентности
м+306
Существенно неоднозначные языки
И снова русский язык
м+6