Участник:Shersh/Тикеты к 1ому терму — различия между версиями
Shersh (обсуждение | вклад) (→5. Алгоритмы сжатия) |
Shersh (обсуждение | вклад) м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 1ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))) |
||
| (не показано 178 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
Тикеты индексируются как "X-Y", где X {{---}} номер раздела, Y {{---}} номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3) | Тикеты индексируются как "X-Y", где X {{---}} номер раздела, Y {{---}} номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3) | ||
| − | + | Обозначением '''!!!''' помечены те конспекты, которые точно дадут 5 баллов при их успешном выполнении. Просто выделены, чтобы сразу можно было на них обратить внимание. | |
| − | |||
| − | |||
| − | |||
== 1. Отношения == | == 1. Отношения == | ||
| − | # [[Определение отношения]] | + | # [[Определение отношения]] (0.5) |
| − | # [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]] | + | ## Дефисы заменить на тире |
| − | # | + | ## Оформить красиво источники информации |
| − | # | + | ## Английские термины к видам отношений |
| − | + | # [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]] (0.5) | |
| − | + | ## Отформатировать свойства красиво | |
| − | # | + | ## Оформить правильно источники информации |
| − | + | ## Англ. термины | |
| − | + | # [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | |
| − | + | # [[Симметричное отношение]] | |
| − | + | # [[Антисимметричное отношение]] | |
| − | |||
# [[Транзитивное отношение]] | # [[Транзитивное отношение]] | ||
# [[Отношение порядка]] | # [[Отношение порядка]] | ||
# [[Отношение эквивалентности]] | # [[Отношение эквивалентности]] | ||
| − | # | + | # [[Транзитивное замыкание|Транзитивное замыкание отношения]] |
| − | # | + | # [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] |
| − | + | # '''fixed''' [[Транзитивный остов]] (5) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
## Добавить категории | ## Добавить категории | ||
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель" | ## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель" | ||
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец | ## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец | ||
| + | ## Отформатировать конспект по правилам | ||
== 2. Булевы функции == | == 2. Булевы функции == | ||
# [[Определение булевой функции]] | # [[Определение булевой функции]] | ||
| + | # [[Побитовые операции]] | ||
| + | # ''fixed'' [[Суперпозиции]] (0.5) | ||
## англоязычных терминов | ## англоязычных терминов | ||
| − | # | + | # ''fixed'' [[ДНФ]] (0.5) |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## англоязычных терминов | ## англоязычных терминов | ||
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо | ## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо | ||
## Убрать странные скобки в формулировке теоремы | ## Убрать странные скобки в формулировке теоремы | ||
## Не то выделено жирным в определениях | ## Не то выделено жирным в определениях | ||
| − | # [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] | + | # ''fixed'' [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] (2.5) |
## англоязычных терминов | ## англоязычных терминов | ||
## Жирные определения | ## Жирные определения | ||
| + | ## Непонятно, как работает метод Карно, возможно в таблице ошибка | ||
## Двойной номер в одной из табличек Квайна | ## Двойной номер в одной из табличек Квайна | ||
## Обернуть в tex бинарные операции в методе Квайна | ## Обернуть в tex бинарные операции в методе Квайна | ||
## Все константы и переменные взять в tex | ## Все константы и переменные взять в tex | ||
| − | # | + | # [[КНФ]] |
| − | # | + | # [[2SAT]] |
| − | + | # ''fixed'' [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] (3) | |
| − | |||
| − | |||
| − | |||
| − | # '' | ||
## англоязычных терминов | ## англоязычных терминов | ||
## написать, почему факт того, что существует полиномиальный алгоритм, интересен | ## написать, почему факт того, что существует полиномиальный алгоритм, интересен | ||
| Строка 70: | Строка 52: | ||
## Добавить ссылки, изменить См. также | ## Добавить ссылки, изменить См. также | ||
## Исправить странное форматирование в форме Крома | ## Исправить странное форматирование в форме Крома | ||
| − | # | + | # [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Полные системы функций. Теорема Поста о полной системе функций]] | # [[Полные системы функций. Теорема Поста о полной системе функций]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Представление функции класса DM с помощью медианы]] | # [[Представление функции класса DM с помощью медианы]] | ||
| − | # | + | # [[Пороговая функция]] |
| − | # | + | # [[Троичная логика]] |
| − | |||
| − | |||
== 3. Схемы из функциональных элементов == | == 3. Схемы из функциональных элементов == | ||
| − | # [[Реализация булевой функции схемой из функциональных элементов]] | + | # ''fixed'' [[Реализация булевой функции схемой из функциональных элементов]] (1) |
## англоязычных терминов (на схемную сложность, глубину схемы) | ## англоязычных терминов (на схемную сложность, глубину схемы) | ||
## Оформить красивее определения из логических элементов | ## Оформить красивее определения из логических элементов | ||
| − | # [[Простейшие методы синтеза схем из функциональных элементов]] | + | ## Сделать красивую табличку |
| + | ## Источники информации и См. также | ||
| + | # [[Простейшие методы синтеза схем из функциональных элементов]] (0.5) | ||
## Изменить знаки неравенств | ## Изменить знаки неравенств | ||
## Ссылку на метод синтеза схем Шэннона сделать примечанием | ## Ссылку на метод синтеза схем Шэннона сделать примечанием | ||
| − | # [[Метод Лупанова синтеза схем]] | + | ## Определение жирным |
| + | ## Оформить правильно См. также и Источники информации | ||
| + | ## Увеличить дроби | ||
| + | # [[Метод Лупанова синтеза схем]] (0.5) | ||
## Заменить литературу на источники информации | ## Заменить литературу на источники информации | ||
## Изменить знаки неравенств | ## Изменить знаки неравенств | ||
## Запятые криво стоят в определении функции g | ## Запятые криво стоят в определении функции g | ||
| − | # | + | ## Увеличить дроби |
| − | # | + | # [[Cумматор]] |
| − | + | # ''fixed'' [[Каскадный сумматор]] (0.5) | |
| − | |||
## англоязычных терминов | ## англоязычных терминов | ||
## Оформить источники информации нормально | ## Оформить источники информации нормально | ||
| − | # | + | # [[Двоичный каскадный сумматор]] |
| − | # | + | # [[Троичный сумматор]] |
| − | |||
| − | |||
# [[Реализация вычитания сумматором]] | # [[Реализация вычитания сумматором]] | ||
# [[Матричный умножитель]] | # [[Матричный умножитель]] | ||
| + | # ''fixed'' [[Дерево Уоллеса]] (1) | ||
## пункт "определение" не нужен | ## пункт "определение" не нужен | ||
## англоязычных терминов | ## англоязычных терминов | ||
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга | ## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга | ||
| − | ## | + | ## Оформить правильно Источники информации |
| − | ## | + | ## См. также |
| − | # [[ | + | ## Увеличить дроби |
| − | # | + | ## Как-нибудь нормально назвать depth, size и sum |
| − | # | + | ## Чуть-чуть увеличить картинки |
| − | + | # [[Контактная схема]] | |
| + | # [[Триггеры]] | ||
| + | # [[Квантовые гейты]] | ||
== 4. Представление информации == | == 4. Представление информации == | ||
| − | # | + | # [[Кодирование информации]] |
| − | # | + | # [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] |
| − | + | # [[Представление вещественных чисел]] | |
| − | + | # [[Представление символов, таблицы кодировок]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 5. Алгоритмы сжатия == | == 5. Алгоритмы сжатия == | ||
| − | # | + | # [[Алгоритм Хаффмана]] |
| − | # | + | # [[Оптимальное хранение словаря в алгоритме Хаффмана]] |
| − | + | # [[Алгоритм Хаффмана за O(n)]] (1) | |
| − | + | ## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок | |
| − | + | # ''fixed'' [[Алгоритм Ху-Таккера]] (1) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ## | ||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
## Англоязычные термины | ## Англоязычные термины | ||
## Заменить дефис на тире | ## Заменить дефис на тире | ||
## Сделать красивый список в определении | ## Сделать красивый список в определении | ||
## Переменные и константы взять в Tex | ## Переменные и константы взять в Tex | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
## Правильно оформить источники информации | ## Правильно оформить источники информации | ||
| − | # | + | # [[Неравенство Крафта]] |
| − | # | + | # [[Неравенство Макмиллана]] |
| − | + | # [[Код Шеннона]] | |
| − | + | # [[Оптимальный префиксный код с длиной кодового слова не более L бит]] | |
| − | + | # [[Алгоритмы LZ77 и LZ78]] (2) | |
| − | ## | ||
| − | # | ||
## Переменные и константы взять в Tex | ## Переменные и константы взять в Tex | ||
## Добавить примеры итоговых таблиц | ## Добавить примеры итоговых таблиц | ||
## Рассказать, как декодировать | ## Рассказать, как декодировать | ||
## Правильно оформить источники информации | ## Правильно оформить источники информации | ||
| − | |||
## Получше расписать описание алгоритма | ## Получше расписать описание алгоритма | ||
## Таблицы сделать красивыми | ## Таблицы сделать красивыми | ||
## Интервики | ## Интервики | ||
| − | # | + | # [[Алгоритм LZW]] |
| − | # | + | # [[Алгоритм LZSS]] |
| − | + | # [[Преобразование Барроуза-Уилера | Преобразование Барроуза-Уиллера и обратное ему]] | |
| − | + | # [[Преобразование MTF]] | |
| − | # | + | # [[Расстояние Хэмминга]] (1) |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Расстояние Хэмминга]] | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Причём там куб? | ## Причём там куб? | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
| − | # | + | # [[Избыточное кодирование, код Хэмминга]] |
| − | # | + | # [[Гамма-, дельта- и омега-код Элиаса]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== 6. Комбинаторика == | == 6. Комбинаторика == | ||
=== Комбинаторные объекты === | === Комбинаторные объекты === | ||
| − | # ''' | + | # '''fixed''' [[Комбинаторные объекты]] (6) |
## Правильно оформить англоязычные термины | ## Правильно оформить англоязычные термины | ||
## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством | ## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством | ||
| Строка 260: | Строка 149: | ||
## Заменить дефисы на тире | ## Заменить дефисы на тире | ||
# [[Лексикографический порядок]] | # [[Лексикографический порядок]] | ||
| − | # | + | # [[Коды Грея]] |
| − | + | # [[Коды Грея для перестановок]] | |
| − | + | # [[Коды антигрея]] | |
| − | + | # [[Цепные коды]] | |
| − | + | # [[Правильные скобочные последовательности]] | |
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
=== Генерация комбинаторных объектов === | === Генерация комбинаторных объектов === | ||
<ol> | <ol> | ||
| − | <li value="8"> | + | <li value="8"> [[Генерация комбинаторных объектов в лексикографическом порядке]]</li> |
| − | # | + | # Заменить скобки "больше-меньше" на угловые |
| − | + | # Нормальную красивую картинку нарисовать | |
| − | # | + | <li> [[Получение номера по объекту]] </li> |
| − | + | <li> [[Получение объекта по номеру]] </li> | |
| − | + | <li> [[Получение следующего объекта]] </li> | |
| − | <li> | + | <li> [[Получение предыдущего объекта]] </li> |
| − | + | <li> ''fixed'' [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (1) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> '' | ||
| − | |||
| − | |||
# Отформатировать псевдокоды | # Отформатировать псевдокоды | ||
| − | # | + | # Мелочи по теху |
| − | # | + | # Какие-то пропуски в обосновании |
| − | + | # Дефисы на тире | |
| + | <li> [[Методы генерации случайного сочетания]] </li> | ||
</ol> | </ol> | ||
=== Подсчёт числа объектов === | === Подсчёт числа объектов === | ||
<ol> | <ol> | ||
| − | <li value="14"> | + | <li value="14"> [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li> |
| − | + | <li> [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li> | |
| − | + | <li> ''fixed'' [[Производящая функция]] (3) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> [[Производящая функция]] </li> | ||
# Оформить правильно англоязычные термины | # Оформить правильно англоязычные термины | ||
# Убрать точки с запятыми из определения | # Убрать точки с запятыми из определения | ||
| Строка 383: | Строка 184: | ||
# Ссылки и литературу заменить на источники информации | # Ссылки и литературу заменить на источники информации | ||
<li> [[Лемма Бёрнсайда и Теорема Пойа]] </li> | <li> [[Лемма Бёрнсайда и Теорема Пойа]] </li> | ||
| − | <li> | + | <li> [[Задача об ожерельях]] </li> |
| − | + | <li> [[Числа Стирлинга первого рода]] </li> | |
| − | + | <li> [[Числа Стирлинга второго рода]] </li> | |
| − | + | <li> [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]] </li> | |
| − | + | <li> [[Числа Каталана]] </li> | |
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</ol> | </ol> | ||
=== Свойства комбинаторных объектов === | === Свойства комбинаторных объектов === | ||
<ol> | <ol> | ||
| − | <li value="22"> ''' | + | <li value="22"> '''взяли''' [[Умножение перестановок, обратная перестановка, группа перестановок]] (5) </li> |
# Определение выделить жирным | # Определение выделить жирным | ||
# Англоязычные термины | # Англоязычные термины | ||
| Строка 421: | Строка 201: | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Добавить примеров из конспекта групп по теории чисел | # Добавить примеров из конспекта групп по теории чисел | ||
| − | <li> | + | # Добавить реккурентную формулу числа инволюций c доказательством |
| − | + | <li> [[Действие перестановки на набор из элементов, представление в виде циклов]] </li> | |
| − | + | <li> [[Таблица инверсий]] </li> | |
| − | + | <li> ''fixed'' [[Теорема Кэли]] (1) </li> | |
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> [[Теорема Кэли]] </li> | ||
# Бинарную операцию в группе обозначают не звёздочкой, а кружочком | # Бинарную операцию в группе обозначают не звёздочкой, а кружочком | ||
# Интервики | # Интервики | ||
# Оформить правильно источники информации, добавить см. также | # Оформить правильно источники информации, добавить см. также | ||
# Добавить словесных пояснений происходящего | # Добавить словесных пояснений происходящего | ||
| − | <li> ''' | + | <li> '''fixed''' [[Матричное представление перестановок]] (5) </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
| − | # Добавить подробные доказательства | + | # Добавить подробные доказательства утверждений (или пояснить получше уже существующие) |
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач) | # Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач) | ||
| − | <li> [[Задача о минимуме/максимуме скалярного произведения]] </li> | + | <li> ''fixed'' [[Задача о минимуме/максимуме скалярного произведения]] (2) </li> |
# Оформить задачу шаблоном Задача | # Оформить задачу шаблоном Задача | ||
# Ссылку в примечании сделать на самом деле примечанием | # Ссылку в примечании сделать на самом деле примечанием | ||
| Строка 453: | Строка 221: | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
# Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться | # Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться | ||
| − | <li> [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] </li> | + | <li> ''fixed'' [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li> |
# Англоязычные термины | # Англоязычные термины | ||
# Определение взять в шаблон | # Определение взять в шаблон | ||
| Строка 461: | Строка 229: | ||
== 7. Динамическое программирование == | == 7. Динамическое программирование == | ||
| − | :0. ''' | + | :0. '''fixed''' [[Динамическое программирование]] (5) |
:# Добавить известную цитату про ДП | :# Добавить известную цитату про ДП | ||
:# Интервики на NP-полноту | :# Интервики на NP-полноту | ||
| Строка 470: | Строка 238: | ||
:# Добавить про мемоизацию (и желательно что-нибудь разумное) | :# Добавить про мемоизацию (и желательно что-нибудь разумное) | ||
=== Классические задачи динамического программирования === | === Классические задачи динамического программирования === | ||
| − | # | + | # [[Кратчайший путь в ациклическом графе]] |
| − | + | # [[Задача о числе путей в ациклическом графе]] (4) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Задача о числе путей в ациклическом графе]] | ||
## Взять задачу в шаблон | ## Взять задачу в шаблон | ||
## Отформатировать псевдокод | ## Отформатировать псевдокод | ||
| Строка 484: | Строка 245: | ||
## Заменить дефисы на тире | ## Заменить дефисы на тире | ||
## Добавить см. также и источники информации | ## Добавить см. также и источники информации | ||
| − | # '''!!!''' [[Задача о расстановке знаков в выражении]] | + | ## Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями |
| + | # '''!!!''' [[Задача о расстановке знаков в выражении]] (6) | ||
## Взять задачу в шаблон | ## Взять задачу в шаблон | ||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
| Строка 493: | Строка 255: | ||
## Описать восстановление ответа | ## Описать восстановление ответа | ||
## Источники информации правильно оформить | ## Источники информации правильно оформить | ||
| − | # | + | ## Добавить решение задачи без возможности использования скобок |
| + | # [[Задача о порядке перемножения матриц]] (3) | ||
## Взять переменные и константы в Tex | ## Взять переменные и константы в Tex | ||
## Обернуть задачу в шаблон | ## Обернуть задачу в шаблон | ||
| Строка 501: | Строка 264: | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Убрать про мемоизацию | ## Убрать про мемоизацию | ||
| − | # | + | # [[Задача о наибольшей общей подпоследовательности]] |
| − | # | + | # [[Задача о наибольшей возрастающей подпоследовательности]] |
| − | + | # [[Задача коммивояжера, ДП по подмножествам]] | |
| − | + | # [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | |
| − | + | # '''!!!''' [[Задача о рюкзаке]] (8) | |
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # '''!!!''' [[Задача о рюкзаке]] | ||
## Взять задачу в шаблон | ## Взять задачу в шаблон | ||
## Отформатировать псевдокоды | ## Отформатировать псевдокоды | ||
| Строка 545: | Строка 278: | ||
## Понизить уровень заголовков первого уровня | ## Понизить уровень заголовков первого уровня | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| − | === Способы оптимизации | + | |
| + | === Способы оптимизации методов динамического программирования === | ||
<ol> | <ol> | ||
| − | <li value="10">[[Метод четырех русских для умножения матриц]] </li> | + | <li value="10"> ''fixed'' [[Метод четырех русских для умножения матриц]] (0.5) </li> |
# Взять скобки в Tex | # Взять скобки в Tex | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
# Заменить литературу на источники информации | # Заменить литературу на источники информации | ||
| − | <li>[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] </li> | + | <li> ''fixed'' [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] (3.5) </li> |
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
# Взять константы в Tex | # Взять константы в Tex | ||
# Сделать нормальные картинки (или заменить на таблички) | # Сделать нормальные картинки (или заменить на таблички) | ||
# Заменить источники на источники информации | # Заменить источники на источники информации | ||
| − | <li>[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] </li> | + | <li> ''fixed'' [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] (1) </li> |
# Кривая ссылка на оптимальный префиксный код | # Кривая ссылка на оптимальный префиксный код | ||
# Заменить дефисы на тире | # Заменить дефисы на тире | ||
| Строка 562: | Строка 296: | ||
# Исправить знаки неравенств | # Исправить знаки неравенств | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
| − | <li> ''' | + | <li> '''fixed''' [[Meet-in-the-middle]] (5) </li> |
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
# Добавить примеры задач | # Добавить примеры задач | ||
| Строка 570: | Строка 304: | ||
=== Другие задачи === | === Другие задачи === | ||
<ol> | <ol> | ||
| − | <li value="14"> | + | <li value="14"> [[Задача о расстоянии Дамерау-Левенштейна]] </li> |
| − | + | <li> [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li> | |
| − | + | <li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li> | |
| − | + | <li> ''fixed'' [[Наибольшая общая возрастающая подпоследовательность]] (2) </li> | |
| − | + | # Переименовать в "Задача о ..." | |
| − | + | # Отформатировать псевдокоды | |
| − | |||
| − | <li> | ||
| − | |||
| − | <li> | ||
| − | # | ||
# Англоязычные термины | # Англоязычные термины | ||
| − | + | # Добавить Шаблон:Задача | |
| − | |||
| − | # Добавить | ||
| − | |||
| − | |||
| − | |||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
| − | <li> '''!!!''' [[Динамическое программирование по профилю]] </li> | + | <li> [[Задача о наибольшей общей палиндромной подпоследовательности]] </li> |
| + | <li> '''!!!''' [[Динамическое программирование по профилю]] (7) </li> | ||
# Англоязычные термины | # Англоязычные термины | ||
# Заменить умножение на \cdot | # Заменить умножение на \cdot | ||
| Строка 597: | Строка 322: | ||
# Добавить ещё примеров | # Добавить ещё примеров | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
| − | <li>[[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] </li> | + | # Добавить нормальное объяснение происходящего (и почему это работает) |
| + | <li> '''fixed''' [[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] (5) </li> | ||
# Взять все переменные в Tex | # Взять все переменные в Tex | ||
# Убрать определение паросочетания | # Убрать определение паросочетания | ||
# Отформатировать псевдокод | # Отформатировать псевдокод | ||
# Оформить правильно источники информации | # Оформить правильно источники информации | ||
| + | # Убрать первый пункт | ||
| + | # Добавить ещё примеров | ||
</ol> | </ol> | ||
== 8. Теория вероятностей == | == 8. Теория вероятностей == | ||
| − | # [[Вероятностное пространство, элементарный исход, событие]] | + | # [[Вероятностное пространство, элементарный исход, событие]] (1) |
## Англоязычные термины | ## Англоязычные термины | ||
## Заменить дефисы на тире | ## Заменить дефисы на тире | ||
| Строка 612: | Строка 340: | ||
## Убрать точки с запятой из определений | ## Убрать точки с запятой из определений | ||
## Оформить правильно см. также и источники информации | ## Оформить правильно см. также и источники информации | ||
| − | # [[Независимые события]] | + | ## Правильно оформить дроби |
| + | # [[Независимые события]] (1.5) | ||
## Оформить правильно англоязычные термины | ## Оформить правильно англоязычные термины | ||
## Тире в шаблон, переменные и константы в Tex | ## Тире в шаблон, переменные и константы в Tex | ||
## Пример несовместных событий | ## Пример несовместных событий | ||
## Определения выделить жирным | ## Определения выделить жирным | ||
| − | ## Заменить все дроби на \ | + | ## Заменить все дроби на \dfrac |
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Пример Тетраэдра оформить нормально | ## Пример Тетраэдра оформить нормально | ||
| − | # [[Условная вероятность]] | + | # [[Условная вероятность]] (0.5) |
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Увеличить дроби | ## Увеличить дроби | ||
## Переменные и константы взять в Tex | ## Переменные и константы взять в Tex | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| − | # [[Формула полной вероятности]] | + | # [[Формула полной вероятности]] |
| − | # | + | # [[Формула Байеса]] |
| − | + | # [[Дискретная случайная величина]] (3) | |
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
## Англоязычные термины | ## Англоязычные термины | ||
## Примеры | ## Примеры | ||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
| − | ## Оформить правильно источники информации | + | ## Оформить правильно источники информации, См. также, списки, вообще всё |
## Добавить про функцию плотности вероятности | ## Добавить про функцию плотности вероятности | ||
| − | # [[Независимые случайные величины]] | + | # [[Независимые случайные величины]] (1) |
## Англоязычные термины | ## Англоязычные термины | ||
## Заменить ссылку примечанием на интервики | ## Заменить ссылку примечанием на интервики | ||
## Заменить дефисы на тире, переменные и константы взять в Tex | ## Заменить дефисы на тире, переменные и константы взять в Tex | ||
## Правильно оформить источники информации | ## Правильно оформить источники информации | ||
| − | # | + | # [[Математическое ожидание случайной величины]] (2) |
| − | ## | + | ## Оформить правильно См. также |
| − | ## Заменить | + | ## Заменить дроби на \dfrac |
| − | + | ## Доказать содержательные утверждения | |
| − | + | # [[Дисперсия случайной величины]] | |
| − | ## | ||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Ковариация случайных величин]] | # [[Ковариация случайных величин]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
# [[Корреляция случайных величин]] | # [[Корреляция случайных величин]] | ||
| − | + | # [[Энтропия случайного источника]] (2) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Энтропия случайного источника]] | ||
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное. | ## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное. | ||
## В Романовском добавить издание и страницу, источники информации правильно оформить | ## В Романовском добавить издание и страницу, источники информации правильно оформить | ||
| Строка 679: | Строка 380: | ||
## Убрать треугольники из свойств | ## Убрать треугольники из свойств | ||
## Исправить знаки неравенств | ## Исправить знаки неравенств | ||
| − | # '''!!!''' [[Симуляция одним распределением другого]] | + | ## Оформить по правилам |
| + | # '''!!!''' [[Симуляция одним распределением другого]] (7) | ||
## так и нет нормального определения распределения | ## так и нет нормального определения распределения | ||
## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы | ## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы | ||
| Строка 690: | Строка 392: | ||
## Увеличить дроби | ## Увеличить дроби | ||
# [[Арифметическое кодирование]] | # [[Арифметическое кодирование]] | ||
| − | # | + | # [[Парадоксы теории вероятностей]] |
| − | + | # '''!!!''' [[Схема Бернулли]] (5) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # '''!!!''' [[Схема Бернулли]] | ||
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать | ## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать | ||
## оформить источник | ## оформить источник | ||
| Строка 710: | Строка 399: | ||
## Определение выделить жирным | ## Определение выделить жирным | ||
## Перерисовать картинку | ## Перерисовать картинку | ||
| − | ## Исправить знаки неравенств | + | ## Исправить знаки неравенств, дроби на \dfrac |
## Константы и переменные взять в Tex | ## Константы и переменные взять в Tex | ||
## Ссылки на формулы красиво оформить | ## Ссылки на формулы красиво оформить | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| + | ## Оформить по правилам | ||
== 9. Марковские цепи == | == 9. Марковские цепи == | ||
| − | + | # '''!!!''' [[Марковская цепь]] (6) | |
| − | # '''!!!''' [[Марковская цепь]] | ||
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому) | ## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому) | ||
## сделать подраздел "циклические классы" | ## сделать подраздел "циклические классы" | ||
| Строка 724: | Строка 413: | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| − | # '''!!!''' [[Теорема о поглощении]] | + | # '''!!!''' [[Теорема о поглощении]] (6) |
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку. | ## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку. | ||
## max -> \max | ## max -> \max | ||
| Строка 731: | Строка 420: | ||
## А что такое непоглощающая матрица? | ## А что такое непоглощающая матрица? | ||
## Источники информации | ## Источники информации | ||
| − | # '''!!!''' [[Фундаментальная матрица]] | + | # '''!!!''' [[Фундаментальная матрица]] (5) |
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется. | ## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется. | ||
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями» | ## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями» | ||
| Строка 738: | Строка 427: | ||
## Определения выделить жирным | ## Определения выделить жирным | ||
## Дефисы на тире, переменные в Tex | ## Дефисы на тире, переменные в Tex | ||
| − | # [[Математическое ожидание времени поглощения]] | + | # [[Математическое ожидание времени поглощения]] (2) |
## не везде переменные обернуты в латех | ## не везде переменные обернуты в латех | ||
| − | # '''!!!''' [[Расчет вероятности поглощения в состоянии]] | + | ## Оформить правильно Источники информации |
| + | ## Добавить См. также | ||
| + | ## Пояснить подробней переходы | ||
| + | # '''!!!''' [[Расчет вероятности поглощения в состоянии]] (5) | ||
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится. | ## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится. | ||
| − | ## имена переменных в тексте оборачиваются в | + | ## имена переменных из псевдокода в тексте оборачиваются в \mathtt |
## оформить псевдокод в виде функций, без всяких println | ## оформить псевдокод в виде функций, без всяких println | ||
## оформить нормально источник | ## оформить нормально источник | ||
| − | |||
## Заголовки первого уровня убрать | ## Заголовки первого уровня убрать | ||
| − | # [[Эргодическая марковская цепь]] | + | # [[Эргодическая марковская цепь]] (1) |
## определения пересекаются с конспектом про марковские цепи | ## определения пересекаются с конспектом про марковские цепи | ||
## Сделать ссылку примечанием | ## Сделать ссылку примечанием | ||
## Заменить дефисы на тире | ## Заменить дефисы на тире | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| − | # [[Регулярная марковская цепь]] | + | # [[Регулярная марковская цепь]] (1) |
## Переменные взять в Tex | ## Переменные взять в Tex | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
| − | # [[Примеры использования Марковских цепей]] | + | ## Дефисы на тире |
| + | ## Добавить См. также | ||
| + | # [[Примеры использования Марковских цепей]] (1) | ||
## Переменные в Tex | ## Переменные в Tex | ||
## Заменить литературу на источники информации | ## Заменить литературу на источники информации | ||
| − | # '''!!!''' [[Скрытые Марковские модели]] | + | ## Оформить по правилам |
| + | # '''!!!''' [[Скрытые Марковские модели]] (7) | ||
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров | ## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров | ||
## Переменные и константы взять в Tex | ## Переменные и константы взять в Tex | ||
| Строка 765: | Строка 459: | ||
## Исправить небольшую багу в картинке | ## Исправить небольшую багу в картинке | ||
## Англоязычные термины | ## Англоязычные термины | ||
| − | # '''!!!''' [[Алгоритм Витерби]] | + | ## Категории |
| + | # '''!!!''' [[Алгоритм Витерби]] (5) | ||
## "правдоподобная последовательность скрытых состояний" {{---}} что такое "наиболее правдоподобная"? | ## "правдоподобная последовательность скрытых состояний" {{---}} что такое "наиболее правдоподобная"? | ||
## имена переменных в тексте оборачиваются в \mathrm или \mathtt | ## имена переменных в тексте оборачиваются в \mathrm или \mathtt | ||
| Строка 772: | Строка 467: | ||
## Англоязычные термины | ## Англоязычные термины | ||
## Заменить ссылки на источники информации | ## Заменить ссылки на источники информации | ||
| − | # [[Алгоритм "Вперед-Назад"]] | + | # [[Алгоритм "Вперед-Назад"]] (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)
- Отформатировать псевдокод
- Заменить литературу на источники информации
- Оформить по правилам
