Участник:Dgerasimov/Тикеты по конспектам year2013 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Комбинаторика)
(→‎Комбинаторика)
Строка 105: Строка 105:
 
# [[Избыточное кодирование, код Хэмминга]]
 
# [[Избыточное кодирование, код Хэмминга]]
  
−
== Комбинаторика ==
+
== 6. Комбинаторика ==
 
# [[Комбинаторные объекты]]
 
# [[Комбинаторные объекты]]
 
## пункт "определение" не нужен
 
## пункт "определение" не нужен

Версия 13:53, 16 ноября 2013

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела

1. Отношения

  1. взяли Определение отношения
    1. Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
    2. На виды и примеры отношений дать внутренние ссылки
    3. англоязычные термины
    4. пункт "Определение" не нужен, см. правила форматирования конспектов
  2. Композиция отношений, степерь отношения, обратное отношение
    1. см. пункт 1.1
    2. англоязычные термины
  3. Рефлексивное отношение. Антирефлексивное отношение.
    1. англоязычные термины
    2. добавить внутренних ссылок на эквивдентность, порядки и т.д.
  4. Симметричное отношение
    1. англоязычные термины
  5. Антисимметричное отношение
    1. англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
  6. Транзитивное отношение
    1. англоязычные термины
  7. Отношение порядка
    1. англоязычные термины
  8. Отношение эквивалентности
    1. пункт "определение" не нужен
    2. англоязычные термины
  9. Транзитивное замыкание отношения
    1. англоязычные термины
  10. взяли Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
    1. пункт "Задача" не нужен
    2. интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
  11. !!! Транзитивный остов
    1. возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
    2. если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
    3. аналогично предыдущему, придумать обобщение на случай бесконечных отношений

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

  1. Определение булевой функции
    1. англоязычных терминов
    2. термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.
  2. Суперпозиции
    1. англоязычных терминов
  3. ДНФ
    1. англоязычных терминов
    2. писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
  4. Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна
    1. англоязычных терминов
  5. КНФ
    1. англоязычных терминов
    2. писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
  6. Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
    1. англоязычных терминов
    2. написать, почему факт того, что существует полиномиальный алгоритм, интересен
  7. Полином Жегалкина, преобразование Мёбиуса
    1. англоязычных терминов
    2. "Предпосылки" — странное название, переименовать в "Полнота", например
  8. Полные системы функций. Теорема Поста о полной системе функций
    1. англоязычных терминов
  9. Представление функции класса DM с помощью медианы
  10. Пороговая функция

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

  1. Реализация булевой функции схемой из функциональных элементов
    1. англоязычных терминов (на схемную сложность, глубину схемы)
  2. Теорема о нижней границе для количества элементов в схеме
  3. Cумматор
    1. англоязычных терминов
  4. Каскадный сумматор
    1. англоязычных терминов
  5. Двоичный каскадный сумматор
    1. англоязычных терминов
    2. из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
  6. Реализация вычитания сумматором
  7. Матричный умножитель
    1. пункт "определение" не нужен
    2. англоязычных терминов
    3. надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
  8. Дерево Уоллеса
    1. пункт "определение" не нужен
    2. англоязычных терминов
    3. надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга

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

  1. Кодирование информации
  2. Представление целых чисел: прямой код, код со сдвигом, дополнительный код
  3. Представление вещественных чисел
  4. Представление символов, таблицы кодировок
    1. сюда неплохо было бы добавить пример на python с созданием юникодной строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length

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

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

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

  1. Комбинаторные объекты
    1. пункт "определение" не нужен
  2. Лексикографический порядок
    1. собственно определения лексикографического порядка тут и нет. англоязычный термин.
    2. ссылку на английскую википедию
    3. Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
    4. return <, return = и т.п. выглядят ужасно. Сделать return LESS, return EQUAL и т.п.
  3. Формула включения-исключения
    1. Перед открывающей скобкой нужен пробел
    2. ссылки на ангийскую вики
  4. Генерация комбинаторных объектов в лексикографическом порядке
  5. Получение номера по объекту
  6. Получение объекта по номеру
  7. Получение следующего объекта
  8. Коды Грея
  9. Коды Грея для перестановок
  10. Коды антигрея
  11. Цепные коды
    1. ссылку на английскую вики
    2. а зачем они нужны?
  12. Правильные скобочные последовательности
    1. англоязычные термины
  13. Действие перестановки на набор из элементов, представление в виде циклов
  14. Метод генерации случайной перестановки, алгоритм Фишера-Йетса
  15. Методы генерации случайного сочетания
  16. Таблица инверсий
  17. Умножение перестановок, обратная перестановка, группа перестановок
    1. Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.
  18. Теорема Кэли
  19. Матричное представление перестановок
  20. Задача о минимуме/максимуме скалярного произведения
    1. непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть
  21. Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
  22. Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
  23. Производящая функция
  24. Лемма Бёрнсайда и Теорема Пойа
    1. сюда добавить категорию "Теория Групп", она где-то есть на конспектах
  25. Задача об ожерельях

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Dgerasimov/Тикеты_по_конспектам_year2013&oldid=33677»