Участник:Shersh/Тикеты к 5ому терму

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

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

Регулярные языки и ДКА

1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками (0.5)
2. fixed Регулярные языки: два определения и их эквивалентность (0.5)
1. Англоязычные термины
2. Ссылки заменить на источники информации
3. Добавить См. также на ДКА
3. Детерминированные конечные автоматы
4. Прямое произведение ДКА

НКА

5. Недетерминированные конечные автоматы
6. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
7. Автоматы с eps-переходами. Eps-замыкание (1)
1. Англоязычные термины правильно
2. Добавить источники информации, см. также
3. Написать, где используется алгоритм eps-замыкания
4. Пофиксить знаки неравенств
5. Определение жирным
6. Многоточия на \ldots
8. fixed Теорема Клини (совпадение классов автоматных и регулярных языков) (0.5)
1. Добавить ссылок
2. Поправить форматирование конспекта
9. взяли Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) (5)
1. Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
2. Неплохо бы добавить ссылку на источник доказательства

Минимизация ДКА

10. Эквивалентность состояний ДКА
11. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
12. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
13. !!! Алгоритм Бржозовского (5)
1. Добавить доказательство

Свойства конечных автоматов

14. взяли Доказательство нерегулярности языков: лемма о разрастании (5)
1. Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
2. Доказательство леммы о накачке в общем виде
15. Интерпретация булевых формул с кванторами как игр для двух игроков (1)

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

Решение уравнений в регулярных выражениях

!!! Замкнутость регулярных языков относительно различных операций (6)

1. Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности

!!! Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов) (5)

1. Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
2. Оформить нормально источники информации
3. Исправить багу с примечаниями
4. Англоязычные термины

Контексты и синтаксические моноиды

Другие автоматы

20. !!! Локальные автоматы (5)
1. Где это нужно и зачем применяется
21. Двусторонний детерминированный конечный автомат
22. Квантовые конечные автоматы
23. !!! Автоматы Мура и Мили (5)
1. Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)

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

Базовые понятия о грамматиках

1. взяли Формальные грамматики (5)
1. Пояснить пример контекстно-зависимой грамматики
2. Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
3. Заменить многоточия на \ldots
4. Оформить правильно источники инфрмации, добавить См. также
5. Категория
6. Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
7. Примеры обозначений
8. Вертикальную черту заменить на \mid
9. В определениях скобки в Tex
10. Интервики на рефлексивно-транзитивное замыкание
11. Убрать ; из определения
12. Выводы в примерах оформить красивей
13. Почистить обсуждения
2. Иерархия Хомского формальных грамматик
3. fixed Неукорачивающие и контекстно-зависимые грамматики, эквивалентность (0.5)
1. Добавить источники информации, ссылок, интервики (на Иерархию)
2. Категория
3. Почистить обсуждения
4. Знаки неравенств
4. Правоконтекстные грамматики, эквивалентность автоматам
5. Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
6. !!! Замкнутость КС-языков относительно различных операций (5)
1. Пропущен - в КС-языках
2. Точку в конкатенации лучше опустить
3. Half некрасивый, c маленькой буквы его
4. Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
5. Добавить примеры других грамматик
6. Добавить ссылок, см. также
7. !!! Регулярная аппроксимация КС-языков (7)
1. Добавить док-во леммы
2. Отформатировать псевдокод
3. Tex правильно оформить
4. Описание перед псевдокодом перенести
5. Картинки убого расположены
6. "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
7. Расшифровать RTN (то же с MT)
8. Источники информации нормально оформить
9. См. обсуждения

Нормальные формы КС-грамматик

