Участник:Shersh/Тикеты к 5ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎1. Автоматы и регулярные языки)
(→‎в процессе проверки 2. Контекстно-свободные грамматики)
Строка 49: Строка 49:
 
# [[Контексты и синтаксические моноиды]]
 
# [[Контексты и синтаксические моноиды]]
  
−
== '''в процессе проверки''' 2. Контекстно-свободные грамматики ==
+
== 2. Контекстно-свободные грамматики ==
−
# '''взяли''' [[Формальные грамматики]]
+
# [[Формальные грамматики]]
−
## примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить
+
## Пояснить пример контекстно-зависимой грамматики
−
## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание.
+
## Можно ещё примеров различных интересных грамматик добавить
−
## заголовки здоровенные, они первого уровня (=) , а надо второго (==)
+
# '''!!!''' [[Иерархия Хомского формальных грамматик]]
−
## англоязычные термины
 
−
## ссылки на английские источники
 
−
# [[Иерархия Хомского формальных грамматик]]
 
 
## добавить англоязычные термины
 
## добавить англоязычные термины
 
## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
 
## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
 
## интервики, ссылка на автоматные граммматики, например, которые есть на вики
 
## интервики, ссылка на автоматные граммматики, например, которые есть на вики
 
## на машину Тьюринга можно внутреннюю ссылку сделать
 
## на машину Тьюринга можно внутреннюю ссылку сделать
 +
## Ссылку на вики заменить на ссылку примечанием
 +
## Добавить интервики на другие факты (добавить См. также)
 +
## Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)
 
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
 
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
 +
## Добавить источники информации, ссылок, интервики (на Иерархию)
 
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
 
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
 
## Англоязычные термины
 
## Англоязычные термины
 
## Источник бесполезен без конкретного указания, где искать
 
## Источник бесполезен без конкретного указания, где искать
−
## Внутреннюю ссылку на ДКА
+
## Добавить интервики
−
# '''взяли''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
+
# '''!!!''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 
## нормально оформить уже существующий источник
 
## нормально оформить уже существующий источник
 
## добавить англоязычные термины
 
## добавить англоязычные термины
 
## интервики
 
## интервики
−
## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.
+
## Симольные скобки взять в tex
 
## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)
 
## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)
 
## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
 
## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
−
# '''взяли''' [[Замкнутость КС-языков относительно различных операций]]
+
## Добавить заголовков
−
## Че за --? Заменить на —
+
## Перерисовать картинку
−
## Half некрасивый, в \mathrm его
+
# '''!!!''' [[Замкнутость КС-языков относительно различных операций]]
−
## В конкатенации что-то немного муть написана
+
## Пропущен - в КС-языках
−
## "Необходима картинка. " — запилить!
+
## Точку в конкатенации лучше опустить
−
## Про разворот — доказать
+
## Half некрасивый, c маленькой буквы его
−
## побольше внутренних ссылок, на МП-автомат там, например
+
## Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
−
## проставить категории
+
## Добавить примеры других грамматик
−
# '''взяли''' [[Удаление бесполезных символов из грамматики]]
+
## Добавить ссылок, см. также
−
## запилить пример (уже есть)
+
# '''!!!''' [[Регулярная аппроксимация КС-языков]]
−
## англоязычных терминов где можно
+
## Добавить док-во леммы
−
## если есть, ссылок на википедию.
+
## Отформатировать псевдокод
−
## вообще нет внутренних ссылок, надо бы добавить
+
## Tex правильно оформить
−
## "нетерминалы правой части являются порождающими" — правой части правила, наверное
+
## Описание перед псевдокодом перенести
−
## первый пример сделай чуть более интеллектуальным, добавь что-нибудь типа "D -> aD", напримре (а то какой дурак будет вводить нетерминал без правил :) )
+
## Картинки убого расположены
−
## асимптотики какие-нибудь нужны
+
## "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
## Расшифровать RTN (то же с MT)
−
# '''взяли''' [[Удаление eps-правил из грамматики]]
+
## Источники информации нормально оформить
−
## запилить пример (уже есть)
+
# '''!!!''' [[Удаление бесполезных символов из грамматики]]
−
## англоязычных терминов где можно
+
## Англоязычных термины нормально оформить
−
## если есть, ссылок на википедию.
+
## Добавить ссылок
−
## почти нет внутренних ссылок, надо бы добавить
+
## Добавить интервики
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
## Грамматики оформлены криво
−
## асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)
+
## Написать, что такое <tex> | \Gamma | </tex>
−
## для алгоритма поиска eps-порождающих точно можно асимптотику написать
+
## Написать, откуда берутся такие асимптотики, и как добавить очередь
−
# '''взяли''' [[Удаление цепных правил из грамматики]]
+
## Аналогично про обход в глубину
−
## как-то странно в примере, на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)
+
## Ссылку на НФХ перенести в источники информации
−
## англоязычных терминов где можно
+
## Алгоритмы оформить отдельным подзаголовком
−
## если есть, ссылок на википедию.
+
# [[Удаление длинных правил из грамматики]]
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
## Добавить источники информации
−
## асимптотику
+
## Подробней расписать время работы
−
# '''взяли''' [[Удаление длинных правил из грамматики]]
+
## Лишняя запятая в алгоритме после многоточия
−
## англоязычных терминов где можно
+
# '''!!!''' [[Удаление eps-правил из грамматики]]
−
## если есть, ссылок на википедию.
+
## Англоязычных термины нормально оформить
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект
−
## асимптотику
+
## Грамматику G заменить на <tex> \Gamma </tex>
−
# '''взяли''' [[Нормальная форма Хомского]]
+
## Ссылку на НФХ перенести в источники информации
−
## "Несколько определений" — а определение одно, выкинуть вообще этот пункт и вынести определение НФХ в заголовок
+
## Написать, почему при удалении длинных правил асимптотика будет линейной
−
## если есть, ссылок на википедию.
+
## Грамматики криво оформлены
−
## такие кавычки в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычек
+
## Пояснить использование очереди
−
# [[Устранение левой рекурсии]]
+
## Пропущены дефисы после КС местами
−
# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]
+
# [[Удаление цепных правил из грамматики]]
 +
