Дискретная математика2:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎2 Формулы расчёта вероятности)
(→‎Алгоритмы разбора)
 
(не показано 47 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
=== 1 Базовые определения ===
 
=== 1 Базовые определения ===
−
# [[Вероятностное пространство, элементарный исход, событие]] 0.5
+
# [[Вероятностное пространство, элементарный исход, событие]]  
−
## заменить .. на \ldots
+
# [[Независимые события]]  
−
# [[Независимые события]] 1
+
# [[Условная вероятность]]  
−
## заменить ... на \ldots
+
# [[Дискретная случайная величина]]  
−
## Сделать умножение везде одинаковым
+
# [[Независимые случайные величины]]  
−
## Добавить см также
+
# взяли[[Математическое ожидание случайной величины]] 1.5
−
#[[Условная вероятность]] 0,5
 
−
## заменить т.к. на так как
 
−
# [[Дискретная случайная величина]] 2
 
−
## Добавить примеров
 
−
# [[Независимые случайные величины]] 1
 
−
## поправить тех
 
−
## Добавить см также
 
−
## Убрать из примечания ссылку на внутренний конспект, сделать интервик
 
−
# [[Математическое ожидание случайной величины]] 1.5
 
 
## "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
 
## "E(ξ)=∑i=1nE(ξi)=1n" что-то пошло не так
 
## сделать умножение везде одинаковым
 
## сделать умножение везде одинаковым
−
# [[Ковариация случайных величин]] 0.5
+
# [[Ковариация случайных величин]]  
−
## сделать умножение везде одинаковым
+
# [[Корреляция случайных величин]]  
−
# [[Корреляция случайных величин]] 0.5
 
−
## Все цифры в тех
 
−
## заменить т.е. на то есть
 
  
 
=== 2 Формулы расчёта вероятности ===
 
=== 2 Формулы расчёта вероятности ===
 
# [[Формула полной вероятности]]
 
# [[Формула полной вероятности]]
−
# [[Формула Байеса]] 0.5
+
# [[Формула Байеса]]
−
## Поправить тех
 
 
# [[Дисперсия случайной величины]]
 
# [[Дисперсия случайной величины]]
−
# взяли [[Неравенство Маркова]] 0.5
+
# [[Неравенство Маркова]]  
−
## формулы и переменные взять в tex
+
# [[Энтропия случайного источника]]  
−
## странный первый пример, он не подходит к условию теоремы
+
# [[Симуляция одним распределением другого]]
−
# взяли [[Энтропия случайного источника]] 0.5
+
# [[Арифметическое кодирование]]  
−
## Сделать все дроби через \dfrac
+
# [[Парадоксы теории вероятностей]]<tex>^\star</tex>
−
# [[Симуляция одним распределением другого]] 8
+
# [[Схема Бернулли]]<tex>^\star</tex>
−
## так и нет нормального определения распределения
 
−
## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
 
−
## издания и страницы в источниках информации
 
−
## Англоязычные термины
 
−
## Исправить знаки неравенств
 
−
## Зачем-то формулы написаны по центру
 
−
## Картинки в общем случае криво расположены
 
−
## Вывод оформить правильно
 
−
## Увеличить дроби
 
−
## Определения в шаблон
 
−
## Увеличить картинки
 
−
# взяли [[Арифметическое кодирование]] 0.5
 
−
## Поправить псевдокод
 
−
## Поправить тех
 
−
# [[Парадоксы теории вероятностей]]<tex>^\star</tex> 0.5
 
−
## Добавить См. также
 
−
## Поправить тех
 
−
# [[Схема Бернулли]]<tex>^\star</tex> 0.5
 
−
## Поправить тех
 
−
## Сделать умножение везде одинаковым
 
  
 
== Марковские цепи ==
 
== Марковские цепи ==
  
 
=== 3 Основные определения и свойства ===
 
=== 3 Основные определения и свойства ===
−
# [[Марковская цепь]] (6)
+
# [[Марковская цепь]]  
−
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
+
# [[Теорема о поглощении]]
−
## сделать подраздел "циклические классы"
+
# [[Фундаментальная матрица]]
−
## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
+
# [[Математическое ожидание времени поглощения]]  
−
## Интервики на графы
+
# взяли[[Расчет вероятности поглощения в состоянии]] (5)
−
## Англоязычные термины правильно оформить
 
−
## Оформить правильно источники информации
 
−
#  [[Теорема о поглощении]] (6)
 
−
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
 
−
## max -> \max
 
−
## в конце какая-то муть. Расписать рассуждения чуть подробнее
 
−
## Заменить дефисы на тире
 
−
## А что такое непоглощающая матрица?
 
−
## Источники информации
 
−
#  [[Фундаментальная матрица]] (5)
 
−
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
 
−
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
 
−
## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
 
−
## Англоязычные термины
 
−
## Определения выделить жирным
 
−
## Дефисы на тире, переменные в Tex
 
−
#  [[Математическое ожидание времени поглощения]] (2)
 
−
## не везде переменные обернуты в латех
 
−
## Оформить правильно Источники информации
 
−
## Добавить См. также
 
−
## Пояснить подробней переходы
 
−
# [[Расчет вероятности поглощения в состоянии]] (5)
 
 
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
 
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
 
## имена переменных из псевдокода в тексте оборачиваются в \mathtt
 
## имена переменных из псевдокода в тексте оборачиваются в \mathtt
Строка 92: Строка 37:
 
## оформить нормально источник
 
## оформить нормально источник
 
## Заголовки первого уровня убрать
 
## Заголовки первого уровня убрать
−
# взяли [[Эргодическая марковская цепь]] 1
+
# [[Эргодическая марковская цепь]]  
−
## Английские термины
+
# [[Регулярная марковская цепь]]  
−
## Поправить тех
+
# [[Примеры использования Марковских цепей]]  
−
## т.е. -> то есть
 
−
# [[Регулярная марковская цепь]] 0.5
 
−
## Убрать ч.т.д
 
−
## т.е. -> то есть
 
−
# [[Примеры использования Марковских цепей]] (1)
 
−
## Поправить Tex
 
−
## Добавить см. также
 
−
## Интервики
 
 
# [[Скрытые Марковские модели]]<tex>^\star</tex>
 
# [[Скрытые Марковские модели]]<tex>^\star</tex>
  
 
=== 4 Алгоритмы на марковских цепях ===
 
=== 4 Алгоритмы на марковских цепях ===
−
# [[Алгоритм Витерби]]<tex>^\star</tex> (5)
+
# [[Алгоритм Витерби]]<tex>^\star</tex>  
−
## "правдоподобная последовательность скрытых состояний" {{---}} что такое "наиболее правдоподобная"?
+
# [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex>  
−
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
+
# [[Алгоритм Баума-Велша]]<tex>^\star</tex>
−
## а \pi что такое?
 
−
## Отформатировать псевдокод
 
−
## Англоязычные термины
 
−
## Заменить ссылки на источники информации
 
−
#  [[Алгоритм "Вперед-Назад"]]<tex>^\star</tex> 2
 
−
## Отформатировать псевдокод
 
−
## Заменить литературу на источники информации
 
−
## Оформить по правилам
 
−
## Поправить тех
 
−
# взяли [[Алгоритм Баума-Велша]]<tex>^\star</tex> 0,5
 
−
## Поправить тех
 
  
 
== 5 Автоматы и регулярные языки ==
 
== 5 Автоматы и регулярные языки ==
Строка 125: Строка 51:
 
<ol>
 
<ol>
 
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
 
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
−
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]] 0.5</li>
+
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]</li>
−
# поправить тех
 
 
<li>[[Детерминированные конечные автоматы]]</li>
 
