Дискретная математика, алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 32: Строка 32:
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
−
*[[Троичная логика]]
+
*[[Троичная логика]]<tex>^\star</tex>
  
 
== Схемы из функциональных элементов ==
 
== Схемы из функциональных элементов ==
Строка 41: Строка 41:
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
 
*[[Двоичный каскадный сумматор]]
−
*[[Троичный сумматор]]
+
*[[Троичный сумматор]]<tex>^\star</tex>
 
*[[Реализация вычитания сумматором]]
 
*[[Реализация вычитания сумматором]]
 
*[[Матричный умножитель]]
 
*[[Матричный умножитель]]
 
*[[Дерево Уоллеса]]
 
*[[Дерево Уоллеса]]
 
*[[Контактная схема]]
 
*[[Контактная схема]]
−
*[[Квантовые гейты]]
+
*[[Квантовые гейты]]<tex>^\star</tex>
  
 
== Представление информации ==
 
== Представление информации ==
Строка 52: Строка 52:
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
 
*[[Представление вещественных чисел]]
 
*[[Представление вещественных чисел]]
−
*[[Представление символов, таблицы кодировок]]
+
*[[Представление символов, таблицы кодировок]]<tex>^\star</tex>
  
 
== Алгоритмы сжатия ==
 
== Алгоритмы сжатия ==
Строка 58: Строка 58:
 
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
 
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
 
* [[Алгоритм Хаффмана за O(n)]]
 
* [[Алгоритм Хаффмана за O(n)]]
−
* [[Алгоритм Ху-Таккера]]
+
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
 
* [[Неравенство Крафта]]
 
* [[Неравенство Крафта]]
 
* [[Неравенство Макмиллана]]
 
* [[Неравенство Макмиллана]]
 
* [[Код Шеннона]]
 
* [[Код Шеннона]]
−
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]
+
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
 
* [[Алгоритмы LZ77 и LZ78]]
 
* [[Алгоритмы LZ77 и LZ78]]
 
* [[Алгоритм LZW]]
 
* [[Алгоритм LZW]]
−
* [[Алгоритм LZSS]]
+
* [[Алгоритм LZSS]]<tex>^\star</tex>
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 
* [[Преобразование MTF]]
 
* [[Преобразование MTF]]
 
* [[Расстояние Хэмминга]]
 
* [[Расстояние Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
−
* [[Гамма-, дельта- и омега-код Элиаса]]
+
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
  
 
== Комбинаторика ==
 
== Комбинаторика ==
Строка 87: Строка 87:
 
* [[Получение объекта по номеру]]
 
* [[Получение объекта по номеру]]
 
* [[Получение следующего объекта]]
 
* [[Получение следующего объекта]]
−
* [[Получение предыдущего объекта]]   
+
* [[Получение предыдущего объекта]]<tex>^\star</tex>  
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
−
* [[Методы генерации случайного сочетания]]
+
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
  
 
=== Подсчёт числа объектов ===
 
=== Подсчёт числа объектов ===
Строка 99: Строка 99:
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга второго рода]]
 
* [[Числа Стирлинга второго рода]]
−
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]
+
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 
* [[Числа Каталана]]
 
* [[Числа Каталана]]
  
Строка 107: Строка 107:
 
* [[Таблица инверсий]]
 
* [[Таблица инверсий]]
 
* [[Теорема Кэли]]
 
* [[Теорема Кэли]]
−
* [[Матричное представление перестановок]]
+
* [[Матричное представление перестановок]
 
* [[Задача о минимуме/максимуме скалярного произведения]]
 
* [[Задача о минимуме/максимуме скалярного произведения]]
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]

Версия 15:31, 11 января 2015


Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Содержание

Первый семестр

Отношения

Булевы функции

Схемы из функциональных элементов

Представление информации

Алгоритмы сжатия

Комбинаторика

Комбинаторные объекты

Генерация комбинаторных объектов

Подсчёт числа объектов

Свойства комбинаторных объектов

Динамическое программирование

Классические задачи динамического программирования

Способы оптимизации методов динамического программирования

Другие задачи

Теория вероятностей

Марковские цепи

Второй семестр

Амортизационный анализ

Приоритетные очереди

Система непересекающихся множеств

Поисковые структуры данных

Дерево отрезков

Дерево Фенвика

Хеширование

Сортировка

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

Связь между структурами данных

Третий семестр

Основные определения теории графов

Связность в графах

Остовные деревья

Построение остовных деревьев

Свойства остовных деревьев

Обходы графов

Эйлеровы графы

Гамильтоновы графы

Укладки графов

Раскраски графов

Обход в глубину

Кратчайшие пути в графах

Задача о паросочетании

Задача о максимальном потоке

Задача о потоке минимальной стоимости

Четвертый семестр

Основные определения. Простые комбинаторные свойства слов

Поиск подстроки в строке

Суффиксное дерево

Суффиксный массив

Задача о наименьшем общем предке

Матроиды

Основные факты теории матроидов

Пересечение матроидов

Объединение матроидов

Теория расписаний

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика,_алгоритмы_и_структуры_данных&oldid=44129»