Участник:Dgerasimov/Тикеты по конспектам year2011

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

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

1. взяли !!! Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
   1. Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их отсюда, оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
   2. В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
   3. Добавить английские аналоги терминам
2. fixed !!! Регулярные языки: два определения и их эквивалентность
   1. Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. Короче, везде надо использовать для классов языков \mathrm!
   2. Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
   3. Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.
   4. [math]\bigcap\limits_{R - nadreg}[/math], вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.
3. Детерминированные конечные автоматы
   1. Английские термины
   2. Добавить ссылку на факт про эквивалентность автоматных и регулярных
   3. Англоязычные источники (хотя бы википедия)
4. Прямое произведение ДКА
   1. Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
5. fixed Недетерминированные конечные автоматы
   1. Английские термины
   2. Англоязычные источники (хотя бы википедия)
   3. Написать, что класс языков совпадает с AUT, и почему (потому что алгоритм Томпсона)
6. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
7. Автоматы с eps-переходами. Eps-замыкание
8. fixed Теорема Клини (совпадение классов автоматных и регулярных языков)
   1. Опять классы языков курсивом
   2. Внутренние ссылки на автоматные и регулярные языки
9. Замкнутость регулярных языков относительно различных операций

   см. 1

10. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
    1. [math]paths[/math] выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
11. Интерпретация булевых формул с кванторами как игр для двух игроков

    вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)

12. взяли !!! Доказательство нерегулярности языков: лемма о разрастании
    1. пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
    2. добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
13. Решение уравнений в регулярных выражениях
14. взяли !!! Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

    фиг знает что это, но надо написать, видимо

15. Эквивалентность состояний ДКА
16. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
17. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
18. взяли !!! Контексты и синтаксические моноиды
    1. добавить английских терминов
    2. доказательство последнего утверждения
    3. вообще написать что-нибудь еще бы, типа зачем оно вообще надо.

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

1. взяли Формальные грамматики
   1. примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить
   2. определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание.
   3. заголовки здоровенные, они первого уровня (=) , а надо второго (==)
   4. англоязычные термины
   5. ссылки на английские источники
2. Иерархия Хомского формальных грамматик
   1. добавить англоязычные термины
   2. добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
   3. интервики, ссылка на автоматные граммматики, например, которые есть на вики
   4. на машину Тьюринга можно внутреннюю ссылку сделать
3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
4. Правоконтекстные грамматики, эквивалентность автоматам
   1. Англоязычные термины
   2. Источник бесполезен без конкретного указания, где искать
   3. Внутреннюю ссылку на ДКА
5. взяли Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
   1. нормально оформить уже существующий источник
   2. добавить англоязычные термины
   3. интервики
   4. Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.
   5. а еще тут стрелки одинаковые и в правилах (надо [math]\to[/math]) и в выводе (надо [math]\Rightarrow[/math])
   6. пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
6. взяли Замкнутость КС-языков относительно различных операций
   1. Че за --? Заменить на —
   2. Half некрасивый, в \mathrm его
   3. В конкатенации что-то немного муть написана
   4. "Необходима картинка. " — запилить!
   5. Про разворот — доказать
   6. побольше внутренних ссылок, на МП-автомат там, например
   7. проставить категории
7. взяли Удаление бесполезных символов из грамматики
   1. запилить пример (уже есть)
   2. англоязычных терминов где можно
   3. если есть, ссылок на википедию.
   4. вообще нет внутренних ссылок, надо бы добавить
   5. "нетерминалы правой части являются порождающими" — правой части правила, наверное
   6. первый пример сделай чуть более интеллектуальным, добавь что-нибудь типа "D -> aD", напримре (а то какой дурак будет вводить нетерминал без правил :) )
   7. асимптотики какие-нибудь нужны
   8. ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
8. взяли Удаление eps-правил из грамматики
   1. запилить пример (уже есть)
   2. англоязычных терминов где можно
   3. если есть, ссылок на википедию.
   4. почти нет внутренних ссылок, надо бы добавить
   5. ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
   6. асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)
   7. для алгоритма поиска eps-порождающих точно можно асимптотику написать
9. взяли Удаление цепных правил из грамматики
   1. как-то странно в примере, на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)
   2. англоязычных терминов где можно
   3. если есть, ссылок на википедию.
   4. ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
   5. асимптотику
