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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе __TOC__ == ...»)
 
м (→‎Опровержение контекстно-свободности языка)
 
(не показано 238 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
 
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
−
__TOC__
+
 
 
== 1. Автоматы и регулярные языки ==
 
== 1. Автоматы и регулярные языки ==
−
# '''fixed !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
+
=== Регулярные языки и ДКА ===
−
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
+
<ol>
−
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
+
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li>
−
## Добавить английские аналоги терминам
+
<li> [[Регулярные языки: два определения и их эквивалентность]] </li>
−
# '''fixed !!!''' [[Регулярные языки: два определения и их эквивалентность]]
+
<li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li>
−
## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!'''
+
# Оформить красиво табличку
−
## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
+
# Оформить подробней и красивей способы представления
−
## Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.
+
<li> [[Прямое произведение ДКА]] </li>
−
## <tex>\bigcap\limits_{R - nadreg}</tex>, вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.
+
</ol>
−
# [[Детерминированные конечные автоматы]]
+
 
−
## Английские термины
+
=== НКА ===
−
## Добавить ссылку на факт про эквивалентность автоматных и регулярных
+
<ol>
−
## Англоязычные источники (хотя бы википедия)
+
<li value="5"> [[Недетерминированные конечные автоматы]] </li>
−
# [[Прямое произведение ДКА]]
+
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>
−
## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
+
<li> [[Автоматы с eps-переходами. Eps-замыкание]] </li>
−
# ''fixed'' [[Недетерминированные конечные автоматы]]
+
<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] </li>
−
## Английские термины
+
<li> '''fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
−
## Англоязычные источники (хотя бы википедия)
+
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
−
## Написать, что класс языков совпадает с AUT, и почему (потому что алгоритм Томпсона)
+
# Неплохо бы добавить ссылку на источник доказательства
−
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
+
# Исправить форматирование
−
# [[Автоматы с eps-переходами. Eps-замыкание]]
+
</ol>
−
# ''fixed'' [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
+
 
−
## Опять классы языков курсивом
+
=== Минимизация ДКА ===
−
## Внутренние ссылки на автоматные и регулярные языки
+
<ol>
−
# [[Замкнутость регулярных языков относительно различных операций]]
+
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
−
#: см. 1
+
<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li>
−
# ''fixed'' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
+
# Оформить таблички покрасивей и marked на что-нибудь заменить
−
## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
+
# Сделать О-красивое
−
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
+
<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li>
−
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
+
# Отформатировать комментарии и добавить их побольше
−
# '''взяли !!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
+
# Оформить правильно декларации функций
−
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
+
# Отформатировать по правилам
−
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины  
+
<li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li>
−
# [[Решение уравнений в регулярных выражениях]]
+
# Добавить доказательство
−
# '''написан !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
+
</ol>
−
#: фиг знает что это, но надо написать, видимо
+
 
−
# [[Эквивалентность состояний ДКА]]
+
=== Свойства конечных автоматов ===
−
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
+
<ol>
−
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
+
<li value="14"> '''fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </li>
−
# '''!!!''' [[Контексты и синтаксические моноиды]]
+
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
−
## добавить английских терминов, ссылку на англоязычную вики
+
# Доказательство леммы о накачке в общем виде
−
## доказательство последнего утверждения
+
# Отформатировать по правилам
−
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо, ну или хотя бы еще пару интересных примеров про синтактические моноиды каких-нибудь классов языков, например.
+
<li> ''fixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>
 +
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
 +
<li> [[Решение уравнений в регулярных выражениях]] </li>
 +
<li> '''fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
 +
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
 +