## Англоязычные термины оформить нормально
 +
## Провести в алгоритме аналогию с транзитивным замыканием
 +
## Грамматика криво криво оформлена
 +
## Расписать асимптотику алгоритма
 +
## Ссылку на НФХ перенести в источники информации
 +
# '''!!!''' [[Нормальная форма Хомского]]
 +
## Англоязычные термины хорошо оформить
 +
## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
 +
## Константы взять в Tex
 +
## Пример грамматики криво оформлен
 +
## Ссылку на НФХ перенести в источники информации
 +
## Заменить знаки неравенств в Tex
 +
# '''!!!''' [[Устранение левой рекурсии]]
 +
## Англоязычные термины оформить правильно
 +
## Кинуть интервики на методы нисходящего разбора (или см. также)
 +
## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
 +
## Отформатировать псевдокод
 +
## Знаки неравенств заменить
 +
## Источники информации нормально оформить
 +
# '''!!!!!''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
## написать, для чего она нужна
 
## написать, для чего она нужна
−
## какая асимптотика алгоритма приведения?
+
## Какая асимптотика алгоритма приведения?
−
## ссылки на источники? --[[Участник:Dgerasimov|Дмитрий Герасимов]]
+
## Добавить источники информации
−
# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
+
## Добавить примеры
−
# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
+
## Англоязычные термины нормально оформить
−
# [[Алгоритм Эрли]]
+
## Отформатировать псевдокод
−
# [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
+
# '''!!!''' [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
−
# [[Лемма о разрастании для КС-грамматик]]
+
## Аккуратно помёрджить с аналогичным конспектом первого курса
 +
# '''!!!''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
 +
## Расписать подробней и формальней
 +
# '''!!!''' [[Алгоритм Эрли]]
 +
## Отформатировать псевдокод
 +
## Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
 +
## Доказательство плохо отформатировано
 +
## Оформить красиво источники информации
 +
# '''!!!''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 +
## Отформатировать псевдокод
 +
## Грамматику G заменить на \Gamma
 +
## Перенести описание алгоритма перед псевдокодом
 +
## Хотелось бы адекватные доказательства читать (см. обсуждения)
 +
# '''!!!''' [[Лемма о разрастании для КС-грамматик]]
 +
## Добавить пример не КС-языка, который удовлетворяют условию леммы
 +
## Источники нормально оформить
 +
## Добавить см. также на варианты леммы
 
# [[Лемма Огдена]]
 
