1679
правок
Изменения
→6. Комбинаторика
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений
== '''!!!''' 2. Булевы функции ==
# [[Определение булевой функции]]
## англоязычных терминов
# [[Пороговая функция]]
== '''!!!''' 3. Схемы из функциональных элементов ==
# [[Реализация булевой функции схемой из функциональных элементов]]
## англоязычных терминов (на схемную сложность, глубину схемы)
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
== '''!!!взяли''' 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 возмножно?
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
# [[Производящая функция]]
# '''!!!взяли''' [[Лемма Бёрнсайда и Теорема Пойа]]
## сюда добавить категорию "Теория Групп", она где-то есть на конспектах
## для сумм надо юзать \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. Марковские цепи ==