<li> '''fixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
 +
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
 +
# Оформить нормально источники информации
 +
# Исправить багу с примечаниями
 +
# Англоязычные термины
 +
<li> ''fixed'' [[Контексты и синтаксические моноиды]] (1) </li>
 +
# Оформить примеры красиво
 +
# Оформить красиво двусторонние доказательства
 +
# Отформатировать по правилам
 +
</ol>
 +
 
 +
=== Другие автоматы ===
 +
<ol>
 +
<li value="20"> '''fixed''' [[Локальные автоматы]] (5) </li>
 +
# Где это нужно и зачем применяется
 +
<li> [[Двусторонний детерминированный конечный автомат]] </li>
 +
<li> [[Квантовые конечные автоматы]] </li>
 +
<li> '''fixed''' [[Автоматы Мура и Мили]] (5) </li>
 +
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
 +
</ol>
  
 
== 2. Контекстно-свободные грамматики ==
 
== 2. Контекстно-свободные грамматики ==
−
# '''взяли''' [[Формальные грамматики]]
+
=== Базовые понятия о грамматиках ===
−
## примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить
+
<ol>
−
## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание.  
+
<li value="1"> '''fixed''' [[Формальные грамматики]] (5) </li>
−
## заголовки здоровенные, они первого уровня (=) , а надо второго (==)
+
# Пояснить пример контекстно-зависимой грамматики
−
## англоязычные термины
+
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
−
## ссылки на английские источники
+
# Заменить многоточия на \ldots
−
# [[Иерархия Хомского формальных грамматик]]
+
# Оформить правильно источники инфрмации, добавить См. также
−
## добавить англоязычные термины
+
# Категория
−
## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
+
# Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
−
## интервики, ссылка на автоматные граммматики, например, которые есть на вики
+
# Примеры обозначений
−
## на машину Тьюринга можно внутреннюю ссылку сделать
+
# Вертикальную черту заменить на \mid
−
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
+
# В определениях скобки в Tex
−
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
+
# Интервики на рефлексивно-транзитивное замыкание
−
## Англоязычные термины
+
# Убрать ; из определения
−
## Источник бесполезен без конкретного указания, где искать
+
# Выводы в примерах оформить красивей
−
## Внутреннюю ссылку на ДКА
+
# Почистить обсуждения
−
# '''взяли''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
+
<li> [[Иерархия Хомского формальных грамматик]] </li>
−
## нормально оформить уже существующий источник
+
<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] </li>
−
## добавить англоязычные термины
+
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
−
## интервики
+
<li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li>
−
## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.
+
# Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
−
## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)
+
<li> '''fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
−
## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
+
# Пропущен - в КС-языках
−
# '''взяли''' [[Замкнутость КС-языков относительно различных операций]]
+
# Точку в конкатенации лучше опустить
−
## Че за --? Заменить на —
+
# Half некрасивый, c маленькой буквы его
−
## Half некрасивый, в \mathrm его
+
# Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
−
## В конкатенации что-то немного муть написана
+
# Добавить примеры других грамматик
−
## "Необходима картинка. " — запилить!
+
# Добавить ссылок, см. также
−
## Про разворот — доказать
+
<li> '''fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li>
−
## побольше внутренних ссылок, на МП-автомат там, например
+
# Добавить док-во леммы
−
## проставить категории
+
# Отформатировать псевдокод
−
# '''взяли''' [[Удаление бесполезных символов из грамматики]]
+
# Tex правильно оформить
−
## запилить пример (уже есть)
+
# Описание перед псевдокодом перенести
−
## англоязычных терминов где можно
+
# Картинки убого расположены
−
## если есть, ссылок на википедию.
+
# "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте
−
## вообще нет внутренних ссылок, надо бы добавить
+
# Расшифровать RTN (то же с MT)
−
## "нетерминалы правой части являются порождающими" — правой части правила, наверное
+
# Источники информации нормально оформить
−
## первый пример сделай чуть более интеллектуальным, добавь что-нибудь типа "D -> aD", напримре (а то какой дурак будет вводить нетерминал без правил :) )
+
# См. обсуждения
−
## асимптотики какие-нибудь нужны
+
</ol>
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
 
