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