http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=188.162.65.86&* 2026-05-24T19:04:19Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Dgerasimov/%D0%A2%D0%B8%D0%BA%D0%B5%D1%82%D1%8B_%D0%BF%D0%BE_%D0%BA%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82%D0%B0%D0%BC_year2013&diff=33507 2013-11-10T17:23:38Z

<p>188.162.65.86: /* 5. Алгоритмы сжатия */</p> <hr /> <div>Тикеты индексируются как &quot;X-Y&quot;, где X — номер раздела, Y — номер конспекта внутри раздела<br /> == 1. Отношения ==<br /> # '''взяли''' [[Определение отношения]]<br /> ## Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде &quot;Операции над отношениями&quot;<br /> ## На виды и примеры отношений дать внутренние ссылки<br /> ## англоязычные термины<br /> ## пункт &quot;Определение&quot; не нужен, см. правила форматирования конспектов<br /> # [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]<br /> ## см. пункт 1.1<br /> ## англоязычные термины<br /> # [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]<br /> ## англоязычные термины<br /> ## добавить внутренних ссылок на эквивдентность, порядки и т.д.<br /> # [[Симметричное отношение]]<br /> ## англоязычные термины<br /> # [[Антисимметричное отношение]]<br /> ## англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние<br /> # [[Транзитивное отношение]]<br /> ## англоязычные термины<br /> # [[Отношение порядка]]<br /> ## англоязычные термины<br /> # [[Отношение эквивалентности]]<br /> ## пункт &quot;определение&quot; не нужен<br /> ## англоязычные термины<br /> # [[Транзитивное замыкание|Транзитивное замыкание отношения]]<br /> ## англоязычные термины<br /> # '''взяли''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]<br /> ## пункт &quot;Задача&quot; не нужен<br /> ## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть &quot;бесконечная матрица&quot; бинарного отношения, и что мы такую же &quot;бесконечную матрицу&quot; заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.<br /> # '''!!!''' [[Транзитивный остов]]<br /> ## возможно, мне показалось, но там, где &quot;ацикличен&quot;, надо писать &quot;без петель&quot;<br /> ## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец<br /> ## аналогично предыдущему, придумать обобщение на случай бесконечных отношений<br /> <br /> == '''!!!''' 2. Булевы функции ==<br /> # [[Определение булевой функции]]<br /> ## англоязычных терминов<br /> ## термины вроде &quot;самодвойственная и т.п.&quot; встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.<br /> # [[Суперпозиции]]<br /> ## англоязычных терминов<br /> # [[ДНФ]]<br /> ## англоязычных терминов<br /> ## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо<br /> # [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]<br /> ## англоязычных терминов<br /> # [[КНФ]]<br /> ## англоязычных терминов<br /> ## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо<br /> # [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]<br /> ## англоязычных терминов<br /> ## написать, почему факт того, что существует полиномиальный алгоритм, интересен<br /> # [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]<br /> ## англоязычных терминов<br /> ## &quot;Предпосылки&quot; — странное название, переименовать в &quot;Полнота&quot;, например<br /> # [[Полные системы функций. Теорема Поста о полной системе функций]]<br /> ## англоязычных терминов<br /> # [[Представление функции класса DM с помощью медианы]]<br /> # [[Пороговая функция]]<br /> <br /> == '''!!!''' 3. Схемы из функциональных элементов ==<br /> # [[Реализация булевой функции схемой из функциональных элементов]]<br /> ## англоязычных терминов (на схемную сложность, глубину схемы)<br /> # [[Теорема о нижней границе для количества элементов в схеме]]<br /> # [[Cумматор]]<br /> ## англоязычных терминов <br /> # [[Каскадный сумматор]]<br /> ## англоязычных терминов <br /> # [[Двоичный каскадный сумматор]]<br /> ## англоязычных терминов <br /> ## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать<br /> # [[Реализация вычитания сумматором]]<br /> # [[Матричный умножитель]]<br /> ## пункт &quot;определение&quot; не нужен<br /> ## англоязычных терминов<br /> ## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга<br /> # [[Дерево Уоллеса]]<br /> ## пункт &quot;определение&quot; не нужен<br /> ## англоязычных терминов<br /> ## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга<br /> <br /> == '''!!!''' 4. Представление информации ==<br /> # [[Кодирование информации]]<br /> # [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]<br /> # [[Представление вещественных чисел]]<br /> # [[Представление символов, таблицы кодировок]]<br /> ## сюда неплохо было бы добавить пример на python с созданием ''юникодной'' строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length<br /> <br /> == 5. Алгоритмы сжатия ==<br /> # '''взяли''' [[Алгоритм Хаффмана]]<br /> ## &quot;Использует только частоту появления одинаковых байт в изображении.&quot; што<br /> ## ссылки на википедию, русскую и английскую<br /> ## внутренние ссылки на префиксный код и все такое.<br /> # [[Алгоритм Ху-Таккера]]<br /> # [[Неравенство Крафта]]<br /> ## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.<br /> ## А зачем оно нужно? Просто интересный факт?<br /> # [[Неравенство Макмиллана]]<br /> ## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.<br /> ## А зачем оно нужно? Просто интересный факт?<br /> # [[Алгоритм LZW]]<br /> # [[Алгоритмы LZ77 и LZ78]]<br /> # '''взяли''' [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]<br /> # [[Преобразование MTF]]<br /> # [[Расстояние Хэмминга]]<br /> # [[Избыточное кодирование, код Хэмминга]]<br /> <br /> == Комбинаторика ==<br /> *[[Комбинаторные объекты]]<br /> *[[Лексикографический порядок]]<br /> *[[Формула включения-исключения]]<br /> *[[Генерация комбинаторных объектов в лексикографическом порядке]]<br /> *[[Получение номера по объекту]]<br /> *[[Получение объекта по номеру]]<br /> *[[Получение следующего объекта]]<br /> *[[Коды Грея]]<br /> *[[Коды Грея для перестановок]]<br /> *[[Коды антигрея]]<br /> *[[Цепные коды]]<br /> *[[Правильные скобочные последовательности]]<br /> *[[Действие перестановки на набор из элементов, представление в виде циклов]]<br /> *[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]<br /> *[[Методы генерации случайного сочетания]]<br /> *[[Таблица инверсий]]<br /> *[[Умножение перестановок, обратная перестановка, группа перестановок]]<br /> *[[Теорема Кэли]]<br /> *[[Матричное представление перестановок]]<br /> *[[Задача о минимуме/максимуме скалярного произведения]]<br /> *[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]<br /> *[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]<br /> *[[Производящая функция]]<br /> *[[Лемма Бёрнсайда и Теорема Пойа]]<br /> *[[Задача об ожерельях]]<br /> <br /> == [[Динамическое программирование]] ==<br /> *[[Кратчайший путь в ациклическом графе]]<br /> *[[Задача о расстановке знаков в выражении]]<br /> *[[Задача о наибольшей общей подпоследовательности]]<br /> *[[Задача о порядке перемножения матриц]]<br /> *[[Задача о наибольшей возрастающей подпоследовательности]]<br /> *[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]<br /> *[[Метод четырех русских для умножения матриц]]<br /> *[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<br /> *[[Задача коммивояжера, ДП по подмножествам]]<br /> *[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]<br /> *[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]<br /> *[[Задача о расстоянии Дамерау-Левенштейна]]<br /> *[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]<br /> *[[Задача о наибольшей подпоследовательности-палиндроме]]<br /> *[[Meet-in-the-middle]]<br /> *[[Динамическое программирование по профилю]]<br /> *[[Задача о рюкзаке]]<br /> *[[Динамика по поддеревьям]]<br /> <br /> == Теория вероятностей ==<br /> *[[Вероятностное пространство, элементарный исход, событие]]<br /> *[[Независимые события]]<br /> *[[Условная вероятность]]<br /> *[[Формула Байеса]]<br /> *[[Формула полной вероятности]]<br /> *[[Дискретная случайная величина]]<br /> *[[Независимые случайные величины]]<br /> *[[Математическое ожидание случайной величины]]<br /> *[[Дисперсия случайной величины]]<br /> *[[Ковариация случайных величин]]<br /> *[[Корреляция случайных величин]]<br /> *[[Энтропия случайного источника]]<br /> *[[Симуляция одним распределением другого]]<br /> *[[Арифметическое кодирование]]<br /> *[[Парадоксы теории вероятностей]]<br /> *[[Схема Бернулли]]<br /> <br /> == Марковские цепи ==<br /> <br /> * [[Марковская цепь]]<br /> * [[Теорема о поглощении]]<br /> * [[Фундаментальная матрица]]<br /> * [[Математическое ожидание времени поглощения]]<br /> * [[Расчет вероятности поглощения в состоянии]]<br /> * [[Эргодическая марковская цепь]]<br /> * [[Регулярная марковская цепь]]<br /> * [[Примеры использования Марковских цепей]]<br /> * [[Скрытые Марковские модели]]<br /> * [[Алгоритм Витерби]]<br /> * [[Алгоритм &quot;Вперед-Назад&quot;]]</div>

188.162.65.86