http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=KirillВикиконспекты - Вклад участника [ru]2026-06-13T18:27:38ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B&diff=5548Дискретная математика и алгоритмы2010-12-06T21:51:07Z<p>Kirill: /* Комбинаторика */</p>
<hr />
<div>== Отношения ==<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 />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<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 />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]</div>Kirillhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B&diff=5547Дискретная математика и алгоритмы2010-12-06T21:48:23Z<p>Kirill: </p>
<hr />
<div>== Отношения ==<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 />
*[[Cумматор]]<br />
*[[Каскадный сумматор]]<br />
*[[Двоичный каскадный сумматор]]<br />
*[[Матричный умножитель]]<br />
*[[Дерево Уоллеса]]<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 />
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]</div>Kirill