Изменения

<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] (0.5) </li><li> [[Регулярные языки: два определения и их эквивалентность]] (0.5) </li># Англоязычные термины# Ссылки заменить на источники информации# Добавить См. также на ДКА<li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li># Оформить красиво табличку# Оформить подробней и красивей способы представления

<li> [[Автоматы с eps-переходами. Eps-замыкание]] (0.7) </li># Англоязычные термины правильно# Добавить источники информации, см. также# Написать, где используется алгоритм eps-замыкания# Пофиксить знаки неравенств# Определение жирным# Многоточия на \ldots<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] (0.3) </li># Добавить ссылок<li> '''взялиfixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>

<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li># Оформить таблички покрасивей и marked на что-нибудь заменить# Сделать О-красивое<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li># Отформатировать комментарии и добавить их побольше# Оформить правильно декларации функций# Отформатировать по правилам<li> '''!!!fixed''' [[Алгоритм Бржозовского]] (5) </li>

<li value="14"> '''!!!fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (56) </li>

# Отформатировать по правилам<li> ''fixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>

<li> '''!!!fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>

<li> '''!!!fixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>

<li> ''fixed'' [[Контексты и синтаксические моноиды]] (1) </li># Оформить примеры красиво# Оформить красиво двусторонние доказательства# Отформатировать по правилам

<li value="20"> '''!!!fixed''' [[Локальные автоматы]] (5) </li>

<li> '''!!!fixed''' [[Автоматы Мура и Мили]] (5) </li>

== 2. Контекстно-свободные грамматики (проверяются) ==# === Базовые понятия о грамматиках ===<ol><li value="1"> '''fixed''' [[Формальные грамматики]](5) </li>## Пояснить пример контекстно-зависимой грамматики## Можно ещё примеров различных интересных грамматик добавить(и добавить ссылку на грамматики языков программирования)# '''fixed''' [[Иерархия Хомского формальных грамматик]]Заменить многоточия на \ldots## добавить англоязычные термины## добавить ссылок на русские и английские Оформить правильно источники. И указать конкретные страницы у уже существующегоинфрмации, либо выпилить его нафигдобавить См.также#Категория# интервикиВыделить в разборах жирным часть правила, ссылка которая раскрывается на автоматные граммматики, например, которые есть на викиданном шаге## на машину Тьюринга можно внутреннюю ссылку сделатьПримеры обозначений## Ссылку на вики Вертикальную черту заменить на ссылку примечанием\mid#В определениях скобки в Tex# Добавить интервики Интервики на другие факты (добавить См. также)рефлексивно-транзитивное замыкание#Убрать ; из определения# Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)Выводы в примерах оформить красивей# Почистить обсуждения<li> [[Иерархия Хомского формальных грамматик]] </li><li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]</li>## Добавить источники информации, ссылок, интервики (на Иерархию)# ''fixed'' <li> [[Правоконтекстные грамматики, эквивалентность автоматам]]</li>## Англоязычные термины## Источник бесполезен без конкретного указания, где искать## Добавить интервики# '<li> ''fixed''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]## нормально оформить уже существующий источник## добавить англоязычные термины## интервики## Симольные скобки взять в tex## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>1) и в выводе (надо <tex>\Rightarrow</texli>)## пояснить, почему грамматика из первого примера неоднозначна, Оформить красиво двусторонние доказательства и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначностьисправить форматирование в остальном.+баллы за более красивые картинки## Добавить заголовков## Перерисовать картинку# <li> '''!!!fixed''' [[Замкнутость КС-языков относительно различных операций]](5) </li>## Пропущен - в КС-языках## Точку в конкатенации лучше опустить## Half некрасивый, c маленькой буквы его## Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half## Добавить примеры других грамматик## Добавить ссылок, см. также# <li> '''!!!fixed''' [[Регулярная аппроксимация КС-языков]](7) </li>## Добавить док-во леммы## Отформатировать псевдокод## Tex правильно оформить## Описание перед псевдокодом перенести## Картинки убого расположены## "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте## Расшифровать RTN (то же с MT)## Источники информации нормально оформить# См. обсуждения</ol> === Нормальные формы КС-грамматик ===<ol><li value="8"> '''взялиfixed''' [[Удаление бесполезных символов из грамматики]](6) </li>## Англоязычных термины нормально оформить## Добавить ссылок## Добавить интервики## Грамматики оформлены криво## Написать, что такое <tex> | \Gamma | </tex>## Написать, откуда берутся такие асимптотики, и как добавить очередь## Аналогично про обход в глубину## Ссылку на НФХ перенести в источники информации## Алгоритмы оформить отдельным подзаголовком# ''fixed'' Категория<li> [[Удаление длинных правил из грамматики]]</li>## Добавить источники информации## Подробней расписать время работы## Лишняя запятая в алгоритме после многоточия# '''!!!''' <li> [[Удаление eps-правил из грамматики]]## Англоязычных термины нормально оформить ## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект## Грамматику G заменить на <tex/li> \Gamma </texli>## Ссылку на НФХ перенести в источники информации## Написать, почему при удалении длинных правил асимптотика будет линейной## Грамматики криво оформлены## Пояснить использование очереди## Пропущены дефисы после КС местами# [[Удаление цепных правил из грамматики]]</li>## Англоязычные термины оформить нормально## Провести в алгоритме аналогию с транзитивным замыканием## Грамматика криво криво оформлена## Расписать асимптотику алгоритма## Ссылку на НФХ перенести в источники информации# '''взяли''' <li> [[Нормальная форма Хомского]]</li>## Англоязычные термины хорошо оформить## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)## Константы взять в Tex## Пример грамматики криво оформлен## Ссылку на НФХ перенести в источники информации## Заменить знаки неравенств в Tex# '''!!!''' <li> [[Устранение левой рекурсии]]</li>## Англоязычные термины оформить правильно## Кинуть интервики на методы нисходящего разбора (или см. также)## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило## Отформатировать псевдокод## Знаки неравенств заменить## Источники информации нормально оформить# <li> '''!!!!!fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]](8) </li>## написать, для чего она нужна## Какая асимптотика алгоритма приведения?## Добавить источники информации## Добавить примеры## Англоязычные термины нормально оформить## Отформатировать псевдокод## Добавить алгоритм приведения к сильной нормальной форме Грейбах(или хотя бы сказать как-нибудь подробней про неё) # '''fixed''' <li> [[Нормальная форма Куроды]] </li></ol> === Алгоритмы разбора ===<ol><li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]</li>## Аккуратно помёрджить с аналогичным конспектом первого курса# <li> '''!!!взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]](10) </li>## Расписать подробней и формальней## А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать## И желательно расписать динамики через полуинтервалы, а не отрезки# '''!!!''' Красиво всё оформить<li> [[Алгоритм Эрли]]</li>## Отформатировать псевдокод## Описать понятно (гуглится ссылка, где алгоритм понятно расписан)## Доказательство плохо отформатировано## Оформить красиво источники информации# <li> '''!!!fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]](5) </li>## Отформатировать псевдокод## Грамматику G заменить на \Gamma## Перенести описание алгоритма перед псевдокодом## Хотелось бы адекватные доказательства читать (см. обсуждения)# </ol> === Опровержение контекстно-свободности языка ===<ol><li value="20"> '''!!!fixed''' [[Лемма о разрастании для КС-грамматик]](6) </li>## Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена## Источники нормально оформить## Добавить см. также на варианты леммы# Категория<li> '''fixed''' [[Лемма Огдена]](10) </li>## Источники информации добавить## '''!!!''' Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести Добавить пример не КС-языка, который удовлетворяет условию этой леммы# Категория<li> [[Существенно неоднозначные языки]]</li></ol> ## Англоязычные термины оформить правильно=== МП-автоматы ===## Ссылки из См. также перенести в источники информации<ol># <li value="23"> ''fixed'' [[Автоматы с магазинной памятью]](0.5) </li>## Картинки увеличить# Определение жирным# ; в определении заменить на ,# Англоязычные термины правильно оформить, убрать дублирования# Источники информации, См. также# Категория<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]</li>## Добавить источники информации# '''!!!''' <li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]</li>## Ссылки и литературу оформить правильно## Оформить доказательство нормально, расписать подробно алгоритм# <li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]](0.5) </li>## В пример добавить язык автомата## Англоязычные термины# Категория<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]](0.5) </li># Категория# Палку заменить на \mid# Источники информации<li> '''!!!!!взяли''' [[Нормальная форма ДМП-автомата]](10) </li>## Написать!# <li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]</li>## Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?<li> [[ДМП-автоматы и неоднозначность]] </li>## Добавить источники информации</ol>

