Изменения

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела= Первый семестр =1. Отношения ==# '''взяли''' [[Определение отношения]]## Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"## На виды и примеры отношений дать внутренние ссылки## англоязычные термины## пункт "Определение" не нужен, см. правила форматирования конспектов# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]## см. пункт 1.1## англоязычные термины# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]## англоязычные термины## добавить внутренних ссылок на эквивдентность, порядки и т.д.# [[Симметричное отношение]]## англоязычные термины# [[Антисимметричное отношение]]## англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние# [[Транзитивное отношение]]## англоязычные термины# [[Отношение порядка]]## англоязычные термины# [[Отношение эквивалентности]]## пункт "определение" не нужен## англоязычные термины# [[Транзитивное замыкание|Транзитивное замыкание отношения]]## англоязычные термины# '''взяли''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]## пункт "Задача" не нужен## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.# '''!!!''' [[Транзитивный остов]]## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец## аналогично предыдущему, придумать обобщение на случай бесконечных отношений

== Отношения 2. Булевы функции ==*# [[Определение отношениябулевой функции]]*## англоязычных терминов## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношениеСуперпозиции]]*## англоязычных терминов# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.ДНФ]]*## англоязычных терминов## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо# [[Симметричное отношениеСокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]*## англоязычных терминов# [[Антисимметричное отношениеКНФ]]*## англоязычных терминов## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо# [[Транзитивное отношениеСпециальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]*## англоязычных терминов## написать, почему факт того, что существует полиномиальный алгоритм, интересен# [[Отношение порядкаПолином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]*## англоязычных терминов## "Предпосылки" — странное название, переименовать в "Полнота", например# [[Отношение эквивалентностиПолные системы функций. Теорема Поста о полной системе функций]]*[[Транзитивное замыкание|Транзитивное замыкание отношения]]## англоязычных терминов*# [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношенияПредставление функции класса DM с помощью медианы]]*# [[Транзитивный остовПороговая функция]]

== Булевы функции 3. Схемы из функциональных элементов ==*# [[Определение Реализация булевой функциисхемой из функциональных элементов]]*## англоязычных терминов (на схемную сложность, глубину схемы)# [[СуперпозицииМетод Лупанова синтеза схем]]*# [[ДНФCумматор]]*## англоязычных терминов # [[КНФКаскадный сумматор]]*## англоязычных терминов # [[Полином ЖегалкинаДвоичный каскадный сумматор]]*## англоязычных терминов ## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать# [[Полные системы функций. Теорема Поста о полной системе функцийРеализация вычитания сумматором]]*# [[Сокращенная и минимальная ДНФМатричный умножитель]]*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]## пункт "определение" не нужен## англоязычных терминов*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ ## надо писать в форме Крома]]определении схем, за сколько они работают, а то не ясно их отличие друг от друга*# [[Преобразование Мёбиуса для получения коэффициентов полинома ЖегалкинаДерево Уоллеса]]*[[Представление функции класса DM с помощью медианы]]## пункт "определение" не нужен## англоязычных терминов*[[Пороговая функция]]## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга

== Схемы из функциональных элементов '''взяли''' 4. Представление информации ==*# [[Реализация булевой функции схемой из функциональных элементовКодирование информации]]*# [[Теорема о нижней границе для количества элементов в схемеПредставление целых чисел: прямой код, код со сдвигом, дополнительный код]]*# [[CумматорПредставление вещественных чисел]]*# [[Каскадный сумматорПредставление символов, таблицы кодировок]]*[[Двоичный каскадный сумматор]]*[[Реализация вычитания сумматором]]*[[Матричный умножитель]]*[[Дерево Уоллеса]]## сюда неплохо было бы добавить пример на 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'' [[Алгоритм LZWПолучение объекта по номеру]]*## "В начале каждого шага numOfObject — номер комбинаторного объекта среди объектов с заданным префиксом." — с заданным — это с каким?## опять в коде чередуются использования табов и фигурных скобок для отделения блоков. Оставить только табы.## Аналогично предыдущим замечаниям про xor# '''fixed''' [[Алгоритмы LZ77 Получение следующего объекта]]## дополнить генерацией следующего сочетания, разбиения на сумму, скобочной последовательности и LZ78мультиперестановки.# '''взяли''' [[Коды Грея]]*## отдельный раздел "определение" не нужен## картинку с построением, имхо, надо немного увеличить## а что такое паразитные состояния? В общем, про применение надо попонятнее написать. И вообще про это в разделе "применение" надо написать## "Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. " — если не пишется про это в конспекте, надо кинуть внешнюю ссылку хотя бы.## В применении надо написать хотя бы немного пояснений, а то применяться-то применяется, а как конкретно — непонятно# [[Коды Грея для перестановок]]## отдельный раздел "определение" не нужен# '''взяли''' [[Коды антигрея]]## Аналогичну пункту 8, "Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность. " — а как конкретно он применяется для выявления поломки?## "Заметим, что для n > 2 невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2. " — ээ, а для n = 2 возмножно?## Для черточки над G надо использовать не bar, а overline# [[Цепные коды]]## ссылку на хоть какие-нибудь источники## а зачем они нужны?# [[Правильные скобочные последовательности]]## англоязычные термины## выделить в псевдокоде ключевые слова жирным## Обозначить биномиальные коэффециенты нормально (не <tex>C_n^k</tex>, а <tex>\binom{n}{k}</tex>)# [[Действие перестановки на набор из элементов, представление в виде циклов]]# [[Преобразование БарроузаМетод генерации случайной перестановки, алгоритм Фишера-УиллераЙетса]]*## убрать пункт "постановка задачи", вынести в заголовок# [[Обратное преобразование БарроузаМетоды генерации случайного сочетания]]## убрать пункт "постановка задачи", вынести в заголовок## что-Уиллерато описание алгоритма не очень соответствует псевдокоду (для O(n^2))# [[Таблица инверсий]]*# [[Умножение перестановок, обратная перестановка, группа перестановок]]## Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.## ссылку на русскую и английскую википедию, на симметрическую группу# [[Теорема Кэли]]# [[Преобразование MTFМатричное представление перестановок]]*# [[Расстояние ХэммингаЗадача о минимуме/максимуме скалярного произведения]]*## непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть# [[Избыточное кодированиеЗадача о монотонных подпоследовательностях, код Хэммингатеорема о связи длины НВП и НУП]]*# [[Неравенство КрафтаНахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]*# [[Неравенство МакмилланаПроизводящая функция]]*# '''взяли''' [[Алгоритм ХуЛемма Бёрнсайда и Теорема Пойа]]## сюда добавить категорию "Теория Групп", она где-Таккерато есть на конспектах## для сумм надо юзать \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. Теория вероятностей ==*[[Кратчайший путь в ациклическом графе]]*[[Задача о расстановке знаков в выражении]]*[[Задача о наибольшей общей подпоследовательности]]*[[Задача о порядке перемножения матриц]]*[[Задача о наибольшей возрастающей подпоследовательности]]*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]*[[Метод четырех русских для умножения матриц]]*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]*[[Задача коммивояжера, ДП по подмножествам]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]*[[Задача о расстоянии Дамерау-Левенштейна]]*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]*[[Задача о наибольшей подпоследовательности-палиндроме]]*[[Meet-in-the-middle]]*[[Динамическое программирование по профилю]]*[[Задача о рюкзаке]]*[[Динамика по поддеревьям]]

== Теория вероятностей ==*[[Вероятностное пространство, элементарный исход, событие]]*[[Независимые события]]*[[Условная вероятность]]*[[Формула Байеса]]*[[Формула полной вероятности]]*[[Дискретная случайная величина]]*[[Независимые случайные величины]]*[[Математическое ожидание случайной величины]]*[[Дисперсия случайной величины]]*[[Ковариация случайных величин]]*[[Корреляция случайных величин]]*[[Энтропия случайного источника]]*[[Симуляция одним распределением другого]]*[[Арифметическое кодирование]]*[[Парадоксы теории вероятностей]]*[[Схема Бернулли]]'''англоязычные термины во все статьи этого раздела для основных определений и понятий'''

* == 9. Марковские цепи == # [[Марковская цепь]]* ## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)## сделать подраздел "циклические классы"## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?# [[Теорема о поглощении]]* ## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.## max -> \max ## в конце какая-то муть. Расписать рассуждения чуть подробнее# [[Фундаментальная матрица]]* ## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть# [[Математическое ожидание времени поглощения]]* ## не везде переменные обернуты в латех# [[Расчет вероятности поглощения в состоянии]]* ## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.## имена переменных в тексте оборачиваются в \mathrm или \mathtt## оформить псевдокод в виде функций, без всяких println## оформить нормально источник# [[Эргодическая марковская цепь]]* ## определения пересекаются с конспектом про марковские цепи# [[Регулярная марковская цепь]]* # [[Примеры использования Марковских цепей]]* # '''!!!''' [[Скрытые Марковские модели]]* ## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики# [[Алгоритм Витерби]]* ## "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?## имена переменных в тексте оборачиваются в \mathrm или \mathtt## а \pi что такое?# [[Алгоритм "Вперед-Назад"]]