Участник:Shersh/Тикеты к 5ому терму — различия между версиями
Shersh (обсуждение | вклад) м (→Алгоритмы разбора) |
Shersh (обсуждение | вклад) м (→Опровержение контекстно-свободности языка) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 163: | Строка 163: | ||
# Добавить см. также на варианты леммы | # Добавить см. также на варианты леммы | ||
# Категория | # Категория | ||
− | <li> ''' | + | <li> '''fixed''' [[Лемма Огдена]] (10) </li> |
# Источники информации добавить | # Источники информации добавить | ||
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы | # Добавить пример не КС-языка, который удовлетворяет условию этой леммы |
Текущая версия на 20:16, 18 января 2017
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
1. Автоматы и регулярные языки
Регулярные языки и ДКА
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
- Регулярные языки: два определения и их эквивалентность
- fixed Детерминированные конечные автоматы (2)
- Оформить красиво табличку
- Оформить подробней и красивей способы представления
- Прямое произведение ДКА
НКА
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- fixed Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) (5)
- Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
- Неплохо бы добавить ссылку на источник доказательства
- Исправить форматирование
Минимизация ДКА
- Эквивалентность состояний ДКА
- fixed Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний (2)
- Оформить таблички покрасивей и marked на что-нибудь заменить
- Сделать О-красивое
- fixed Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) (2.5)
- Отформатировать комментарии и добавить их побольше
- Оформить правильно декларации функций
- Отформатировать по правилам
- fixed Алгоритм Бржозовского (5)
- Добавить доказательство
Свойства конечных автоматов
- fixed Доказательство нерегулярности языков: лемма о разрастании (6)
- Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
- Доказательство леммы о накачке в общем виде
- Отформатировать по правилам
- fixed Интерпретация булевых формул с кванторами как игр для двух игроков (1)
- Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
- Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
- Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
- Оформить нормально источники информации
- Исправить багу с примечаниями
- Англоязычные термины
- Оформить примеры красиво
- Оформить красиво двусторонние доказательства
- Отформатировать по правилам
Другие автоматы
- fixed Локальные автоматы (5)
- Где это нужно и зачем применяется
- Двусторонний детерминированный конечный автомат
- Квантовые конечные автоматы
- fixed Автоматы Мура и Мили (5)
- Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
2. Контекстно-свободные грамматики
Базовые понятия о грамматиках
- fixed Формальные грамматики (5)
- Пояснить пример контекстно-зависимой грамматики
- Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
- Заменить многоточия на \ldots
- Оформить правильно источники инфрмации, добавить См. также
- Категория
- Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
- Примеры обозначений
- Вертикальную черту заменить на \mid
- В определениях скобки в Tex
- Интервики на рефлексивно-транзитивное замыкание
- Убрать ; из определения
- Выводы в примерах оформить красивей
- Почистить обсуждения
- Иерархия Хомского формальных грамматик
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Правоконтекстные грамматики, эквивалентность автоматам
- fixed Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора (1)
- Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
- fixed Замкнутость КС-языков относительно различных операций (5)
- Пропущен - в КС-языках
- Точку в конкатенации лучше опустить
- Half некрасивый, c маленькой буквы его
- Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
- Добавить примеры других грамматик
- Добавить ссылок, см. также
- fixed Регулярная аппроксимация КС-языков (7)
- Добавить док-во леммы
- Отформатировать псевдокод
- Tex правильно оформить
- Описание перед псевдокодом перенести
- Картинки убого расположены
- "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
- Расшифровать RTN (то же с MT)
- Источники информации нормально оформить
- См. обсуждения
Нормальные формы КС-грамматик
- fixed Удаление бесполезных символов из грамматики (6)
- Англоязычных термины нормально оформить
- Добавить ссылок
- Добавить интервики
- Грамматики оформлены криво
- Написать, что такое
- Написать, откуда берутся такие асимптотики, и как добавить очередь
- Аналогично про обход в глубину
- Ссылку на НФХ перенести в источники информации
- Алгоритмы оформить отдельным подзаголовком
- Категория
- Удаление длинных правил из грамматики
- Удаление eps-правил из грамматики
- Удаление цепных правил из грамматики
- Нормальная форма Хомского
- Устранение левой рекурсии
- fixed Приведение грамматики к ослабленной нормальной форме Грейбах (8)
- написать, для чего она нужна
- Какая асимптотика алгоритма приведения?
- Добавить источники информации
- Добавить примеры
- Англоязычные термины нормально оформить
- Отформатировать псевдокод
- Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
- Нормальная форма Куроды
Алгоритмы разбора
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- взяли Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики (10)
- Расписать подробней и формальней
- А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
- И желательно расписать динамики через полуинтервалы, а не отрезки
- Красиво всё оформить
- Алгоритм Эрли
- fixed Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики (5)
- Отформатировать псевдокод
- Грамматику G заменить на \Gamma
- Перенести описание алгоритма перед псевдокодом
- Хотелось бы адекватные доказательства читать (см. обсуждения)
Опровержение контекстно-свободности языка
- fixed Лемма о разрастании для КС-грамматик (6)
- Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
- Источники нормально оформить
- Добавить см. также на варианты леммы
- Категория
- fixed Лемма Огдена (10)
- Источники информации добавить
- Добавить пример не КС-языка, который удовлетворяет условию этой леммы
- Категория
- Существенно неоднозначные языки
МП-автоматы
- fixed Автоматы с магазинной памятью (0.5)
- Картинки увеличить
- Определение жирным
- ; в определении заменить на ,
- Англоязычные термины правильно оформить, убрать дублирования
- Источники информации, См. также
- Категория
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Совпадение множества языков МП-автоматов и контекстно-свободных языков
- fixed Детерминированные автоматы с магазинной памятью (0.5)
- В пример добавить язык автомата
- Англоязычные термины
- Категория
- fixed Детерминированные автоматы с магазинной памятью, допуск по пустому стеку (0.5)
- Категория
- Палку заменить на \mid
- Источники информации
- взяли Нормальная форма ДМП-автомата (10)
- Написать!
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность
3. Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- fixed Перечислимые языки (2)
- Добавить содержательный пример коперечислимого языка
- fixed Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций (2.5)
- Убрать лишние знаки препинания из списков в теоремах
- Заменить литературу на источники информации
- Категории
- Отформатировать по правилам
- Вычислимые функции
- fixed Вычислимые числа (2)
- Правильно оформить англоязычные термины
- Пояснить a(eps) в определении
- Единообразно оформить множество рациональных чисел
- Все переменные и константы занести в Tex
- Ссылки заменить на источники информации
- Увеличить дроби
- Пояснить подробней мутные места
- fixed Универсальная функция (1)
- Англоязычные термины правильно оформить
- Оформить правильно источники информации
- Заменить дефисы на тире
- Пояснить нотацию про U(n, x) и U_n(x)
- Заголовки внутри конспекта поправить
- fixed Свойства перечислимых языков. Теорема Успенского-Райса (1)
- Почему языком L_g(i,x) будет X? Как i связано с X?
- И вообще доказательство можно сделать чуть менее мутным :)
- Неотделимые множества
- fixed Иммунные и простые множества (7)
- английские источиники и термины
- ссылки на вики
- а зачем оно нужно?
- Интервики
- Добавить категории
- Подробней расписать доказательства
- Ссылки на леммы внутри конспекта
- fixed Теорема о рекурсии (8)
- дать ссылки на английские источники и термины
- Неформальное пояснение к теореме
- у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
- следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
- Квайны
- Busy beaver
- Колмогоровская сложность
Вычислительные формализмы
- Машина Тьюринга
- Лямбда-исчисление
- fixed Примитивно рекурсивные функции (10)
- названия функций надо в \mathrm
- Помёрджить с конспектом математической логики Рекурсивные функции, представимость в формальной арифметике
- fixed Частично рекурсивные функции (2)
- Замечание про взаимную рекурсию в обсуждениях
- Стековые машины, эквивалентность двухстековой машины МТ
- Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
- Линейный клеточный автомат, эквивалентность МТ
- Возможность порождения формальной грамматикой произвольного перечислимого языка
- Линейный ограниченный автомат
- Сверхтьюринговые вычисления (гипервычисления)
Примеры неразрешимых задач
- fixed m-сводимость (3)
- Англоязычные термины правильно оформить
- Добавить примеры m-сведения задач
- Заменить знаки неравенств
- Добавить категории
- Ссылку на ПСП оформить правильно
- Переменные и константы взять в Tex
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик
- fixed Задача о замощении полимино (6)
- Оформить правильно англоязычные термины
- Написать более подробное и понятное доказательство
- Заменить ссылки на источники информации
- Добавить категории
- Добавить см. также
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- взяли Неразрешимость проблемы существования решения диофантова уравления в целых числах (10)
- написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
- Игра «Жизнь»
- Неразрешимость игры Braid
- fixed Теорема Райса-Шапиро (8)
- Англоязычные термины
- Отформатировать псевдокоды
- Дать более формальное и понятное определение образца
- Разбить доказательство на две части, чтобы это было видно
- Написать строгую формулировку теоремы
- "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
- Лучше явно написать разрешитель для K
- "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
- Добавить категории, см. также
- Заменить литературу на источники информации