8. !!! Удаление бесполезных символов из грамматики (6)
1. Англоязычных термины нормально оформить
2. Добавить ссылок
3. Добавить интервики
4. Грамматики оформлены криво
5. Написать, что такое [math] | \Gamma | [/math]
6. Написать, откуда берутся такие асимптотики, и как добавить очередь
7. Аналогично про обход в глубину
8. Ссылку на НФХ перенести в источники информации
9. Алгоритмы оформить отдельным подзаголовком
10. Категория
9. Удаление длинных правил из грамматики
10. !!! Удаление eps-правил из грамматики (6)
1. Англоязычных термины нормально оформить
2. Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже — реструктуризовать конспект
3. Грамматику G заменить на [math] \Gamma [/math]
4. Ссылку на НФХ перенести в источники информации
5. Написать, почему при удалении длинных правил асимптотика будет линейной
6. Грамматики криво оформлены
7. Пояснить использование очереди
8. Пропущены дефисы после КС местами
9. Категория
11. взяли Удаление цепных правил из грамматики (3)
1. Англоязычные термины оформить нормально
2. Провести в алгоритме аналогию с транзитивным замыканием
3. Грамматика криво криво оформлена
4. Расписать асимптотику алгоритма
5. Ссылку на НФХ перенести в источники информации
6. Категория
12. fixed Нормальная форма Хомского (5)
1. Англоязычные термины хорошо оформить
2. Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)
3. Константы взять в Tex
4. Пример грамматики криво оформлен
5. Ссылку на НФХ перенести в источники информации
6. Заменить знаки неравенств в Tex
7. Категория
13. fixed Устранение левой рекурсии (5)
1. Англоязычные термины оформить правильно
2. Кинуть интервики на методы нисходящего разбора (или см. также)
3. Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило
4. Отформатировать псевдокод
5. Знаки неравенств заменить
6. Источники информации нормально оформить
7. Категория
14. !!! Приведение грамматики к ослабленной нормальной форме Грейбах (8)
1. написать, для чего она нужна
2. Какая асимптотика алгоритма приведения?
3. Добавить источники информации
4. Добавить примеры
5. Англоязычные термины нормально оформить
6. Отформатировать псевдокод
7. Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
15. fixed Нормальная форма Куроды (0.5)
1. Заменить везде G на \Gamma

Алгоритмы разбора

16. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ (1)
1. Добавить примеров разбора слов из различных грамматик (в том числе и разбор слова из примера)
17. !!! Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики (7)
1. Расписать подробней и формальней
2. А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
3. И желательно расписать динамики через полуинтервалы, а не отрезки
4. Красиво всё оформить
18. взяли Алгоритм Эрли (7)
1. Отформатировать псевдокод
2. Описать понятно (гуглится ссылка, где алгоритм понятно расписан)
3. Доказательство плохо отформатировано
4. Оформить красиво источники информации
19. !!! Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики (5)
1. Отформатировать псевдокод
2. Грамматику G заменить на \Gamma
3. Перенести описание алгоритма перед псевдокодом
4. Хотелось бы адекватные доказательства читать (см. обсуждения)

Опровержение контекстно-свободности языка

20. взяли Лемма о разрастании для КС-грамматик (6)
1. Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
2. Источники нормально оформить
3. Добавить см. также на варианты леммы
4. Категория
21. взяли Лемма Огдена (7)
1. Источники информации добавить
2. Добавить пример не КС-языка, который удовлетворяет условию этой леммы
3. Категория
22. fixed Существенно неоднозначные языки (0.5)
1. Англоязычные термины оформить правильно
2. Ссылки из См. также перенести в источники информации
3. Категория

МП-автоматы

23. Автоматы с магазинной памятью (0.5)
1. Картинки увеличить
2. Определение жирным
3.  ; в определении заменить на ,
4. Англоязычные термины правильно оформить, убрать дублирования
5. Источники информации, См. также
6. Категория
24. fixed МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность (0.5)
1. Добавить источники информации
2. Категория
25. взяли Совпадение множества языков МП-автоматов и контекстно-свободных языков (3)
1. Ссылки и литературу оформить правильно
2. Оформить доказательство красиво
3. Расписать подробней алгоритм
4. Категория
26. Детерминированные автоматы с магазинной памятью (0.5)
1. В пример добавить язык автомата
2. Англоязычные термины
3. Категория
27. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку (0.5)
1. Категория
2. Палку заменить на \mid
3. Источники информации
28. !!! Нормальная форма ДМП-автомата (10)
1. Написать!
29. fixed Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами (2)
1. Как-то в кучу всё в теореме. Лучше разделить совпадение по пустому стеку и по состоянию для ДМП и сравнить отдельно МП и ДМП
2. Добавить источники информации
3. Категория
4. См. также
30. ДМП-автоматы и неоднозначность

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

Разрешимые и перечислимые языки

1. Разрешимые (рекурсивные) языки
2. !!! Перечислимые языки (6)
   1. Оформить правильно англоязычные термины
   2. Поправить чуть определение полуразрешимого языка
   3. Отформатировать псевдокоды
   4. Оформить правильно в обе стороны доказательство теоремы
   5. Заменить источники на источники информации
   6. Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков
3. взяли Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций (1)
   1. Чуть-чуть код форматнуть
   2. Заменить литературу на источники информации
4. fixed Вычислимые функции (0.5)
   1. Заменить источники на источники информации
   2. Англоязычные термины
5. взяли Вычислимые числа (1)
   1. Правильно оформить англоязычные термины
   2. Пояснить a(eps) в определении
   3. Единообразно оформить множество рациональных чисел
   4. Все переменные и константы занести в Tex
   5. Ссылки заменить на источники информации
   6. Увеличить дроби
