Дискретная математика2:Тикеты — различия между версиями
(→3 Основные определения и свойства) |
(→4 Алгоритмы на марковских цепях) |
||
| Строка 43: | Строка 43: | ||
=== 4 Алгоритмы на марковских цепях === | === 4 Алгоритмы на марковских цепях === | ||
| − | # | + | # [[Алгоритм Витерби]]<tex>^\star</tex> |
| − | # | + | # [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex> |
| − | + | # [[Алгоритм Баума-Велша]]<tex>^\star</tex> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 5 Автоматы и регулярные языки == | == 5 Автоматы и регулярные языки == | ||
Версия 22:33, 8 марта 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
- Поправить тех
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ 0.5
- Поправить тех
- Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики 0.5
- Поправить тех
- Алгоритм Эрли 2
- разобраться с псевдокодами, там определенно есть лажа в индексах
- поправить тех
- Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
- Лемма о разрастании для КС-грамматик
- Лемма Огдена
- Существенно неоднозначные языки
- Теорема Парика
- Автоматы с магазинной памятью
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Совпадение множества языков МП-автоматов и контекстно-свободных языков 0.5
- Поправить тех
- Детерминированные автоматы с магазинной памятью
- Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
- Нормальная форма ДМП-автомата
- Эквивалентность ДМП-автоматов
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность
