Дискретная математика:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎2 Булевы функции)
(→‎Алгоритмы сжатия)
Строка 81: Строка 81:
 
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>
 
# [[Представление символов, таблицы кодировок]]<tex>^\star</tex>
  
−
== Алгоритмы сжатия ==
+
== 5 Алгоритмы сжатия ==
−
* [[Алгоритм Хаффмана]]
+
# [[Алгоритм Хаффмана]]
−
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
+
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
−
* [[Алгоритм Хаффмана за O(n)]]
+
# [[Алгоритм Хаффмана за O(n)]] 1
−
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
+
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
−
* [[Неравенство Крафта]]
+
# [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
−
* [[Неравенство Макмиллана]]
+
# [[Неравенство Крафта]]
−
* [[Код Шеннона]]
+
# [[Неравенство Макмиллана]]
−
* [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
+
# [[Код Шеннона]]
−
* [[Алгоритмы LZ77 и LZ78]]
+
# [[Оптимальный префиксный код с длиной кодового слова не более L бит]]<tex>^\star</tex>
−
* [[Алгоритм LZW]]
+
# [[Алгоритмы LZ77 и LZ78]] 2
−
* [[Алгоритм LZSS]]<tex>^\star</tex>
+
## Переменные и константы взять в Tex
−
* [[Алгоритм LZMA]]<tex>^\star</tex>
+
## Добавить примеры итоговых таблиц
−
* [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
+
## Рассказать, как декодировать
−
* [[Преобразование MTF]]
+
## Правильно оформить источники информации
−
* [[Расстояние Хэмминга]]
+
## Получше расписать описание алгоритма
−
* [[Избыточное кодирование, код Хэмминга]]
+
## Таблицы сделать красивыми
−
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
+
## Интервики
 +
# [[Алгоритм LZW]] 0,25
 +
## См. также
 +
# [[Алгоритм LZSS]]<tex>^\star</tex>
 +
# [[Алгоритм LZMA]]<tex>^\star</tex>
 +
# [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 +
# [[Преобразование MTF]]
 +
# [[Расстояние Хэмминга]]
 +
# [[Избыточное кодирование, код Хэмминга]] 0,25
 +
## См. также
 +
# [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex> 0,25
 +
## См. также
  
 
== Комбинаторика ==
 
== Комбинаторика ==

Версия 00:03, 1 марта 2017

1. Отношения

  1. Определение отношения 0.5
    1. Дефисы заменить на тире
    2. Оформить красиво источники информации
    3. Английские термины к видам отношений
  2. Композиция отношений, степень отношения, обратное отношение 2
    1. Английские термины
    2. Источники информации
    3. Свойства оформить красиво
    4. Свойства обратного отношения
  3. Рефлексивное отношение. Антирефлексивное отношение. 0,25
    1. См. также
  4. Симметричное отношение
  5. Антисимметричное отношение
  6. Транзитивное отношение 0,25
    1. См. также
  7. Отношение порядка 0,5
    1. Английские термины
    2. См. также
  8. Изоморфизмы упорядоченных множеств[math]^\star[/math]
  9. Отношение эквивалентности 0,25
    1. См. также
  10. Транзитивное замыкание отношения 0,25
    1. См. также
  11. Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
  12. Транзитивный остов 0,25
    1. Английские термины

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

  1. Определение булевой функции 0,5
    1. Добавить интервики на термины монотонности, линейности, сохранения [math]0[/math] и [math]1[/math], самодвойственности для булевой функции. (все определения здесь)
  2. Побитовые операции[math]^\star[/math]
  3. Суперпозиции 0,25
    1. См. также
  4. ДНФ
  5. Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
  6. КНФ 0,25
    1. См. также
  7. 2-SAT
  8. XOR-SAT[math]^\star[/math]
  9. Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
  10. Полином Жегалкина, преобразование Мёбиуса 0,25
    1. См. также
  11. Полные системы функций. Теорема Поста о полной системе функций 0,25
    1. См. также
  12. Представление функции класса DM с помощью медианы 0.25
    1. См. также
  13. Пороговая функция 0.25
    1. См. также
  14. Троичная логика[math]^\star[/math]

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

  1. Реализация булевой функции схемой из функциональных элементов
  2. Простейшие методы синтеза схем из функциональных элементов 0.5
    1. Изменить знаки неравенств
    2. Ссылку на метод синтеза схем Шэннона сделать примечанием
    3. Определение жирным
    4. Оформить правильно См. также и Источники информации
    5. Увеличить дроби
  3. Метод Лупанова синтеза схем 0.5
    1. Заменить литературу на источники информации
    2. Изменить знаки неравенств
    3. Запятые криво стоят в определении функции g
    4. Увеличить дроби
  4. Cумматор
  5. Каскадный сумматор
  6. Двоичный каскадный сумматор
  7. Троичный сумматор[math]^\star[/math]
  8. Реализация вычитания сумматором
  9. Матричный умножитель
  10. Дерево Уоллеса
  11. Контактная схема 1
    1. Перерисовать картинки с построением контактных схем и дерево конъюнктов
  12. Триггеры[math]^\star[/math]
  13. Квантовые гейты[math]^\star[/math]

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

  1. Кодирование информации
  2. Представление целых чисел: прямой код, код со сдвигом, дополнительный код
  3. Представление вещественных чисел
  4. Представление символов, таблицы кодировок[math]^\star[/math]

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

  1. Алгоритм Хаффмана
  2. Оптимальное хранение словаря в алгоритме Хаффмана
  3. Алгоритм Хаффмана за O(n) 1
    1. Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
  4. Алгоритм Ху-Таккера[math]^\star[/math]
  5. Неравенство Крафта
  6. Неравенство Макмиллана
  7. Код Шеннона
  8. Оптимальный префиксный код с длиной кодового слова не более L бит[math]^\star[/math]
  9. Алгоритмы LZ77 и LZ78 2
    1. Переменные и константы взять в Tex
    2. Добавить примеры итоговых таблиц
    3. Рассказать, как декодировать
    4. Правильно оформить источники информации
    5. Получше расписать описание алгоритма
    6. Таблицы сделать красивыми
    7. Интервики
  10. Алгоритм LZW 0,25
    1. См. также
  11. Алгоритм LZSS[math]^\star[/math]
  12. Алгоритм LZMA[math]^\star[/math]
  13. Преобразование Барроуза-Уиллера и обратное ему
  14. Преобразование MTF
  15. Расстояние Хэмминга
  16. Избыточное кодирование, код Хэмминга 0,25
    1. См. также
  17. Гамма-, дельта- и омега-код Элиаса[math]^\star[/math] 0,25
    1. См. также

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

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

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

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

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика:Тикеты&oldid=60498»