3622
правки
Изменения
м
→Опровержение контекстно-свободности языка
<li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li>
<li> [[Регулярные языки: два определения и их эквивалентность]] </li>
<li> ''взялиfixed'' [[Детерминированные конечные автоматы]] (2) </li>
# Оформить красиво табличку
# Оформить подробней и красивей способы представления
<li> [[Автоматы с eps-переходами. Eps-замыкание]] </li>
<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]] </li>
<li> '''!!!fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>
# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
# Неплохо бы добавить ссылку на источник доказательства
<ol>
<li value="10"> [[Эквивалентность состояний ДКА]] </li>
<li> ''fixed'' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] (2) </li>
# Оформить таблички покрасивей и marked на что-нибудь заменить
# Сделать О-красивое
<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li>
# Отформатировать комментарии и добавить их побольше
# Оформить правильно декларации функций
# Отформатировать по правилам<li> '''взялиfixed''' [[Алгоритм Бржозовского]] (5) </li>
# Добавить доказательство
</ol>
=== Свойства конечных автоматов ===
<ol>
<li value="14"> '''взялиfixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </li>
# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
# Доказательство леммы о накачке в общем виде
# Отформатировать по правилам
<li> ''взялиfixed'' [[Интерпретация булевых формул с кванторами как игр для двух игроков]] (1) </li>
* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
<li> [[Решение уравнений в регулярных выражениях]] </li>
<li> '''!!!fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
<li> '''взялиfixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
# Оформить нормально источники информации
=== Другие автоматы ===
<ol>
<li value="20"> '''!!!fixed''' [[Локальные автоматы]] (5) </li>
# Где это нужно и зачем применяется
<li> [[Двусторонний детерминированный конечный автомат]] </li>
<li> [[Квантовые конечные автоматы]] </li>
<li> '''!!!fixed''' [[Автоматы Мура и Мили]] (5) </li>
# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
</ol>
<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] </li>
<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>
<li> ''fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] (1) </li>
# Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
<li> '''!!!fixed''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>
# Пропущен - в КС-языках
# Точку в конкатенации лучше опустить
# Добавить примеры других грамматик
# Добавить ссылок, см. также
<li> '''!!!fixed''' [[Регулярная аппроксимация КС-языков]] (7) </li>
# Добавить док-во леммы
# Отформатировать псевдокод
=== Нормальные формы КС-грамматик ===
<ol>
<li value="8"> '''!!!fixed''' [[Удаление бесполезных символов из грамматики]] (6) </li>
# Англоязычных термины нормально оформить
# Добавить ссылок
<li> [[Нормальная форма Хомского]] </li>
<li> [[Устранение левой рекурсии]] </li>
<li> '''!!!fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]] (8) </li>
# написать, для чего она нужна
# Какая асимптотика алгоритма приведения?
<ol>
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
<li> '''!!!взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (710) </li>
# Расписать подробней и формальней
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
# Красиво всё оформить
<li> [[Алгоритм Эрли]] </li>
<li> '''!!!fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] (5) </li>
# Отформатировать псевдокод
# Грамматику G заменить на \Gamma
=== Опровержение контекстно-свободности языка ===
<ol>
<li value="20"> '''!!!fixed''' [[Лемма о разрастании для КС-грамматик]] (6) </li>
# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
# Источники нормально оформить
# Добавить см. также на варианты леммы
# Категория
<li> '''!!!fixed''' [[Лемма Огдена]] (710) </li>
# Источники информации добавить
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы
=== МП-автоматы ===
<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>
=== Разрешимые и перечислимые языки ===
# [[Разрешимые (рекурсивные) языки]]
# '''взяли'fixed'' [[Перечислимые языки]] (62)## Оформить правильно англоязычные термины## Поправить чуть определение полуразрешимого Добавить содержательный пример коперечислимого языка## Отформатировать псевдокоды## Оформить правильно в обе стороны доказательство теоремы## Заменить источники на источники информации## Добавить примеры перечислимых, коперечеслимых языков и неперечислимых языков# ''взялиfixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (12.5)## Чуть-чуть код форматнутьУбрать лишние знаки препинания из списков в теоремах
## Заменить литературу на источники информации
# ''fixed'' # Категории## Отформатировать по правилам# [[Вычислимые функции]] (0.5)## Заменить источники на источники информации## Англоязычные термины# ''взялиfixed'' [[Вычислимые числа]] (12)
## Правильно оформить англоязычные термины
## Пояснить a(eps) в определении
## Ссылки заменить на источники информации
## Увеличить дроби
# # Пояснить подробней мутные места# ''fixed'' [[Универсальная функция]] (1)
## Англоязычные термины правильно оформить
## Оформить правильно источники информации
## Пояснить нотацию про U(n, x) и U_n(x)
## Заголовки внутри конспекта поправить
# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1)
## Почему языком L_g(i,x) будет X? Как i связано с X?
## И вообще доказательство можно сделать чуть менее мутным :)
# [[Неотделимые множества]]
# '''!!!fixed''' [[Иммунные и простые множества]] (7)
## английские источиники и термины
## ссылки на вики
## Подробней расписать доказательства
## Ссылки на леммы внутри конспекта
# '''!!!fixed''' [[Теорема о рекурсии]] (8)
## дать ссылки на английские источники и термины
## Неформальное пояснение к теореме
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
# [[Квайны]]
# ''fixed'' [[Busy beaver]] (1)## Правильно оформить англоязычные термины## Отформатировать псевдокод## Нормально оформить см. также, источники информации и вывод из теоремы
# [[Колмогоровская сложность]]
=== Вычислительные формализмы ===
<ol>
<li value="14">'''fixed''' [[Машина Тьюринга]] (7) </li># Англоязычные термины# Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)# Выделить машину Тьюринга жирным в определении# Алгоритмы примеров красиво оформить# Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)# Добавить в многоленточной, что эмулируется многодорожечной# Рассказать весёлую историю про тезис Чёрча-Тьюринга# Заменить ссылки на источники информации# Добавить категории
<li> [[Лямбда-исчисление]]</li>
<li> '''взялиfixed''' [[Примитивно рекурсивные функции]] (610) </li>
# названия функций надо в \mathrm
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
<li> '''взяли'fixed'' [[Частично рекурсивные функции]] (52) </li># См. замечания Замечание про взаимную рекурсию в обсуждениях# англоязычные термины# Дефис заменить на тире# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом# Заменить знаки неравенств # "неразрешимость проврк," {{---}} опечатки# Оформить правильно источники информации# Добавить категории <li> ''fixed'' [[Стековые машины, эквивалентность двухстековой машины МТ]] (0.5) </li># Интервики# Разбить доказательство на абзацы для читабельности# Добавить категории# Правильно оформить источники информации<li> ''fixed'' [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] (0.5) </li># Оформить правильно источники информации# Добавить категории <li> ''fixed'' [[Линейный клеточный автомат, эквивалентность МТ]] (0.5) </li># Англоязычные термины правильно оформить# Переменные взять в Tex# Добавить категории# Оформить правильно источники информации<li> ''fixed'' [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] (1) </li># внутренние ссылки# категории# Добавить см. также и источники информации
<li> [[Линейный ограниченный автомат]]</li>
<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>
=== Примеры неразрешимых задач ===
<ol>
<li value="24"> ''fixed'' [[m-сводимость]] (3) </li>
# Англоязычные термины правильно оформить
# Добавить примеры m-сведения задач
# Переменные и константы взять в Tex
<li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li>
<li> ''fixed'' [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] (0.5) </li># Источники информации# Добавить см. также# Англ. термины
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
<li> '''!!!fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
# Оформить правильно англоязычные термины
# Написать более подробное и понятное доказательство
# Добавить категории
# Добавить см. также
<li> '''взяли''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] (5) </li># Англоязычные термины оформить правильно# Заменить дефисы на тире# Заменить прим. на более адекватный аналог# Заменить источники на источники информации# Добавить информацию по последнему замечанию из обсуждений# Добавить см. также<li> ''fixed'' [[Неразрешимость исчисления предикатов первого порядка]] (0.5) </li># Добавить см. также# Интервики на конспекты по математической логигике# Заменить ссылки на источники информации<li> '''!!!взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (110) </li>
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
<li> [[Игра «Жизнь»]] </li><li> [[Неразрешимость игры Braid]] </li><li> '''!!!fixed''' [[Теорема Райса-Шапиро]] (8) </li>
# Англоязычные термины
# Отформатировать псевдокоды
