Участник:Shersh/Тикеты к 1ому терму — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела == 1...»)
 
м (Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 1ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно)))
 
(не показаны 252 промежуточные версии этого же участника)
Строка 1: Строка 1:
−
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела
+
Тикеты индексируются как "X-Y", где X {{---}} номер раздела, Y {{---}} номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)
 +
 
 +
Обозначением '''!!!''' помечены те конспекты, которые точно дадут 5 баллов при их успешном выполнении. Просто выделены, чтобы сразу можно было на них обратить внимание.
 +
 
 
== 1. Отношения ==
 
== 1. Отношения ==
−
# '''взяли''' [[Определение отношения]]
+
# [[Определение отношения]] (0.5)
−
## Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
+
## Дефисы заменить на тире
−
## На виды и примеры отношений дать внутренние ссылки
+
## Оформить красиво источники информации
−
## англоязычные термины
+
## Английские термины к видам отношений
−
## пункт "Определение" не нужен, см. правила форматирования конспектов
+
# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]] (0.5)
−
# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]
+
## Отформатировать свойства красиво
−
## см. пункт 1.1
+
## Оформить правильно источники информации
−
## англоязычные термины
+
## Англ. термины
 
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
−
## англоязычные термины
 
−
## добавить внутренних ссылок на эквивдентность, порядки и т.д.
 
 
# [[Симметричное отношение]]
 
# [[Симметричное отношение]]
−
## англоязычные термины
 
 
# [[Антисимметричное отношение]]
 
# [[Антисимметричное отношение]]
−
## англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
 
 
# [[Транзитивное отношение]]
 
# [[Транзитивное отношение]]
−
## англоязычные термины
 
 
# [[Отношение порядка]]
 
# [[Отношение порядка]]
−
## англоязычные термины
 
 
# [[Отношение эквивалентности]]
 
# [[Отношение эквивалентности]]
−
## пункт "определение" не нужен
 
−
## англоязычные термины
 
 
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]
 
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]
−
## англоязычные термины
+
# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
−
# '''взяли''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
+
# '''fixed''' [[Транзитивный остов]] (5)
−
## пункт "Задача" не нужен
+
## Отформатировать псевдокод
−
## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
+
## Добавить категории
−
# '''!!!''' [[Транзитивный остов]]
 
 
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
 
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
 
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
 
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
−
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений
+
## Отформатировать конспект по правилам
  
 
== 2. Булевы функции ==
 
== 2. Булевы функции ==
 
# [[Определение булевой функции]]
 
# [[Определение булевой функции]]
 +
# [[Побитовые операции]]
 +
# ''fixed'' [[Суперпозиции]] (0.5)
 
## англоязычных терминов
 
## англоязычных терминов
−
## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.
+
# ''fixed'' [[ДНФ]] (0.5)
−
# [[Суперпозиции]]
 
−
## англоязычных терминов
 
−
# [[ДНФ]]
 
 
## англоязычных терминов
 
## англоязычных терминов
 
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
 
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
−
# [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
+
## Убрать странные скобки в формулировке теоремы
 +
## Не то выделено жирным в определениях
 +
# ''fixed'' [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] (2.5)
 
## англоязычных терминов
 
## англоязычных терминов
 +
## Жирные определения
 +
## Непонятно, как работает метод Карно, возможно в таблице ошибка
 +
## Двойной номер в одной из табличек Квайна
 +
## Обернуть в tex бинарные операции в методе Квайна
 +
## Все константы и переменные взять в tex
 
# [[КНФ]]
 
# [[КНФ]]
−
## англоязычных терминов
+
# [[2SAT]]
−
## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
+
# ''fixed'' [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] (3)
−
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 
 
## англоязычных терминов
 
## англоязычных терминов
 
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
 
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
 +
## Ссылку на википедию сделать примечанием
 +
## Добавить ссылки, изменить См. также
 +
## Исправить странное форматирование в форме Крома
 
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
−
## англоязычных терминов
 
−
## "Предпосылки" — странное название, переименовать в "Полнота", например
 
 
# [[Полные системы функций. Теорема Поста о полной системе функций]]
 
# [[Полные системы функций. Теорема Поста о полной системе функций]]
−
## англоязычных терминов
 
 
# [[Представление функции класса DM с помощью медианы]]
 
# [[Представление функции класса DM с помощью медианы]]
 
# [[Пороговая функция]]
 
# [[Пороговая функция]]
 +
# [[Троичная логика]]
  
 
== 3. Схемы из функциональных элементов ==
 
== 3. Схемы из функциональных элементов ==
−
# [[Реализация булевой функции схемой из функциональных элементов]]
+
# ''fixed'' [[Реализация булевой функции схемой из функциональных элементов]] (1)
 
## англоязычных терминов (на схемную сложность, глубину схемы)
 
## англоязычных терминов (на схемную сложность, глубину схемы)
−
# [[Метод Лупанова синтеза схем]]
+
## Оформить красивее определения из логических элементов
 +
## Сделать красивую табличку
 +
## Источники информации и См. также
 +
# [[Простейшие методы синтеза схем из функциональных элементов]] (0.5)
 +
## Изменить знаки неравенств
 +
## Ссылку на метод синтеза схем Шэннона сделать примечанием
 +
## Определение жирным
 +
## Оформить правильно См. также и Источники информации
 +
## Увеличить дроби
 +
# [[Метод Лупанова синтеза схем]] (0.5)
 +
## Заменить литературу на источники информации
 +
## Изменить знаки неравенств
 +
## Запятые криво стоят в определении функции g
 +
## Увеличить дроби
 
# [[Cумматор]]
 
# [[Cумматор]]
 +
# ''fixed'' [[Каскадный сумматор]] (0.5)
 
## англоязычных терминов  
 
## англоязычных терминов  
−
# [[Каскадный сумматор]]
+
## Оформить источники информации нормально
−
## англоязычных терминов
 
 
# [[Двоичный каскадный сумматор]]
 
# [[Двоичный каскадный сумматор]]
−
## англоязычных терминов
+
# [[Троичный сумматор]]
−
## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
 
 
# [[Реализация вычитания сумматором]]
 
# [[Реализация вычитания сумматором]]
 
# [[Матричный умножитель]]
 
# [[Матричный умножитель]]
 +
# ''fixed'' [[Дерево Уоллеса]] (1)
 
## пункт "определение" не нужен
 
## пункт "определение" не нужен
 
## англоязычных терминов
 
## англоязычных терминов
 
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
 
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
−
# [[Дерево Уоллеса]]
+
## Оформить правильно Источники информации
−
## пункт "определение" не нужен
+
## См. также
−
## англоязычных терминов
+
## Увеличить дроби
−
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
+
## Как-нибудь нормально назвать depth, size и sum
 +
## Чуть-чуть увеличить картинки
 +
# [[Контактная схема]]
 +
# [[Триггеры]]
 +
# [[Квантовые гейты]]
  
−
== '''взяли''' 4. Представление информации ==
+
== 4. Представление информации ==
 
# [[Кодирование информации]]
 
# [[Кодирование информации]]
 
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
# [[Представление вещественных чисел]]
 
# [[Представление вещественных чисел]]
 
# [[Представление символов, таблицы кодировок]]
 
# [[Представление символов, таблицы кодировок]]
−
## сюда неплохо было бы добавить пример на python с созданием ''юникодной'' строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length
 
  
 
== 5. Алгоритмы сжатия ==
 
== 5. Алгоритмы сжатия ==
−
# '''взяли''' [[Алгоритм Хаффмана]]
+
# [[Алгоритм Хаффмана]]
−
## "Использует только частоту появления одинаковых байт в изображении." што
+
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
−
## ссылки на википедию, русскую и английскую
+
# [[Алгоритм Хаффмана за O(n)]] (1)
−
## внутренние ссылки на префиксный код и все такое.
+
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
−
# [[Алгоритм Ху-Таккера]]
+
# ''fixed'' [[Алгоритм Ху-Таккера]] (1)
 +
## Англоязычные термины
 +
## Заменить дефис на тире
 +
## Сделать красивый список в определении
 +
## Переменные и константы взять в Tex
 +
## Исправить знаки неравенств
 +
## Правильно оформить источники информации
 
# [[Неравенство Крафта]]
 
# [[Неравенство Крафта]]
−
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
 
−
## А зачем оно нужно? Просто интересный факт?
 
 
# [[Неравенство Макмиллана]]
 
# [[Неравенство Макмиллана]]
−
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
+
# [[Код Шеннона]]
−
## А зачем оно нужно? Просто интересный факт?
+
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]
 +
# [[Алгоритмы LZ77 и LZ78]] (2)
 +
## Переменные и константы взять в Tex
 +
## Добавить примеры итоговых таблиц
 +
## Рассказать, как декодировать
 +
## Правильно оформить источники информации
 +
## Получше расписать описание алгоритма
 +
## Таблицы сделать красивыми
 +
## Интервики
 
# [[Алгоритм LZW]]
 
# [[Алгоритм LZW]]
−
# [[Алгоритмы LZ77 и LZ78]]
+
# [[Алгоритм LZSS]]
−
# '''взяли''' [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
+
# [[Преобразование Барроуза-Уилера | Преобразование Барроуза-Уиллера и обратное ему]]
 
# [[Преобразование MTF]]
 
# [[Преобразование MTF]]
−
# [[Расстояние Хэмминга]]
+
# [[Расстояние Хэмминга]] (1)
 +
## Англоязычные термины правильно оформить
 +
## Причём там куб?
 +
## Оформить правильно источники информации
 +
## Исправить знаки неравенств
 
# [[Избыточное кодирование, код Хэмминга]]
 
# [[Избыточное кодирование, код Хэмминга]]
 +
# [[Гамма-, дельта- и омега-код Элиаса]]
  
−
== 6. Комбинаторика ==
+
== 6. Комбинаторика ==
−
# ''fixed'' [[Комбинаторные объекты]]
+
=== Комбинаторные объекты ===
−
## пункт "определение" не нужен
+
# '''fixed''' [[Комбинаторные объекты]] (6)
−
# ''взяли'' [[Лексикографический порядок]]
+
## Правильно оформить англоязычные термины
−
## собственно определения лексикографического порядка тут и нет. англоязычный термин.
+
## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
−
## ссылку на английскую википедию
+
## Под каждый комбинаторный объект сделать свой подзаголовк уровня ниже
−
## Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
+
## Все переменные и константы взять в Tex
−
## return <, return = и т.п. выглядят ужасно. Сделать return LESS, return EQUAL и т.п.
+
## Добавить ссылок по всем объектам в источники информации
−
# ''fixed'' [[Формула включения-исключения]]
+
## Заменить ссылку на числа Стирлинга ссылкой на конспект
−
## Перед открывающей скобкой нужен пробел
+
## Заменить дефисы на тире
−
## ссылки на ангийскую вики
+
# [[Лексикографический порядок]]
−
# ''fixed'' [[Генерация комбинаторных объектов в лексикографическом порядке]]
+
# [[Коды Грея]]
−
## отдельный раздел "определение" не нужен, перенести в заголовок
 
−
## псевдокод генерации некрасивый, оформить его в соответствии с правилами
 
−
## привести пример генерации для сочетаний, раз тут алгоритм для сочетаний, а не для перестановок
 
−
# '''fixed''' [[Получение номера по объекту]]
 
−
## В псевдокоде явно какой-то баг: was[i] = true устанавливается внутри внутреннего цикла, не исключено, что есть еще баги
 
−
## В последнем псевдокоде зачем-то фигурные скобки. Также ^ традиционно означает xor, так что лучше использовать 2 ** x или pow(2, x) для обозначения степени.
 
−
# ''fixed'' [[Получение объекта по номеру]]
 
−
## "В начале каждого шага numOfObject — номер комбинаторного объекта среди объектов с заданным префиксом." — с заданным — это с каким?
 
−
## опять в коде чередуются использования табов и фигурных скобок для отделения блоков. Оставить только табы.
 
−
## Аналогично предыдущим замечаниям про xor
 
−
# '''fixed''' [[Получение следующего объекта]]
 
−
## дополнить генерацией следующего сочетания, разбиения на сумму, скобочной последовательности и мультиперестановки.
 
−
# '''взяли''' [[Коды Грея]]
 
−
## отдельный раздел "определение" не нужен
 
−
## картинку с построением, имхо, надо немного увеличить
 
−
## а что такое паразитные состояния? В общем, про применение надо попонятнее написать. И вообще про это в разделе "применение" надо написать
 
−
## "Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. " — если не пишется про это в конспекте, надо кинуть внешнюю ссылку хотя бы.
 
−
## В применении надо написать хотя бы немного пояснений, а то применяться-то применяется, а как конкретно — непонятно
 
 
# [[Коды Грея для перестановок]]
 
# [[Коды Грея для перестановок]]
−
## отдельный раздел "определение" не нужен
+
# [[Коды антигрея]]
−
# '''взяли''' [[Коды антигрея]]
 
−
## Аналогичну пункту 8, "Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность. " — а как конкретно он применяется для выявления поломки?
 
−
## "Заметим, что для n > 2 невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2. " — ээ, а для n = 2 возмножно?
 
−
## Для черточки над G надо использовать не bar, а overline
 
 
# [[Цепные коды]]
 
# [[Цепные коды]]
−
## ссылку на хоть какие-нибудь источники
 
−
## а зачем они нужны?
 
 
# [[Правильные скобочные последовательности]]
 
# [[Правильные скобочные последовательности]]
−
## англоязычные термины
 
−
## выделить в псевдокоде ключевые слова жирным
 
−
## Обозначить биномиальные коэффециенты нормально (не <tex>C_n^k</tex>, а <tex>\binom{n}{k}</tex>)
 
−
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
 
−
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
−
## убрать пункт "постановка задачи", вынести в заголовок
 
−
# [[Методы генерации случайного сочетания]]
 
−
## убрать пункт "постановка задачи", вынести в заголовок
 
−
## что-то описание алгоритма не очень соответствует псевдокоду (для O(n^2))
 
−
# [[Таблица инверсий]]
 
−
# [[Умножение перестановок, обратная перестановка, группа перестановок]]
 
−
## Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.
 
−
## ссылку на русскую и английскую википедию, на симметрическую группу
 
−
# [[Теорема Кэли]]
 
−
# [[Матричное представление перестановок]]
 
−
# [[Задача о минимуме/максимуме скалярного произведения]]
 
−
## непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть
 
−
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
−
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 
−
# [[Производящая функция]]
 
−
# '''взяли''' [[Лемма Бёрнсайда и Теорема Пойа]]
 
−
## сюда добавить категорию "Теория Групп", она где-то есть на конспектах
 
−
## для сумм надо юзать \limits
 
−
## В теореме Пойа как-то неожиданно появляется группа перестановок, в ее условии тут это почему-то явно не сказано
 
−
## Можно добавить пример подсчета количества различных раскрасок кубика в k цветов. Раскраски эквивалентны, если одну можно получить из другой поворотами кубика.
 
−
# '''взяли''' [[Задача об ожерельях]]
 
−
## а если можно делать не только сдвиги, а еще и отражения? (это называется bracelets: https://en.wikipedia.org/wiki/Necklace_(combinatorics) )
 
−
## ссылки в статье почему-то оформлены как внешние, хотя должны быть внутренними
 
−
## lcm и gcd обернуть в \operatorname или \mathrm
 
  
−
== 7. [[Динамическое программирование]] ==
+
=== Генерация комбинаторных объектов ===
 +
<ol>
 +
<li value="8"> [[Генерация комбинаторных объектов в лексикографическом порядке]]</li>
 +
# Заменить скобки "больше-меньше" на угловые
 +
# Нормальную красивую картинку нарисовать
 +
<li> [[Получение номера по объекту]] </li>
 +
<li> [[Получение объекта по номеру]] </li>
 +
<li> [[Получение следующего объекта]] </li>
 +
<li> [[Получение предыдущего объекта]] </li>
 +
<li> ''fixed'' [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (1) </li>
 +
# Отформатировать псевдокоды
 +
# Мелочи по теху
 +
# Какие-то пропуски в обосновании
 +
# Дефисы на тире
 +
<li> [[Методы генерации случайного сочетания]] </li>
 +
</ol>
 +
 
 +
=== Подсчёт числа объектов ===
 +
<ol>
 +
<li value="14"> [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li>
 +
<li> [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li>
 +
<li> ''fixed'' [[Производящая функция]] (3) </li>
 +
# Оформить правильно англоязычные термины
 +
# Убрать точки с запятыми из определения
 +
# Все переменные и константы в Tex взять
 +
# Исправить знаки неравенств
 +
# Оформить ссылки примечаниями
 +
# Ссылки и литературу заменить на источники информации
 +
<li> [[Лемма Бёрнсайда и Теорема Пойа]] </li>
 +
<li> [[Задача об ожерельях]] </li>
 +
<li> [[Числа Стирлинга первого рода]] </li>
 +
<li> [[Числа Стирлинга второго рода]] </li>
 +
<li> [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]] </li>
 +
<li> [[Числа Каталана]] </li>
 +
</ol>
 +
 
 +
=== Свойства комбинаторных объектов ===
 +
<ol>
 +
<li value="22"> '''взяли''' [[Умножение перестановок, обратная перестановка, группа перестановок]] (5) </li>
 +
# Определение выделить жирным
 +
# Англоязычные термины
 +
# Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
 +
# Отформатировать псевдокоды
 +
# Все переменные и константы взять в Tex
 +
# Оформить правильно источники информации
 +
# Добавить примеров из конспекта групп по теории чисел
 +
# Добавить реккурентную формулу числа инволюций c доказательством
 +
<li> [[Действие перестановки на набор из элементов, представление в виде циклов]] </li>
 +
<li> [[Таблица инверсий]] </li>
 +
<li> ''fixed'' [[Теорема Кэли]] (1) </li>
 +
# Бинарную операцию в группе обозначают не звёздочкой, а кружочком
 +
# Интервики
 +
# Оформить правильно источники информации, добавить см. также
 +
# Добавить словесных пояснений происходящего
 +
<li> '''fixed''' [[Матричное представление перестановок]] (5) </li>
 +
# Англоязычные термины
 +
# Заменить дефисы на тире
 +
# Добавить подробные доказательства утверждений (или пояснить получше уже существующие)
 +
# Оформить правильно источники информации
 +
# Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
 +
<li> ''fixed'' [[Задача о минимуме/максимуме скалярного произведения]] (2) </li>
 +
# Оформить задачу шаблоном Задача
 +
# Ссылку в примечании сделать на самом деле примечанием
 +
# Добавить использование этой теоремы (в теории матроидов и теории расписаний)
 +
# Оформить правильно источники информации
 +
# Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться
 +
<li> ''fixed'' [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li>
 +
# Англоязычные термины
 +
# Определение взять в шаблон
 +
# Заменить дефисы на тире
 +
# Оформить правильно источники информации
 +
</ol>
 +
 
 +
== 7. Динамическое программирование ==
 +
:0. '''fixed''' [[Динамическое программирование]] (5)
 +
:# Добавить известную цитату про ДП
 +
:# Интервики на NP-полноту
 +
:# Картинки криво расположены
 +
:# Добавить больше примеров
 +
:# Добавить описание принципа оптимальности на подмножествах
 +
:# Оформить правильно источники информации
 +
:# Добавить про мемоизацию (и желательно что-нибудь разумное)
 +
=== Классические задачи динамического программирования ===
 
# [[Кратчайший путь в ациклическом графе]]
 
# [[Кратчайший путь в ациклическом графе]]
−
## в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится
+
# [[Задача о числе путей в ациклическом графе]] (4)
−
## псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData
+
## Взять задачу в шаблон
−
# [[Задача о расстановке знаков в выражении]]
+
## Отформатировать псевдокод
−
## "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке
+
## Обернуть имя функции в тексте в mathrm
−
## ссылка просто на "динамическое программирование" в википедии не нужна
+
## Заменить дефисы на тире
−
## доказать оптимальность
+
## Добавить см. также и источники информации
−
## нет номера страницы в источнике
+
## Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
 +
# '''!!!''' [[Задача о расстановке знаков в выражении]] (6)
 +
## Взять задачу в шаблон
 +
## Исправить знаки неравенств
 +
## Ссылку примечанием оформить нормально
 +
## Взять все переменные и константы в тексте в Tex
 +
## Отформатировать псевдокод
 +
## Табличку нормально оформить
 +
## Описать восстановление ответа
 +
## Источники информации правильно оформить
 +
## Добавить решение задачи без возможности использования скобок
 +
# [[Задача о порядке перемножения матриц]] (3)
 +
## Взять переменные и константы в Tex
 +
## Обернуть задачу в шаблон
 +
## Интервики на конспект правильных скобочных последовательностей
 +
## Написать, почему нас не устраивает число Каталана в асимптотике
 +
## Отформатировать псевдокоды
 +
## Оформить правильно источники информации
 +
## Убрать про мемоизацию
 
# [[Задача о наибольшей общей подпоследовательности]]
 
# [[Задача о наибольшей общей подпоследовательности]]
−
# [[Задача о порядке перемножения матриц]]
 
 
# [[Задача о наибольшей возрастающей подпоследовательности]]
 
# [[Задача о наибольшей возрастающей подпоследовательности]]
−
# [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
 
−
# [[Метод четырех русских для умножения матриц]]
 
−
# [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
 
# [[Задача коммивояжера, ДП по подмножествам]]
 
# [[Задача коммивояжера, ДП по подмножествам]]
−
## указать страницы в источниках
 
−
# [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
 
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
−
# [[Задача о расстоянии Дамерау-Левенштейна]]
+
# '''!!!''' [[Задача о рюкзаке]] (8)
−
# [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
+
## Взять задачу в шаблон
−
# [[Задача о наибольшей подпоследовательности-палиндроме]]
+
## Отформатировать псевдокоды
−
# '''!!!''' [[Meet-in-the-middle]]
+
## Заменить дефисы на тире
−
## можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.
+
## Исправить знаки неравенств
−
# [[Динамическое программирование по профилю]]
+
## Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
−
# [[Задача о рюкзаке]]
+
## Сделать итоговую формулу для А c помощью фигурной скобки
−
## разделы первого уровня должны быть ==
+
## Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
−
# [[Динамика по поддеревьям]]
+
## Понизить уровень заголовков первого уровня
−
## разделы первого уровня должны быть ==, а не =
+
## Оформить правильно источники информации
−
## '''эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть'''
 
  
−
== 8. Теория вероятностей ==
+
=== Способы оптимизации методов динамического программирования ===
 +
<ol>
 +
<li value="10"> ''fixed'' [[Метод четырех русских для умножения матриц]] (0.5) </li>
 +
# Взять скобки в Tex
 +
# Заменить дефисы на тире
 +
# Заменить литературу на источники информации
 +
<li> ''fixed'' [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] (3.5) </li>
 +
# Заменить дефисы на тире
 +
# Взять константы в Tex
 +
# Сделать нормальные картинки (или заменить на таблички)
 +
# Заменить источники на источники информации
 +
<li> ''fixed'' [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] (1) </li>
 +
# Кривая ссылка на оптимальный префиксный код
 +
# Заменить дефисы на тире
 +
# Взять переменные и константы в Tex
 +
# Исправить знаки неравенств
 +
# Оформить правильно источники информации
 +
<li> '''fixed''' [[Meet-in-the-middle]] (5) </li>
 +
# Отформатировать псевдокод
 +
# Добавить примеры задач
 +
# Оформить правильно источники информации
 +
</ol>
  
−
* '''англоязычные термины во все статьи этого раздела для основных определений и понятий'''
+
=== Другие задачи ===
 +
<ol>
 +
<li value="14"> [[Задача о расстоянии Дамерау-Левенштейна]] </li>
 +
<li> [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li>
 +
<li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li>
 +
<li> ''fixed'' [[Наибольшая общая возрастающая подпоследовательность]] (2) </li>
 +
# Переименовать в "Задача о ..."
 +
# Отформатировать псевдокоды
 +
# Англоязычные термины
 +
# Добавить Шаблон:Задача
 +
# Оформить правильно источники информации
 +
<li> [[Задача о наибольшей общей палиндромной подпоследовательности]] </li>
 +
<li> '''!!!''' [[Динамическое программирование по профилю]] (7) </li>
 +
# Англоязычные термины
 +
# Заменить умножение на \cdot
 +
# Заменить дефисы на тире
 +
# Взять переменные и константы в Tex
 +
# Отформатировать псевдокоды
 +
# Добавить ещё примеров
 +
# Оформить правильно источники информации
 +
# Добавить нормальное объяснение происходящего (и почему это работает)
 +
<li> '''fixed''' [[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] (5) </li>
 +
# Взять все переменные в Tex
 +
# Убрать определение паросочетания
 +
# Отформатировать псевдокод
 +
# Оформить правильно источники информации
 +
# Убрать первый пункт
 +
# Добавить ещё примеров
 +
</ol>
  
−
# [[Вероятностное пространство, элементарный исход, событие]]
+
== 8. Теория вероятностей ==
−
## для угловых скобок юзать \langle, \rangle
+
# [[Вероятностное пространство, элементарный исход, событие]] (1)
−
## перечисление оформить как википеречисление
+
## Англоязычные термины
−
## привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий.
+
## Заменить дефисы на тире
−
# [[Независимые события]]
+
## Определения выделить жирным
−
## определение несовместных событий  
+
## Все константы и переменные взять в Tex
−
## критерий для независимости несовместных событий
+
## Убрать точки с запятой из определений
−
# [[Условная вероятность]]
+
## Оформить правильно см. также и источники информации
−
## раздел "определение" не нужен, перенести в заголовок
+
## Правильно оформить дроби
 +
# [[Независимые события]] (1.5)
 +
## Оформить правильно англоязычные термины
 +
## Тире в шаблон, переменные и константы в Tex
 +
## Пример несовместных событий
 +
## Определения выделить жирным
 +
## Заменить все дроби на \dfrac
 +
## Оформить правильно источники информации
 +
## Пример Тетраэдра оформить нормально
 +
# [[Условная вероятность]] (0.5)
 +
## Англоязычные термины правильно оформить
 +
## Увеличить дроби
 +
## Переменные и константы взять в Tex
 +
## Оформить правильно источники информации
 +
# [[Формула полной вероятности]]
 
# [[Формула Байеса]]
 
# [[Формула Байеса]]
−
## определение какое-то дурацкое и копипаста с википедии
+
# [[Дискретная случайная величина]] (3)
−
# [[Формула полной вероятности]]
+
## Англоязычные термины
−
## примеры перечислить как подразделы
+
## Примеры
−
# [[Дискретная случайная величина]]
+
## Исправить знаки неравенств
−
# [[Независимые случайные величины]]
+
## Оформить правильно источники информации, См. также, списки, вообще всё
−
# ''взяли'' [[Математическое ожидание случайной величины]]
+
## Добавить про функцию плотности вероятности
−
## пробел перед открывающей скобкой должен быть
+
# [[Независимые случайные величины]] (1)
 +
## Англоязычные термины
 +
## Заменить ссылку примечанием на интервики
 +
## Заменить дефисы на тире, переменные и константы взять в Tex
 +
## Правильно оформить источники информации
 +
# [[Математическое ожидание случайной величины]] (2)
 +
## Оформить правильно См. также
 +
## Заменить дроби на \dfrac
 +
## Доказать содержательные утверждения
 
# [[Дисперсия случайной величины]]
 
# [[Дисперсия случайной величины]]
−
# ''взяли'' [[Ковариация случайных величин]]
+
# [[Ковариация случайных величин]]
 
# [[Корреляция случайных величин]]
 
# [[Корреляция случайных величин]]
−
# [[Энтропия случайного источника]]
+
# [[Энтропия случайного источника]] (2)
 
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
 
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
−
## В Романовском добавить издание и страницу
+
## В Романовском добавить издание и страницу, источники информации правильно оформить
−
# [[Симуляция одним распределением другого]]
+
## Англоязычные термины
 +
## Убрать треугольники из свойств
 +
## Исправить знаки неравенств
 +
## Оформить по правилам
 +
# '''!!!''' [[Симуляция одним распределением другого]] (7)
 
## так и нет нормального определения распределения
 
## так и нет нормального определения распределения
−
## список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли.
+
## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
−
## издания и страницы в испточниках
+
## издания и страницы в источниках информации
 +
## Англоязычные термины
 +
## Увеличить дроби, исправить знаки неравенств
 +
## Зачем-то формулы написаны по центру
 +
## Картинки в общем случае криво расположены
 +
## Вывод оформить правильно
 +
## Увеличить дроби
 
# [[Арифметическое кодирование]]
 
# [[Арифметическое кодирование]]
−
## раздел "определение" не нужен, перенести в заголовок
 
 
# [[Парадоксы теории вероятностей]]
 
# [[Парадоксы теории вероятностей]]
−
## "Пусть p - предельно ненулевая вероятность" — а что это такое?
+
# '''!!!''' [[Схема Бернулли]] (5)
−
## для предела использовать \limits
+
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать
−
# [[Схема Бернулли]]
 
−
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел
 
 
## оформить источник
 
## оформить источник
 +
## Англоязычные термины
 +
## Определение выделить жирным
 +
## Перерисовать картинку
 +
## Исправить знаки неравенств, дроби на \dfrac
 +
## Константы и переменные взять в Tex
 +
## Ссылки на формулы красиво оформить
 +
## Оформить правильно источники информации
 +
## Оформить по правилам
  
 
== 9. Марковские цепи ==
 
== 9. Марковские цепи ==
−
 
+
# '''!!!''' [[Марковская цепь]] (6)
−
# [[Марковская цепь]]
 
 
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
 
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
 
## сделать подраздел "циклические классы"
 
## сделать подраздел "циклические классы"
 
## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
 
## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
−
# [[Теорема о поглощении]]
+
## Интервики на графы
 +
## Англоязычные термины правильно оформить
 +
## Оформить правильно источники информации
 +
# '''!!!''' [[Теорема о поглощении]] (6)
 
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
 
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
 
## max -> \max  
 
## max -> \max  
 
## в конце какая-то муть. Расписать рассуждения чуть подробнее
 
## в конце какая-то муть. Расписать рассуждения чуть подробнее
−
# [[Фундаментальная матрица]]
+
## Заменить дефисы на тире
 +
## А что такое непоглощающая матрица?
 +
## Источники информации
 +
# '''!!!''' [[Фундаментальная матрица]] (5)
 
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
 
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
 
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
 
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
 
## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
 
## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
−
# [[Математическое ожидание времени поглощения]]
+
## Англоязычные термины
 +
## Определения выделить жирным
 +
## Дефисы на тире, переменные в Tex
 +
# [[Математическое ожидание времени поглощения]] (2)
 
## не везде переменные обернуты в латех
 
## не везде переменные обернуты в латех
−
# [[Расчет вероятности поглощения в состоянии]]
+
## Оформить правильно Источники информации
 +
## Добавить См. также
 +
## Пояснить подробней переходы
 +
# '''!!!''' [[Расчет вероятности поглощения в состоянии]] (5)
 
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
 
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
−
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
+
## имена переменных из псевдокода в тексте оборачиваются в \mathtt
 
## оформить псевдокод в виде функций, без всяких println
 
## оформить псевдокод в виде функций, без всяких println
 
## оформить нормально источник
 
## оформить нормально источник
−
# [[Эргодическая марковская цепь]]
+
## Заголовки первого уровня убрать
 +
# [[Эргодическая марковская цепь]] (1)
 
## определения пересекаются с конспектом про марковские цепи
 
## определения пересекаются с конспектом про марковские цепи
−
# [[Регулярная марковская цепь]]
+
## Сделать ссылку примечанием
−
# [[Примеры использования Марковских цепей]]
+
## Заменить дефисы на тире
−
# '''!!!''' [[Скрытые Марковские модели]]
+
## Оформить правильно источники информации
−
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики
+
# [[Регулярная марковская цепь]] (1)
−
# [[Алгоритм Витерби]]
+
## Переменные взять в Tex
−
## "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?
+
## Оформить правильно источники информации
 +
## Дефисы на тире
 +
## Добавить См. также
 +
# [[Примеры использования Марковских цепей]] (1)
 +
## Переменные в Tex
 +
## Заменить литературу на источники информации
 +
## Оформить по правилам
 +
# '''!!!''' [[Скрытые Марковские модели]] (7)
 +
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров
 +
## Переменные и константы взять в Tex
 +
## Ссылку на вики оформить примечанием
 +
## Оформить правильно источники информации
 +
## Исправить небольшую багу в картинке
 +
## Англоязычные термины
 +
## Категории
 +
# '''!!!''' [[Алгоритм Витерби]] (5)
 +
## "правдоподобная последовательность скрытых состояний" {{---}} что такое "наиболее правдоподобная"?
 
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
 
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
 
## а \pi что такое?
 
## а \pi что такое?
−
# [[Алгоритм "Вперед-Назад"]]
+
## Отформатировать псевдокод
 +
## Англоязычные термины
 +
## Заменить ссылки на источники информации
 +
# [[Алгоритм "Вперед-Назад"]] (5)
 +
## Отформатировать псевдокод
 +
## Заменить литературу на источники информации
 +
## Оформить по правилам

Текущая версия на 19:15, 23 февраля 2017

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)

Обозначением !!! помечены те конспекты, которые точно дадут 5 баллов при их успешном выполнении. Просто выделены, чтобы сразу можно было на них обратить внимание.

1. Отношения

  1. Определение отношения (0.5)
    1. Дефисы заменить на тире
    2. Оформить красиво источники информации
    3. Английские термины к видам отношений
  2. Композиция отношений, степерь отношения, обратное отношение (0.5)
    1. Отформатировать свойства красиво
    2. Оформить правильно источники информации
    3. Англ. термины
  3. Рефлексивное отношение. Антирефлексивное отношение.
  4. Симметричное отношение
  5. Антисимметричное отношение
  6. Транзитивное отношение
  7. Отношение порядка
  8. Отношение эквивалентности
  9. Транзитивное замыкание отношения
  10. Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
  11. fixed Транзитивный остов (5)
    1. Отформатировать псевдокод
    2. Добавить категории
    3. возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
    4. если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
    5. Отформатировать конспект по правилам

2. Булевы функции

  1. Определение булевой функции
  2. Побитовые операции
  3. fixed Суперпозиции (0.5)
    1. англоязычных терминов
  4. fixed ДНФ (0.5)
    1. англоязычных терминов
    2. писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
    3. Убрать странные скобки в формулировке теоремы
    4. Не то выделено жирным в определениях
  5. fixed Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна (2.5)
    1. англоязычных терминов
    2. Жирные определения
    3. Непонятно, как работает метод Карно, возможно в таблице ошибка
    4. Двойной номер в одной из табличек Квайна
    5. Обернуть в tex бинарные операции в методе Квайна
    6. Все константы и переменные взять в tex
  6. КНФ
  7. 2SAT
  8. fixed Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома (3)
    1. англоязычных терминов
    2. написать, почему факт того, что существует полиномиальный алгоритм, интересен
    3. Ссылку на википедию сделать примечанием
    4. Добавить ссылки, изменить См. также
    5. Исправить странное форматирование в форме Крома
  9. Полином Жегалкина, преобразование Мёбиуса
  10. Полные системы функций. Теорема Поста о полной системе функций
  11. Представление функции класса DM с помощью медианы
  12. Пороговая функция
  13. Троичная логика

3. Схемы из функциональных элементов

  1. fixed Реализация булевой функции схемой из функциональных элементов (1)
    1. англоязычных терминов (на схемную сложность, глубину схемы)
    2. Оформить красивее определения из логических элементов
    3. Сделать красивую табличку
    4. Источники информации и См. также
  2. Простейшие методы синтеза схем из функциональных элементов (0.5)
    1. Изменить знаки неравенств
    2. Ссылку на метод синтеза схем Шэннона сделать примечанием
    3. Определение жирным
    4. Оформить правильно См. также и Источники информации
    5. Увеличить дроби
  3. Метод Лупанова синтеза схем (0.5)
    1. Заменить литературу на источники информации
    2. Изменить знаки неравенств
    3. Запятые криво стоят в определении функции g
    4. Увеличить дроби
  4. Cумматор
  5. fixed Каскадный сумматор (0.5)
    1. англоязычных терминов
    2. Оформить источники информации нормально
  6. Двоичный каскадный сумматор
  7. Троичный сумматор
  8. Реализация вычитания сумматором
  9. Матричный умножитель
  10. fixed Дерево Уоллеса (1)
    1. пункт "определение" не нужен
    2. англоязычных терминов
    3. надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
    4. Оформить правильно Источники информации
    5. См. также
    6. Увеличить дроби
    7. Как-нибудь нормально назвать depth, size и sum
    8. Чуть-чуть увеличить картинки
  11. Контактная схема
  12. Триггеры
  13. Квантовые гейты

4. Представление информации

5. Алгоритмы сжатия

  1. Алгоритм Хаффмана
  2. Оптимальное хранение словаря в алгоритме Хаффмана
  3. Алгоритм Хаффмана за O(n) (1)
    1. Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
  4. fixed Алгоритм Ху-Таккера (1)
    1. Англоязычные термины
    2. Заменить дефис на тире
    3. Сделать красивый список в определении
    4. Переменные и константы взять в Tex
    5. Исправить знаки неравенств
    6. Правильно оформить источники информации
  5. Неравенство Крафта
  6. Неравенство Макмиллана
  7. Код Шеннона
  8. Оптимальный префиксный код с длиной кодового слова не более L бит
  9. Алгоритмы LZ77 и LZ78 (2)
    1. Переменные и константы взять в Tex
    2. Добавить примеры итоговых таблиц
    3. Рассказать, как декодировать
    4. Правильно оформить источники информации
    5. Получше расписать описание алгоритма
    6. Таблицы сделать красивыми
    7. Интервики
  10. Алгоритм LZW
  11. Алгоритм LZSS
  12. Преобразование Барроуза-Уиллера и обратное ему
  13. Преобразование MTF
  14. Расстояние Хэмминга (1)
    1. Англоязычные термины правильно оформить
    2. Причём там куб?
    3. Оформить правильно источники информации
    4. Исправить знаки неравенств
  15. Избыточное кодирование, код Хэмминга
  16. Гамма-, дельта- и омега-код Элиаса

6. Комбинаторика

Комбинаторные объекты

  1. fixed Комбинаторные объекты (6)
    1. Правильно оформить англоязычные термины
    2. Привести формулы каждого объекта — общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
    3. Под каждый комбинаторный объект сделать свой подзаголовк уровня ниже
    4. Все переменные и константы взять в Tex
    5. Добавить ссылок по всем объектам в источники информации
    6. Заменить ссылку на числа Стирлинга ссылкой на конспект
    7. Заменить дефисы на тире
  2. Лексикографический порядок
  3. Коды Грея
  4. Коды Грея для перестановок
  5. Коды антигрея
  6. Цепные коды
  7. Правильные скобочные последовательности

Генерация комбинаторных объектов

  1. Генерация комбинаторных объектов в лексикографическом порядке
    1. Заменить скобки "больше-меньше" на угловые
    2. Нормальную красивую картинку нарисовать
  2. Получение номера по объекту
  3. Получение объекта по номеру
  4. Получение следующего объекта
  5. Получение предыдущего объекта
  6. fixed Метод генерации случайной перестановки, алгоритм Фишера-Йетса (1)
    1. Отформатировать псевдокоды
    2. Мелочи по теху
    3. Какие-то пропуски в обосновании
    4. Дефисы на тире
  7. Методы генерации случайного сочетания

Подсчёт числа объектов

  1. Формула включения-исключения, подсчет числа беспорядков
  2. Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
  3. fixed Производящая функция (3)
    1. Оформить правильно англоязычные термины
    2. Убрать точки с запятыми из определения
    3. Все переменные и константы в Tex взять
    4. Исправить знаки неравенств
    5. Оформить ссылки примечаниями
    6. Ссылки и литературу заменить на источники информации
  4. Лемма Бёрнсайда и Теорема Пойа
  5. Задача об ожерельях
  6. Числа Стирлинга первого рода
  7. Числа Стирлинга второго рода
  8. Числа Эйлера первого и второго рода. Подъемы в перестановках
  9. Числа Каталана

Свойства комбинаторных объектов

  1. взяли Умножение перестановок, обратная перестановка, группа перестановок (5)
    1. Определение выделить жирным
    2. Англоязычные термины
    3. Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
    4. Отформатировать псевдокоды
    5. Все переменные и константы взять в Tex
    6. Оформить правильно источники информации
    7. Добавить примеров из конспекта групп по теории чисел
    8. Добавить реккурентную формулу числа инволюций c доказательством
  2. Действие перестановки на набор из элементов, представление в виде циклов
  3. Таблица инверсий
  4. fixed Теорема Кэли (1)
    1. Бинарную операцию в группе обозначают не звёздочкой, а кружочком
    2. Интервики
    3. Оформить правильно источники информации, добавить см. также
    4. Добавить словесных пояснений происходящего
  5. fixed Матричное представление перестановок (5)
    1. Англоязычные термины
    2. Заменить дефисы на тире
    3. Добавить подробные доказательства утверждений (или пояснить получше уже существующие)
    4. Оформить правильно источники информации
    5. Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
  6. fixed Задача о минимуме/максимуме скалярного произведения (2)
    1. Оформить задачу шаблоном Задача
    2. Ссылку в примечании сделать на самом деле примечанием
    3. Добавить использование этой теоремы (в теории матроидов и теории расписаний)
    4. Оформить правильно источники информации
    5. Доказательство плохо разбито на пункты — от нумерации в доказательстве вообще можно избавиться
  7. fixed Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП (0.5)
    1. Англоязычные термины
    2. Определение взять в шаблон
    3. Заменить дефисы на тире
    4. Оформить правильно источники информации

7. Динамическое программирование

0. fixed Динамическое программирование (5)
  1. Добавить известную цитату про ДП
  2. Интервики на NP-полноту
  3. Картинки криво расположены
  4. Добавить больше примеров
  5. Добавить описание принципа оптимальности на подмножествах
  6. Оформить правильно источники информации
  7. Добавить про мемоизацию (и желательно что-нибудь разумное)

Классические задачи динамического программирования

  1. Кратчайший путь в ациклическом графе
  2. Задача о числе путей в ациклическом графе (4)
    1. Взять задачу в шаблон
    2. Отформатировать псевдокод
    3. Обернуть имя функции в тексте в mathrm
    4. Заменить дефисы на тире
    5. Добавить см. также и источники информации
    6. Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
  3. !!! Задача о расстановке знаков в выражении (6)
    1. Взять задачу в шаблон
    2. Исправить знаки неравенств
    3. Ссылку примечанием оформить нормально
    4. Взять все переменные и константы в тексте в Tex
    5. Отформатировать псевдокод
    6. Табличку нормально оформить
    7. Описать восстановление ответа
    8. Источники информации правильно оформить
    9. Добавить решение задачи без возможности использования скобок
  4. Задача о порядке перемножения матриц (3)
    1. Взять переменные и константы в Tex
    2. Обернуть задачу в шаблон
    3. Интервики на конспект правильных скобочных последовательностей
    4. Написать, почему нас не устраивает число Каталана в асимптотике
    5. Отформатировать псевдокоды
    6. Оформить правильно источники информации
    7. Убрать про мемоизацию
  5. Задача о наибольшей общей подпоследовательности
  6. Задача о наибольшей возрастающей подпоследовательности
  7. Задача коммивояжера, ДП по подмножествам
  8. Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
  9. !!! Задача о рюкзаке (8)
    1. Взять задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить дефисы на тире
    4. Исправить знаки неравенств
    5. Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
    6. Сделать итоговую формулу для А c помощью фигурной скобки
    7. Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
    8. Понизить уровень заголовков первого уровня
    9. Оформить правильно источники информации

Способы оптимизации методов динамического программирования

  1. fixed Метод четырех русских для умножения матриц (0.5)
    1. Взять скобки в Tex
    2. Заменить дефисы на тире
    3. Заменить литературу на источники информации
  2. fixed Применение метода четырех русских в задачах ДП на примере задачи о НОП (3.5)
    1. Заменить дефисы на тире
    2. Взять константы в Tex
    3. Сделать нормальные картинки (или заменить на таблички)
    4. Заменить источники на источники информации
  3. fixed Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза (1)
    1. Кривая ссылка на оптимальный префиксный код
    2. Заменить дефисы на тире
    3. Взять переменные и константы в Tex
    4. Исправить знаки неравенств
    5. Оформить правильно источники информации
  4. fixed Meet-in-the-middle (5)
    1. Отформатировать псевдокод
    2. Добавить примеры задач
    3. Оформить правильно источники информации

Другие задачи

  1. Задача о расстоянии Дамерау-Левенштейна
  2. Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
  3. Задача о наибольшей подпоследовательности-палиндроме
  4. fixed Наибольшая общая возрастающая подпоследовательность (2)
    1. Переименовать в "Задача о ..."
    2. Отформатировать псевдокоды
    3. Англоязычные термины
    4. Добавить Шаблон:Задача
    5. Оформить правильно источники информации
  5. Задача о наибольшей общей палиндромной подпоследовательности
  6. !!! Динамическое программирование по профилю (7)
    1. Англоязычные термины
    2. Заменить умножение на \cdot
    3. Заменить дефисы на тире
    4. Взять переменные и константы в Tex
    5. Отформатировать псевдокоды
    6. Добавить ещё примеров
    7. Оформить правильно источники информации
    8. Добавить нормальное объяснение происходящего (и почему это работает)
  7. fixed Динамика по поддеревьям, задача о паросочетании максимального веса в дереве (5)
    1. Взять все переменные в Tex
    2. Убрать определение паросочетания
    3. Отформатировать псевдокод
    4. Оформить правильно источники информации
    5. Убрать первый пункт
    6. Добавить ещё примеров

8. Теория вероятностей

  1. Вероятностное пространство, элементарный исход, событие (1)
    1. Англоязычные термины
    2. Заменить дефисы на тире
    3. Определения выделить жирным
    4. Все константы и переменные взять в Tex
    5. Убрать точки с запятой из определений
    6. Оформить правильно см. также и источники информации
    7. Правильно оформить дроби
  2. Независимые события (1.5)
    1. Оформить правильно англоязычные термины
    2. Тире в шаблон, переменные и константы в Tex
    3. Пример несовместных событий
    4. Определения выделить жирным
    5. Заменить все дроби на \dfrac
    6. Оформить правильно источники информации
    7. Пример Тетраэдра оформить нормально
  3. Условная вероятность (0.5)
    1. Англоязычные термины правильно оформить
    2. Увеличить дроби
    3. Переменные и константы взять в Tex
    4. Оформить правильно источники информации
  4. Формула полной вероятности
  5. Формула Байеса
  6. Дискретная случайная величина (3)
    1. Англоязычные термины
    2. Примеры
    3. Исправить знаки неравенств
    4. Оформить правильно источники информации, См. также, списки, вообще всё
    5. Добавить про функцию плотности вероятности
  7. Независимые случайные величины (1)
    1. Англоязычные термины
    2. Заменить ссылку примечанием на интервики
    3. Заменить дефисы на тире, переменные и константы взять в Tex
    4. Правильно оформить источники информации
  8. Математическое ожидание случайной величины (2)
    1. Оформить правильно См. также
    2. Заменить дроби на \dfrac
    3. Доказать содержательные утверждения
  9. Дисперсия случайной величины
  10. Ковариация случайных величин
  11. Корреляция случайных величин
  12. Энтропия случайного источника (2)
    1. воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
    2. В Романовском добавить издание и страницу, источники информации правильно оформить
    3. Англоязычные термины
    4. Убрать треугольники из свойств
    5. Исправить знаки неравенств
    6. Оформить по правилам
  13. !!! Симуляция одним распределением другого (7)
    1. так и нет нормального определения распределения
    2. список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
    3. издания и страницы в источниках информации
    4. Англоязычные термины
    5. Увеличить дроби, исправить знаки неравенств
    6. Зачем-то формулы написаны по центру
    7. Картинки в общем случае криво расположены
    8. Вывод оформить правильно
    9. Увеличить дроби
  14. Арифметическое кодирование
  15. Парадоксы теории вероятностей
  16. !!! Схема Бернулли (5)
    1. запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать
    2. оформить источник
    3. Англоязычные термины
    4. Определение выделить жирным
    5. Перерисовать картинку
    6. Исправить знаки неравенств, дроби на \dfrac
    7. Константы и переменные взять в Tex
    8. Ссылки на формулы красиво оформить
    9. Оформить правильно источники информации
    10. Оформить по правилам

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

  1. !!! Марковская цепь (6)
    1. два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
    2. сделать подраздел "циклические классы"
    3. "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
    4. Интервики на графы
    5. Англоязычные термины правильно оформить
    6. Оформить правильно источники информации
  2. !!! Теорема о поглощении (6)
    1. определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
    2. max -> \max
    3. в конце какая-то муть. Расписать рассуждения чуть подробнее
    4. Заменить дефисы на тире
    5. А что такое непоглощающая матрица?
    6. Источники информации
  3. !!! Фундаментальная матрица (5)
    1. написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
    2. не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
    3. получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
    4. Англоязычные термины
    5. Определения выделить жирным
    6. Дефисы на тире, переменные в Tex
  4. Математическое ожидание времени поглощения (2)
    1. не везде переменные обернуты в латех
    2. Оформить правильно Источники информации
    3. Добавить См. также
    4. Пояснить подробней переходы
  5. !!! Расчет вероятности поглощения в состоянии (5)
    1. куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
    2. имена переменных из псевдокода в тексте оборачиваются в \mathtt
    3. оформить псевдокод в виде функций, без всяких println
    4. оформить нормально источник
    5. Заголовки первого уровня убрать
  6. Эргодическая марковская цепь (1)
    1. определения пересекаются с конспектом про марковские цепи
    2. Сделать ссылку примечанием
    3. Заменить дефисы на тире
    4. Оформить правильно источники информации
  7. Регулярная марковская цепь (1)
    1. Переменные взять в Tex
    2. Оформить правильно источники информации
    3. Дефисы на тире
    4. Добавить См. также
  8. Примеры использования Марковских цепей (1)
    1. Переменные в Tex
    2. Заменить литературу на источники информации
    3. Оформить по правилам
  9. !!! Скрытые Марковские модели (7)
    1. можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров
    2. Переменные и константы взять в Tex
    3. Ссылку на вики оформить примечанием
    4. Оформить правильно источники информации
    5. Исправить небольшую багу в картинке
    6. Англоязычные термины
    7. Категории
  10. !!! Алгоритм Витерби (5)
    1. "правдоподобная последовательность скрытых состояний" — что такое "наиболее правдоподобная"?
    2. имена переменных в тексте оборачиваются в \mathrm или \mathtt
    3. а \pi что такое?
    4. Отформатировать псевдокод
    5. Англоязычные термины
    6. Заменить ссылки на источники информации
  11. Алгоритм "Вперед-Назад" (5)
    1. Отформатировать псевдокод
    2. Заменить литературу на источники информации
    3. Оформить по правилам
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Shersh/Тикеты_к_1ому_терму&oldid=60456»