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