10. взяли Удаление длинных правил из грамматики
    1. англоязычных терминов где можно
    2. если есть, ссылок на википедию.
    3. ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
    4. асимптотику
11. взяли Нормальная форма Хомского
    1. "Несколько определений" — а определение одно, выкинуть вообще этот пункт и вынести определение НФХ в заголовок
    2. если есть, ссылок на википедию.
    3. такие кавычки в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычек
12. Устранение левой рекурсии
13. Приведение грамматики к ослабленной нормальной форме Грейбах
    1. написать, для чего она нужна
    2. какая асимптотика алгоритма приведения?
    3. ссылки на источники? --Дмитрий Герасимов
14. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
15. Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
16. Алгоритм Эрли
17. Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
18. Лемма о разрастании для КС-грамматик
19. Лемма Огдена
20. Существенно неоднозначные языки
    1. добавить английские термины
    2. добавить всякое интервики
    3. добавить ссылок на русские и английские источники
    4. упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.
21. Автоматы с магазинной памятью
22. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
23. fixedСовпадение множества языков МП-автоматов и контекстно-свободных языков
    1. Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.
    2. Картинка. Что она означает?
    3. Доказательства утверждений написаны непонятно.
    4. Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.
24. Детерминированные автоматы с магазинной памятью
25. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
26. !!!Нормальная форма ДМП-автомата
    1. написать
27. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами

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

1. Разрешимые (рекурсивные) языки
   1. англоязычные термины
   2. категории
   3. ссылки на википедию, русскую и английскую
2. Перечислимые языки
   1. англоязычные термины
   2. ссылки на википедию
   3. написать про классы RE, R, co-RE.
3. Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
4. Вычислимые функции
   1. англоязычные термины
   2. ссылки на википедию
5. Вычислимые числа
6. !!! Диагональный метод
   1. объяснить, что такое универсальная функция неформально, и нафига она нужна.
   2. англоязычные термины
   3. внутренние ссылки
   4. нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например
   5. непонятно, где, собственно, возникает диагональ, надо это показать
   6. также статья называется как-то глупо, лучше назвать ее "Универсальная функция"
   7. см. замечания для главных нумераций
   8. категорию проставить
7. Свойства перечислимых языков. Теорема Успенского-Райса
   1. классы языков в mathrm
   2. заголовки верхнего уровня в ==, а не =
   3. англоязычные термины
   4. категорию проставить
   5. ссылки на вики
8. Главные нумерации
   1. см. "Диагональный метод"
   2. во-первых, тут какая-то муть
   3. во-вторых, тут копипаста из Шеня, кажется
   4. в третьих тут наполовину совпадает с "Диагональным методом". Короче их надо смержить и нормально написать.
   5. ну и надо написать, зачем вообще нужны эти главные нумерации
9. Неотделимые множества
   1. английские источиники и термины
   2. нормально оформить уже существующий источник
   3. написать, зачем оно может пригодиться
10. Иммунные и простые множества
    1. английские источиники и термины
    2. ссылки на вики
    3. а зачем оно нужно?
11. !!! Теорема о рекурсии
    1. во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские)
    2. дать ссылки на английские источники и термины
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце.
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
12. !!! Теорема о рекурсии

    Добавить примеры простых доказательств с использованием теоремы о рекурсии:

    1. Теоремы Успенского-Райса
    2. Невычислимости Колмогоровской сложности
    3. Невычислимости Busy beaver
    4. аналога I теоремы Геделя о неполноте
    5. аналога II теоремы Геделя о неполноте
    6. теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)
13. Busy beaver

---

• Машина Тьюринга
• Лямбда-исчисление
• Примитивно рекурсивные функции
• Частично рекурсивные функции
• Стековые машины, эквивалентность двухстековой машины МТ
• Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
• Линейный клеточный автомат, эквивалентность МТ
• Возможность порождения формальной грамматикой произвольного перечислимого языка

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

• m-сводимость
• Проблема соответствий Поста
• Однозначность КС-грамматики
• Задача о замощении полимино
• Задача о выводе в полусистеме Туэ
• Неразрешимость исчисления предикатов первого порядка
• Неразрешимость проблемы существования решения диофантова уравления в целых числах

• Теорема Райса-Шапиро