# [[Лемма Огдена]]
−
# ''взяли'' [[Существенно неоднозначные языки]]
+
## Источники информации добавить
−
## добавить английские термины
+
## '''!!!''' Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы
−
## добавить всякое интервики
+
# [[Существенно неоднозначные языки]]
−
## добавить ссылок на русские и английские источники
+
## Англоязычные термины оформить правильно
−
## упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.
+
## Ссылки из См. также перенести в источники информации
 
# [[Автоматы с магазинной памятью]]
 
# [[Автоматы с магазинной памятью]]
 +
## Картинки увеличить
 
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
 
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
−
# '''fixed''' [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
+
## Добавить источники информации
−
## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.
+
# [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
−
## Картинка. Что она означает?
+
## Ссылки и литературу оформить правильно
−
## Доказательства утверждений написаны непонятно.
 
−
## Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.
 
 
# [[Детерминированные автоматы с магазинной памятью]]
 
# [[Детерминированные автоматы с магазинной памятью]]
 +
## В пример добавить язык автомата
 +
## Англоязычные термины
 
# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 
# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
−
# '''!!!'''[[Нормальная форма ДМП-автомата]]
+
# '''!!!!!''' [[Нормальная форма ДМП-автомата]]
−
## написать
+
## Написать!
 
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 +
## Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?
 +
## Добавить источники информации
  
 
== '''в процессе проверки''' 3. Теория вычислимости ==
 
== '''в процессе проверки''' 3. Теория вычислимости ==

Версия 20:30, 15 сентября 2014

Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе

1. Автоматы и регулярные языки

  1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
  2. Регулярные языки: два определения и их эквивалентность
    1. Англоязычные термины
  3. Детерминированные конечные автоматы
    1. Английские термины
    2. Добавить ссылку на факт про эквивалентность автоматных и регулярных
    3. Англоязычные источники (хотя бы википедия)
  4. !!! Прямое произведение ДКА
    1. Написать, как построить автомат для пересечения языков (с картинками)
    2. Добавить фактов про прямое произведение (задание 4.2.14 из ХМУ)
  5. Недетерминированные конечные автоматы
    1. Английские термины
    2. Отрефакторить псевдокод
  6. !!! Построение по НКА эквивалентного ДКА, алгоритм Томпсона
    1. Отрефакторить псевдокод
    2. Добавить ссылки, см. также
    3. Исправить tex в знаках неравенств
    4. Какой-то абсолютно нечитабельный конспект. Словесное описание не помешало бы в начале
    5. Можно добавить простое альтернативное доказательство
  7. Автоматы с eps-переходами. Eps-замыкание
    1. Добавить источники информации, см. также
    2. Написать, где используется алгоритм eps-замыкания
  8. Теорема Клини (совпадение классов автоматных и регулярных языков)
    1. Добавить ссылок
  9. !!! Решение уравнений в регулярных выражениях
    1. Исправить неясный переход во второй части утверждения (да и вообще лучше доказательство поясней написать)
    2. Добавить ссылки
    3. Добавить ещё что-нибудь про то, где используются такие системы (кроме теоремы Клини)
  10. !!! Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
    1. Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини
  11. !!! Замкнутость регулярных языков относительно различных операций
    1. Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
  12. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
  13. Интерпретация булевых формул с кванторами как игр для двух игроков
    вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
  14. !!! Доказательство нерегулярности языков: лемма о разрастании
    1. Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
    2. Доказательство леммы о накачке в общем виде
  15. Эквивалентность состояний ДКА
    1. Добавить ссылок
  16. !!! Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
    1. Структурно написать алгоритм
    2. Таблички оформить прилично
    3. Добавить ссылок
  17. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
  18. Контексты и синтаксические моноиды

