Просмотр исходного текста страницы Участник:Dgerasimov/Тикеты по конспектам year2011

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