6. Универсальная функция (1)
   1. Англоязычные термины правильно оформить
   2. Оформить правильно источники информации
   3. Заменить дефисы на тире
   4. Пояснить нотацию про U(n, x) и U_n(x)
   5. Заголовки внутри конспекта поправить
7. Свойства перечислимых языков. Теорема Успенского-Райса (1)
   1. Почему языком L_g(i,x) будет X? Как i связано с X?
   2. И вообще доказательство можно сделать чуть менее мутным :)
8. Неотделимые множества
9. !!! Иммунные и простые множества (7)
   1. английские источиники и термины
   2. ссылки на вики
   3. а зачем оно нужно?
   4. Интервики
   5. Добавить категории
   6. Подробней расписать доказательства
   7. Ссылки на леммы внутри конспекта
10. !!! Теорема о рекурсии (8)
    1. дать ссылки на английские источники и термины
    2. Неформальное пояснение к теореме
    3. у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
    4. следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
11. Квайны
12. fixed Busy beaver (1)
    1. Правильно оформить англоязычные термины
    2. Отформатировать псевдокод
    3. Нормально оформить см. также, источники информации и вывод из теоремы
13. Колмогоровская сложность

Вычислительные формализмы

14. fixed Машина Тьюринга (7)
1. Англоязычные термины
2. Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)
3. Выделить машину Тьюринга жирным в определении
4. Алгоритмы примеров красиво оформить
5. Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)
6. Добавить в многоленточной, что эмулируется многодорожечной
7. Рассказать весёлую историю про тезис Чёрча-Тьюринга
8. Заменить ссылки на источники информации
9. Добавить категории
15. Лямбда-исчисление
16. взяли Примитивно рекурсивные функции (6)
1. названия функций надо в \mathrm
2. Помёрджить с конспектом математической логики Рекурсивные функции, представимость в формальной арифметике
17. взяли Частично рекурсивные функции (5)
1. См. замечания в обсуждениях
2. англоязычные термины
3. Дефис заменить на тире
4. "функция g(x_1,\ldots,x_k) = минимальное y" — плохо, когда смешиваются формулы с текстом
5. Заменить знаки неравенств
6. "неразрешимость проврк," — опечатки
7. Оформить правильно источники информации
8. Добавить категории
18. fixed Стековые машины, эквивалентность двухстековой машины МТ (0.5)
1. Интервики
2. Разбить доказательство на абзацы для читабельности
3. Добавить категории
4. Правильно оформить источники информации
19. fixed Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ (0.5)
1. Оформить правильно источники информации
2. Добавить категории
20. fixed Линейный клеточный автомат, эквивалентность МТ (0.5)
1. Англоязычные термины правильно оформить
2. Переменные взять в Tex
3. Добавить категории
4. Оформить правильно источники информации
21. fixed Возможность порождения формальной грамматикой произвольного перечислимого языка (1)
1. внутренние ссылки
2. категории
3. Добавить см. также и источники информации
22. Линейный ограниченный автомат
23. Сверхтьюринговые вычисления (гипервычисления)

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

24. m-сводимость (3)
1. Англоязычные термины правильно оформить
2. Добавить примеры m-сведения задач
3. Заменить знаки неравенств
4. Добавить категории
5. Ссылку на ПСП оформить правильно
6. Переменные и константы взять в Tex
25. Проблема соответствий Поста
26. fixed Однозначность КС-грамматики (0.5)
1. Источники информации
2. Добавить см. также
3. Англ. термины
27. Неразрешимость задачи об эквивалентности КС-грамматик
28. !!! Задача о замощении полимино (6)
1. Оформить правильно англоязычные термины
2. Написать более подробное и понятное доказательство
3. Заменить ссылки на источники информации
4. Добавить категории
5. Добавить см. также
29. взяли Задача о выводе в полусистеме Туэ (5)
1. Англоязычные термины оформить правильно
2. Заменить дефисы на тире
3. Заменить прим. на более адекватный аналог
4. Заменить источники на источники информации
5. Добавить информацию по последнему замечанию из обсуждений
6. Добавить см. также
30. fixed Неразрешимость исчисления предикатов первого порядка (0.5)
1. Добавить см. также
2. Интервики на конспекты по математической логигике
3. Заменить ссылки на источники информации
31. !!! Неразрешимость проблемы существования решения диофантова уравления в целых числах (1)
1. написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
32. !!! Теорема Райса-Шапиро (8)
1. Англоязычные термины
2. Отформатировать псевдокоды
3. Дать более формальное и понятное определение образца
4. Разбить доказательство на две части, чтобы это было видно
5. Написать строгую формулировку теоремы
6. "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
7. Лучше явно написать разрешитель для K
8. "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
9. Добавить категории, см. также
10. Заменить литературу на источники информации