Участник:Shersh/Тикеты к 1ому терму — различия между версиями
Shersh (обсуждение | вклад) (→9. Марковские цепи (проверяются): проверены) |
Shersh (обсуждение | вклад) м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 1ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))) |
||
(не показано 56 промежуточных версий этого же участника) | |||
Строка 8: | Строка 8: | ||
## Оформить красиво источники информации | ## Оформить красиво источники информации | ||
## Английские термины к видам отношений | ## Английские термины к видам отношений | ||
− | # [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]] | + | # [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]] (0.5) |
+ | ## Отформатировать свойства красиво | ||
+ | ## Оформить правильно источники информации | ||
+ | ## Англ. термины | ||
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | # [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | ||
# [[Симметричное отношение]] | # [[Симметричное отношение]] | ||
Строка 17: | Строка 20: | ||
# [[Транзитивное замыкание|Транзитивное замыкание отношения]] | # [[Транзитивное замыкание|Транзитивное замыкание отношения]] | ||
# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | # [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | ||
− | # ''' | + | # '''fixed''' [[Транзитивный остов]] (5) |
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
## Добавить категории | ## Добавить категории | ||
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель" | ## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель" | ||
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец | ## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец | ||
+ | ## Отформатировать конспект по правилам | ||
== 2. Булевы функции == | == 2. Булевы функции == | ||
# [[Определение булевой функции]] | # [[Определение булевой функции]] | ||
− | # [[Суперпозиции]] (0.5) | + | # [[Побитовые операции]] |
+ | # ''fixed'' [[Суперпозиции]] (0.5) | ||
## англоязычных терминов | ## англоязычных терминов | ||
− | # [[ДНФ]] (0.5) | + | # ''fixed'' [[ДНФ]] (0.5) |
## англоязычных терминов | ## англоязычных терминов | ||
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо | ## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо | ||
## Убрать странные скобки в формулировке теоремы | ## Убрать странные скобки в формулировке теоремы | ||
## Не то выделено жирным в определениях | ## Не то выделено жирным в определениях | ||
− | # [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] (2.5) | + | # ''fixed'' [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] (2.5) |
## англоязычных терминов | ## англоязычных терминов | ||
## Жирные определения | ## Жирные определения | ||
Строка 40: | Строка 45: | ||
## Все константы и переменные взять в tex | ## Все константы и переменные взять в tex | ||
# [[КНФ]] | # [[КНФ]] | ||
− | # [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] (3) | + | # [[2SAT]] |
+ | # ''fixed'' [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] (3) | ||
## англоязычных терминов | ## англоязычных терминов | ||
## написать, почему факт того, что существует полиномиальный алгоритм, интересен | ## написать, почему факт того, что существует полиномиальный алгоритм, интересен | ||
Строка 50: | Строка 56: | ||
# [[Представление функции класса DM с помощью медианы]] | # [[Представление функции класса DM с помощью медианы]] | ||
# [[Пороговая функция]] | # [[Пороговая функция]] | ||
+ | # [[Троичная логика]] | ||
== 3. Схемы из функциональных элементов == | == 3. Схемы из функциональных элементов == | ||
− | # [[Реализация булевой функции схемой из функциональных элементов]] (1) | + | # ''fixed'' [[Реализация булевой функции схемой из функциональных элементов]] (1) |
## англоязычных терминов (на схемную сложность, глубину схемы) | ## англоязычных терминов (на схемную сложность, глубину схемы) | ||
## Оформить красивее определения из логических элементов | ## Оформить красивее определения из логических элементов | ||
Строка 69: | Строка 76: | ||
## Увеличить дроби | ## Увеличить дроби | ||
# [[Cумматор]] | # [[Cумматор]] | ||
− | # [[Каскадный сумматор]] (0.5) | + | # ''fixed'' [[Каскадный сумматор]] (0.5) |
## англоязычных терминов | ## англоязычных терминов | ||
## Оформить источники информации нормально | ## Оформить источники информации нормально | ||
Строка 76: | Строка 83: | ||
# [[Реализация вычитания сумматором]] | # [[Реализация вычитания сумматором]] | ||
# [[Матричный умножитель]] | # [[Матричный умножитель]] | ||
− | # [[Дерево Уоллеса]] (1) | + | # ''fixed'' [[Дерево Уоллеса]] (1) |
## пункт "определение" не нужен | ## пункт "определение" не нужен | ||
## англоязычных терминов | ## англоязычных терминов | ||
Строка 86: | Строка 93: | ||
## Чуть-чуть увеличить картинки | ## Чуть-чуть увеличить картинки | ||
# [[Контактная схема]] | # [[Контактная схема]] | ||
+ | # [[Триггеры]] | ||
# [[Квантовые гейты]] | # [[Квантовые гейты]] | ||
Строка 99: | Строка 107: | ||
# [[Алгоритм Хаффмана за O(n)]] (1) | # [[Алгоритм Хаффмана за O(n)]] (1) | ||
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок | ## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок | ||
− | # [[Алгоритм Ху-Таккера]] (1) | + | # ''fixed'' [[Алгоритм Ху-Таккера]] (1) |
## Англоязычные термины | ## Англоязычные термины | ||
## Заменить дефис на тире | ## Заменить дефис на тире | ||
Строка 132: | Строка 140: | ||
== 6. Комбинаторика == | == 6. Комбинаторика == | ||
=== Комбинаторные объекты === | === Комбинаторные объекты === | ||
− | # ''' | + | # '''fixed''' [[Комбинаторные объекты]] (6) |
## Правильно оформить англоязычные термины | ## Правильно оформить англоязычные термины | ||
## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством | ## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством | ||
Строка 156: | Строка 164: | ||
<li> [[Получение следующего объекта]] </li> | <li> [[Получение следующего объекта]] </li> | ||
<li> [[Получение предыдущего объекта]] </li> | <li> [[Получение предыдущего объекта]] </li> | ||
− | <li> [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (1) </li> | + | <li> ''fixed'' [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (1) </li> |
# Отформатировать псевдокоды | # Отформатировать псевдокоды | ||
# Мелочи по теху | # Мелочи по теху | ||
Строка 168: | Строка 176: | ||
<li value="14"> [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li> | <li value="14"> [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li> | ||
<li> [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li> | <li> [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li> | ||
− | <li> [[Производящая функция]] (3) </li> | + | <li> ''fixed'' [[Производящая функция]] (3) </li> |
# Оформить правильно англоязычные термины | # Оформить правильно англоязычные термины | ||
# Убрать точки с запятыми из определения | # Убрать точки с запятыми из определения | ||
Строка 185: | Строка 193: | ||
=== Свойства комбинаторных объектов === | === Свойства комбинаторных объектов === | ||
<ol> | <ol> | ||
− | <li value="22"> ''' | + | <li value="22"> '''взяли''' [[Умножение перестановок, обратная перестановка, группа перестановок]] (5) </li> |
# Определение выделить жирным | # Определение выделить жирным | ||
# Англоязычные термины | # Англоязычные термины | ||
Строка 196: | Строка 204: | ||
<li> [[Действие перестановки на набор из элементов, представление в виде циклов]] </li> | <li> [[Действие перестановки на набор из элементов, представление в виде циклов]] </li> | ||
<li> [[Таблица инверсий]] </li> | <li> [[Таблица инверсий]] </li> | ||
− | <li> [[Теорема Кэли]] (1) </li> | + | <li> ''fixed'' [[Теорема Кэли]] (1) </li> |
# Бинарную операцию в группе обозначают не звёздочкой, а кружочком | # Бинарную операцию в группе обозначают не звёздочкой, а кружочком | ||
# Интервики | # Интервики | ||
# Оформить правильно источники информации, добавить см. также | # Оформить правильно источники информации, добавить см. также | ||
# Добавить словесных пояснений происходящего | # Добавить словесных пояснений происходящего | ||
− | <li> ''' | + | <li> '''fixed''' [[Матричное представление перестановок]] (5) </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
Строка 207: | Строка 215: | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач) | # Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач) | ||
− | <li> [[Задача о минимуме/максимуме скалярного произведения]] (2) </li> | + | <li> ''fixed'' [[Задача о минимуме/максимуме скалярного произведения]] (2) </li> |
# Оформить задачу шаблоном Задача | # Оформить задачу шаблоном Задача | ||
# Ссылку в примечании сделать на самом деле примечанием | # Ссылку в примечании сделать на самом деле примечанием | ||
Строка 213: | Строка 221: | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться | # Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться | ||
− | <li> [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li> | + | <li> ''fixed'' [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Определение взять в шаблон | # Определение взять в шаблон | ||
Строка 221: | Строка 229: | ||
== 7. Динамическое программирование == | == 7. Динамическое программирование == | ||
− | :0. ''' | + | :0. '''fixed''' [[Динамическое программирование]] (5) |
:# Добавить известную цитату про ДП | :# Добавить известную цитату про ДП | ||
:# Интервики на NP-полноту | :# Интервики на NP-полноту | ||
Строка 273: | Строка 281: | ||
=== Способы оптимизации методов динамического программирования === | === Способы оптимизации методов динамического программирования === | ||
<ol> | <ol> | ||
− | <li value="10">[[Метод четырех русских для умножения матриц]] (0.5) </li> | + | <li value="10"> ''fixed'' [[Метод четырех русских для умножения матриц]] (0.5) </li> |
# Взять скобки в Tex | # Взять скобки в Tex | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
# Заменить литературу на источники информации | # Заменить литературу на источники информации | ||
− | <li>[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] (3.5) </li> | + | <li> ''fixed'' [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] (3.5) </li> |
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
# Взять константы в Tex | # Взять константы в Tex | ||
# Сделать нормальные картинки (или заменить на таблички) | # Сделать нормальные картинки (или заменить на таблички) | ||
# Заменить источники на источники информации | # Заменить источники на источники информации | ||
− | <li>[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] (1) </li> | + | <li> ''fixed'' [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] (1) </li> |
# Кривая ссылка на оптимальный префиксный код | # Кривая ссылка на оптимальный префиксный код | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
Строка 288: | Строка 296: | ||
# Исправить знаки неравенств | # Исправить знаки неравенств | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
− | <li> ''' | + | <li> '''fixed''' [[Meet-in-the-middle]] (5) </li> |
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
# Добавить примеры задач | # Добавить примеры задач | ||
Строка 299: | Строка 307: | ||
<li> [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li> | <li> [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li> | ||
<li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li> | <li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li> | ||
− | <li> [[Наибольшая общая возрастающая подпоследовательность]] (2) </li> | + | <li> ''fixed'' [[Наибольшая общая возрастающая подпоследовательность]] (2) </li> |
# Переименовать в "Задача о ..." | # Переименовать в "Задача о ..." | ||
# Отформатировать псевдокоды | # Отформатировать псевдокоды | ||
Строка 315: | Строка 323: | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Добавить нормальное объяснение происходящего (и почему это работает) | # Добавить нормальное объяснение происходящего (и почему это работает) | ||
− | <li> ''' | + | <li> '''fixed''' [[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] (5) </li> |
# Взять все переменные в Tex | # Взять все переменные в Tex | ||
# Убрать определение паросочетания | # Убрать определение паросочетания | ||
Строка 333: | Строка 341: | ||
## Оформить правильно см. также и источники информации | ## Оформить правильно см. также и источники информации | ||
## Правильно оформить дроби | ## Правильно оформить дроби | ||
− | # [[Независимые события]] (1) | + | # [[Независимые события]] (1.5) |
## Оформить правильно англоязычные термины | ## Оформить правильно англоязычные термины | ||
## Тире в шаблон, переменные и константы в Tex | ## Тире в шаблон, переменные и константы в Tex | ||
Строка 359: | Строка 367: | ||
## Заменить дефисы на тире, переменные и константы взять в Tex | ## Заменить дефисы на тире, переменные и константы взять в Tex | ||
## Правильно оформить источники информации | ## Правильно оформить источники информации | ||
− | # [[Математическое ожидание случайной величины]] ( | + | # [[Математическое ожидание случайной величины]] (2) |
## Оформить правильно См. также | ## Оформить правильно См. также | ||
## Заменить дроби на \dfrac | ## Заменить дроби на \dfrac | ||
− | # | + | ## Доказать содержательные утверждения |
− | + | # [[Дисперсия случайной величины]] | |
− | + | # [[Ковариация случайных величин]] | |
− | + | # [[Корреляция случайных величин]] | |
− | |||
− | |||
− | |||
− | # [[Ковариация случайных величин]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | # [[Корреляция случайных величин]] | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
# [[Энтропия случайного источника]] (2) | # [[Энтропия случайного источника]] (2) | ||
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное. | ## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное. | ||
Строка 402: | Строка 391: | ||
## Вывод оформить правильно | ## Вывод оформить правильно | ||
## Увеличить дроби | ## Увеличить дроби | ||
− | # [[Арифметическое кодирование]] | + | # [[Арифметическое кодирование]] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
# [[Парадоксы теории вероятностей]] | # [[Парадоксы теории вероятностей]] | ||
# '''!!!''' [[Схема Бернулли]] (5) | # '''!!!''' [[Схема Бернулли]] (5) |
Текущая версия на 19:15, 23 февраля 2017
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)
Обозначением !!! помечены те конспекты, которые точно дадут 5 баллов при их успешном выполнении. Просто выделены, чтобы сразу можно было на них обратить внимание.
1. Отношения
- Определение отношения (0.5)
- Дефисы заменить на тире
- Оформить красиво источники информации
- Английские термины к видам отношений
- Композиция отношений, степерь отношения, обратное отношение (0.5)
- Отформатировать свойства красиво
- Оформить правильно источники информации
- Англ. термины
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- fixed Транзитивный остов (5)
- Отформатировать псевдокод
- Добавить категории
- возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
- если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
- Отформатировать конспект по правилам
2. Булевы функции
- Определение булевой функции
- Побитовые операции
- fixed Суперпозиции (0.5)
- англоязычных терминов
- fixed ДНФ (0.5)
- англоязычных терминов
- писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
- Убрать странные скобки в формулировке теоремы
- Не то выделено жирным в определениях
- fixed Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна (2.5)
- англоязычных терминов
- Жирные определения
- Непонятно, как работает метод Карно, возможно в таблице ошибка
- Двойной номер в одной из табличек Квайна
- Обернуть в tex бинарные операции в методе Квайна
- Все константы и переменные взять в tex
- КНФ
- 2SAT
- fixed Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома (3)
- англоязычных терминов
- написать, почему факт того, что существует полиномиальный алгоритм, интересен
- Ссылку на википедию сделать примечанием
- Добавить ссылки, изменить См. также
- Исправить странное форматирование в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Пороговая функция
- Троичная логика
3. Схемы из функциональных элементов
- fixed Реализация булевой функции схемой из функциональных элементов (1)
- англоязычных терминов (на схемную сложность, глубину схемы)
- Оформить красивее определения из логических элементов
- Сделать красивую табличку
- Источники информации и См. также
- Простейшие методы синтеза схем из функциональных элементов (0.5)
- Изменить знаки неравенств
- Ссылку на метод синтеза схем Шэннона сделать примечанием
- Определение жирным
- Оформить правильно См. также и Источники информации
- Увеличить дроби
- Метод Лупанова синтеза схем (0.5)
- Заменить литературу на источники информации
- Изменить знаки неравенств
- Запятые криво стоят в определении функции g
- Увеличить дроби
- Cумматор
- fixed Каскадный сумматор (0.5)
- англоязычных терминов
- Оформить источники информации нормально
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- fixed Дерево Уоллеса (1)
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
- Оформить правильно Источники информации
- См. также
- Увеличить дроби
- Как-нибудь нормально назвать depth, size и sum
- Чуть-чуть увеличить картинки
- Контактная схема
- Триггеры
- Квантовые гейты
4. Представление информации
5. Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n) (1)
- Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
- fixed Алгоритм Ху-Таккера (1)
- Англоязычные термины
- Заменить дефис на тире
- Сделать красивый список в определении
- Переменные и константы взять в Tex
- Исправить знаки неравенств
- Правильно оформить источники информации
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78 (2)
- Переменные и константы взять в Tex
- Добавить примеры итоговых таблиц
- Рассказать, как декодировать
- Правильно оформить источники информации
- Получше расписать описание алгоритма
- Таблицы сделать красивыми
- Интервики
- Алгоритм LZW
- Алгоритм LZSS
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга (1)
- Англоязычные термины правильно оформить
- Причём там куб?
- Оформить правильно источники информации
- Исправить знаки неравенств
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
6. Комбинаторика
Комбинаторные объекты
- fixed Комбинаторные объекты (6)
- Правильно оформить англоязычные термины
- Привести формулы каждого объекта — общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
- Под каждый комбинаторный объект сделать свой подзаголовк уровня ниже
- Все переменные и константы взять в Tex
- Добавить ссылок по всем объектам в источники информации
- Заменить ссылку на числа Стирлинга ссылкой на конспект
- Заменить дефисы на тире
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Заменить скобки "больше-меньше" на угловые
- Нормальную красивую картинку нарисовать
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- fixed Метод генерации случайной перестановки, алгоритм Фишера-Йетса (1)
- Отформатировать псевдокоды
- Мелочи по теху
- Какие-то пропуски в обосновании
- Дефисы на тире
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- fixed Производящая функция (3)
- Оформить правильно англоязычные термины
- Убрать точки с запятыми из определения
- Все переменные и константы в Tex взять
- Исправить знаки неравенств
- Оформить ссылки примечаниями
- Ссылки и литературу заменить на источники информации
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- взяли Умножение перестановок, обратная перестановка, группа перестановок (5)
- Определение выделить жирным
- Англоязычные термины
- Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
- Отформатировать псевдокоды
- Все переменные и константы взять в Tex
- Оформить правильно источники информации
- Добавить примеров из конспекта групп по теории чисел
- Добавить реккурентную формулу числа инволюций c доказательством
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- fixed Теорема Кэли (1)
- Бинарную операцию в группе обозначают не звёздочкой, а кружочком
- Интервики
- Оформить правильно источники информации, добавить см. также
- Добавить словесных пояснений происходящего
- fixed Матричное представление перестановок (5)
- Англоязычные термины
- Заменить дефисы на тире
- Добавить подробные доказательства утверждений (или пояснить получше уже существующие)
- Оформить правильно источники информации
- Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
- fixed Задача о минимуме/максимуме скалярного произведения (2)
- Оформить задачу шаблоном Задача
- Ссылку в примечании сделать на самом деле примечанием
- Добавить использование этой теоремы (в теории матроидов и теории расписаний)
- Оформить правильно источники информации
- Доказательство плохо разбито на пункты — от нумерации в доказательстве вообще можно избавиться
- fixed Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП (0.5)
- Англоязычные термины
- Определение взять в шаблон
- Заменить дефисы на тире
- Оформить правильно источники информации
7. Динамическое программирование
- 0. fixed Динамическое программирование (5)
- Добавить известную цитату про ДП
- Интервики на NP-полноту
- Картинки криво расположены
- Добавить больше примеров
- Добавить описание принципа оптимальности на подмножествах
- Оформить правильно источники информации
- Добавить про мемоизацию (и желательно что-нибудь разумное)
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе (4)
- Взять задачу в шаблон
- Отформатировать псевдокод
- Обернуть имя функции в тексте в mathrm
- Заменить дефисы на тире
- Добавить см. также и источники информации
- Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
- !!! Задача о расстановке знаков в выражении (6)
- Взять задачу в шаблон
- Исправить знаки неравенств
- Ссылку примечанием оформить нормально
- Взять все переменные и константы в тексте в Tex
- Отформатировать псевдокод
- Табличку нормально оформить
- Описать восстановление ответа
- Источники информации правильно оформить
- Добавить решение задачи без возможности использования скобок
- Задача о порядке перемножения матриц (3)
- Взять переменные и константы в Tex
- Обернуть задачу в шаблон
- Интервики на конспект правильных скобочных последовательностей
- Написать, почему нас не устраивает число Каталана в асимптотике
- Отформатировать псевдокоды
- Оформить правильно источники информации
- Убрать про мемоизацию
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- !!! Задача о рюкзаке (8)
- Взять задачу в шаблон
- Отформатировать псевдокоды
- Заменить дефисы на тире
- Исправить знаки неравенств
- Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
- Сделать итоговую формулу для А c помощью фигурной скобки
- Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
- Понизить уровень заголовков первого уровня
- Оформить правильно источники информации
Способы оптимизации методов динамического программирования
- fixed Метод четырех русских для умножения матриц (0.5)
- Взять скобки в Tex
- Заменить дефисы на тире
- Заменить литературу на источники информации
- fixed Применение метода четырех русских в задачах ДП на примере задачи о НОП (3.5)
- Заменить дефисы на тире
- Взять константы в Tex
- Сделать нормальные картинки (или заменить на таблички)
- Заменить источники на источники информации
- fixed Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза (1)
- Кривая ссылка на оптимальный префиксный код
- Заменить дефисы на тире
- Взять переменные и константы в Tex
- Исправить знаки неравенств
- Оформить правильно источники информации
- fixed Meet-in-the-middle (5)
- Отформатировать псевдокод
- Добавить примеры задач
- Оформить правильно источники информации
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- fixed Наибольшая общая возрастающая подпоследовательность (2)
- Переименовать в "Задача о ..."
- Отформатировать псевдокоды
- Англоязычные термины
- Добавить Шаблон:Задача
- Оформить правильно источники информации
- Задача о наибольшей общей палиндромной подпоследовательности
- !!! Динамическое программирование по профилю (7)
- Англоязычные термины
- Заменить умножение на \cdot
- Заменить дефисы на тире
- Взять переменные и константы в Tex
- Отформатировать псевдокоды
- Добавить ещё примеров
- Оформить правильно источники информации
- Добавить нормальное объяснение происходящего (и почему это работает)
- fixed Динамика по поддеревьям, задача о паросочетании максимального веса в дереве (5)
- Взять все переменные в Tex
- Убрать определение паросочетания
- Отформатировать псевдокод
- Оформить правильно источники информации
- Убрать первый пункт
- Добавить ещё примеров
8. Теория вероятностей
- Вероятностное пространство, элементарный исход, событие (1)
- Англоязычные термины
- Заменить дефисы на тире
- Определения выделить жирным
- Все константы и переменные взять в Tex
- Убрать точки с запятой из определений
- Оформить правильно см. также и источники информации
- Правильно оформить дроби
- Независимые события (1.5)
- Оформить правильно англоязычные термины
- Тире в шаблон, переменные и константы в Tex
- Пример несовместных событий
- Определения выделить жирным
- Заменить все дроби на \dfrac
- Оформить правильно источники информации
- Пример Тетраэдра оформить нормально
- Условная вероятность (0.5)
- Англоязычные термины правильно оформить
- Увеличить дроби
- Переменные и константы взять в Tex
- Оформить правильно источники информации
- Формула полной вероятности
- Формула Байеса
- Дискретная случайная величина (3)
- Англоязычные термины
- Примеры
- Исправить знаки неравенств
- Оформить правильно источники информации, См. также, списки, вообще всё
- Добавить про функцию плотности вероятности
- Независимые случайные величины (1)
- Англоязычные термины
- Заменить ссылку примечанием на интервики
- Заменить дефисы на тире, переменные и константы взять в Tex
- Правильно оформить источники информации
- Математическое ожидание случайной величины (2)
- Оформить правильно См. также
- Заменить дроби на \dfrac
- Доказать содержательные утверждения
- Дисперсия случайной величины
- Ковариация случайных величин
- Корреляция случайных величин
- Энтропия случайного источника (2)
- воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
- В Романовском добавить издание и страницу, источники информации правильно оформить
- Англоязычные термины
- Убрать треугольники из свойств
- Исправить знаки неравенств
- Оформить по правилам
- !!! Симуляция одним распределением другого (7)
- так и нет нормального определения распределения
- список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
- издания и страницы в источниках информации
- Англоязычные термины
- Увеличить дроби, исправить знаки неравенств
- Зачем-то формулы написаны по центру
- Картинки в общем случае криво расположены
- Вывод оформить правильно
- Увеличить дроби
- Арифметическое кодирование
- Парадоксы теории вероятностей
- !!! Схема Бернулли (5)
- запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать
- оформить источник
- Англоязычные термины
- Определение выделить жирным
- Перерисовать картинку
- Исправить знаки неравенств, дроби на \dfrac
- Константы и переменные взять в Tex
- Ссылки на формулы красиво оформить
- Оформить правильно источники информации
- Оформить по правилам
9. Марковские цепи
- !!! Марковская цепь (6)
- два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
- сделать подраздел "циклические классы"
- "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
- Интервики на графы
- Англоязычные термины правильно оформить
- Оформить правильно источники информации
- !!! Теорема о поглощении (6)
- определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
- max -> \max
- в конце какая-то муть. Расписать рассуждения чуть подробнее
- Заменить дефисы на тире
- А что такое непоглощающая матрица?
- Источники информации
- !!! Фундаментальная матрица (5)
- написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
- не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
- получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
- Англоязычные термины
- Определения выделить жирным
- Дефисы на тире, переменные в Tex
- Математическое ожидание времени поглощения (2)
- не везде переменные обернуты в латех
- Оформить правильно Источники информации
- Добавить См. также
- Пояснить подробней переходы
- !!! Расчет вероятности поглощения в состоянии (5)
- куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
- имена переменных из псевдокода в тексте оборачиваются в \mathtt
- оформить псевдокод в виде функций, без всяких println
- оформить нормально источник
- Заголовки первого уровня убрать
- Эргодическая марковская цепь (1)
- определения пересекаются с конспектом про марковские цепи
- Сделать ссылку примечанием
- Заменить дефисы на тире
- Оформить правильно источники информации
- Регулярная марковская цепь (1)
- Переменные взять в Tex
- Оформить правильно источники информации
- Дефисы на тире
- Добавить См. также
- Примеры использования Марковских цепей (1)
- Переменные в Tex
- Заменить литературу на источники информации
- Оформить по правилам
- !!! Скрытые Марковские модели (7)
- можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров
- Переменные и константы взять в Tex
- Ссылку на вики оформить примечанием
- Оформить правильно источники информации
- Исправить небольшую багу в картинке
- Англоязычные термины
- Категории
- !!! Алгоритм Витерби (5)
- "правдоподобная последовательность скрытых состояний" — что такое "наиболее правдоподобная"?
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- а \pi что такое?
- Отформатировать псевдокод
- Англоязычные термины
- Заменить ссылки на источники информации
- Алгоритм "Вперед-Назад" (5)
- Отформатировать псевдокод
- Заменить литературу на источники информации
- Оформить по правилам