== 3. Теория вычислимости (проверяется) ==

# '''fixed''' [[Разрешимые (рекурсивные) языки]]## Оформить правильно англоязычные термины## Отформатировать псевдокод## Перенести сюда определение вычислимой функции## Добавить определение разрешимого языка в терминах вычислимой функции## Заменить источники на источники информации## Обернуть if в доказательстве неразрешимого языка в \mathrm## Ещё примеров разрешимых языков (желательно не очень тривиальных)# '''!!!'fixed'' [[Перечислимые языки]](2)## Оформить правильно англоязычные термины## Поправить чуть определение полуразрешимого Добавить содержательный пример коперечислимого языка## Отформатировать псевдокоды## Оформить правильно в обе стороны доказательство теоремы## Заменить источники на источники информации## Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]](2.5)## Чуть-чуть код форматнутьУбрать лишние знаки препинания из списков в теоремах

## Заменить источники на источники информации## Определения вычислимой функции перенести в конспект Разрешимых языков## Переименовать конспект и чуть-чуть реструктуризовать# ''fixed'' [[Вычислимые числа]](2)

# # Пояснить подробней мутные места# ''fixed'' [[Универсальная функция]] (1)

# '# Пояснить нотацию про U(n, x) и U_n(x)## Заголовки внутри конспекта поправить# ''fixed''' [[Свойства перечислимых языков. Теорема Успенского-Райса]](1)## англоязычные термины## классы языков в mathrm## заголовки верхнего уровня в ==Почему языком L_g(i, а не =x) будет X? Как i связано с X? ## категорию проставитьИ вообще доказательство можно сделать чуть менее мутным :)## Добавить источники информации## Заменить в множестве | на \mid## Отформатировать псевдокод# '''fixed''' [[Неотделимые множества]]## английские источиники и термины ## нормально оформить уже существующий источник ## написать, зачем оно может пригодиться## Добавить категории## Интервики# '''!!!fixed''' [[Иммунные и простые множества]](7)