−
# '''взяли''' [[Удаление eps-правил из грамматики]]
+
=== Нормальные формы КС-грамматик ===
−
## запилить пример (уже есть)
+
<ol>
−
## англоязычных терминов где можно
+
<li value="8"> '''fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li>
−
## если есть, ссылок на википедию.
+
# Англоязычных термины нормально оформить
−
## почти нет внутренних ссылок, надо бы добавить
+
# Добавить ссылок
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
# Добавить интервики
−
## асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)
+
# Грамматики оформлены криво
−
## для алгоритма поиска eps-порождающих точно можно асимптотику написать
+
# Написать, что такое <tex> | \Gamma | </tex>
−
# '''взяли''' [[Удаление цепных правил из грамматики]]
+
# Написать, откуда берутся такие асимптотики, и как добавить очередь
−
## как-то странно в примере, на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)
+
# Аналогично про обход в глубину
−
## англоязычных терминов где можно
+
# Ссылку на НФХ перенести в источники информации
−
## если есть, ссылок на википедию.
+
# Алгоритмы оформить отдельным подзаголовком
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
# Категория
−
## асимптотику
+
<li> [[Удаление длинных правил из грамматики]] </li>
−
# '''взяли''' [[Удаление длинных правил из грамматики]]
+
<li> [[Удаление eps-правил из грамматики]] </li>
−
## англоязычных терминов где можно
+
<li> [[Удаление цепных правил из грамматики]] </li>
−
## если есть, ссылок на википедию.
+
<li> [[Нормальная форма Хомского]] </li>
−
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
+
<li> [[Устранение левой рекурсии]] </li>
−
## асимптотику
+
<li> '''fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
−
# '''взяли''' [[Нормальная форма Хомского]]
+
# написать, для чего она нужна
−
## "Несколько определений" — а определение одно, выкинуть вообще этот пункт и вынести определение НФХ в заголовок
+
# Какая асимптотика алгоритма приведения?
−
## если есть, ссылок на википедию.
+
# Добавить источники информации
−
## такие кавычки в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычек
+
# Добавить примеры
−
# [[Устранение левой рекурсии]]
+
# Англоязычные термины нормально оформить
−
# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]
+
# Отформатировать псевдокод
−
## написать, для чего она нужна
+
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
−
## какая асимптотика алгоритма приведения?
+
<li> [[Нормальная форма Куроды]] </li>
−
## ссылки на источники? --[[Участник:Dgerasimov|Дмитрий Герасимов]]
+
</ol>
−
# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
+
 
−
# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
+
=== Алгоритмы разбора ===
−
# [[Алгоритм Эрли]]
+
<ol>
−
# [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
+
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
−
# [[Лемма о разрастании для КС-грамматик]]
+
<li> '''взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (10) </li>
−
# [[Лемма Огдена]]
+
# Расписать подробней и формальней
−
# ''взяли'' [[Существенно неоднозначные языки]]
+
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
−
## добавить английские термины
+
# И желательно расписать динамики через полуинтервалы, а не отрезки
−
## добавить всякое интервики
+
# Красиво всё оформить
−
## добавить ссылок на русские и английские источники
+
<li> [[Алгоритм Эрли]] </li>
−
## упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.
+
<li> '''fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
−
# [[Автоматы с магазинной памятью]]
+
# Отформатировать псевдокод
−
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
+
# Грамматику G заменить на \Gamma
−
# '''fixed''' [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
+
# Перенести описание алгоритма перед псевдокодом
−
## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.
+
# Хотелось бы адекватные доказательства читать (см. обсуждения)
−
## Картинка. Что она означает?
+
</ol>
−
## Доказательства утверждений написаны непонятно.
+
 