2. Контекстно-свободные грамматики

  1. Формальные грамматики
    1. Пояснить пример контекстно-зависимой грамматики
    2. Можно ещё примеров различных интересных грамматик добавить
  2. !!! Иерархия Хомского формальных грамматик
    1. добавить англоязычные термины
    2. добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
    3. интервики, ссылка на автоматные граммматики, например, которые есть на вики
    4. на машину Тьюринга можно внутреннюю ссылку сделать
    5. Ссылку на вики заменить на ссылку примечанием
    6. Добавить интервики на другие факты (добавить См. также)
    7. Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)
  3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
    1. Добавить источники информации, ссылок, интервики (на Иерархию)
  4. Правоконтекстные грамматики, эквивалентность автоматам
    1. Англоязычные термины
    2. Источник бесполезен без конкретного указания, где искать
    3. Добавить интервики
  5. !!! Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
    1. нормально оформить уже существующий источник
    2. добавить англоязычные термины
    3. интервики
    4. Симольные скобки взять в tex
    5. а еще тут стрелки одинаковые и в правилах (надо [math]\to[/math]) и в выводе (надо [math]\Rightarrow[/math])
    6. пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
    7. Добавить заголовков
    8. Перерисовать картинку
  6. !!! Замкнутость КС-языков относительно различных операций
    1. Пропущен - в КС-языках
    2. Точку в конкатенации лучше опустить
    3. Half некрасивый, c маленькой буквы его
    4. Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
    5. Добавить примеры других грамматик
    6. Добавить ссылок, см. также
  7. !!! Регулярная аппроксимация КС-языков
    1. Добавить док-во леммы
    2. Отформатировать псевдокод
    3. Tex правильно оформить
    4. Описание перед псевдокодом перенести
    5. Картинки убого расположены
    6. "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
    7. Расшифровать RTN (то же с MT)
    8. Источники информации нормально оформить
  8. !!! Удаление бесполезных символов из грамматики
    1. Англоязычных термины нормально оформить
    2. Добавить ссылок
    3. Добавить интервики
    4. Грамматики оформлены криво
    5. Написать, что такое [math] | \Gamma | [/math]
    6. Написать, откуда берутся такие асимптотики, и как добавить очередь
    7. Аналогично про обход в глубину
    8. Ссылку на НФХ перенести в источники информации
    9. Алгоритмы оформить отдельным подзаголовком
  9. Удаление длинных правил из грамматики
    1. Добавить источники информации
    2. Подробней расписать время работы
    3. Лишняя запятая в алгоритме после многоточия
  10. !!! Удаление eps-правил из грамматики
    1. Англоязычных термины нормально оформить
    2. Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже — реструктуризовать конспект
    3. Грамматику G заменить на [math] \Gamma [/math]
    4. Ссылку на НФХ перенести в источники информации
    5. Написать, почему при удалении длинных правил асимптотика будет линейной
    6. Грамматики криво оформлены
    7. Пояснить использование очереди
    8. Пропущены дефисы после КС местами
  11. Удаление цепных правил из грамматики
    1. Англоязычные термины оформить нормально
    2. Провести в алгоритме аналогию с транзитивным замыканием
    3. Грамматика криво криво оформлена
    4. Расписать асимптотику алгоритма
    5. Ссылку на НФХ перенести в источники информации
  12. !!! Нормальная форма Хомского
    1. Англоязычные термины хорошо оформить
    2. Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
    3. Константы взять в Tex
    4. Пример грамматики криво оформлен
    5. Ссылку на НФХ перенести в источники информации
    6. Заменить знаки неравенств в Tex
  13. !!! Устранение левой рекурсии
    1. Англоязычные термины оформить правильно
    2. Кинуть интервики на методы нисходящего разбора (или см. также)
    3. Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
    4. Отформатировать псевдокод
    5. Знаки неравенств заменить
    6. Источники информации нормально оформить
  14. !!!!! Приведение грамматики к ослабленной нормальной форме Грейбах
    1. написать, для чего она нужна
    2. Какая асимптотика алгоритма приведения?
    3. Добавить источники информации
    4. Добавить примеры
    5. Англоязычные термины нормально оформить
    6. Отформатировать псевдокод
  15. !!! Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
    1. Аккуратно помёрджить с аналогичным конспектом первого курса
  16. !!! Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
    1. Расписать подробней и формальней
  17. !!! Алгоритм Эрли
    1. Отформатировать псевдокод
    2. Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
    3. Доказательство плохо отформатировано
    4. Оформить красиво источники информации
  18. !!! Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
    1. Отформатировать псевдокод
    2. Грамматику G заменить на \Gamma
    3. Перенести описание алгоритма перед псевдокодом
    4. Хотелось бы адекватные доказательства читать (см. обсуждения)
  19. !!! Лемма о разрастании для КС-грамматик
    1. Добавить пример не КС-языка, который удовлетворяют условию леммы
    2. Источники нормально оформить
    3. Добавить см. также на варианты леммы
  20. Лемма Огдена
    1. Источники информации добавить
    2. !!! Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы
  21. Существенно неоднозначные языки
    1. Англоязычные термины оформить правильно
    2. Ссылки из См. также перенести в источники информации
  22. Автоматы с магазинной памятью
    1. Картинки увеличить
  23. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
    1. Добавить источники информации
  24. Совпадение множества языков МП-автоматов и контекстно-свободных языков
    1. Ссылки и литературу оформить правильно
  25. Детерминированные автоматы с магазинной памятью
    1. В пример добавить язык автомата
    2. Англоязычные термины
  26. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  27. !!!!! Нормальная форма ДМП-автомата
    1. Написать!
  28. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
    1. Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?
    2. Добавить источники информации

