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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «= Первый семестр = == Отношения == *Определение отношения *[[Композиция отношений|Компози...»)
 
(→‎6. Комбинаторика)
 
(не показаны 43 промежуточные версии 3 участников)
Строка 1: Строка 1:
−
= Первый семестр =
+
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела
 +
== 1. Отношения ==
 +
# '''взяли''' [[Определение отношения]]
 +
## Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
 +
## На виды и примеры отношений дать внутренние ссылки
 +
## англоязычные термины
 +
## пункт "Определение" не нужен, см. правила форматирования конспектов
 +
# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]
 +
## см. пункт 1.1
 +
## англоязычные термины
 +
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
 +
## англоязычные термины
 +
## добавить внутренних ссылок на эквивдентность, порядки и т.д.
 +
# [[Симметричное отношение]]
 +
## англоязычные термины
 +
# [[Антисимметричное отношение]]
 +
## англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
 +
# [[Транзитивное отношение]]
 +
## англоязычные термины
 +
# [[Отношение порядка]]
 +
## англоязычные термины
 +
# [[Отношение эквивалентности]]
 +
## пункт "определение" не нужен
 +
## англоязычные термины
 +
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]
 +
## англоязычные термины
 +
# '''взяли''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
 +
## пункт "Задача" не нужен
 +
## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
 +
# '''!!!''' [[Транзитивный остов]]
 +
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
 +
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
 +
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений
  
