3622
правки
Изменения
м
→Опровержение контекстно-свободности языка
=== Регулярные языки и ДКА ===
<ol>
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] (0.5) </li><li> ''fixed'' [[Регулярные языки: два определения и их эквивалентность]] (0.5) </li># Англоязычные термины# Ссылки заменить на источники информации# Добавить См. также на ДКА<li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li># Оформить красиво табличку# Оформить подробней и красивей способы представления
<li> [[Прямое произведение ДКА]] </li>
</ol>
<li value="5"> [[Недетерминированные конечные автоматы]] </li>
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>
<li> [[Автоматы с eps-переходами. Eps-замыкание]] (1) </li># Англоязычные термины правильно# Добавить источники информации, см. также# Написать, где используется алгоритм eps-замыкания# Пофиксить знаки неравенств# Определение жирным# Многоточия на \ldots<li> ''взяли'' [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] (0.5) </li># Добавить ссылок# Поправить форматирование конспекта<li> '''взялиfixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
# Неплохо бы добавить ссылку на источник доказательства
# Исправить форматирование
</ol>
<ol>
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li># Оформить таблички покрасивей и marked на что-нибудь заменить# Сделать О-красивое<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li># Отформатировать комментарии и добавить их побольше# Оформить правильно декларации функций# Отформатировать по правилам<li> '''!!!fixed''' [[Алгоритм Бржозовского]] (5) </li>
# Добавить доказательство
</ol>
=== Свойства конечных автоматов ===
<ol>
<li value="14"> '''взялиfixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (56) </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>
=== Базовые понятия о грамматиках ===
<ol>
<li value="1"> '''взялиfixed''' [[Формальные грамматики]] (5) </li>
# Пояснить пример контекстно-зависимой грамматики
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
# Почистить обсуждения
<li> [[Иерархия Хомского формальных грамматик]] </li>
<li> ''взяли'' [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] (0.5) </li># Добавить источники информации, ссылок, интервики (на Иерархию)# Категория# Почистить обсуждения# Знаки неравенств
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
<li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li># Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки<li> '''!!!fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
# Пропущен - в КС-языках
# Точку в конкатенации лучше опустить
# Добавить примеры других грамматик
# Добавить ссылок, см. также
<li> '''!!!fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li>
# Добавить док-во леммы
# Отформатировать псевдокод
=== Нормальные формы КС-грамматик ===
<ol>
<li value="8"> '''!!!fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li>
# Англоязычных термины нормально оформить
# Добавить ссылок
# Категория
<li> [[Удаление длинных правил из грамматики]] </li>
<li> '''!!!''' [[Удаление eps-правил из грамматики]] (6) </li># Англоязычных термины нормально оформить # Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект# Грамматику G заменить на <tex> \Gamma </tex># Ссылку на НФХ перенести в источники информации# Написать, почему при удалении длинных правил асимптотика будет линейной# Грамматики криво оформлены# Пояснить использование очереди# Пропущены дефисы после КС местами# Категория<li> ''взяли'' [[Удаление цепных правил из грамматики]] (3) </li># Англоязычные термины оформить нормально# Провести в алгоритме аналогию с транзитивным замыканием# Грамматика криво криво оформлена# Расписать асимптотику алгоритма# Ссылку на НФХ перенести в источники информации# Категория<li> '''fixed''' [[Нормальная форма Хомского]] (5) </li># Англоязычные термины хорошо оформить# Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)# Константы взять в Tex# Пример грамматики криво оформлен# Ссылку на НФХ перенести в источники информации# Заменить знаки неравенств в Tex# Категория<li> '''!!!''' [[Устранение левой рекурсии]] (5) </li># Англоязычные термины оформить правильно# Кинуть интервики на методы нисходящего разбора (или см. также)# Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило# Отформатировать псевдокод# Знаки неравенств заменить# Источники информации нормально оформить# Категория<li> '''!!!fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
# написать, для чего она нужна
# Какая асимптотика алгоритма приведения?
# Отформатировать псевдокод
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
<li> ''fixed'' [[Нормальная форма Куроды]] (0.5) </li># Заменить везде G на \Gamma
</ol>
=== Алгоритмы разбора ===
<ol>
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] (1) </li># Добавить примеров разбора слов из различных грамматик (в том числе и разбор слова из примера)<li> '''!!!взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (710) </li>
# Расписать подробней и формальней
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
# И желательно расписать динамики через полуинтервалы, а не отрезки
# Красиво всё оформить
<li> '''!!!''' [[Алгоритм Эрли]] (7) </li># Отформатировать псевдокод# Описать понятно (гуглится ссылка, где алгоритм понятно расписан)# Доказательство плохо отформатировано# Оформить красиво источники информации<li> '''!!!fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
# Отформатировать псевдокод
# Грамматику G заменить на \Gamma
=== Опровержение контекстно-свободности языка ===
<ol>
<li value="20"> '''взялиfixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
# Источники нормально оформить
# Добавить см. также на варианты леммы
# Категория
<li> '''!!!fixed''' [[Лемма Огдена]] (710) </li>
# Источники информации добавить
# Добавить пример, удовлетворяющий не КС-языка, который удовлетворяет условию этой леммы# Категория<li> ''fixed'' [[Существенно неоднозначные языки]] (0.5) </li># Англоязычные термины оформить правильно# Ссылки из См. также перенести в источники информации
# Категория
<li> [[Существенно неоднозначные языки]]</li>
</ol>
=== МП-автоматы ===
<ol>
<li value="23"> ''fixed'' [[Автоматы с магазинной памятью]] (0.5) </li>
# Картинки увеличить
# Определение жирным
# Источники информации, См. также
# Категория
<li> ''fixed'' [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] (0.5) </li># Добавить источники информации# Категория<li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] (3) </li># Ссылки и литературу оформить правильно# Оформить доказательство красиво# Расписать подробней алгоритм# Категория<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]] (0.5) </li>
# В пример добавить язык автомата
# Англоязычные термины
# Категория
<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, до пуск допуск по пустому стеку]] (0.5) </li>
# Категория
# Палку заменить на \mid
# Источники информации
<li> '''!!!взяли''' [[Нормальная форма ДМП-автомата]] (10) </li>
# Написать!
<li> ''взяли'' [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] (2) </li># Как-то в кучу всё в теореме. Лучше разделить совпадение по пустому стеку и по состоянию для ДМП и сравнить отдельно МП и ДМП# Добавить источники информации# Категория# См. также
<li> [[ДМП-автоматы и неоднозначность]] </li>
</ol>
=== Разрешимые и перечислимые языки ===
# [[Разрешимые (рекурсивные) языки]]
# '''!!!'fixed'' [[Перечислимые языки]] (62)## Оформить правильно англоязычные термины## Поправить чуть определение полуразрешимого Добавить содержательный пример коперечислимого языка## Отформатировать псевдокоды## Оформить правильно в обе стороны доказательство теоремы## Заменить источники на источники информации## Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков# ''взялиfixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (12.5)## Чуть-чуть код форматнутьУбрать лишние знаки препинания из списков в теоремах
## Заменить литературу на источники информации
# ''fixed'' # Категории## Отформатировать по правилам# [[Вычислимые функции]] (0.5)## Заменить источники на источники информации## Англоязычные термины# ''взялиfixed'' [[Вычислимые числа]] (12)
## Правильно оформить англоязычные термины
## Пояснить a(eps) в определении
## Ссылки заменить на источники информации
## Увеличить дроби
# # Пояснить подробней мутные места# ''fixed'' [[Универсальная функция]] (1)
## Англоязычные термины правильно оформить
## Оформить правильно источники информации
## Пояснить нотацию про U(n, x) и U_n(x)
## Заголовки внутри конспекта поправить
# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1)
## Почему языком L_g(i,x) будет X? Как i связано с X?
## И вообще доказательство можно сделать чуть менее мутным :)
# [[Неотделимые множества]]
# '''!!!fixed''' [[Иммунные и простые множества]] (7)
## английские источиники и термины
## ссылки на вики
## Подробней расписать доказательства
## Ссылки на леммы внутри конспекта
# '''!!!fixed''' [[Теорема о рекурсии]] (8)
## дать ссылки на английские источники и термины
## Неформальное пояснение к теореме
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
# [[Квайны]]
# ''взяли'' [[Busy beaver]] (1)## Правильно оформить англоязычные термины## Отформатировать псевдокод## Нормально оформить см. также, источники информации и вывод из теоремы
# [[Колмогоровская сложность]]
=== Вычислительные формализмы ===
<ol>
<li value="14">'''взяли''' [[Машина Тьюринга]] (7) </li># Англоязычные термины# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)# Выделить машину Тьюринга жирным в определении# Алгоритмы примеров красиво оформить# Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)# Добавить в многоленточной, что эмулируется многодорожечной# Рассказать весёлую историю про тезис Чёрча-Тьюринга# Заменить ссылки на источники информации# Добавить категории
<li> [[Лямбда-исчисление]]</li>
<li> '''взялиfixed''' [[Примитивно рекурсивные функции]] (610) </li>
# названия функций надо в \mathrm
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
<li> '''взяли'fixed'' [[Частично рекурсивные функции]] (52) </li># См. замечания Замечание про взаимную рекурсию в обсуждениях# англоязычные термины# Дефис заменить на тире# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом# Заменить знаки неравенств # "неразрешимость проврк," {{---}} опечатки# Оформить правильно источники информации# Добавить категории <li> ''fixed'' [[Стековые машины, эквивалентность двухстековой машины МТ]] (0.5) </li># Интервики# Разбить доказательство на абзацы для читабельности# Добавить категории# Правильно оформить источники информации<li> ''fixed'' [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] (0.5) </li># Оформить правильно источники информации# Добавить категории <li> ''fixed'' [[Линейный клеточный автомат, эквивалентность МТ]] (0.5) </li># Англоязычные термины правильно оформить# Переменные взять в Tex# Добавить категории# Оформить правильно источники информации<li> ''fixed'' [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] (1) </li># внутренние ссылки# категории# Добавить см. также и источники информации
<li> [[Линейный ограниченный автомат]]</li>
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
=== Примеры неразрешимых задач ===
<ol>
<li value="24"> ''fixed'' [[m-сводимость]] (3) </li>
# Англоязычные термины правильно оформить
# Добавить примеры m-сведения задач
# Переменные и константы взять в Tex
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
<li> ''взяли'' [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] (0.5) </li># Источники информации# Добавить см. также# Англ. термины
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
<li> '''!!!fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
# Оформить правильно англоязычные термины
# Написать более подробное и понятное доказательство
# Добавить категории
# Добавить см. также
<li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] (5) </li># Англоязычные термины оформить правильно# Заменить дефисы на тире# Заменить прим. на более адекватный аналог# Заменить источники на источники информации# Добавить информацию по последнему замечанию из обсуждений# Добавить см. также<li> ''взяли'' [[Неразрешимость исчисления предикатов первого порядка]] (0.5) </li># Добавить см. также# Интервики на конспекты по математической логигике# Заменить ссылки на источники информации<li> '''!!!взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (110) </li>
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
<li> [[Игра «Жизнь»]] </li><li> [[Неразрешимость игры Braid]] </li><li> '''!!!fixed''' [[Теорема Райса-Шапиро]] (8) </li>
# Англоязычные термины
# Отформатировать псевдокоды
