Дискретная математика2:Тикеты — различия между версиями
(→Нормальные формы КС-грамматик) |
(→Теория вероятностей:Тикеты) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 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> |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | # | ||
− | |||
− | # | ||
− | |||
− | |||
− | # | ||
− | |||
− | |||
− | |||
== Марковские цепи == | == Марковские цепи == | ||
Строка 125: | Строка 92: | ||
<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: | Строка 106: | ||
=== Минимизация ДКА === | === Минимизация ДКА === | ||
<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> | ||
=== Свойства конечных автоматов === | === Свойства конечных автоматов === | ||
− | <li> | + | <li> [[Доказательство нерегулярности языков: лемма о разрастании]]</li> |
− | + | <li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]] </li> | |
− | <li> | ||
− | |||
<li>[[Решение уравнений в регулярных выражениях]]</li> | <li>[[Решение уравнений в регулярных выражениях]]</li> | ||
− | <li>[[Замкнутость регулярных языков относительно различных операций]] | + | <li>[[Замкнутость регулярных языков относительно различных операций]]</li> |
− | |||
− | |||
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li> | <li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li> | ||
<li>[[Контексты и синтаксические моноиды]] 0.5</li> | <li>[[Контексты и синтаксические моноиды]] 0.5</li> | ||
Строка 164: | Строка 120: | ||
=== Другие автоматы === | === Другие автоматы === | ||
− | <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> | ||
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li> | <li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li> | ||
− | <li> | + | <li> [[Автоматы в современном мире]]<tex> ^\star </tex></li> |
− | |||
</ol> | </ol> | ||
Строка 178: | Строка 132: | ||
<li>[[Формальные грамматики]] | <li>[[Формальные грамматики]] | ||
</li><li>[[Иерархия Хомского формальных грамматик]] | </li><li>[[Иерархия Хомского формальных грамматик]] | ||
− | </li><li> | + | </li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] |
− | + | </li><li> [[Правоконтекстные грамматики, эквивалентность автоматам]] | |
− | </li><li> | ||
− | |||
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5 | </li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5 | ||
# Поправить тех | # Поправить тех | ||
− | </li><li> | + | </li><li>[[Замкнутость КС-языков относительно различных операций]] |
− | |||
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex> | </li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex> | ||
</li> | </li> | ||
Строка 215: | Строка 166: | ||
=== Опровержение контекстно-свободности языка === | === Опровержение контекстно-свободности языка === | ||
</li><li>[[Лемма о разрастании для КС-грамматик]] | </li><li>[[Лемма о разрастании для КС-грамматик]] | ||
− | </li><li> | + | </li><li> [[Лемма Огдена]] |
− | + | </li><li> [[Существенно неоднозначные языки]] | |
− | </li><li> | ||
− | |||
</li><li>[[Теорема Парика]]<tex> ^\star </tex> | </li><li>[[Теорема Парика]]<tex> ^\star </tex> | ||
</li> | </li> | ||
Строка 224: | Строка 173: | ||
=== МП-автоматы === | === МП-автоматы === | ||
<li>[[Автоматы с магазинной памятью]] | <li>[[Автоматы с магазинной памятью]] | ||
− | </li><li> | + | </li><li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] |
− | |||
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5 | </li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5 | ||
# Поправить тех | # Поправить тех | ||
</li><li>[[Детерминированные автоматы с магазинной памятью]] | </li><li>[[Детерминированные автоматы с магазинной памятью]] | ||
− | </li><li> | + | </li><li> [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] |
− | |||
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex> | </li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex> | ||
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex> | </li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex> |
Версия 23:43, 22 февраля 2019
Содержание
Теория вероятностей:Тикеты
1 Базовые определения
- Вероятностное пространство, элементарный исход, событие
- Независимые события
- Условная вероятность
- Дискретная случайная величина
- Независимые случайные величины
- Математическое ожидание случайной величины 1.5
- "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
- сделать умножение везде одинаковым
- Ковариация случайных величин
- Корреляция случайных величин
2 Формулы расчёта вероятности
- Формула полной вероятности
- Формула Байеса
- Дисперсия случайной величины
- Неравенство Маркова
- Энтропия случайного источника
- Симуляция одним распределением другого
- Арифметическое кодирование
- Парадоксы теории вероятностей
- Схема Бернулли
Марковские цепи
3 Основные определения и свойства
- взяли Марковская цепь (6)
- два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
- сделать подраздел "циклические классы"
- "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
- Интервики на графы
- Англоязычные термины правильно оформить
- Оформить правильно источники информации
- взяли Теорема о поглощении (6)
- определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
- max -> \max
- в конце какая-то муть. Расписать рассуждения чуть подробнее
- Заменить дефисы на тире
- А что такое непоглощающая матрица?
- Источники информации
- взяли Фундаментальная матрица (5)
- написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
- не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
- получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
- Англоязычные термины
- Определения выделить жирным
- Дефисы на тире, переменные в Tex
- взяли Математическое ожидание времени поглощения (2)
- не везде переменные обернуты в латех
- Оформить правильно Источники информации
- Добавить См. также
- Пояснить подробней переходы
- взяли Расчет вероятности поглощения в состоянии (5)
- куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
- имена переменных из псевдокода в тексте оборачиваются в \mathtt
- оформить псевдокод в виде функций, без всяких println
- оформить нормально источник
- Заголовки первого уровня убрать
- взяли Эргодическая марковская цепь 1
- Английские термины
- Поправить тех
- т.е. -> то есть
- взяли Регулярная марковская цепь 0.5
- Убрать ч.т.д
- т.е. -> то есть
- взяли Примеры использования Марковских цепей (1)
- Поправить Tex
- Добавить см. также
- Интервики
- Скрытые Марковские модели
4 Алгоритмы на марковских цепях
- взяли Алгоритм Витерби (5)
- "правдоподобная последовательность скрытых состояний" — что такое "наиболее правдоподобная"?
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- а \pi что такое?
- Отформатировать псевдокод
- Англоязычные термины
- Заменить ссылки на источники информации
- взяли Алгоритм "Вперед-Назад" 2
- Отформатировать псевдокод
- Заменить литературу на источники информации
- Оформить по правилам
- Поправить тех
- взяли Алгоритм Баума-Велша 0,5
- Поправить тех
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
- Поправить тех
- Детерминированные автоматы с магазинной памятью
- Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
- Нормальная форма ДМП-автомата
- Эквивалентность ДМП-автоматов
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность