Участник:Dgerasimov/Тикеты по конспектам year2013 — различия между версиями
(→Комбинаторика) |
(→6. Комбинаторика) |
||
(не показано 29 промежуточных версий 2 участников) | |||
Строка 33: | Строка 33: | ||
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений | ## аналогично предыдущему, придумать обобщение на случай бесконечных отношений | ||
− | == | + | == 2. Булевы функции == |
# [[Определение булевой функции]] | # [[Определение булевой функции]] | ||
## англоязычных терминов | ## англоязычных терминов | ||
Строка 58: | Строка 58: | ||
# [[Пороговая функция]] | # [[Пороговая функция]] | ||
− | == | + | == 3. Схемы из функциональных элементов == |
# [[Реализация булевой функции схемой из функциональных элементов]] | # [[Реализация булевой функции схемой из функциональных элементов]] | ||
## англоязычных терминов (на схемную сложность, глубину схемы) | ## англоязычных терминов (на схемную сложность, глубину схемы) | ||
− | # [[ | + | # [[Метод Лупанова синтеза схем]] |
# [[Cумматор]] | # [[Cумматор]] | ||
## англоязычных терминов | ## англоязычных терминов | ||
Строка 79: | Строка 79: | ||
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга | ## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга | ||
− | == ''' | + | == '''взяли''' 4. Представление информации == |
# [[Кодирование информации]] | # [[Кодирование информации]] | ||
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] | # [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] | ||
Строка 105: | Строка 105: | ||
# [[Избыточное кодирование, код Хэмминга]] | # [[Избыточное кодирование, код Хэмминга]] | ||
− | == Комбинаторика == | + | == 6. Комбинаторика == |
− | # [[Комбинаторные объекты]] | + | # ''fixed'' [[Комбинаторные объекты]] |
## пункт "определение" не нужен | ## пункт "определение" не нужен | ||
− | # [[Лексикографический порядок]] | + | # ''взяли'' [[Лексикографический порядок]] |
## собственно определения лексикографического порядка тут и нет. англоязычный термин. | ## собственно определения лексикографического порядка тут и нет. англоязычный термин. | ||
## ссылку на английскую википедию | ## ссылку на английскую википедию | ||
## Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей | ## Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей | ||
## return <, return = и т.п. выглядят ужасно. Сделать return LESS, return EQUAL и т.п. | ## 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)) | ||
# [[Таблица инверсий]] | # [[Таблица инверсий]] | ||
# [[Умножение перестановок, обратная перестановка, группа перестановок]] | # [[Умножение перестановок, обратная перестановка, группа перестановок]] | ||
## Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться. | ## Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться. | ||
+ | ## ссылку на русскую и английскую википедию, на симметрическую группу | ||
# [[Теорема Кэли]] | # [[Теорема Кэли]] | ||
# [[Матричное представление перестановок]] | # [[Матричное представление перестановок]] | ||
Строка 141: | Строка 165: | ||
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] | # [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]] | ||
# [[Производящая функция]] | # [[Производящая функция]] | ||
− | # [[Лемма Бёрнсайда и Теорема Пойа]] | + | # '''взяли''' [[Лемма Бёрнсайда и Теорема Пойа]] |
## сюда добавить категорию "Теория Групп", она где-то есть на конспектах | ## сюда добавить категорию "Теория Групп", она где-то есть на конспектах | ||
− | # [[Задача об ожерельях]] | + | ## для сумм надо юзать \limits |
+ | ## В теореме Пойа как-то неожиданно появляется группа перестановок, в ее условии тут это почему-то явно не сказано | ||
+ | ## Можно добавить пример подсчета количества различных раскрасок кубика в k цветов. Раскраски эквивалентны, если одну можно получить из другой поворотами кубика. | ||
+ | # '''взяли''' [[Задача об ожерельях]] | ||
+ | ## а если можно делать не только сдвиги, а еще и отражения? (это называется bracelets: https://en.wikipedia.org/wiki/Necklace_(combinatorics) ) | ||
+ | ## ссылки в статье почему-то оформлены как внешние, хотя должны быть внутренними | ||
+ | ## lcm и gcd обернуть в \operatorname или \mathrm | ||
− | == [[Динамическое программирование]] == | + | == 7. [[Динамическое программирование]] == |
− | + | # [[Кратчайший путь в ациклическом графе]] | |
− | + | ## в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится | |
− | + | ## псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData | |
− | + | # [[Задача о расстановке знаков в выражении]] | |
− | + | ## "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке | |
− | + | ## ссылка просто на "динамическое программирование" в википедии не нужна | |
− | + | ## доказать оптимальность | |
− | + | ## нет номера страницы в источнике | |
− | + | # [[Задача о наибольшей общей подпоследовательности]] | |
− | + | # [[Задача о порядке перемножения матриц]] | |
− | + | # [[Задача о наибольшей возрастающей подпоследовательности]] | |
− | + | # [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]] | |
− | + | # [[Метод четырех русских для умножения матриц]] | |
− | + | # [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] | |
− | + | # [[Задача коммивояжера, ДП по подмножествам]] | |
− | + | ## указать страницы в источниках | |
− | + | # [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] | |
− | + | # [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] | |
+ | # [[Задача о расстоянии Дамерау-Левенштейна]] | ||
+ | # [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] | ||
+ | # [[Задача о наибольшей подпоследовательности-палиндроме]] | ||
+ | # '''!!!''' [[Meet-in-the-middle]] | ||
+ | ## можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект. | ||
+ | # [[Динамическое программирование по профилю]] | ||
+ | # [[Задача о рюкзаке]] | ||
+ | ## разделы первого уровня должны быть == | ||
+ | # [[Динамика по поддеревьям]] | ||
+ | ## разделы первого уровня должны быть ==, а не = | ||
+ | ## '''эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть''' | ||
− | == Теория вероятностей == | + | == 8. Теория вероятностей == |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | * '''англоязычные термины во все статьи этого раздела для основных определений и понятий''' | |
− | + | # [[Вероятностное пространство, элементарный исход, событие]] | |
− | + | ## для угловых скобок юзать \langle, \rangle | |
− | + | ## перечисление оформить как википеречисление | |
− | + | ## привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий. | |
− | + | # [[Независимые события]] | |
− | + | ## определение несовместных событий | |
− | + | ## критерий для независимости несовместных событий | |
− | + | # [[Условная вероятность]] | |
− | + | ## раздел "определение" не нужен, перенести в заголовок | |
− | + | # [[Формула Байеса]] | |
− | + | ## определение какое-то дурацкое и копипаста с википедии | |
+ | # [[Формула полной вероятности]] | ||
+ | ## примеры перечислить как подразделы | ||
+ | # [[Дискретная случайная величина]] | ||
+ | # [[Независимые случайные величины]] | ||
+ | # ''взяли'' [[Математическое ожидание случайной величины]] | ||
+ | ## пробел перед открывающей скобкой должен быть | ||
+ | # [[Дисперсия случайной величины]] | ||
+ | # ''взяли'' [[Ковариация случайных величин]] | ||
+ | # [[Корреляция случайных величин]] | ||
+ | # [[Энтропия случайного источника]] | ||
+ | ## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное. | ||
+ | ## В Романовском добавить издание и страницу | ||
+ | # [[Симуляция одним распределением другого]] | ||
+ | ## так и нет нормального определения распределения | ||
+ | ## список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли. | ||
+ | ## издания и страницы в испточниках | ||
+ | # [[Арифметическое кодирование]] | ||
+ | ## раздел "определение" не нужен, перенести в заголовок | ||
+ | # [[Парадоксы теории вероятностей]] | ||
+ | ## "Пусть p - предельно ненулевая вероятность" — а что это такое? | ||
+ | ## для предела использовать \limits | ||
+ | # [[Схема Бернулли]] | ||
+ | ## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел | ||
+ | ## оформить источник | ||
+ | |||
+ | == 9. Марковские цепи == | ||
+ | |||
+ | # [[Марковская цепь]] | ||
+ | ## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому) | ||
+ | ## сделать подраздел "циклические классы" | ||
+ | ## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению? | ||
+ | # [[Теорема о поглощении]] | ||
+ | ## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку. | ||
+ | ## max -> \max | ||
+ | ## в конце какая-то муть. Расписать рассуждения чуть подробнее | ||
+ | # [[Фундаментальная матрица]] | ||
+ | ## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется. | ||
+ | ## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями» | ||
+ | ## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть | ||
+ | # [[Математическое ожидание времени поглощения]] | ||
+ | ## не везде переменные обернуты в латех | ||
+ | # [[Расчет вероятности поглощения в состоянии]] | ||
+ | ## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится. | ||
+ | ## имена переменных в тексте оборачиваются в \mathrm или \mathtt | ||
+ | ## оформить псевдокод в виде функций, без всяких println | ||
+ | ## оформить нормально источник | ||
+ | # [[Эргодическая марковская цепь]] | ||
+ | ## определения пересекаются с конспектом про марковские цепи | ||
+ | # [[Регулярная марковская цепь]] | ||
+ | # [[Примеры использования Марковских цепей]] | ||
+ | # '''!!!''' [[Скрытые Марковские модели]] | ||
+ | ## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики | ||
+ | # [[Алгоритм Витерби]] | ||
+ | ## "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"? | ||
+ | ## имена переменных в тексте оборачиваются в \mathrm или \mathtt | ||
+ | ## а \pi что такое? | ||
+ | # [[Алгоритм "Вперед-Назад"]] |
Текущая версия на 23:05, 6 января 2014
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела
1. Отношения
- взяли Определение отношения
- Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
- На виды и примеры отношений дать внутренние ссылки
- англоязычные термины
- пункт "Определение" не нужен, см. правила форматирования конспектов
- Композиция отношений, степерь отношения, обратное отношение
- см. пункт 1.1
- англоязычные термины
- Рефлексивное отношение. Антирефлексивное отношение.
- англоязычные термины
- добавить внутренних ссылок на эквивдентность, порядки и т.д.
- Симметричное отношение
- англоязычные термины
- Антисимметричное отношение
- англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
- Транзитивное отношение
- англоязычные термины
- Отношение порядка
- англоязычные термины
- Отношение эквивалентности
- пункт "определение" не нужен
- англоязычные термины
- Транзитивное замыкание отношения
- англоязычные термины
- взяли Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- пункт "Задача" не нужен
- интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
- !!! Транзитивный остов
- возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
- если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
- аналогично предыдущему, придумать обобщение на случай бесконечных отношений
2. Булевы функции
- Определение булевой функции
- англоязычных терминов
- термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.
- Суперпозиции
- англоязычных терминов
- ДНФ
- англоязычных терминов
- писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
- англоязычных терминов
- КНФ
- англоязычных терминов
- писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- англоязычных терминов
- написать, почему факт того, что существует полиномиальный алгоритм, интересен
- Полином Жегалкина, преобразование Мёбиуса
- англоязычных терминов
- "Предпосылки" — странное название, переименовать в "Полнота", например
- Полные системы функций. Теорема Поста о полной системе функций
- англоязычных терминов
- Представление функции класса DM с помощью медианы
- Пороговая функция
3. Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов
- англоязычных терминов (на схемную сложность, глубину схемы)
- Метод Лупанова синтеза схем
- Cумматор
- англоязычных терминов
- Каскадный сумматор
- англоязычных терминов
- Двоичный каскадный сумматор
- англоязычных терминов
- из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
- Реализация вычитания сумматором
- Матричный умножитель
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
- Дерево Уоллеса
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
взяли 4. Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
- сюда неплохо было бы добавить пример на python с созданием юникодной строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length
5. Алгоритмы сжатия
- взяли Алгоритм Хаффмана
- "Использует только частоту появления одинаковых байт в изображении." што
- ссылки на википедию, русскую и английскую
- внутренние ссылки на префиксный код и все такое.
- Алгоритм Ху-Таккера
- Неравенство Крафта
- Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
- А зачем оно нужно? Просто интересный факт?
- Неравенство Макмиллана
- Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
- А зачем оно нужно? Просто интересный факт?
- Алгоритм LZW
- Алгоритмы LZ77 и LZ78
- взяли Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга
- Избыточное кодирование, код Хэмминга
6. Комбинаторика
- fixed Комбинаторные объекты
- пункт "определение" не нужен
- взяли Лексикографический порядок
- собственно определения лексикографического порядка тут и нет. англоязычный термин.
- ссылку на английскую википедию
- Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
- 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
- Цепные коды
- ссылку на хоть какие-нибудь источники
- а зачем они нужны?
- Правильные скобочные последовательности
- англоязычные термины
- выделить в псевдокоде ключевые слова жирным
- Обозначить биномиальные коэффециенты нормально (не , а )
- Действие перестановки на набор из элементов, представление в виде циклов
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса
- убрать пункт "постановка задачи", вынести в заголовок
- Методы генерации случайного сочетания
- убрать пункт "постановка задачи", вынести в заголовок
- что-то описание алгоритма не очень соответствует псевдокоду (для O(n^2))
- Таблица инверсий
- Умножение перестановок, обратная перестановка, группа перестановок
- Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.
- ссылку на русскую и английскую википедию, на симметрическую группу
- Теорема Кэли
- Матричное представление перестановок
- Задача о минимуме/максимуме скалярного произведения
- непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция
- взяли Лемма Бёрнсайда и Теорема Пойа
- сюда добавить категорию "Теория Групп", она где-то есть на конспектах
- для сумм надо юзать \limits
- В теореме Пойа как-то неожиданно появляется группа перестановок, в ее условии тут это почему-то явно не сказано
- Можно добавить пример подсчета количества различных раскрасок кубика в k цветов. Раскраски эквивалентны, если одну можно получить из другой поворотами кубика.
- взяли Задача об ожерельях
- а если можно делать не только сдвиги, а еще и отражения? (это называется bracelets: https://en.wikipedia.org/wiki/Necklace_(combinatorics) )
- ссылки в статье почему-то оформлены как внешние, хотя должны быть внутренними
- lcm и gcd обернуть в \operatorname или \mathrm
7. Динамическое программирование
- Кратчайший путь в ациклическом графе
- в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится
- псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData
- Задача о расстановке знаков в выражении
- "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке
- ссылка просто на "динамическое программирование" в википедии не нужна
- доказать оптимальность
- нет номера страницы в источнике
- Задача о наибольшей общей подпоследовательности
- Задача о порядке перемножения матриц
- Задача о наибольшей возрастающей подпоследовательности
- Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
- Метод четырех русских для умножения матриц
- Применение метода четырех русских в задачах ДП на примере задачи о НОП
- Задача коммивояжера, ДП по подмножествам
- указать страницы в источниках
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- Задача о расстоянии Дамерау-Левенштейна
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
- Задача о наибольшей подпоследовательности-палиндроме
- !!! Meet-in-the-middle
- можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.
- Динамическое программирование по профилю
- Задача о рюкзаке
- разделы первого уровня должны быть ==
- Динамика по поддеревьям
- разделы первого уровня должны быть ==, а не =
- эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть
8. Теория вероятностей
- англоязычные термины во все статьи этого раздела для основных определений и понятий
- Вероятностное пространство, элементарный исход, событие
- для угловых скобок юзать \langle, \rangle
- перечисление оформить как википеречисление
- привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий.
- Независимые события
- определение несовместных событий
- критерий для независимости несовместных событий
- Условная вероятность
- раздел "определение" не нужен, перенести в заголовок
- Формула Байеса
- определение какое-то дурацкое и копипаста с википедии
- Формула полной вероятности
- примеры перечислить как подразделы
- Дискретная случайная величина
- Независимые случайные величины
- взяли Математическое ожидание случайной величины
- пробел перед открывающей скобкой должен быть
- Дисперсия случайной величины
- взяли Ковариация случайных величин
- Корреляция случайных величин
- Энтропия случайного источника
- воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
- В Романовском добавить издание и страницу
- Симуляция одним распределением другого
- так и нет нормального определения распределения
- список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли.
- издания и страницы в испточниках
- Арифметическое кодирование
- раздел "определение" не нужен, перенести в заголовок
- Парадоксы теории вероятностей
- "Пусть p - предельно ненулевая вероятность" — а что это такое?
- для предела использовать \limits
- Схема Бернулли
- запихать примеры в один раздел "Примеры", и оформить каждый как подраздел
- оформить источник
9. Марковские цепи
- Марковская цепь
- два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
- сделать подраздел "циклические классы"
- "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
- Теорема о поглощении
- определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
- max -> \max
- в конце какая-то муть. Расписать рассуждения чуть подробнее
- Фундаментальная матрица
- написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
- не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
- получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
- Математическое ожидание времени поглощения
- не везде переменные обернуты в латех
- Расчет вероятности поглощения в состоянии
- куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- оформить псевдокод в виде функций, без всяких println
- оформить нормально источник
- Эргодическая марковская цепь
- определения пересекаются с конспектом про марковские цепи
- Регулярная марковская цепь
- Примеры использования Марковских цепей
- !!! Скрытые Марковские модели
- можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики
- Алгоритм Витерби
- "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- а \pi что такое?
- Алгоритм "Вперед-Назад"