Изменения

Перейти к: навигация, поиск

Дискретная математика2:Тикеты

2261 байт добавлено, 15:28, 25 мая 2019
Алгоритмы разбора
=== 1 Базовые определения ===
# [[Вероятностное пространство, элементарный исход, событие]] 0.5## заменить .. на \ldots# [[Независимые события]] 1## заменить ... на \ldots## Сделать умножение везде одинаковым## Добавить см также#[[Условная вероятность]] 0,5## заменить т.к. на так как# [[Дискретная случайная величина]] 2## Добавить примеров# [[Независимые случайные величины]] 1## поправить тех## Добавить см также## Убрать из примечания ссылку на внутренний конспект, сделать интервик# взяли[[Математическое ожидание случайной величины]] 1.5
## "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
## сделать умножение везде одинаковым
# [[Ковариация случайных величин]] 0.5## сделать умножение везде одинаковым# [[Корреляция случайных величин]] 0.5## Все цифры в тех## заменить т.е. на то есть
=== 2 Формулы расчёта вероятности ===
# [[Формула полной вероятности]]
# [[Формула Байеса]] 0.5## Поправить тех
# [[Дисперсия случайной величины]]
# взяли [[Неравенство Маркова]] 0.5## формулы и переменные взять в tex# взяли [[Энтропия случайного источника]] 0.5## Сделать все дроби через \dfrac# [[Симуляция одним распределением другого]] 8## так и нет нормального определения распределения## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы## издания и страницы в источниках информации## Англоязычные термины## Исправить знаки неравенств## Зачем-то формулы написаны по центру## Картинки в общем случае криво расположены## Вывод оформить правильно## Увеличить дроби## Определения в шаблон## Увеличить картинки# взяли [[Арифметическое кодирование]] 0.5## Поправить псевдокод## Поправить тех# [[Парадоксы теории вероятностей]]<tex>^\star</tex> 0.5## Добавить См. также## Поправить тех# [[Схема Бернулли]]<tex>^\star</tex> 0.5## Поправить тех## Сделать умножение везде одинаковым
== Марковские цепи ==
=== 3 Основные определения и свойства ===
# [[Марковская цепь]] (6)## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)## сделать подраздел "циклические классы"## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?## Интервики на графы## Англоязычные термины правильно оформить## Оформить правильно источники информации# [[Теорема о поглощении]] (6)## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.## max -> \max ## в конце какая-то муть. Расписать рассуждения чуть подробнее## Заменить дефисы на тире## А что такое непоглощающая матрица?## Источники информации# [[Фундаментальная матрица]] (5)## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть## Англоязычные термины## Определения выделить жирным## Дефисы на тире, переменные в Tex# [[Математическое ожидание времени поглощения]] (2)## не везде переменные обернуты в латех## Оформить правильно Источники информации## Добавить См. также## Пояснить подробней переходы# взяли[[Расчет вероятности поглощения в состоянии]] (5)
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
## имена переменных из псевдокода в тексте оборачиваются в \mathtt
## оформить нормально источник
## Заголовки первого уровня убрать
# взяли [[Эргодическая марковская цепь]] 1## Английские термины## Поправить тех## т.е. -> то есть# [[Регулярная марковская цепь]] 0.5## Убрать ч.т.д## т.е. -> то есть# [[Примеры использования Марковских цепей]] (1)## Поправить Tex## Добавить см. также## Интервики
# [[Скрытые Марковские модели]]<tex>^\star</tex>
=== 4 Алгоритмы на марковских цепях ===
# [[Алгоритм Витерби]]<tex>^\star</tex> (5)## [[Алгоритм "правдоподобная последовательность скрытых состоянийВперед-Назад" {{]]<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> ^\mathrm или star </tex> </li><li>[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex></li><li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li><li>[[Автоматы Мура и Мили]]<tex> ^\mathttstar </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> ^\pi что такое?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> 2## Отформатировать псевдокод</li> === МП-автоматы ===## Заменить литературу на источники информации<li>[[Автоматы с магазинной памятью]]## Оформить </li><li> [[МП-автоматы, допуск по пустому стеку и по правиламдопускающему состоянию, эквивалентность]]</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5## Поправить тех# взяли </li><li>[[Детерминированные автоматы с магазинной памятью]] </li><li> [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex></li><li>[[Алгоритм БаумаЭквивалентность ДМП-Велшаавтоматов]]<tex>^\star</tex> 0</li><li>[[Несовпадение класса языков,5распознаваемых ДМП автоматами и произвольными МП автоматами]]</li><li>[[ДМП-автоматы и неоднозначность]]</li> ## Поправить тех</ol>

Навигация