−
## Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.
+
=== Опровержение контекстно-свободности языка ===
−
# [[Детерминированные автоматы с магазинной памятью]]
+
<ol>
−
# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
+
<li value="20"> '''fixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
−
# '''!!!'''[[Нормальная форма ДМП-автомата]]
+
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
−
## написать
+
# Источники нормально оформить
−
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
+
# Добавить см. также на варианты леммы
 +
# Категория
 +
<li> '''fixed''' [[Лемма Огдена]] (10) </li>
 +
# Источники информации добавить
 +
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы
 +
# Категория
 +
<li> [[Существенно неоднозначные языки]]</li>
 +
</ol>
 +
 
 +
=== МП-автоматы ===
 +
<ol>
 +
<li value="23"> ''fixed'' [[Автоматы с магазинной памятью]] (0.5) </li>
 +
# Картинки увеличить
 +
# Определение жирным
 +
# ; в определении заменить на ,
 +
# Англоязычные термины правильно оформить, убрать дублирования
 +
# Источники информации, См. также
 +
# Категория
 +
<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] </li>
 +
<li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] </li>
 +
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]] (0.5) </li>
 +
# В пример добавить язык автомата
 +
# Англоязычные термины
 +
# Категория
 +
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] (0.5) </li>
 +
# Категория
 +
# Палку заменить на \mid
 +
# Источники информации
 +
<li> '''взяли''' [[Нормальная форма ДМП-автомата]] (10) </li>
 +
# Написать!
 +
<li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] </li>
 +
<li> [[ДМП-автоматы и неоднозначность]] </li>
 +
</ol>
  
 
== 3. Теория вычислимости ==
 
== 3. Теория вычислимости ==
−
# ''fixed'' [[Разрешимые (рекурсивные) языки]]
+
=== Разрешимые и перечислимые языки ===
−
## англоязычные термины
+
# [[Разрешимые (рекурсивные) языки]]
−
## категории
+
# ''fixed'' [[Перечислимые языки]] (2)
−
## ссылки на википедию, русскую и английскую
+
## Добавить содержательный пример коперечислимого языка
−
# ''fixed'' [[Перечислимые языки]]
+
# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (2.5)
−
## англоязычные термины
+
## Убрать лишние знаки препинания из списков в теоремах
−
## ссылки на википедию
+
## Заменить литературу на источники информации
−
## написать про классы RE, R, co-RE.
+
## Категории
−
# [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
+
## Отформатировать по правилам
−
# ''fixed'' [[Вычислимые функции]]
+
# [[Вычислимые функции]]
−
## англоязычные термины
+
# ''fixed'' [[Вычислимые числа]] (2)
−
## ссылки на википедию
+
## Правильно оформить англоязычные термины
−
# [[Вычислимые числа]]
+
## Пояснить a(eps) в определении
−
# '''взяли''' [[Диагональный метод]]  
+
## Единообразно оформить множество рациональных чисел
−
## объяснить, что такое универсальная функция неформально, и нафига она нужна.
+
## Все переменные и константы занести в Tex
−
## англоязычные термины  
+
## Ссылки заменить на источники информации
−
## внутренние ссылки
+
## Увеличить дроби
−
## нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например
+
## Пояснить подробней мутные места
−
## непонятно, где, собственно, возникает диагональ, надо это показать
+
# ''fixed'' [[Универсальная функция]] (1)
−
## также статья называется как-то глупо, лучше назвать ее "Универсальная функция"
+
## Англоязычные термины правильно оформить
−
## см. замечания для главных нумераций
+
## Оформить правильно источники информации
−
## категорию проставить
+
## Заменить дефисы на тире
−
# [[Свойства перечислимых языков. Теорема Успенского-Райса]]
+
## Пояснить нотацию про U(n, x) и U_n(x)
−
## классы языков в mathrm
+
## Заголовки внутри конспекта поправить
−
## заголовки верхнего уровня в ==, а не =
+
# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1)
−
## англоязычные термины
+
## Почему языком L_g(i,x) будет X? Как i связано с X?
−
## категорию проставить
+
## И вообще доказательство можно сделать чуть менее мутным :)
−
## ссылки на вики
 
−
# [[Главные нумерации]]
 
−
## см. "Диагональный метод"
 
−
## во-первых, тут какая-то муть
 
−
## во-вторых, тут копипаста из Шеня, кажется
 
−
## в третьих тут наполовину совпадает с "Диагональным методом". Короче их надо смержить и нормально написать.
 
−
## ну и надо написать, зачем вообще нужны эти главные нумерации
 
 
# [[Неотделимые множества]]
 
# [[Неотделимые множества]]
−
## английские источиники и термины
+
# '''fixed''' [[Иммунные и простые множества]] (7)
−
## нормально оформить уже существующий источник
 
−
## написать, зачем оно может пригодиться
 
−
# [[Иммунные и простые множества]]
 
 
## английские источиники и термины
 
## английские источиники и термины
 
## ссылки на вики
 
## ссылки на вики
 
## а зачем оно нужно?
 
## а зачем оно нужно?
−
# '''взяли''' [[Теорема о рекурсии]]
+
## Интервики
−
## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)  
+
## Добавить категории
 +
## Подробней расписать доказательства
 +
## Ссылки на леммы внутри конспекта
 +
# '''fixed''' [[Теорема о рекурсии]] (8)
 
## дать ссылки на английские источники и термины  
 
## дать ссылки на английские источники и термины  
−
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.  
+
## Неформальное пояснение к теореме
 +
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
 
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.  
−
# '''взяли''' [[Теорема о рекурсии]]
+
# [[Квайны]]
−
#: Добавить примеры простых доказательств с использованием теоремы о рекурсии:
 
−
## Теоремы Успенского-Райса
 
−
## Невычислимости Колмогоровской сложности
 
−
## Невычислимости Busy beaver
 
−
## аналога I теоремы Геделя о неполноте
 
−
## аналога II теоремы Геделя о неполноте
 
−
## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
 
 
# [[Busy beaver]]
 
# [[Busy beaver]]
−
# [[Машина Тьюринга]]
+
# [[Колмогоровская сложность]]
−
# [[Лямбда-исчисление]]
+
 
−
# [[Примитивно рекурсивные функции]]
+
=== Вычислительные формализмы ===
−
## названия функций надо в \mathrm или \mathtt
+
<ol>
−
## привести пример использования теоремы о примитивной рекурсивности
+
<li value="14">[[Машина Тьюринга]] </li>
−
# [[Частично рекурсивные функции]]
+
<li> [[Лямбда-исчисление]]</li>
−
## англоязычные термины
+
<li> '''fixed''' [[Примитивно рекурсивные функции]] (10) </li>
−
## [[Стековые машины, эквивалентность двухстековой машины МТ]]
+
# названия функций надо в \mathrm
−
# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
+
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
−
# [[Линейный клеточный автомат, эквивалентность МТ]]
+
<li> ''fixed'' [[Частично рекурсивные функции]] (2) </li>
−
# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
+
# Замечание про взаимную рекурсию в обсуждениях
−
## внутренние ссылки
+
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
−
## категории
+
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>
−
# '''взяли''' [[m-сводимость]]
+
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>
−
## англоязычные термины
+
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>
−
## ссылка на английскую википедию, у существующих источников ссылки на номер страницы
+
<li> [[Линейный ограниченный автомат]]</li>
−
## написать еще про сведение по Тьюрингу и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюринга
+
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
−
# '''взяли''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
+
</ol>
−
## англоязычные термины
+
 