−
== Отношения ==
+
== 2. Булевы функции ==
−
*[[Определение отношения]]
+
# [[Определение булевой функции]]
−
*[[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]
+
## англоязычных терминов
−
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
+
## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.
−
*[[Симметричное отношение]]
+
# [[Суперпозиции]]
−
*[[Антисимметричное отношение]]
+
## англоязычных терминов
−
*[[Транзитивное отношение]]
+
# [[ДНФ]]
−
*[[Отношение порядка]]
+
## англоязычных терминов
−
*[[Отношение эквивалентности]]
+
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
−
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
+
# [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
−
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
+
## англоязычных терминов
−
*[[Транзитивный остов]]
+
# [[КНФ]]
 +
## англоязычных терминов
 +
## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
 +
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
 +
## англоязычных терминов
 +
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
 +
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
 +
## англоязычных терминов
 +
## "Предпосылки" — странное название, переименовать в "Полнота", например
 +
# [[Полные системы функций. Теорема Поста о полной системе функций]]
 +
## англоязычных терминов
 +
# [[Представление функции класса DM с помощью медианы]]
 +
# [[Пороговая функция]]
  
−
== Булевы функции ==
+
== 3. Схемы из функциональных элементов ==
−
*[[Определение булевой функции]]
+
# [[Реализация булевой функции схемой из функциональных элементов]]
−
*[[Суперпозиции]]
+
## англоязычных терминов (на схемную сложность, глубину схемы)
−
*[[ДНФ]]
+
# [[Метод Лупанова синтеза схем]]
−
*[[КНФ]]
+
# [[Cумматор]]
−
*[[Полином Жегалкина]]
+
## англоязычных терминов
−
*[[Полные системы функций. Теорема Поста о полной системе функций]]
+
# [[Каскадный сумматор]]
−
*[[Сокращенная и минимальная ДНФ]]
+
## англоязычных терминов
−
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
+
# [[Двоичный каскадный сумматор]]
−
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
+
## англоязычных терминов
−
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
+
## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
−
*[[Представление функции класса DM с помощью медианы]]
+
# [[Реализация вычитания сумматором]]
−
*[[Пороговая функция]]
+
# [[Матричный умножитель]]
 +
## пункт "определение" не нужен
 +
## англоязычных терминов
 +
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
 +
# [[Дерево Уоллеса]]
 +
## пункт "определение" не нужен
 +
## англоязычных терминов
 +
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
  
−
== Схемы из функциональных элементов ==
+
== '''взяли''' 4. Представление информации ==
−
*[[Реализация булевой функции схемой из функциональных элементов]]
+
# [[Кодирование информации]]
−
*[[Теорема о нижней границе для количества элементов в схеме]]
+
# [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
−
*[[Cумматор]]
+
# [[Представление вещественных чисел]]
−
*[[Каскадный сумматор]]
+
# [[Представление символов, таблицы кодировок]]
−
*[[Двоичный каскадный сумматор]]
+
## сюда неплохо было бы добавить пример на python с созданием ''юникодной'' строки и записью ее в файл в кодировке utf-8, а также hex-дампом этого файла и иллюстрацией того, где там BOM, где там каждый символ, и так, чтобы было видно, что UTF-8 — variable-length
−
*[[Реализация вычитания сумматором]]
 
−
*[[Матричный умножитель]]
 
−
*[[Дерево Уоллеса]]
 
  
−
== Представление информации ==
+
== 5. Алгоритмы сжатия ==
−
*[[Кодирование информации]]
+
# '''взяли''' [[Алгоритм Хаффмана]]
−
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
+
## "Использует только частоту появления одинаковых байт в изображении." што
−
*[[Представление вещественных чисел]]
+
## ссылки на википедию, русскую и английскую
−
*[[Представление символов, таблицы кодировок]]
+
## внутренние ссылки на префиксный код и все такое.
 +
# [[Алгоритм Ху-Таккера]]
 +
# [[Неравенство Крафта]]
 +
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
 +
## А зачем оно нужно? Просто интересный факт?
 +
# [[Неравенство Макмиллана]]
 +
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
 +
## А зачем оно нужно? Просто интересный факт?
 +
# [[Алгоритм LZW]]
 +
# [[Алгоритмы LZ77 и LZ78]]
 +
# '''взяли''' [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
 +
# [[Преобразование MTF]]
 +
# [[Расстояние Хэмминга]]
 +
# [[Избыточное кодирование, код Хэмминга]]
  
−
== Алгоритмы сжатия ==
+
== 6. Комбинаторика ==
−
*[[Алгоритм Хаффмана]]
+
# ''fixed'' [[Комбинаторные объекты]]
−
*[[Алгоритм LZW]]
+
## пункт "определение" не нужен
−
*[[Алгоритмы LZ77 и LZ78]]
+
# ''взяли'' [[Лексикографический порядок]]
−
*[[Преобразование Барроуза-Уиллера]]
+
## собственно определения лексикографического порядка тут и нет. англоязычный термин.
−
*[[Обратное преобразование Барроуза-Уиллера]]
+
## ссылку на английскую википедию
−
*[[Преобразование MTF]]
+
## Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
−
*[[Расстояние Хэмминга]]
+
## return <, return = и т.п. выглядят ужасно. Сделать return LESS, return EQUAL и т.п.
−
*[[Избыточное кодирование, код Хэмминга]]
+
# ''fixed'' [[Формула включения-исключения]]
−
*[[Неравенство Крафта]]
+
## Перед открывающей скобкой нужен пробел
−
*[[Неравенство Макмиллана]]
+
## ссылки на ангийскую вики
−
*[[Алгоритм Ху-Таккера]]
+
# ''fixed'' [[Генерация комбинаторных объектов в лексикографическом порядке]]
 +
## отдельный раздел "определение" не нужен, перенести в заголовок
 +
## псевдокод генерации некрасивый, оформить его в соответствии с правилами
 +
## привести пример генерации для сочетаний, раз тут алгоритм для сочетаний, а не для перестановок
 +
# '''fixed''' [[Получение номера по объекту]]
 +
## В псевдокоде явно какой-то баг: was[i] = true устанавливается внутри внутреннего цикла, не исключено, что есть еще баги
 +
## В последнем псевдокоде зачем-то фигурные скобки. Также ^ традиционно означает xor, так что лучше использовать 2 ** x или pow(2, x) для обозначения степени.
 +
# ''fixed'' [[Получение объекта по номеру]]
 +
## "В начале каждого шага numOfObject — номер комбинаторного объекта среди объектов с заданным префиксом." — с заданным — это с каким?
 +
## опять в коде чередуются использования табов и фигурных скобок для отделения блоков. Оставить только табы.
 +
## Аналогично предыдущим замечаниям про xor
 +
# '''fixed''' [[Получение следующего объекта]]
 +
## дополнить генерацией следующего сочетания, разбиения на сумму, скобочной последовательности и мультиперестановки.
 +
# '''взяли''' [[Коды Грея]]
 +
## отдельный раздел "определение" не нужен
 +
## картинку с построением, имхо, надо немного увеличить
 +
## а что такое паразитные состояния? В общем, про применение надо попонятнее написать. И вообще про это в разделе "применение" надо написать
 +
## "Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. " — если не пишется про это в конспекте, надо кинуть внешнюю ссылку хотя бы.
 +
## В применении надо написать хотя бы немного пояснений, а то применяться-то применяется, а как конкретно — непонятно
 +
# [[Коды Грея для перестановок]]
 +
## отдельный раздел "определение" не нужен
 +
# '''взяли''' [[Коды антигрея]]
 +
## Аналогичну пункту 8, "Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность. " — а как конкретно он применяется для выявления поломки?
 +
## "Заметим, что для n > 2 невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2. " — ээ, а для n = 2 возмножно?
 +
## Для черточки над G надо использовать не bar, а overline
 +
# [[Цепные коды]]
 +
## ссылку на хоть какие-нибудь источники
 +
## а зачем они нужны?
 +
# [[Правильные скобочные последовательности]]
 +
## англоязычные термины
 +
## выделить в псевдокоде ключевые слова жирным
 +
## Обозначить биномиальные коэффециенты нормально (не <tex>C_n^k</tex>, а <tex>\binom{n}{k}</tex>)
 +
# [[Действие перестановки на набор из элементов, представление в виде циклов]]
 +
# [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 +
## убрать пункт "постановка задачи", вынести в заголовок
 +
# [[Методы генерации случайного сочетания]]
 +
## убрать пункт "постановка задачи", вынести в заголовок
 +
## что-то описание алгоритма не очень соответствует псевдокоду (для O(n^2))
 +
# [[Таблица инверсий]]
 +
# [[Умножение перестановок, обратная перестановка, группа перестановок]]
 +
## Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.
 +
## ссылку на русскую и английскую википедию, на симметрическую группу
 +
# [[Теорема Кэли]]
 +
# [[Матричное представление перестановок]]
 +
# [[Задача о минимуме/максимуме скалярного произведения]]
 +
## непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть
 +
# [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 +
# [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 +
# [[Производящая функция]]
 +
# '''взяли''' [[Лемма Бёрнсайда и Теорема Пойа]]
 +
## сюда добавить категорию "Теория Групп", она где-то есть на конспектах
 +
## для сумм надо юзать \limits
 +
## В теореме Пойа как-то неожиданно появляется группа перестановок, в ее условии тут это почему-то явно не сказано
 +
## Можно добавить пример подсчета количества различных раскрасок кубика в k цветов. Раскраски эквивалентны, если одну можно получить из другой поворотами кубика.
 +
# '''взяли''' [[Задача об ожерельях]]
 +
## а если можно делать не только сдвиги, а еще и отражения? (это называется bracelets: https://en.wikipedia.org/wiki/Necklace_(combinatorics) )
 +
## ссылки в статье почему-то оформлены как внешние, хотя должны быть внутренними
 +
## lcm и gcd обернуть в \operatorname или \mathrm
  
−
== Комбинаторика ==
+
== 7. [[Динамическое программирование]] ==
−
*[[Комбинаторные объекты]]
+
# [[Кратчайший путь в ациклическом графе]]
−
*[[Лексикографический порядок]]
+
## в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится
−
*[[Формула включения-исключения]]
+
## псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData
−
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
+
# [[Задача о расстановке знаков в выражении]]
−
*[[Получение номера по объекту]]
+
## "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке
−
*[[Получение объекта по номеру]]
+
## ссылка просто на "динамическое программирование" в википедии не нужна
−
*[[Получение следующего объекта]]
+
## доказать оптимальность
−
*[[Коды Грея]]
+
## нет номера страницы в источнике
−
*[[Коды Грея для перестановок]]
+
# [[Задача о наибольшей общей подпоследовательности]]
−
*[[Коды антигрея]]
+
# [[Задача о порядке перемножения матриц]]
−
*[[Цепные коды]]
+
# [[Задача о наибольшей возрастающей подпоследовательности]]
−
*[[Правильные скобочные последовательности]]
+
# [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
−
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
+
# [[Метод четырех русских для умножения матриц]]
−
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
+
# [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
−
*[[Методы генерации случайного сочетания]]
+
# [[Задача коммивояжера, ДП по подмножествам]]
−
*[[Таблица инверсий]]
+
## указать страницы в источниках
−
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
+
# [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
−
*[[Теорема Кэли]]
+
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
−
*[[Матричное представление перестановок]]
+
# [[Задача о расстоянии Дамерау-Левенштейна]]
−
*[[Задача о минимуме/максимуме скалярного произведения]]
+
# [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
−
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
+
# [[Задача о наибольшей подпоследовательности-палиндроме]]
−
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
+
# '''!!!''' [[Meet-in-the-middle]]
−
*[[Производящая функция]]
+
## можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.
−
*[[Лемма Бёрнсайда и Теорема Пойа]]
+
# [[Динамическое программирование по профилю]]
−
*[[Задача об ожерельях]]
+
# [[Задача о рюкзаке]]
 +
## разделы первого уровня должны быть ==
 +
# [[Динамика по поддеревьям]]
 +
## разделы первого уровня должны быть ==, а не =
 +
## '''эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть'''
  
−
== [[Динамическое программирование]] ==
+
== 8. Теория вероятностей ==
−
*[[Кратчайший путь в ациклическом графе]]
 
−
*[[Задача о расстановке знаков в выражении]]
 
−
*[[Задача о наибольшей общей подпоследовательности]]
 
−
*[[Задача о порядке перемножения матриц]]
 
−
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
−
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
 
−
*[[Метод четырех русских для умножения матриц]]
 
−
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
 
−
*[[Задача коммивояжера, ДП по подмножествам]]
 
−
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
−
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
−
*[[Задача о расстоянии Дамерау-Левенштейна]]
 
−
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
−
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
−
*[[Meet-in-the-middle]]
 
−
*[[Динамическое программирование по профилю]]
 
−
*[[Задача о рюкзаке]]
 
−
*[[Динамика по поддеревьям]]
 
  
−
== Теория вероятностей ==
+
* '''англоязычные термины во все статьи этого раздела для основных определений и понятий'''
−
*[[Вероятностное пространство, элементарный исход, событие]]
 
−
*[[Независимые события]]
 
−
*[[Условная вероятность]]
 
−
*[[Формула Байеса]]
 
−
*[[Формула полной вероятности]]
 
−
*[[Дискретная случайная величина]]
 
−
*[[Независимые случайные величины]]
 
−
*[[Математическое ожидание случайной величины]]
 
−
*[[Дисперсия случайной величины]]
 
−
*[[Ковариация случайных величин]]
 
−
*[[Корреляция случайных величин]]
 
−
*[[Энтропия случайного источника]]
 
−
*[[Симуляция одним распределением другого]]
 
−
*[[Арифметическое кодирование]]
 
−
*[[Парадоксы теории вероятностей]]
 
−
*[[Схема Бернулли]]
 
  
−
== Марковские цепи ==
+
# [[Вероятностное пространство, элементарный исход, событие]]
 +
## для угловых скобок юзать \langle, \rangle
 +
## перечисление оформить как википеречисление
 +
## привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий.
 +
# [[Независимые события]]
 +
## определение несовместных событий
 +
## критерий для независимости несовместных событий
 +
# [[Условная вероятность]]
 +
## раздел "определение" не нужен, перенести в заголовок
 +
# [[Формула Байеса]]
 +
## определение какое-то дурацкое и копипаста с википедии
 +
# [[Формула полной вероятности]]
 +
## примеры перечислить как подразделы
 +
# [[Дискретная случайная величина]]
 +
# [[Независимые случайные величины]]
 +
# ''взяли'' [[Математическое ожидание случайной величины]]
 +
## пробел перед открывающей скобкой должен быть
 +
# [[Дисперсия случайной величины]]
 +
# ''взяли'' [[Ковариация случайных величин]]
 +
# [[Корреляция случайных величин]]
 +
# [[Энтропия случайного источника]]
 +
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
 +
## В Романовском добавить издание и страницу
 +
# [[Симуляция одним распределением другого]]
 +
## так и нет нормального определения распределения
 +
## список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли.
 +
## издания и страницы в испточниках
 +
# [[Арифметическое кодирование]]
 +
## раздел "определение" не нужен, перенести в заголовок
 +
# [[Парадоксы теории вероятностей]]
 +
## "Пусть p - предельно ненулевая вероятность" — а что это такое?
 +
## для предела использовать \limits
 +
# [[Схема Бернулли]]
 +
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел
 +
## оформить источник
  
−
* [[Марковская цепь]]
+
== 9. Марковские цепи ==
−
* [[Теорема о поглощении]]
+
 
−
* [[Фундаментальная матрица]]
+
# [[Марковская цепь]]
−
* [[Математическое ожидание времени поглощения]]
+
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
−
* [[Расчет вероятности поглощения в состоянии]]
+
## сделать подраздел "циклические классы"
−
* [[Эргодическая марковская цепь]]
+
## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
−
* [[Регулярная марковская цепь]]
+
# [[Теорема о поглощении]]
−
* [[Примеры использования Марковских цепей]]
+
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
−
* [[Скрытые Марковские модели]]
+
## max -> \max
−
* [[Алгоритм Витерби]]
+
## в конце какая-то муть. Расписать рассуждения чуть подробнее
−
* [[Алгоритм "Вперед-Назад"]]
+
# [[Фундаментальная матрица]]
 +
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
 +
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
 +
## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
 +
# [[Математическое ожидание времени поглощения]]
 +
## не везде переменные обернуты в латех
 +
# [[Расчет вероятности поглощения в состоянии]]
 +
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
 +
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
 +
## оформить псевдокод в виде функций, без всяких println
 +
## оформить нормально источник
 +
# [[Эргодическая марковская цепь]]
 +
## определения пересекаются с конспектом про марковские цепи
 +
# [[Регулярная марковская цепь]]
 +
# [[Примеры использования Марковских цепей]]
 +
# '''!!!''' [[Скрытые Марковские модели]]
 +
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики
 +
# [[Алгоритм Витерби]]
 +
## "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?
 +
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
 +
## а \pi что такое?
 +
# [[Алгоритм "Вперед-Назад"]]

Текущая версия на 23:05, 6 января 2014

Тикеты индексируются как "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. fixed Комбинаторные объекты
    1. пункт "определение" не нужен
  2. взяли Лексикографический порядок
    1. собственно определения лексикографического порядка тут и нет. англоязычный термин.
    2. ссылку на английскую википедию
    3. Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
    4. return <, return = и т.п. выглядят ужасно. Сделать return LESS, return EQUAL и т.п.
  3. fixed Формула включения-исключения
    1. Перед открывающей скобкой нужен пробел
    2. ссылки на ангийскую вики
  4. fixed Генерация комбинаторных объектов в лексикографическом порядке
    1. отдельный раздел "определение" не нужен, перенести в заголовок
    2. псевдокод генерации некрасивый, оформить его в соответствии с правилами
    3. привести пример генерации для сочетаний, раз тут алгоритм для сочетаний, а не для перестановок
  5. fixed Получение номера по объекту
    1. В псевдокоде явно какой-то баг: was[i] = true устанавливается внутри внутреннего цикла, не исключено, что есть еще баги
    2. В последнем псевдокоде зачем-то фигурные скобки. Также ^ традиционно означает xor, так что лучше использовать 2 ** x или pow(2, x) для обозначения степени.
  6. fixed Получение объекта по номеру
    1. "В начале каждого шага numOfObject — номер комбинаторного объекта среди объектов с заданным префиксом." — с заданным — это с каким?
    2. опять в коде чередуются использования табов и фигурных скобок для отделения блоков. Оставить только табы.
    3. Аналогично предыдущим замечаниям про xor
  7. fixed Получение следующего объекта
    1. дополнить генерацией следующего сочетания, разбиения на сумму, скобочной последовательности и мультиперестановки.
  8. взяли Коды Грея
    1. отдельный раздел "определение" не нужен
    2. картинку с построением, имхо, надо немного увеличить
    3. а что такое паразитные состояния? В общем, про применение надо попонятнее написать. И вообще про это в разделе "применение" надо написать
    4. "Существует ещё несколько видов Кода Грея — сбалансированный Код Грея, код Беккета-Грея, одноколейный Код Грея. " — если не пишется про это в конспекте, надо кинуть внешнюю ссылку хотя бы.
    5. В применении надо написать хотя бы немного пояснений, а то применяться-то применяется, а как конкретно — непонятно
  9. Коды Грея для перестановок
    1. отдельный раздел "определение" не нужен
  10. взяли Коды антигрея
    1. Аналогичну пункту 8, "Код антигрея может использоваться для обнаружения неисправностей в устройстве при переходе в соседнее состояние. Часто используется в приборах, устанавливающихся на улице. Такое кодирование позволяет вовремя выявить поломку или какое-то загрязнение и своевременно устранить неисправность. " — а как конкретно он применяется для выявления поломки?
    2. "Заметим, что для n > 2 невозможно такое упорядочивание двоичных векторов, что соседние отличаются во всех битах. Объясняется это тем, что для двоичного вектора существует ровно один вектор, отличающийся во всех битах. А в последовательности их должно быть 2. " — ээ, а для n = 2 возмножно?
    3. Для черточки над G надо использовать не bar, а overline
  11. Цепные коды
    1. ссылку на хоть какие-нибудь источники
    2. а зачем они нужны?
  12. Правильные скобочные последовательности
    1. англоязычные термины
    2. выделить в псевдокоде ключевые слова жирным
    3. Обозначить биномиальные коэффециенты нормально (не [math]C_n^k[/math], а [math]\binom{n}{k}[/math])
  13. Действие перестановки на набор из элементов, представление в виде циклов
  14. Метод генерации случайной перестановки, алгоритм Фишера-Йетса
    1. убрать пункт "постановка задачи", вынести в заголовок
  15. Методы генерации случайного сочетания
    1. убрать пункт "постановка задачи", вынести в заголовок
    2. что-то описание алгоритма не очень соответствует псевдокоду (для O(n^2))
  16. Таблица инверсий
  17. Умножение перестановок, обратная перестановка, группа перестановок
    1. Не надо приводить определение группы, оно уже есть в конспектах, надо на него сослаться.
    2. ссылку на русскую и английскую википедию, на симметрическую группу
  18. Теорема Кэли
  19. Матричное представление перестановок
  20. Задача о минимуме/максимуме скалярного произведения
    1. непонятно, что это делает в комбинаторике, с другой стороны, непонятно, куда это впихнуть
  21. Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
  22. Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
  23. Производящая функция
  24. взяли Лемма Бёрнсайда и Теорема Пойа
    1. сюда добавить категорию "Теория Групп", она где-то есть на конспектах
    2. для сумм надо юзать \limits
    3. В теореме Пойа как-то неожиданно появляется группа перестановок, в ее условии тут это почему-то явно не сказано
    4. Можно добавить пример подсчета количества различных раскрасок кубика в k цветов. Раскраски эквивалентны, если одну можно получить из другой поворотами кубика.
  25. взяли Задача об ожерельях
    1. а если можно делать не только сдвиги, а еще и отражения? (это называется bracelets: https://en.wikipedia.org/wiki/Necklace_(combinatorics) )
    2. ссылки в статье почему-то оформлены как внешние, хотя должны быть внутренними
    3. lcm и gcd обернуть в \operatorname или \mathrm

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

  1. Кратчайший путь в ациклическом графе
    1. в тексте d, i, j и т.п. обернуть в латех, а то страшно смотрится
    2. псевдокод оформить как функцию, принимающую матрицу смежности и возвращающую кратчайший путь, без всяких inputData и writeData
  2. Задача о расстановке знаков в выражении
    1. "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезке
    2. ссылка просто на "динамическое программирование" в википедии не нужна
    3. доказать оптимальность
    4. нет номера страницы в источнике
  3. Задача о наибольшей общей подпоследовательности
  4. Задача о порядке перемножения матриц
  5. Задача о наибольшей возрастающей подпоследовательности
  6. Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве
  7. Метод четырех русских для умножения матриц
  8. Применение метода четырех русских в задачах ДП на примере задачи о НОП
  9. Задача коммивояжера, ДП по подмножествам
    1. указать страницы в источниках
  10. Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
  11. Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
  12. Задача о расстоянии Дамерау-Левенштейна
  13. Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
  14. Задача о наибольшей подпоследовательности-палиндроме
  15. !!! Meet-in-the-middle
    1. можете попробовать вспомнить какую-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.
  16. Динамическое программирование по профилю
  17. Задача о рюкзаке
    1. разделы первого уровня должны быть ==
  18. Динамика по поддеревьям
    1. разделы первого уровня должны быть ==, а не =
    2. эээ, а вообще-то статья про паросочетание максимального веса в дереве уже есть

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

  • англоязычные термины во все статьи этого раздела для основных определений и понятий
  1. Вероятностное пространство, элементарный исход, событие
    1. для угловых скобок юзать \langle, \rangle
    2. перечисление оформить как википеречисление
    3. привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий.
  2. Независимые события
    1. определение несовместных событий
    2. критерий для независимости несовместных событий
  3. Условная вероятность
    1. раздел "определение" не нужен, перенести в заголовок
  4. Формула Байеса
    1. определение какое-то дурацкое и копипаста с википедии
  5. Формула полной вероятности
    1. примеры перечислить как подразделы
  6. Дискретная случайная величина
  7. Независимые случайные величины
  8. взяли Математическое ожидание случайной величины
    1. пробел перед открывающей скобкой должен быть
  9. Дисперсия случайной величины
  10. взяли Ковариация случайных величин
  11. Корреляция случайных величин
  12. Энтропия случайного источника
    1. воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
    2. В Романовском добавить издание и страницу
  13. Симуляция одним распределением другого
    1. так и нет нормального определения распределения
    2. список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли.
    3. издания и страницы в испточниках
  14. Арифметическое кодирование
    1. раздел "определение" не нужен, перенести в заголовок
  15. Парадоксы теории вероятностей
    1. "Пусть p - предельно ненулевая вероятность" — а что это такое?
    2. для предела использовать \limits
  16. Схема Бернулли
    1. запихать примеры в один раздел "Примеры", и оформить каждый как подраздел
    2. оформить источник

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

  1. Марковская цепь
    1. два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
    2. сделать подраздел "циклические классы"
    3. "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
  2. Теорема о поглощении
    1. определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
    2. max -> \max
    3. в конце какая-то муть. Расписать рассуждения чуть подробнее
  3. Фундаментальная матрица
    1. написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
    2. не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
    3. получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
  4. Математическое ожидание времени поглощения
    1. не везде переменные обернуты в латех
  5. Расчет вероятности поглощения в состоянии
    1. куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
    2. имена переменных в тексте оборачиваются в \mathrm или \mathtt
    3. оформить псевдокод в виде функций, без всяких println
    4. оформить нормально источник
  6. Эргодическая марковская цепь
    1. определения пересекаются с конспектом про марковские цепи
  7. Регулярная марковская цепь
  8. Примеры использования Марковских цепей
  9. !!! Скрытые Марковские модели
    1. можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики
  10. Алгоритм Витерби
    1. "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?
    2. имена переменных в тексте оборачиваются в \mathrm или \mathtt
    3. а \pi что такое?
  11. Алгоритм "Вперед-Назад"
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Dgerasimov/Тикеты_по_конспектам_year2013&oldid=35271»