<li>[[Детерминированные конечные автоматы]]</li>
−
<li>[[Прямое произведение ДКА]] 0.5</li>
+
<li> [[Прямое произведение ДКА]] </li>
−
# поправить тех
+
<li> [[Простой сопоставитель регулярных выражений]]<tex> \star  
−
<li>[[Простой сопоставитель регулярных выражений]] 0.5 <tex> \star  
 
 
</tex></li>
 
</tex></li>
−
# поправить тех
+
 
 
=== НКА ===
 
=== НКА ===
 
<li>[[Недетерминированные конечные автоматы]]</li>
 
<li>[[Недетерминированные конечные автоматы]]</li>
Строка 141: Строка 65:
 
=== Минимизация ДКА ===
 
=== Минимизация ДКА ===
 
<li>[[Эквивалентность состояний ДКА]]</li>
 
<li>[[Эквивалентность состояний ДКА]]</li>
−
<li>[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] 0.5</li>
+
<li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]</li>
−
# поправить тех
+
<li> [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]</li>
−
<li>[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 
−
0.5</li>
 
−
# поправить тех
 
−
# заменить дефис на тире, там где это надо
 
 
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
 
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
 +
 
=== Свойства конечных автоматов ===
 
=== Свойства конечных автоматов ===
−
<li>[[Доказательство нерегулярности языков: лемма о разрастании]] 0.5</li>
+
<li> [[Доказательство нерегулярности языков: лемма о разрастании]]</li>
−
# оформить правильно английские термины
+
<li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]] </li>
−
<li>[[Интерпретация булевых формул с кванторами как игр для двух игроков]] 2</li>
 
−
# Создать новый конспект и вынести материал из статьи "Исчисление предикатов"
 
 
<li>[[Решение уравнений в регулярных выражениях]]</li>
 
<li>[[Решение уравнений в регулярных выражениях]]</li>
−
<li>[[Замкнутость регулярных языков относительно различных операций]]
+
<li>[[Замкнутость регулярных языков относительно различных операций]]</li>
−
0.5</li>
+
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li>
 +
<li>взяли[[Контексты и синтаксические моноиды]] 0.5</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></li>
 
