436
правок
Изменения
м
Napisal po-russky
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
__TOC__
== 1. Автоматы и регулярные языки ==
# '''взяли fixed !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
# [[Прямое произведение ДКА]]
## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
# '''fixed''' [[Недетерминированные конечные автоматы]]
## Английские термины
## Англоязычные источники (хотя бы википедия)
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
# [[Автоматы с eps-переходами. Eps-замыкание]]
# '''fixed''' [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
## Опять классы языков курсивом
## Внутренние ссылки на автоматные и регулярные языки
# [[Замкнутость регулярных языков относительно различных операций]]
#: см. 1
# ''fixed'' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
# [[Решение уравнений в регулярных выражениях]]
# '''взяли написан !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
#: фиг знает что это, но надо написать, видимо
# [[Эквивалентность состояний ДКА]]
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log 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 в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.
## вообще в целов привести к более адекватному и понятному виду
# [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
# '''взяли''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
## замечания в обсуждении
# '''взяли''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
## замечения в обсуждении
# '''взяли''' [[Неразрешимость исчисления предикатов первого порядка]]
## написать. Это очень просто на самом деле, если немного помнить матлогику
# '''!!!''' [[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
# [[Теорема Райса-Шапиро]]