в процессе проверки 3. Теория вычислимости

  1. fixed Разрешимые (рекурсивные) языки
    1. англоязычные термины
    2. категории
    3. ссылки на википедию, русскую и английскую
  2. fixed Перечислимые языки
    1. англоязычные термины
    2. ссылки на википедию
    3. написать про классы RE, R, co-RE.
  3. Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
  4. fixed Вычислимые функции
    1. англоязычные термины
    2. ссылки на википедию
  5. Вычислимые числа
  6. взяли Диагональный метод
    1. объяснить, что такое универсальная функция неформально, и нафига она нужна.
    2. англоязычные термины
    3. внутренние ссылки
    4. нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например
    5. непонятно, где, собственно, возникает диагональ, надо это показать
    6. также статья называется как-то глупо, лучше назвать ее "Универсальная функция"
    7. см. замечания для главных нумераций
    8. категорию проставить
  7. Свойства перечислимых языков. Теорема Успенского-Райса
    1. классы языков в mathrm
    2. заголовки верхнего уровня в ==, а не =
    3. англоязычные термины
    4. категорию проставить
    5. ссылки на вики
  8. Главные нумерации
    1. см. "Диагональный метод"
    2. во-первых, тут какая-то муть
    3. во-вторых, тут копипаста из Шеня, кажется
    4. в третьих тут наполовину совпадает с "Диагональным методом". Короче их надо смержить и нормально написать.
    5. ну и надо написать, зачем вообще нужны эти главные нумерации
  9. Неотделимые множества
    1. английские источиники и термины
    2. нормально оформить уже существующий источник
    3. написать, зачем оно может пригодиться
  10. Иммунные и простые множества
    1. английские источиники и термины
    2. ссылки на вики
    3. а зачем оно нужно?
  11. взяли Теорема о рекурсии
    1. во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
    2. дать ссылки на английские источники и термины
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
  12. взяли Теорема о рекурсии
    Добавить примеры простых доказательств с использованием теоремы о рекурсии:
    1. Теоремы Успенского-Райса
    2. Невычислимости Колмогоровской сложности
    3. Невычислимости Busy beaver
    4. аналога I теоремы Геделя о неполноте
    5. аналога II теоремы Геделя о неполноте
    6. теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
  13. Busy beaver
  14. Машина Тьюринга
  15. Лямбда-исчисление
  16. Примитивно рекурсивные функции
    1. названия функций надо в \mathrm или \mathtt
    2. привести пример использования теоремы о примитивной рекурсивности
  17. Частично рекурсивные функции
    1. англоязычные термины
    2. Стековые машины, эквивалентность двухстековой машины МТ
  18. Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
  19. Линейный клеточный автомат, эквивалентность МТ
  20. Возможность порождения формальной грамматикой произвольного перечислимого языка
    1. внутренние ссылки
    2. категории
  21. взяли m-сводимость
    1. англоязычные термины
    2. ссылка на английскую википедию, у существующих источников ссылки на номер страницы
    3. написать еще про сведение по Тьюрингу и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюринга
  22. взяли Проблема соответствий Поста
    1. англоязычные термины
    2. ☐ англоязычные источники, в частности, википедия
    3. ☐ Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название
    4. ☐ "Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?
    5. ☐ "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо
    6. ☐ побольше интервики
    7. ☐ форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.
    8. ☐ Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.
    9. вообще в целов привести к более адекватному и понятному виду
  23. Однозначность КС-грамматики
  24. взяли Задача о замощении полимино
    1. замечания в обсуждении
  25. взяли Задача о выводе в полусистеме Туэ
    1. замечения в обсуждении
  26. взяли Неразрешимость исчисления предикатов первого порядка
    1. написать. Это очень просто на самом деле, если немного помнить матлогику
  27. !!! Неразрешимость проблемы существования решения диофантова уравления в целых числах
    1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
  28. Теорема Райса-Шапиро
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_5ому_терму&oldid=40002»