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

Теория вероятностей:Тикеты

1 Базовые определения

1. Вероятностное пространство, элементарный исход, событие
2. Независимые события
3. Условная вероятность
4. Дискретная случайная величина
5. Независимые случайные величины
6. взялиМатематическое ожидание случайной величины 1.5
   1. "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
   2. сделать умножение везде одинаковым
7. Ковариация случайных величин
8. Корреляция случайных величин

2 Формулы расчёта вероятности

1. Формула полной вероятности
2. Формула Байеса
3. Дисперсия случайной величины
4. Неравенство Маркова
5. Энтропия случайного источника
6. Симуляция одним распределением другого
7. Арифметическое кодирование
8. Парадоксы теории вероятностей[math]^\star[/math]
9. Схема Бернулли[math]^\star[/math]

Марковские цепи

3 Основные определения и свойства

1. Марковская цепь
2. Теорема о поглощении
3. Фундаментальная матрица
4. Математическое ожидание времени поглощения
5. взялиРасчет вероятности поглощения в состоянии (5)
   1. куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
   2. имена переменных из псевдокода в тексте оборачиваются в \mathtt
   3. оформить псевдокод в виде функций, без всяких println
   4. оформить нормально источник
   5. Заголовки первого уровня убрать
6. Эргодическая марковская цепь
7. Регулярная марковская цепь
8. Примеры использования Марковских цепей
9. Скрытые Марковские модели[math]^\star[/math]

4 Алгоритмы на марковских цепях

1. Алгоритм Витерби[math]^\star[/math]
2. Алгоритм "Вперед-Назад"[math]^\star[/math]
3. Алгоритм Баума-Велша[math]^\star[/math]

5 Автоматы и регулярные языки

Регулярные языки и ДКА

1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
2. Регулярные языки: два определения и их эквивалентность, регулярные выражения
3. Детерминированные конечные автоматы
4. Прямое произведение ДКА
5. Простой сопоставитель регулярных выражений[math] \star [/math]

НКА

6. Недетерминированные конечные автоматы
7. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
8. Автоматы с eps-переходами. Eps-замыкание
9. Теорема Клини (совпадение классов автоматных и регулярных языков)
10. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Минимизация ДКА

11. Эквивалентность состояний ДКА
12. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
13. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
14. Алгоритм Бржозовского[math] ^\star [/math]

Свойства конечных автоматов

15. Доказательство нерегулярности языков: лемма о разрастании
16. Интерпретация булевых формул с кванторами как игр для двух игроков
17. Решение уравнений в регулярных выражениях
18. Замкнутость регулярных языков относительно различных операций
19. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
20. взялиКонтексты и синтаксические моноиды 0.5
1. поправить тех

Другие автоматы

21. Локальные автоматы[math] ^\star [/math]
22. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
23. Квантовые конечные автоматы[math] ^\star [/math]
24. Автоматы Мура и Мили[math] ^\star [/math]
25. Автоматы в современном мире[math] ^\star [/math]

6 Контекстно-свободные грамматики

Базовые понятия о грамматиках

1. Формальные грамматики
2. Иерархия Хомского формальных грамматик
3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
4. Правоконтекстные грамматики, эквивалентность автоматам
5. взялиКонтекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора 0.5
   1. Поправить тех
6. Замкнутость КС-языков относительно различных операций
7. Регулярная аппроксимация КС-языков[math] ^\star [/math]

Нормальные формы КС-грамматик

8. Удаление бесполезных символов из грамматики
9. Удаление длинных правил из грамматики
10. взялиУдаление eps-правил из грамматики 0.5
    1. Поправить тех
11. Удаление цепных правил из грамматики
12. Нормальная форма Хомского
13. Устранение левой рекурсии
14. Приведение грамматики к ослабленной нормальной форме Грейбах
15. Нормальная форма Куроды[math] ^\star [/math]

Алгоритмы разбора

16. взялиАлгоритм Кока-Янгера-Касами разбора грамматики в НФХ 0.5
    1. Поправить тех
17. взялиАлгоритм Кока-Янгера-Касами, модификация для произвольной грамматики 0.5
    1. Поправить тех
18. взялиАлгоритм Эрли 2
    1. разобраться с псевдокодами, там определенно есть лажа в индексах
    2. поправить тех
19. Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики

Опровержение контекстно-свободности языка

20. Лемма о разрастании для КС-грамматик
21. Лемма Огдена
22. Существенно неоднозначные языки
23. Теорема Парика[math] ^\star [/math]

МП-автоматы

24. Автоматы с магазинной памятью
25. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
26. Совпадение множества языков МП-автоматов и контекстно-свободных языков 0.5
    1. Поправить тех
27. Детерминированные автоматы с магазинной памятью
28. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
29. Нормальная форма ДМП-автомата[math] ^\star [/math]
30. Эквивалентность ДМП-автоматов[math] ^\star [/math]
31. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
32. ДМП-автоматы и неоднозначность