Дискретная математика, алгоритмы и структуры данных

Материал из Викиконспекты
Версия от 23:16, 5 ноября 2013; Dgerasimov (обсуждение | вклад) (Алгоритмы сжатия)
Перейти к: навигация, поиск


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

Содержание

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

Отношения

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

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

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

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

  1. Алгоритм Хаффмана
    1. "Использует только частоту появления одинаковых байт в изображении." што
    2. ссылки на википедию, русскую и английскую
    3. внутренние ссылки на префиксный код и все такое.
  2. Алгоритм Ху-Таккера
  3. Неравенство Крафта
    1. Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
    2. А зачем оно нужно? Просто интересный факт?
  4. Неравенство Макмиллана
    1. Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
    2. А зачем оно нужно? Просто интересный факт?
  5. Алгоритм LZW
  6. Алгоритмы LZ77 и LZ78
  7. взяли Преобразование Барроуза-Уиллера и обратное ему
  8. Преобразование MTF
  9. Расстояние Хэмминга
  10. Избыточное кодирование, код Хэмминга

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

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

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

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

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

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

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

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

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

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

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

Хеширование

Сортировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матроиды

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

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

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