Просмотр исходного текста страницы Участник:Dgerasimov/Тикеты по конспектам year2013

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела
== 1. Отношения ==
# '''взяли''' [[Определение отношения]]
## Определение степени отношения есть и здесь и в следующем конспекте, непорядок. Сделать ссылку на следующий вроде "Операции над отношениями"
## На виды и примеры отношений дать внутренние ссылки
## англоязычные термины
## пункт "Определение" не нужен, см. правила форматирования конспектов
# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]]
## см. пункт 1.1
## англоязычные термины
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
## англоязычные термины
## добавить внутренних ссылок на эквивдентность, порядки и т.д.
# [[Симметричное отношение]]
## англоязычные термины
# [[Антисимметричное отношение]]
## англоязычные термины, на отношения порядка теперь есть внутренние ссылки, убрать внешние
# [[Транзитивное отношение]]
## англоязычные термины
# [[Отношение порядка]]
## англоязычные термины
# [[Отношение эквивалентности]]
## пункт "определение" не нужен
## англоязычные термины
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]
## англоязычные термины
# '''взяли''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
## пункт "Задача" не нужен
## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.
# '''!!!''' [[Транзитивный остов]]
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
## аналогично предыдущему, придумать обобщение на случай бесконечных отношений

== 2. Булевы функции ==
# [[Определение булевой функции]]
## англоязычных терминов
## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.
# [[Суперпозиции]]
## англоязычных терминов
# [[ДНФ]]
## англоязычных терминов
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
# [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]]
## англоязычных терминов
# [[КНФ]]
## англоязычных терминов
## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо
# [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
## англоязычных терминов
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
## англоязычных терминов
## "Предпосылки" — странное название, переименовать в "Полнота", например
# [[Полные системы функций. Теорема Поста о полной системе функций]]
## англоязычных терминов
# [[Представление функции класса DM с помощью медианы]]
# [[Пороговая функция]]

== 3. Схемы из функциональных элементов ==
# [[Реализация булевой функции схемой из функциональных элементов]]
## англоязычных терминов (на схемную сложность, глубину схемы)
# [[Метод Лупанова синтеза схем]]
# [[Cумматор]]
## англоязычных терминов 
# [[Каскадный сумматор]]
## англоязычных терминов 
# [[Двоичный каскадный сумматор]]
## англоязычных терминов 
## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
# [[Реализация вычитания сумматором]]
# [[Матричный умножитель]]
## пункт "определение" не нужен
## англоязычных терминов
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
# [[Дерево Уоллеса]]
## пункт "определение" не нужен
## англоязычных терминов
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга

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

== 5. Алгоритмы сжатия ==
# '''взяли''' [[Алгоритм Хаффмана]]
## "Использует только частоту появления одинаковых байт в изображении." што
## ссылки на википедию, русскую и английскую
## внутренние ссылки на префиксный код и все такое.
# [[Алгоритм Ху-Таккера]]
# [[Неравенство Крафта]]
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
## А зачем оно нужно? Просто интересный факт?
# [[Неравенство Макмиллана]]
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
## А зачем оно нужно? Просто интересный факт?
# [[Алгоритм LZW]]
# [[Алгоритмы LZ77 и LZ78]]
# '''взяли''' [[Преобразование Барроуза-Уиллера | Преобразование Барроуза-Уиллера и обратное ему]]
# [[Преобразование MTF]]
# [[Расстояние Хэмминга]]
# [[Избыточное кодирование, код Хэмминга]]

== 6. Комбинаторика ==
# ''fixed'' [[Комбинаторные объекты]]
## пункт "определение" не нужен
# ''взяли'' [[Лексикографический порядок]]
## собственно определения лексикографического порядка тут и нет. англоязычный термин.
## ссылку на английскую википедию
## Как-то не очень круто формулировать в терминах алфавита и строк, надо просто в терминах последовательностей
## 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. Теория вероятностей ==

* '''англоязычные термины во все статьи этого раздела для основных определений и понятий'''

# [[Вероятностное пространство, элементарный исход, событие]]
## для угловых скобок юзать \langle, \rangle
## перечисление оформить как википеречисление
## привести пример вероятностного пространтсва с счетно-бесконечным числом элементарных событий.
# [[Независимые события]]
## определение несовместных событий 
## критерий для независимости несовместных событий
# [[Условная вероятность]]
## раздел "определение" не нужен, перенести в заголовок
# [[Формула Байеса]]
## определение какое-то дурацкое и копипаста с википедии
# [[Формула полной вероятности]]
## примеры перечислить как подразделы 
# [[Дискретная случайная величина]]
# [[Независимые случайные величины]]
# ''взяли'' [[Математическое ожидание случайной величины]]
## пробел перед открывающей скобкой должен быть
# [[Дисперсия случайной величины]]
# ''взяли'' [[Ковариация случайных величин]]
# [[Корреляция случайных величин]]
# [[Энтропия случайного источника]]
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
## В Романовском добавить издание и страницу
# [[Симуляция одним распределением другого]]
## так и нет нормального определения распределения
## список примеров распределений есть, а самих распределений нет. Надо хотя бы ссылки на википедию кинуть, чтоли.
## издания и страницы в испточниках
# [[Арифметическое кодирование]]
## раздел "определение" не нужен, перенести в заголовок
# [[Парадоксы теории вероятностей]]
## "Пусть p - предельно ненулевая вероятность" — а что это такое?
## для предела использовать \limits
# [[Схема Бернулли]]
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел
## оформить источник

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

# [[Марковская цепь]]
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
## сделать подраздел "циклические классы"
## "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
# [[Теорема о поглощении]]
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
## max -> \max 
## в конце какая-то муть. Расписать рассуждения чуть подробнее
# [[Фундаментальная матрица]]
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
## получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
# [[Математическое ожидание времени поглощения]]
## не везде переменные обернуты в латех
# [[Расчет вероятности поглощения в состоянии]]
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
## оформить псевдокод в виде функций, без всяких println
## оформить нормально источник
# [[Эргодическая марковская цепь]]
## определения пересекаются с конспектом про марковские цепи
# [[Регулярная марковская цепь]]
# [[Примеры использования Марковских цепей]]
# '''!!!''' [[Скрытые Марковские модели]]
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики
# [[Алгоритм Витерби]]
## "правдоподобная последовательность скрытых состояний" -- что такое "наиболее правдоподобная"?
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
## а \pi что такое?
# [[Алгоритм "Вперед-Назад"]]