1679
правок
Изменения
→6. Комбинаторика
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений
== '''!!!''' 2. Булевы функции ==
# [[Определение булевой функции]]
## англоязычных терминов
# [[Пороговая функция]]
== '''!!!''' 3. Схемы из функциональных элементов ==
# [[Реализация булевой функции схемой из функциональных элементов]]
## англоязычных терминов (на схемную сложность, глубину схемы)
# [[Теорема о нижней границе для количества элементов в схемеМетод Лупанова синтеза схем]]
# [[Cумматор]]
## англоязычных терминов
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
== '''!!!взяли''' 4. Представление информации ==
# [[Кодирование информации]]
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
# [[Избыточное кодирование, код Хэмминга]]
== 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
# [[Цепные коды]]
## ссылку на хоть какие-нибудь источники
## а зачем они нужны?
# [[Правильные скобочные последовательности]]
## англоязычные термины
## выделить в псевдокоде ключевые слова жирным
## Обозначить биномиальные коэффециенты нормально (не <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. [[Динамическое программирование]] ==# [[Кратчайший путь в ациклическом графе]]## в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится## псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData# [[Задача о расстановке знаков в выражении]]## "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке## ссылка просто на "динамическое программирование" в википедии не нужна## доказать оптимальность## нет номера страницы в источнике# [[Задача о наибольшей общей подпоследовательности]]# [[Задача о порядке перемножения матриц]]# [[Задача о наибольшей возрастающей подпоследовательности]]# [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]# [[Метод четырех русских для умножения матриц]]# [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]# [[Задача коммивояжера, ДП по подмножествам]]## указать страницы в источниках# [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]# [[Задача о расстоянии Дамерау-Левенштейна]]# [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]# [[Задача о наибольшей подпоследовательности-палиндроме]]# '''!!!''' [[Meet-in-the-middle]]## можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.# [[Динамическое программирование по профилю]]# [[Задача о рюкзаке]]## разделы первого уровня должны быть ==# [[Динамика по поддеревьям]]## разделы первого уровня должны быть ==, а не =## '''эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть''' == 8. Теория вероятностей ==
== 9. Марковские цепи ==