# '''!!!fixed''' [[Теорема о рекурсии]](8)

## Правильно оформить англоязычные термины## Отформатировать псевдокод## Нормально оформить см. также, источники информации и вывод из теоремы[[Колмогоровская сложность]]

<li value="1214">'''!!!''' [[Машина Тьюринга]] </li># Англоязычные термины# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)# Выделить машину Тьюринга жирным в определении# Алгоритмы примеров красиво оформить# Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)# Добавить в многоленточной, что эмулируется многодорожечной# Рассказать весёлую историю про тезис Чёрча-Тьюринга# Заменить ссылки на источники информации# Добавить категории<li> '''fixed''' [[Лямбда-исчисление]]</li># Англоязычные термины# Заменить "в разработке" на "nohate"# Написать грамматику лямбд адекватно# "Аппликация забирает себе всё," - ошибка - абстракция забирает# Провести аналогию между связанными переменными и локальными переменными# "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?# Написать, что alpha-конверсия -- отношение эквивалентности# beta-редукция не олицетворяет. Написать определение формально# Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней# Провести аналогию между нумералами Чёрча и нумерацией Гёделя# Убрать маркированный список из чисел, лучше просто отступ оставить# "<<числу>>" {{---}} получше оформить# Все константы и переменные взять в Tex# Добавить примеры выполнения операций сложения, умножения и вычитания# "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается# Добавить в неподвижной точке про Y-комбинатор# Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном# Оформить правильно источники информации, см. также# Добавить категории<li> '''!!!fixed''' [[Примитивно рекурсивные функции]] (10) </li>

<li> '''взяли'fixed'' [[Частично рекурсивные функции]] (2) </li># См. замечания Замечание про взаимную рекурсию в обсуждениях# англоязычные термины# Дефис заменить на тире# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом# Заменить знаки неравенств # "неразрешимость проврк," {{---}} опечатки# Оформить правильно источники информации# Добавить категории <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li># Интервики# Разбить доказательство на абзацы для читабельности# Добавить категории# Правильно оформить источники информации

<li value="2024"> '''взяли'fixed'' [[m-сводимость]] (3) </li>

<li> '''fixed''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li># Англоязычные термины правильно оформить# Заменить дефисы на тире# Заменить знаки неравенств# Все переменные и константы взять в Tex# Добавить примеров решения задач ПСП# Отфомартировать псевдокод# Добавить больше подзаголовков нижнего уровня# Больше интервики# Заменить источники на источники информации# Добавить категории, см. также

# Источники информации# Добавить см. также<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность Неразрешимость задачи об эквивалентности КС-грамматикиграмматик]]</li># Добавить см. также<li> '''!!!fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>

<li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li># Англоязычные термины оформить правильно# Заменить дефисы на тире# Заменить прим. на более адекватный аналог# Заменить источники на источники информации# Добавить информацию по последнему замечанию из обсуждений# Добавить см. также

# Добавить см. также# Заменить ссылки на источники информации<li> '''!!!взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>

<li> [[Игра «Жизнь»]] </li><li> [[Неразрешимость игры Braid]] </li><li> '''!!!fixed''' [[Теорема Райса-Шапиро]] (8) </li>