748
правок
Изменения
→Алгоритмы разбора
== Теория вероятностей:Тикеты ==
=== 1 Базовые определения ===
# [[Вероятностное пространство, элементарный исход, событие]]
# [[Независимые события]]
# [[Условная вероятность]]
# [[Дискретная случайная величина]]
# [[Независимые случайные величины]]
# взяли[[Математическое ожидание случайной величины]] 1.5
## "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
## сделать умножение везде одинаковым
# [[Ковариация случайных величин]]
# [[Корреляция случайных величин]]
=== 2 Формулы расчёта вероятности ===
# [[Формула полной вероятности]]
# [[Формула Байеса]]
# [[Дисперсия случайной величины]]
# [[Неравенство Маркова]]
# [[Энтропия случайного источника]]
# [[Симуляция одним распределением другого]]
# [[Арифметическое кодирование]]
# [[Парадоксы теории вероятностей]]<tex>^\star</tex>
# [[Схема Бернулли]]<tex>^\star</tex>
== Марковские цепи ==
=== 3 Основные определения и свойства ===
# [[Марковская цепь]]
# [[Теорема о поглощении]]
# [[Фундаментальная матрица]]
# [[Математическое ожидание времени поглощения]]
# взяли[[Расчет вероятности поглощения в состоянии]] (5)
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
## имена переменных из псевдокода в тексте оборачиваются в \mathtt
## оформить псевдокод в виде функций, без всяких println
## оформить нормально источник
## Заголовки первого уровня убрать
# [[Эргодическая марковская цепь]]
# [[Регулярная марковская цепь]]
# [[Примеры использования Марковских цепей]]
# [[Скрытые Марковские модели]]<tex>^\star</tex>
=== 4 Алгоритмы на марковских цепях ===
# [[Алгоритм Витерби]]<tex>^\star</tex>
# [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>
# [[Алгоритм Баума-Велша]]<tex>^\star</tex>
== 5 Автоматы и регулярные языки ==
=== Регулярные языки и ДКА ===
<ol>
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]</li>
<li>[[Детерминированные конечные автоматы]]</li>
<li> [[Прямое произведение ДКА]] </li>
<li> [[Простой сопоставитель регулярных выражений]]<tex> \star
</tex></li>
=== НКА ===
<li>[[Недетерминированные конечные автоматы]]</li>
<li>[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]</li>
<li>[[Автоматы с eps-переходами. Eps-замыкание]]</li>
<li>[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]</li>
<li>[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]</li>
=== Минимизация ДКА ===
<li>[[Эквивалентность состояний ДКА]]</li>
<li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]</li>
<li> [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]</li>
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
=== Свойства конечных автоматов ===
<li> [[Доказательство нерегулярности языков: лемма о разрастании]]</li>
<li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]] </li>
<li>[[Решение уравнений в регулярных выражениях]]</li>
<li>[[Замкнутость регулярных языков относительно различных операций]]</li>
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li>
<li>взяли[[Контексты и синтаксические моноиды]] 0.5</li>
# поправить тех
=== Другие автоматы ===
<li>[[Локальные автоматы]]<tex> ^\star </tex> </li>
<li>[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex></li>
<li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li>
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
<li> [[Автоматы в современном мире]]<tex> ^\star </tex></li>
</ol>
== 6 Контекстно-свободные грамматики ==
=== Базовые понятия о грамматиках ===
<ol>
<li>[[Формальные грамматики]]
</li><li>[[Иерархия Хомского формальных грамматик]]
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
</li><li> [[Правоконтекстные грамматики, эквивалентность автоматам]]
</li><li>взяли[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5
# Поправить тех
</li><li>[[Замкнутость КС-языков относительно различных операций]]
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
</li>
=== Нормальные формы КС-грамматик ===
<li>[[Удаление бесполезных символов из грамматики]]
</li><li>[[Удаление длинных правил из грамматики]]
</li><li>взяли[[Удаление eps-правил из грамматики]] 0.5
# Поправить тех
</li><li>[[Удаление цепных правил из грамматики]]
</li><li>[[Нормальная форма Хомского]]
</li><li>[[Устранение левой рекурсии]]
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex>
</li>
=== Алгоритмы разбора ===
<li>взяли[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] 0.5
# Поправить тех
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] 2
# исправить псевдокод
</li><li>взяли[[Алгоритм Эрли]] 2
# разобраться с псевдокодами, там определенно есть лажа в индексах
# поправить тех
</li><li>[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
</li>
=== Опровержение контекстно-свободности языка ===
</li><li>[[Лемма о разрастании для КС-грамматик]]
</li><li> [[Лемма Огдена]]
</li><li> [[Существенно неоднозначные языки]]
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
</li>
=== МП-автоматы ===
<li>[[Автоматы с магазинной памятью]]
</li><li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5
# Поправить тех
</li><li>[[Детерминированные автоматы с магазинной памятью]]
</li><li> [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
</li><li>[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
</li><li>[[ДМП-автоматы и неоднозначность]]</li>
</ol>