−
## {{tick}} англоязычные источники, в частности, википедия
+
=== Примеры неразрешимых задач ===
−
## {{tick}} Выполним m-сведение множества пар из машины Тьюринга (МТ)  и строки w , где M(w) не зависает — у этого множества есть название
+
<ol>
−
## {{tick}} "Договоримся, что состояния  в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?
+
<li value="24"> ''fixed'' [[m-сводимость]] (3) </li>
−
## {{tick}} "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо
+
# Англоязычные термины правильно оформить
−
## {{tick}} побольше интервики
+
# Добавить примеры m-сведения задач
−
## {{tick}} форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.
+
# Заменить знаки неравенств
−
## {{tick}} Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.
+
# Добавить категории
−
## вообще в целов привести к более адекватному и понятному виду
+
# Ссылку на ПСП оформить правильно
−
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
+
# Переменные и константы взять в Tex
−
# '''взяли''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
+
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
−
## замечания в обсуждении
+
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
−
# '''взяли''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
+
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
−
## замечения в обсуждении
+
<li> '''fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
−
# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]
+
# Оформить правильно англоязычные термины
−
## написать. Это очень просто на самом деле, если немного помнить матлогику
+
# Написать более подробное и понятное доказательство
−
# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
+
# Заменить ссылки на источники информации
−
## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
+
# Добавить категории
−
# [[Теорема Райса-Шапиро]]
+
# Добавить см. также
 +
<li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li>
 +
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>
 +
<li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>
 +
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
 +
<li> [[Игра «Жизнь»]] </li>
 +
<li> [[Неразрешимость игры Braid]] </li>
 +
<li> '''fixed''' [[Теорема Райса-Шапиро]] (8) </li>
 +
# Англоязычные термины
 +
# Отформатировать псевдокоды
 +
# Дать более формальное и понятное определение образца
 +
# Разбить доказательство на две части, чтобы это было видно
 +
# Написать строгую формулировку теоремы
 +
# "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие
 +
# Лучше явно написать разрешитель для K
 +
# "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
 +
# Добавить категории, см. также
 +
# Заменить литературу на источники информации
 +
</ol>

Текущая версия на 20:16, 18 января 2017

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

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

Регулярные языки и ДКА

  1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
  2. Регулярные языки: два определения и их эквивалентность
  3. fixed Детерминированные конечные автоматы (2)
    1. Оформить красиво табличку
    2. Оформить подробней и красивей способы представления
  4. Прямое произведение ДКА

НКА

  1. Недетерминированные конечные автоматы
  2. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  3. Автоматы с eps-переходами. Eps-замыкание
  4. Теорема Клини (совпадение классов автоматных и регулярных языков)
  5. fixed Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) (5)
    1. Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
    2. Неплохо бы добавить ссылку на источник доказательства
    3. Исправить форматирование

Минимизация ДКА

  1. Эквивалентность состояний ДКА
  2. fixed Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний (2)
    1. Оформить таблички покрасивей и marked на что-нибудь заменить
    2. Сделать О-красивое
  3. fixed Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) (2.5)
    1. Отформатировать комментарии и добавить их побольше
    2. Оформить правильно декларации функций
    3. Отформатировать по правилам
  4. fixed Алгоритм Бржозовского (5)
    1. Добавить доказательство

Свойства конечных автоматов

  1. fixed Доказательство нерегулярности языков: лемма о разрастании (6)
    1. Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
    2. Доказательство леммы о накачке в общем виде
    3. Отформатировать по правилам
  2. fixed Интерпретация булевых формул с кванторами как игр для двух игроков (1)
    • Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
  3. Решение уравнений в регулярных выражениях
  4. fixed Замкнутость регулярных языков относительно различных операций (6)
    1. Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
  5. fixed Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов) (5)
    1. Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
    2. Оформить нормально источники информации
    3. Исправить багу с примечаниями
    4. Англоязычные термины
  6. fixed Контексты и синтаксические моноиды (1)
    1. Оформить примеры красиво
    2. Оформить красиво двусторонние доказательства
    3. Отформатировать по правилам

Другие автоматы

  1. fixed Локальные автоматы (5)
    1. Где это нужно и зачем применяется
  2. Двусторонний детерминированный конечный автомат
  3. Квантовые конечные автоматы
  4. fixed Автоматы Мура и Мили (5)
    1. Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)

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

Базовые понятия о грамматиках

  1. fixed Формальные грамматики (5)
    1. Пояснить пример контекстно-зависимой грамматики
    2. Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
    3. Заменить многоточия на \ldots
    4. Оформить правильно источники инфрмации, добавить См. также
    5. Категория
    6. Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
    7. Примеры обозначений
    8. Вертикальную черту заменить на \mid
    9. В определениях скобки в Tex
    10. Интервики на рефлексивно-транзитивное замыкание
    11. Убрать ; из определения
    12. Выводы в примерах оформить красивей
    13. Почистить обсуждения
  2. Иерархия Хомского формальных грамматик
  3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
  4. Правоконтекстные грамматики, эквивалентность автоматам
  5. fixed Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора (1)
    1. Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
  6. fixed Замкнутость КС-языков относительно различных операций (5)
    1. Пропущен - в КС-языках
    2. Точку в конкатенации лучше опустить
    3. Half некрасивый, c маленькой буквы его
    4. Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
    5. Добавить примеры других грамматик
    6. Добавить ссылок, см. также
  7. fixed Регулярная аппроксимация КС-языков (7)
    1. Добавить док-во леммы
    2. Отформатировать псевдокод
    3. Tex правильно оформить
    4. Описание перед псевдокодом перенести
    5. Картинки убого расположены
    6. "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
    7. Расшифровать RTN (то же с MT)
    8. Источники информации нормально оформить
    9. См. обсуждения

Нормальные формы КС-грамматик

  1. fixed Удаление бесполезных символов из грамматики (6)
    1. Англоязычных термины нормально оформить
    2. Добавить ссылок
    3. Добавить интервики
    4. Грамматики оформлены криво
    5. Написать, что такое [math] | \Gamma | [/math]
    6. Написать, откуда берутся такие асимптотики, и как добавить очередь
    7. Аналогично про обход в глубину
    8. Ссылку на НФХ перенести в источники информации
    9. Алгоритмы оформить отдельным подзаголовком
    10. Категория
  2. Удаление длинных правил из грамматики
  3. Удаление eps-правил из грамматики
  4. Удаление цепных правил из грамматики
  5. Нормальная форма Хомского
  6. Устранение левой рекурсии
  7. fixed Приведение грамматики к ослабленной нормальной форме Грейбах (8)
    1. написать, для чего она нужна
    2. Какая асимптотика алгоритма приведения?
    3. Добавить источники информации
    4. Добавить примеры
    5. Англоязычные термины нормально оформить
    6. Отформатировать псевдокод
    7. Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
  8. Нормальная форма Куроды

Алгоритмы разбора

  1. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
  2. взяли Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики (10)
    1. Расписать подробней и формальней
    2. А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
    3. И желательно расписать динамики через полуинтервалы, а не отрезки
    4. Красиво всё оформить
  3. Алгоритм Эрли
  4. fixed Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики (5)
    1. Отформатировать псевдокод
    2. Грамматику G заменить на \Gamma
    3. Перенести описание алгоритма перед псевдокодом
    4. Хотелось бы адекватные доказательства читать (см. обсуждения)

Опровержение контекстно-свободности языка

  1. fixed Лемма о разрастании для КС-грамматик (6)
    1. Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
    2. Источники нормально оформить
    3. Добавить см. также на варианты леммы
    4. Категория
  2. fixed Лемма Огдена (10)
    1. Источники информации добавить
    2. Добавить пример не КС-языка, который удовлетворяет условию этой леммы
    3. Категория
  3. Существенно неоднозначные языки

МП-автоматы

  1. fixed Автоматы с магазинной памятью (0.5)
    1. Картинки увеличить
    2. Определение жирным
    3.  ; в определении заменить на ,
    4. Англоязычные термины правильно оформить, убрать дублирования
    5. Источники информации, См. также
    6. Категория
  2. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  3. Совпадение множества языков МП-автоматов и контекстно-свободных языков
  4. fixed Детерминированные автоматы с магазинной памятью (0.5)
    1. В пример добавить язык автомата
    2. Англоязычные термины
    3. Категория
  5. fixed Детерминированные автоматы с магазинной памятью, допуск по пустому стеку (0.5)
    1. Категория
    2. Палку заменить на \mid
    3. Источники информации
  6. взяли Нормальная форма ДМП-автомата (10)
    1. Написать!
  7. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
  8. ДМП-автоматы и неоднозначность

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

Разрешимые и перечислимые языки

  1. Разрешимые (рекурсивные) языки
  2. fixed Перечислимые языки (2)
    1. Добавить содержательный пример коперечислимого языка
  3. fixed Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций (2.5)
    1. Убрать лишние знаки препинания из списков в теоремах
    2. Заменить литературу на источники информации
    3. Категории
    4. Отформатировать по правилам
  4. Вычислимые функции
  5. fixed Вычислимые числа (2)
    1. Правильно оформить англоязычные термины
    2. Пояснить a(eps) в определении
    3. Единообразно оформить множество рациональных чисел
    4. Все переменные и константы занести в Tex
    5. Ссылки заменить на источники информации
    6. Увеличить дроби
    7. Пояснить подробней мутные места
  6. fixed Универсальная функция (1)
    1. Англоязычные термины правильно оформить
    2. Оформить правильно источники информации
    3. Заменить дефисы на тире
    4. Пояснить нотацию про U(n, x) и U_n(x)
    5. Заголовки внутри конспекта поправить
  7. fixed Свойства перечислимых языков. Теорема Успенского-Райса (1)
    1. Почему языком L_g(i,x) будет X? Как i связано с X?
    2. И вообще доказательство можно сделать чуть менее мутным :)
  8. Неотделимые множества
  9. fixed Иммунные и простые множества (7)
    1. английские источиники и термины
    2. ссылки на вики
    3. а зачем оно нужно?
    4. Интервики
    5. Добавить категории
    6. Подробней расписать доказательства
    7. Ссылки на леммы внутри конспекта
  10. fixed Теорема о рекурсии (8)
    1. дать ссылки на английские источники и термины
    2. Неформальное пояснение к теореме
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
  11. Квайны
  12. Busy beaver
  13. Колмогоровская сложность

Вычислительные формализмы

  1. Машина Тьюринга
  2. Лямбда-исчисление
  3. fixed Примитивно рекурсивные функции (10)
    1. названия функций надо в \mathrm
    2. Помёрджить с конспектом математической логики Рекурсивные функции, представимость в формальной арифметике
  4. fixed Частично рекурсивные функции (2)
    1. Замечание про взаимную рекурсию в обсуждениях
  5. Стековые машины, эквивалентность двухстековой машины МТ
  6. Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
  7. Линейный клеточный автомат, эквивалентность МТ
  8. Возможность порождения формальной грамматикой произвольного перечислимого языка
  9. Линейный ограниченный автомат
  10. Сверхтьюринговые вычисления (гипервычисления)

Примеры неразрешимых задач

  1. fixed m-сводимость (3)
    1. Англоязычные термины правильно оформить
    2. Добавить примеры m-сведения задач
    3. Заменить знаки неравенств
    4. Добавить категории
    5. Ссылку на ПСП оформить правильно
    6. Переменные и константы взять в Tex
  2. Проблема соответствий Поста
  3. Однозначность КС-грамматики
  4. Неразрешимость задачи об эквивалентности КС-грамматик
  5. fixed Задача о замощении полимино (6)
    1. Оформить правильно англоязычные термины
    2. Написать более подробное и понятное доказательство
    3. Заменить ссылки на источники информации
    4. Добавить категории
    5. Добавить см. также
  6. Задача о выводе в полусистеме Туэ
  7. Неразрешимость исчисления предикатов первого порядка
  8. взяли Неразрешимость проблемы существования решения диофантова уравления в целых числах (10)
    1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
  9. Игра «Жизнь»
  10. Неразрешимость игры Braid
  11. fixed Теорема Райса-Шапиро (8)
    1. Англоязычные термины
    2. Отформатировать псевдокоды
    3. Дать более формальное и понятное определение образца
    4. Разбить доказательство на две части, чтобы это было видно
    5. Написать строгую формулировку теоремы
    6. "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
    7. Лучше явно написать разрешитель для K
    8. "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
    9. Добавить категории, см. также
    10. Заменить литературу на источники информации
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_5ому_терму&oldid=60030»