Участник:Shersh/Тикеты к 5ому терму — различия между версиями
Shersh (обсуждение | вклад) (→Примеры неразрешимых задач) |
Shersh (обсуждение | вклад) м (→Опровержение контекстно-свободности языка) |
||
| (не показаны 104 промежуточные версии этого же участника) | |||
| Строка 4: | Строка 4: | ||
=== Регулярные языки и ДКА === | === Регулярные языки и ДКА === | ||
<ol> | <ol> | ||
| − | <li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] | + | <li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li> |
| − | <li> | + | <li> [[Регулярные языки: два определения и их эквивалентность]] </li> |
| − | + | <li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li> | |
| − | + | # Оформить красиво табличку | |
| − | + | # Оформить подробней и красивей способы представления | |
| − | <li> [[Детерминированные конечные автоматы]] </li> | ||
<li> [[Прямое произведение ДКА]] </li> | <li> [[Прямое произведение ДКА]] </li> | ||
</ol> | </ol> | ||
| Строка 17: | Строка 16: | ||
<li value="5"> [[Недетерминированные конечные автоматы]] </li> | <li value="5"> [[Недетерминированные конечные автоматы]] </li> | ||
<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li> | <li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li> | ||
| − | <li> [[Автоматы с eps-переходами. Eps-замыкание]] | + | <li> [[Автоматы с eps-переходами. Eps-замыкание]] </li> |
| − | + | <li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] </li> | |
| − | + | <li> '''fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | <li> ''' | ||
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример) | # Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример) | ||
# Неплохо бы добавить ссылку на источник доказательства | # Неплохо бы добавить ссылку на источник доказательства | ||
| + | # Исправить форматирование | ||
</ol> | </ol> | ||
| Строка 35: | Строка 27: | ||
<ol> | <ol> | ||
<li value="10"> [[Эквивалентность состояний ДКА]] </li> | <li value="10"> [[Эквивалентность состояний ДКА]] </li> | ||
| − | <li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] </li> | + | <li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li> |
| − | <li> [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] </li> | + | # Оформить таблички покрасивей и marked на что-нибудь заменить |
| − | <li> ''' | + | # Сделать О-красивое |
| + | <li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li> | ||
| + | # Отформатировать комментарии и добавить их побольше | ||
| + | # Оформить правильно декларации функций | ||
| + | # Отформатировать по правилам | ||
| + | <li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li> | ||
# Добавить доказательство | # Добавить доказательство | ||
</ol> | </ol> | ||
| Строка 43: | Строка 40: | ||
=== Свойства конечных автоматов === | === Свойства конечных автоматов === | ||
<ol> | <ol> | ||
| − | <li value="14"> ''' | + | <li value="14"> '''fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </li> |
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии) | # Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии) | ||
# Доказательство леммы о накачке в общем виде | # Доказательство леммы о накачке в общем виде | ||
| − | <li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li> | + | # Отформатировать по правилам |
| + | <li> ''fixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li> | ||
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта | * Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта | ||
<li> [[Решение уравнений в регулярных выражениях]] </li> | <li> [[Решение уравнений в регулярных выражениях]] </li> | ||
| − | <li> ''' | + | <li> '''fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li> |
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности | # Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности | ||
| − | <li> ''' | + | <li> '''fixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li> |
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать) | # Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать) | ||
# Оформить нормально источники информации | # Оформить нормально источники информации | ||
# Исправить багу с примечаниями | # Исправить багу с примечаниями | ||
# Англоязычные термины | # Англоязычные термины | ||
| − | <li> [[Контексты и синтаксические моноиды]] </li> | + | <li> ''fixed'' [[Контексты и синтаксические моноиды]] (1) </li> |
| + | # Оформить примеры красиво | ||
| + | # Оформить красиво двусторонние доказательства | ||
| + | # Отформатировать по правилам | ||
</ol> | </ol> | ||
=== Другие автоматы === | === Другие автоматы === | ||
<ol> | <ol> | ||
| − | <li value="20"> ''' | + | <li value="20"> '''fixed''' [[Локальные автоматы]] (5) </li> |
# Где это нужно и зачем применяется | # Где это нужно и зачем применяется | ||
<li> [[Двусторонний детерминированный конечный автомат]] </li> | <li> [[Двусторонний детерминированный конечный автомат]] </li> | ||
<li> [[Квантовые конечные автоматы]] </li> | <li> [[Квантовые конечные автоматы]] </li> | ||
| − | <li> ''' | + | <li> '''fixed''' [[Автоматы Мура и Мили]] (5) </li> |
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору) | # Примеры интересных задач или применений на эти автоматы (для согласования написать куратору) | ||
</ol> | </ol> | ||
| Строка 72: | Строка 73: | ||
=== Базовые понятия о грамматиках === | === Базовые понятия о грамматиках === | ||
<ol> | <ol> | ||
| − | <li value="1"> ''' | + | <li value="1"> '''fixed''' [[Формальные грамматики]] (5) </li> |
# Пояснить пример контекстно-зависимой грамматики | # Пояснить пример контекстно-зависимой грамматики | ||
# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования) | # Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования) | ||
| Строка 87: | Строка 88: | ||
# Почистить обсуждения | # Почистить обсуждения | ||
<li> [[Иерархия Хомского формальных грамматик]] </li> | <li> [[Иерархия Хомского формальных грамматик]] </li> | ||
| − | <li> | + | <li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li> | <li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li> | ||
| − | <li> [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] </li> | + | <li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li> |
| − | <li> ''' | + | # Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки |
| + | <li> '''fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li> | ||
# Пропущен - в КС-языках | # Пропущен - в КС-языках | ||
# Точку в конкатенации лучше опустить | # Точку в конкатенации лучше опустить | ||
| Строка 101: | Строка 99: | ||
# Добавить примеры других грамматик | # Добавить примеры других грамматик | ||
# Добавить ссылок, см. также | # Добавить ссылок, см. также | ||
| − | <li> ''' | + | <li> '''fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li> |
# Добавить док-во леммы | # Добавить док-во леммы | ||
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
| Строка 115: | Строка 113: | ||
=== Нормальные формы КС-грамматик === | === Нормальные формы КС-грамматик === | ||
<ol> | <ol> | ||
| − | <li value="8"> ''' | + | <li value="8"> '''fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li> |
# Англоязычных термины нормально оформить | # Англоязычных термины нормально оформить | ||
# Добавить ссылок | # Добавить ссылок | ||
| Строка 127: | Строка 125: | ||
# Категория | # Категория | ||
<li> [[Удаление длинных правил из грамматики]] </li> | <li> [[Удаление длинных правил из грамматики]] </li> | ||
| − | <li> | + | <li> [[Удаление eps-правил из грамматики]] </li> |
| − | + | <li> [[Удаление цепных правил из грамматики]] </li> | |
| − | + | <li> [[Нормальная форма Хомского]] </li> | |
| − | + | <li> [[Устранение левой рекурсии]] </li> | |
| − | + | <li> '''fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> ''' | ||
# написать, для чего она нужна | # написать, для чего она нужна | ||
# Какая асимптотика алгоритма приведения? | # Какая асимптотика алгоритма приведения? | ||
| Строка 168: | Строка 137: | ||
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё) | # Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё) | ||
| − | <li> | + | <li> [[Нормальная форма Куроды]] </li> |
| − | |||
</ol> | </ol> | ||
=== Алгоритмы разбора === | === Алгоритмы разбора === | ||
<ol> | <ol> | ||
| − | <li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] | + | <li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li> |
| − | + | <li> '''взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (10) </li> | |
| − | <li> ''' | ||
# Расписать подробней и формальней | # Расписать подробней и формальней | ||
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать | # А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать | ||
# И желательно расписать динамики через полуинтервалы, а не отрезки | # И желательно расписать динамики через полуинтервалы, а не отрезки | ||
# Красиво всё оформить | # Красиво всё оформить | ||
| − | <li> | + | <li> [[Алгоритм Эрли]] </li> |
| − | + | <li> '''fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li> | |
| − | |||
| − | |||
| − | |||
| − | <li> ''' | ||
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
# Грамматику G заменить на \Gamma | # Грамматику G заменить на \Gamma | ||
| Строка 195: | Строка 158: | ||
=== Опровержение контекстно-свободности языка === | === Опровержение контекстно-свободности языка === | ||
<ol> | <ol> | ||
| − | <li value="20"> ''' | + | <li value="20"> '''fixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li> |
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена | # Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена | ||
# Источники нормально оформить | # Источники нормально оформить | ||
# Добавить см. также на варианты леммы | # Добавить см. также на варианты леммы | ||
# Категория | # Категория | ||
| − | <li> ''' | + | <li> '''fixed''' [[Лемма Огдена]] (10) </li> |
# Источники информации добавить | # Источники информации добавить | ||
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы | # Добавить пример не КС-языка, который удовлетворяет условию этой леммы | ||
# Категория | # Категория | ||
| − | <li> | + | <li> [[Существенно неоднозначные языки]]</li> |
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
=== МП-автоматы === | === МП-автоматы === | ||
<ol> | <ol> | ||
| − | <li value="23"> [[Автоматы с магазинной памятью]] (0.5) </li> | + | <li value="23"> ''fixed'' [[Автоматы с магазинной памятью]] (0.5) </li> |
# Картинки увеличить | # Картинки увеличить | ||
# Определение жирным | # Определение жирным | ||
| Строка 219: | Строка 179: | ||
# Источники информации, См. также | # Источники информации, См. также | ||
# Категория | # Категория | ||
| − | <li> | + | <li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] </li> |
| − | + | <li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] </li> | |
| − | + | <li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]] (0.5) </li> | |
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> [[Детерминированные автоматы с магазинной памятью]] (0.5) </li> | ||
# В пример добавить язык автомата | # В пример добавить язык автомата | ||
# Англоязычные термины | # Англоязычные термины | ||
# Категория | # Категория | ||
| − | <li> [[Детерминированные автоматы с магазинной памятью, | + | <li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] (0.5) </li> |
# Категория | # Категория | ||
# Палку заменить на \mid | # Палку заменить на \mid | ||
# Источники информации | # Источники информации | ||
| − | <li> ''' | + | <li> '''взяли''' [[Нормальная форма ДМП-автомата]] (10) </li> |
# Написать! | # Написать! | ||
| − | <li> | + | <li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[ДМП-автоматы и неоднозначность]] </li> | <li> [[ДМП-автоматы и неоднозначность]] </li> | ||
</ol> | </ol> | ||
| Строка 248: | Строка 198: | ||
=== Разрешимые и перечислимые языки === | === Разрешимые и перечислимые языки === | ||
# [[Разрешимые (рекурсивные) языки]] | # [[Разрешимые (рекурсивные) языки]] | ||
| − | # '' | + | # ''fixed'' [[Перечислимые языки]] (2) |
| − | ## | + | ## Добавить содержательный пример коперечислимого языка |
| − | + | # ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (2.5) | |
| − | + | ## Убрать лишние знаки препинания из списков в теоремах | |
| − | |||
| − | |||
| − | |||
| − | # '' | ||
| − | ## | ||
## Заменить литературу на источники информации | ## Заменить литературу на источники информации | ||
| − | # | + | ## Категории |
| − | + | ## Отформатировать по правилам | |
| − | + | # [[Вычислимые функции]] | |
| − | # '' | + | # ''fixed'' [[Вычислимые числа]] (2) |
## Правильно оформить англоязычные термины | ## Правильно оформить англоязычные термины | ||
## Пояснить a(eps) в определении | ## Пояснить a(eps) в определении | ||
| Строка 268: | Строка 213: | ||
## Ссылки заменить на источники информации | ## Ссылки заменить на источники информации | ||
## Увеличить дроби | ## Увеличить дроби | ||
| − | # [[Универсальная функция]] (1) | + | ## Пояснить подробней мутные места |
| + | # ''fixed'' [[Универсальная функция]] (1) | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| Строка 274: | Строка 220: | ||
## Пояснить нотацию про U(n, x) и U_n(x) | ## Пояснить нотацию про U(n, x) и U_n(x) | ||
## Заголовки внутри конспекта поправить | ## Заголовки внутри конспекта поправить | ||
| − | # [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1) | + | # ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1) |
## Почему языком L_g(i,x) будет X? Как i связано с X? | ## Почему языком L_g(i,x) будет X? Как i связано с X? | ||
## И вообще доказательство можно сделать чуть менее мутным :) | ## И вообще доказательство можно сделать чуть менее мутным :) | ||
# [[Неотделимые множества]] | # [[Неотделимые множества]] | ||
| − | # ''' | + | # '''fixed''' [[Иммунные и простые множества]] (7) |
## английские источиники и термины | ## английские источиники и термины | ||
## ссылки на вики | ## ссылки на вики | ||
| Строка 286: | Строка 232: | ||
## Подробней расписать доказательства | ## Подробней расписать доказательства | ||
## Ссылки на леммы внутри конспекта | ## Ссылки на леммы внутри конспекта | ||
| − | # ''' | + | # '''fixed''' [[Теорема о рекурсии]] (8) |
## дать ссылки на английские источники и термины | ## дать ссылки на английские источники и термины | ||
## Неформальное пояснение к теореме | ## Неформальное пояснение к теореме | ||
| Строка 292: | Строка 238: | ||
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. | ## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. | ||
# [[Квайны]] | # [[Квайны]] | ||
| − | # | + | # [[Busy beaver]] |
| − | |||
| − | |||
| − | |||
# [[Колмогоровская сложность]] | # [[Колмогоровская сложность]] | ||
=== Вычислительные формализмы === | === Вычислительные формализмы === | ||
<ol> | <ol> | ||
| − | <li value="14"> | + | <li value="14">[[Машина Тьюринга]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Лямбда-исчисление]]</li> | <li> [[Лямбда-исчисление]]</li> | ||
| − | <li> ''' | + | <li> '''fixed''' [[Примитивно рекурсивные функции]] (10) </li> |
# названия функций надо в \mathrm | # названия функций надо в \mathrm | ||
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]] | # Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]] | ||
| − | <li> '' | + | <li> ''fixed'' [[Частично рекурсивные функции]] (2) </li> |
| − | # | + | # Замечание про взаимную рекурсию в обсуждениях |
| − | + | <li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li> | |
| − | + | <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li> | |
| − | + | <li> [[Линейный клеточный автомат, эквивалентность МТ]] </li> | |
| − | + | <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li> | |
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
<li> [[Линейный ограниченный автомат]]</li> | <li> [[Линейный ограниченный автомат]]</li> | ||
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li> | <li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li> | ||
| Строка 346: | Строка 260: | ||
=== Примеры неразрешимых задач === | === Примеры неразрешимых задач === | ||
<ol> | <ol> | ||
| − | <li value="24"> [[m-сводимость]] (3) </li> | + | <li value="24"> ''fixed'' [[m-сводимость]] (3) </li> |
# Англоязычные термины правильно оформить | # Англоязычные термины правильно оформить | ||
# Добавить примеры m-сведения задач | # Добавить примеры m-сведения задач | ||
| Строка 354: | Строка 268: | ||
# Переменные и константы взять в Tex | # Переменные и константы взять в Tex | ||
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li> | <li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li> | ||
| − | <li> | + | <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li> |
| − | |||
| − | |||
| − | |||
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li> | <li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li> | ||
| − | <li> ''' | + | <li> '''fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li> |
# Оформить правильно англоязычные термины | # Оформить правильно англоязычные термины | ||
# Написать более подробное и понятное доказательство | # Написать более подробное и понятное доказательство | ||
| Строка 365: | Строка 276: | ||
# Добавить категории | # Добавить категории | ||
# Добавить см. также | # Добавить см. также | ||
| − | <li> | + | <li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li> |
| − | + | <li> [[Неразрешимость исчисления предикатов первого порядка]] </li> | |
| − | + | <li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | <li> ''' | ||
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными. | # написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными. | ||
| − | <li> ''' | + | <li> [[Игра «Жизнь»]] </li> |
| + | <li> [[Неразрешимость игры Braid]] </li> | ||
| + | <li> '''fixed''' [[Теорема Райса-Шапиро]] (8) </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)
- Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
- Решение уравнений в регулярных выражениях
- fixed Замкнутость регулярных языков относительно различных операций (6)
- Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
- fixed Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов) (5)
- Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
- Оформить нормально источники информации
- Исправить багу с примечаниями
- Англоязычные термины
- fixed Контексты и синтаксические моноиды (1)
- Оформить примеры красиво
- Оформить красиво двусторонние доказательства
- Отформатировать по правилам
Другие автоматы
- 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" можно написать понятней
- Добавить категории, см. также
- Заменить литературу на источники информации