<li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li>
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
−
<li>[[Автоматы в современном мире]]<tex> ^\star </tex> 0.5</li>
+
<li> [[Автоматы в современном мире]]<tex> ^\star </tex></li>
−
# поправить тех
 
 
</ol>
 
</ol>
 +
 
== 6 Контекстно-свободные грамматики ==
 
== 6 Контекстно-свободные грамматики ==
 
=== Базовые понятия о грамматиках ===
 
=== Базовые понятия о грамматиках ===
Строка 174: Строка 91:
 
<li>[[Формальные грамматики]]
 
<li>[[Формальные грамматики]]
 
</li><li>[[Иерархия Хомского формальных грамматик]]
 
</li><li>[[Иерархия Хомского формальных грамматик]]
−
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] 1
+
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]  
−
# Поправить тех
+
</li><li> [[Правоконтекстные грамматики, эквивалентность автоматам]]  
−
</li><li>[[Правоконтекстные грамматики, эквивалентность автоматам]] 0.5
+
</li><li>взяли[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5
−
# Добавить см. также
 
−
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5
 
 
# Поправить тех
 
# Поправить тех
−
</li><li>[[Замкнутость КС-языков относительно различных операций]] 0.5
+
</li><li>[[Замкнутость КС-языков относительно различных операций]]  
−
# поправить тех
 
 
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 
</li>
 
</li>
Строка 188: Строка 102:
 
<li>[[Удаление бесполезных символов из грамматики]]
 
<li>[[Удаление бесполезных символов из грамматики]]
 
</li><li>[[Удаление длинных правил из грамматики]]
 
</li><li>[[Удаление длинных правил из грамматики]]
−
</li><li>[[Удаление eps-правил из грамматики]] 0.5
+
</li><li>взяли[[Удаление eps-правил из грамматики]] 0.5
 
# Поправить тех
 
# Поправить тех
 
</li><li>[[Удаление цепных правил из грамматики]]
 
</li><li>[[Удаление цепных правил из грамматики]]
Строка 194: Строка 108:
 
</li><li>[[Устранение левой рекурсии]]
 
</li><li>[[Устранение левой рекурсии]]
 
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
−
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex> 0.5
+
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex>  
−
# Поправить тех
 
 
</li>
 
</li>
  
 
=== Алгоритмы разбора ===
 
=== Алгоритмы разбора ===
−
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] 0.5
+
<li>взяли[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] 0.5
−
# Поправить тех
 
−
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] 0.5
 
 
# Поправить тех
 
# Поправить тех
−
</li><li>[[Алгоритм Эрли]] 2
+
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] 2
 +
# исправить псевдокод
 +
</li><li>взяли[[Алгоритм Эрли]] 2
 
# разобраться с псевдокодами, там определенно есть лажа в индексах
 
# разобраться с псевдокодами, там определенно есть лажа в индексах
 
# поправить тех
 
# поправить тех
Строка 211: Строка 124:
 
=== Опровержение контекстно-свободности языка ===
 
=== Опровержение контекстно-свободности языка ===
 
</li><li>[[Лемма о разрастании для КС-грамматик]]
 
</li><li>[[Лемма о разрастании для КС-грамматик]]
−
</li><li>[[Лемма Огдена]] 0.5
+
</li><li> [[Лемма Огдена]]  
−
# В названиях раздела цифры в тех
+
</li><li> [[Существенно неоднозначные языки]]  
−
</li><li>[[Существенно неоднозначные языки]] 0.5
 
−
# Добавить см. также
 
 
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
 
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
 
</li>
 
</li>
Строка 220: Строка 131:
 
=== МП-автоматы ===
 
=== МП-автоматы ===
 
<li>[[Автоматы с магазинной памятью]]
 
<li>[[Автоматы с магазинной памятью]]
−
</li><li>[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] 0.5
+
</li><li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
−
# Добавить см. также
 
 
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5
 
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5
 
# Поправить тех
 
# Поправить тех
 
</li><li>[[Детерминированные автоматы с магазинной памятью]]  
 
</li><li>[[Детерминированные автоматы с магазинной памятью]]  
−
</li><li>[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] 0.5
+
</li><li> [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
−
# Добавить см. также
 
 
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
 
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>

Текущая версия на 15:28, 25 мая 2019

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

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. НКА

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

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

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

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

  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. Нормальные формы КС-грамматик

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

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

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

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

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

    24. МП-автоматы

  24. Автоматы с магазинной памятью
  25. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  26. Совпадение множества языков МП-автоматов и контекстно-свободных языков 0.5
    1. Поправить тех
  27. Детерминированные автоматы с магазинной памятью
  28. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  29. Нормальная форма ДМП-автомата[math] ^\star [/math]
  30. Эквивалентность ДМП-автоматов[math] ^\star [/math]
  31. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
  32. ДМП-автоматы и неоднозначность
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика2:Тикеты&oldid=71310»