436
правок
Изменения
м
Napisal po-russky
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
__TOC__
== 1. Автоматы и регулярные языки ==
# '''fixed !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
## Добавить английские аналоги терминам
# '''fixed !!!''' [[Регулярные языки: два определения и их эквивалентность]]
## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!'''
## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
# [[Прямое произведение ДКА]]
## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
# ''fixed'' [[Недетерминированные конечные автоматы]]
## Английские термины
## Англоязычные источники (хотя бы википедия)
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
# [[Автоматы с eps-переходами. Eps-замыкание]]
# ''fixed'' [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
## Опять классы языков курсивом
## Внутренние ссылки на автоматные и регулярные языки
# [[Замкнутость регулярных языков относительно различных операций]]
#: см. 1
# ''fixed'' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
# '''взяли !!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
# [[Решение уравнений в регулярных выражениях]]
# '''написан !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
#: фиг знает что это, но надо написать, видимо
# [[Эквивалентность состояний ДКА]]
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
# '''!!!''' [[Контексты и синтаксические моноиды]]
## добавить английских терминов, ссылку на англоязычную вики
## доказательство последнего утверждения
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо, ну или хотя бы еще пару интересных примеров про синтактические моноиды каких-нибудь классов языков, например. == 2. Контекстно-свободные грамматики ==# '''взяли''' [[Формальные грамматики]]## примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание. ## заголовки здоровенные, они первого уровня (=) , а надо второго (==)## англоязычные термины## ссылки на английские источники# [[Иерархия Хомского формальных грамматик]]## добавить англоязычные термины## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.## интервики, ссылка на автоматные граммматики, например, которые есть на вики## на машину Тьюринга можно внутреннюю ссылку сделать# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]# [[Правоконтекстные грамматики, эквивалентность автоматам]]## Англоязычные термины## Источник бесполезен без конкретного указания, где искать## Внутреннюю ссылку на ДКА# '''взяли''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]## нормально оформить уже существующий источник## добавить англоязычные термины## интервики## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.# '''взяли''' [[Замкнутость КС-языков относительно различных операций]]## Че за --? Заменить на —## Half некрасивый, в \mathrm его## В конкатенации что-то немного муть написана## "Необходима картинка. " — запилить!## Про разворот — доказать## побольше внутренних ссылок, на МП-автомат там, например## проставить категории# '''взяли''' [[Удаление бесполезных символов из грамматики]]## запилить пример (уже есть)## англоязычных терминов где можно## если есть, ссылок на википедию.## вообще нет внутренних ссылок, надо бы добавить## "нетерминалы правой части являются порождающими" — правой части правила, наверное## первый пример сделай чуть более интеллектуальным, добавь что-нибудь типа "D -> aD", напримре (а то какой дурак будет вводить нетерминал без правил :) )## асимптотики какие-нибудь нужны## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также# '''взяли''' [[Удаление eps-правил из грамматики]]## запилить пример (уже есть)## англоязычных терминов где можно## если есть, ссылок на википедию.## почти нет внутренних ссылок, надо бы добавить## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)## для алгоритма поиска eps-порождающих точно можно асимптотику написать# '''взяли''' [[Удаление цепных правил из грамматики]]## как-то странно в примере, на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)## англоязычных терминов где можно## если есть, ссылок на википедию.## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотику# '''взяли''' [[Удаление длинных правил из грамматики]]## англоязычных терминов где можно## если есть, ссылок на википедию.## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотику# '''взяли''' [[Нормальная форма Хомского]]## "Несколько определений" — а определение одно, выкинуть вообще этот пункт и вынести определение НФХ в заголовок## если есть, ссылок на википедию.## такие кавычки в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычек# [[Устранение левой рекурсии]]# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]## написать, для чего она нужна## какая асимптотика алгоритма приведения?## ссылки на источники? --[[Участник:Dgerasimov|Дмитрий Герасимов]]# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]# [[Алгоритм Эрли]]# [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]# [[Лемма о разрастании для КС-грамматик]]# [[Лемма Огдена]]# ''взяли'' [[Существенно неоднозначные языки]]## добавить английские термины## добавить всякое интервики## добавить ссылок на русские и английские источники## упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.# [[Автоматы с магазинной памятью]]# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]# '''fixed''' [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.## Картинка. Что она означает?## Доказательства утверждений написаны непонятно.## Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.# [[Детерминированные автоматы с магазинной памятью]]# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]# '''!!!'''[[Нормальная форма ДМП-автомата]]## написать# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] == 3. Теория вычислимости ==# ''fixed'' [[Разрешимые (рекурсивные) языки]]## англоязычные термины## категории## ссылки на википедию, русскую и английскую# ''fixed'' [[Перечислимые языки]]## англоязычные термины## ссылки на википедию## написать про классы RE, R, co-RE. # [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]# ''fixed'' [[Вычислимые функции]]## англоязычные термины## ссылки на википедию# [[Вычислимые числа]]# '''взяли''' [[Диагональный метод]] ## объяснить, что такое универсальная функция неформально, и нафига она нужна. ## англоязычные термины ## внутренние ссылки## нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например ## непонятно, где, собственно, возникает диагональ, надо это показать ## также статья называется как-то глупо, лучше назвать ее "Универсальная функция" ## см. замечания для главных нумераций## категорию проставить# [[Свойства перечислимых языков. Теорема Успенского-Райса]]## классы языков в mathrm## заголовки верхнего уровня в ==, а не =## англоязычные термины## категорию проставить## ссылки на вики# [[Главные нумерации]]## см. "Диагональный метод"## во-первых, тут какая-то муть## во-вторых, тут копипаста из Шеня, кажется## в третьих тут наполовину совпадает с "Диагональным методом". Короче их надо смержить и нормально написать.## ну и надо написать, зачем вообще нужны эти главные нумерации# [[Неотделимые множества]]## английские источиники и термины ## нормально оформить уже существующий источник ## написать, зачем оно может пригодиться# [[Иммунные и простые множества]]## английские источиники и термины## ссылки на вики## а зачем оно нужно?# '''взяли''' [[Теорема о рекурсии]]## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские) ## дать ссылки на английские источники и термины ## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. ## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. # '''взяли''' [[Теорема о рекурсии]]#: Добавить примеры простых доказательств с использованием теоремы о рекурсии:## Теоремы Успенского-Райса ## Невычислимости Колмогоровской сложности ## Невычислимости Busy beaver ## аналога I теоремы Геделя о неполноте ## аналога II теоремы Геделя о неполноте ## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)# [[Busy beaver]]# [[Машина Тьюринга]]# [[Лямбда-исчисление]]# [[Примитивно рекурсивные функции]]## названия функций надо в \mathrm или \mathtt## привести пример использования теоремы о примитивной рекурсивности# [[Частично рекурсивные функции]]## англоязычные термины## [[Стековые машины, эквивалентность двухстековой машины МТ]]# [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]# [[Линейный клеточный автомат, эквивалентность МТ]]# [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]## внутренние ссылки## категории# '''взяли''' [[m-сводимость]]## англоязычные термины## ссылка на английскую википедию, у существующих источников ссылки на номер страницы## написать еще про сведение по Тьюрингу и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюринга# '''взяли''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]## англоязычные термины## {{tick}} англоязычные источники, в частности, википедия## {{tick}} Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название## {{tick}} "Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?## {{tick}} "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо## {{tick}} побольше интервики## {{tick}} форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.## {{tick}} Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.## вообще в целов привести к более адекватному и понятному виду# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]# '''взяли''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]## замечания в обсуждении# '''взяли''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]## замечения в обсуждении# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]## написать. Это очень просто на самом деле, если немного помнить матлогику# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.# [[Теорема Райса-Шапиро]]
