Участник:Shersh/Тикеты к 1ому терму — различия между версиями
Shersh (обсуждение | вклад) (→8. Теория вероятностей (проверяется)) |
Shersh (обсуждение | вклад) (→8. Теория вероятностей (проверяется): проверены) |
||
Строка 324: | Строка 324: | ||
</ol> | </ol> | ||
− | == 8. Теория вероятностей | + | == 8. Теория вероятностей == |
# [[Вероятностное пространство, элементарный исход, событие]] (1) | # [[Вероятностное пространство, элементарный исход, событие]] (1) | ||
## Англоязычные термины | ## Англоязычные термины |
Версия 14:15, 2 февраля 2016
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)
Обозначением !!! помечены те конспекты, которые точно дадут 5 баллов при их успешном выполнении. Просто выделены, чтобы сразу можно было на них обратить внимание.
Содержание
1. Отношения
- Определение отношения (0.5)
- Дефисы заменить на тире
- Оформить красиво источники информации
- Английские термины к видам отношений
- Композиция отношений, степерь отношения, обратное отношение
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Транзитивное отношение
- Отношение порядка
- Отношение эквивалентности
- Транзитивное замыкание отношения
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
- !!! Транзитивный остов (5)
- Отформатировать псевдокод
- Добавить категории
- возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
- если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
2. Булевы функции
- Определение булевой функции
- Суперпозиции (0.5)
- англоязычных терминов
- ДНФ (0.5)
- англоязычных терминов
- писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
- Убрать странные скобки в формулировке теоремы
- Не то выделено жирным в определениях
- Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна (2.5)
- англоязычных терминов
- Жирные определения
- Непонятно, как работает метод Карно, возможно в таблице ошибка
- Двойной номер в одной из табличек Квайна
- Обернуть в tex бинарные операции в методе Квайна
- Все константы и переменные взять в tex
- КНФ
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома (3)
- англоязычных терминов
- написать, почему факт того, что существует полиномиальный алгоритм, интересен
- Ссылку на википедию сделать примечанием
- Добавить ссылки, изменить См. также
- Исправить странное форматирование в форме Крома
- Полином Жегалкина, преобразование Мёбиуса
- Полные системы функций. Теорема Поста о полной системе функций
- Представление функции класса DM с помощью медианы
- Пороговая функция
3. Схемы из функциональных элементов
- Реализация булевой функции схемой из функциональных элементов (1)
- англоязычных терминов (на схемную сложность, глубину схемы)
- Оформить красивее определения из логических элементов
- Сделать красивую табличку
- Источники информации и См. также
- Простейшие методы синтеза схем из функциональных элементов (0.5)
- Изменить знаки неравенств
- Ссылку на метод синтеза схем Шэннона сделать примечанием
- Определение жирным
- Оформить правильно См. также и Источники информации
- Увеличить дроби
- Метод Лупанова синтеза схем (0.5)
- Заменить литературу на источники информации
- Изменить знаки неравенств
- Запятые криво стоят в определении функции g
- Увеличить дроби
- Cумматор
- Каскадный сумматор (0.5)
- англоязычных терминов
- Оформить источники информации нормально
- Двоичный каскадный сумматор
- Троичный сумматор
- Реализация вычитания сумматором
- Матричный умножитель
- Дерево Уоллеса (1)
- пункт "определение" не нужен
- англоязычных терминов
- надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
- Оформить правильно Источники информации
- См. также
- Увеличить дроби
- Как-нибудь нормально назвать depth, size и sum
- Чуть-чуть увеличить картинки
- Контактная схема
- Квантовые гейты
4. Представление информации
- Кодирование информации
- Представление целых чисел: прямой код, код со сдвигом, дополнительный код
- Представление вещественных чисел
- Представление символов, таблицы кодировок
5. Алгоритмы сжатия
- Алгоритм Хаффмана
- Оптимальное хранение словаря в алгоритме Хаффмана
- Алгоритм Хаффмана за O(n) (1)
- Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
- Алгоритм Ху-Таккера (1)
- Англоязычные термины
- Заменить дефис на тире
- Сделать красивый список в определении
- Переменные и константы взять в Tex
- Исправить знаки неравенств
- Правильно оформить источники информации
- Неравенство Крафта
- Неравенство Макмиллана
- Код Шеннона
- Оптимальный префиксный код с длиной кодового слова не более L бит
- Алгоритмы LZ77 и LZ78 (2)
- Переменные и константы взять в Tex
- Добавить примеры итоговых таблиц
- Рассказать, как декодировать
- Правильно оформить источники информации
- Получше расписать описание алгоритма
- Таблицы сделать красивыми
- Интервики
- Алгоритм LZW
- Алгоритм LZSS
- Преобразование Барроуза-Уиллера и обратное ему
- Преобразование MTF
- Расстояние Хэмминга (1)
- Англоязычные термины правильно оформить
- Причём там куб?
- Оформить правильно источники информации
- Исправить знаки неравенств
- Избыточное кодирование, код Хэмминга
- Гамма-, дельта- и омега-код Элиаса
6. Комбинаторика
Комбинаторные объекты
- !!! Комбинаторные объекты (6)
- Правильно оформить англоязычные термины
- Привести формулы каждого объекта — общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
- Под каждый комбинаторный объект сделать свой подзаголовк уровня ниже
- Все переменные и константы взять в Tex
- Добавить ссылок по всем объектам в источники информации
- Заменить ссылку на числа Стирлинга ссылкой на конспект
- Заменить дефисы на тире
- Лексикографический порядок
- Коды Грея
- Коды Грея для перестановок
- Коды антигрея
- Цепные коды
- Правильные скобочные последовательности
Генерация комбинаторных объектов
- Генерация комбинаторных объектов в лексикографическом порядке
- Заменить скобки "больше-меньше" на угловые
- Нормальную красивую картинку нарисовать
- Получение номера по объекту
- Получение объекта по номеру
- Получение следующего объекта
- Получение предыдущего объекта
- Метод генерации случайной перестановки, алгоритм Фишера-Йетса (1)
- Отформатировать псевдокоды
- Мелочи по теху
- Какие-то пропуски в обосновании
- Дефисы на тире
- Методы генерации случайного сочетания
Подсчёт числа объектов
- Формула включения-исключения, подсчет числа беспорядков
- Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
- Производящая функция (3)
- Оформить правильно англоязычные термины
- Убрать точки с запятыми из определения
- Все переменные и константы в Tex взять
- Исправить знаки неравенств
- Оформить ссылки примечаниями
- Ссылки и литературу заменить на источники информации
- Лемма Бёрнсайда и Теорема Пойа
- Задача об ожерельях
- Числа Стирлинга первого рода
- Числа Стирлинга второго рода
- Числа Эйлера первого и второго рода. Подъемы в перестановках
- Числа Каталана
Свойства комбинаторных объектов
- !!! Умножение перестановок, обратная перестановка, группа перестановок (5)
- Определение выделить жирным
- Англоязычные термины
- Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
- Отформатировать псевдокоды
- Все переменные и константы взять в Tex
- Оформить правильно источники информации
- Добавить примеров из конспекта групп по теории чисел
- Добавить реккурентную формулу числа инволюций c доказательством
- Действие перестановки на набор из элементов, представление в виде циклов
- Таблица инверсий
- Теорема Кэли (1)
- Бинарную операцию в группе обозначают не звёздочкой, а кружочком
- Интервики
- Оформить правильно источники информации, добавить см. также
- Добавить словесных пояснений происходящего
- !!! Матричное представление перестановок (5)
- Англоязычные термины
- Заменить дефисы на тире
- Добавить подробные доказательства утверждений (или пояснить получше уже существующие)
- Оформить правильно источники информации
- Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
- Задача о минимуме/максимуме скалярного произведения (2)
- Оформить задачу шаблоном Задача
- Ссылку в примечании сделать на самом деле примечанием
- Добавить использование этой теоремы (в теории матроидов и теории расписаний)
- Оформить правильно источники информации
- Доказательство плохо разбито на пункты — от нумерации в доказательстве вообще можно избавиться
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП (0.5)
- Англоязычные термины
- Определение взять в шаблон
- Заменить дефисы на тире
- Оформить правильно источники информации
7. Динамическое программирование
- 0. !!! Динамическое программирование (5)
- Добавить известную цитату про ДП
- Интервики на NP-полноту
- Картинки криво расположены
- Добавить больше примеров
- Добавить описание принципа оптимальности на подмножествах
- Оформить правильно источники информации
- Добавить про мемоизацию (и желательно что-нибудь разумное)
Классические задачи динамического программирования
- Кратчайший путь в ациклическом графе
- Задача о числе путей в ациклическом графе (4)
- Взять задачу в шаблон
- Отформатировать псевдокод
- Обернуть имя функции в тексте в mathrm
- Заменить дефисы на тире
- Добавить см. также и источники информации
- Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями
- !!! Задача о расстановке знаков в выражении (6)
- Взять задачу в шаблон
- Исправить знаки неравенств
- Ссылку примечанием оформить нормально
- Взять все переменные и константы в тексте в Tex
- Отформатировать псевдокод
- Табличку нормально оформить
- Описать восстановление ответа
- Источники информации правильно оформить
- Добавить решение задачи без возможности использования скобок
- Задача о порядке перемножения матриц (3)
- Взять переменные и константы в Tex
- Обернуть задачу в шаблон
- Интервики на конспект правильных скобочных последовательностей
- Написать, почему нас не устраивает число Каталана в асимптотике
- Отформатировать псевдокоды
- Оформить правильно источники информации
- Убрать про мемоизацию
- Задача о наибольшей общей подпоследовательности
- Задача о наибольшей возрастающей подпоследовательности
- Задача коммивояжера, ДП по подмножествам
- Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
- !!! Задача о рюкзаке (8)
- Взять задачу в шаблон
- Отформатировать псевдокоды
- Заменить дефисы на тире
- Исправить знаки неравенств
- Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
- Сделать итоговую формулу для А c помощью фигурной скобки
- Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
- Понизить уровень заголовков первого уровня
- Оформить правильно источники информации
Способы оптимизации методов динамического программирования
- Метод четырех русских для умножения матриц (0.5)
- Взять скобки в Tex
- Заменить дефисы на тире
- Заменить литературу на источники информации
- Применение метода четырех русских в задачах ДП на примере задачи о НОП (3.5)
- Заменить дефисы на тире
- Взять константы в Tex
- Сделать нормальные картинки (или заменить на таблички)
- Заменить источники на источники информации
- Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза (1)
- Кривая ссылка на оптимальный префиксный код
- Заменить дефисы на тире
- Взять переменные и константы в Tex
- Исправить знаки неравенств
- Оформить правильно источники информации
- !!! Meet-in-the-middle (5)
- Отформатировать псевдокод
- Добавить примеры задач
- Оформить правильно источники информации
Другие задачи
- Задача о расстоянии Дамерау-Левенштейна
- Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
- Задача о наибольшей подпоследовательности-палиндроме
- Наибольшая общая возрастающая подпоследовательность (2)
- Переименовать в "Задача о ..."
- Отформатировать псевдокоды
- Англоязычные термины
- Добавить Шаблон:Задача
- Оформить правильно источники информации
- Задача о наибольшей общей палиндромной подпоследовательности
- !!! Динамическое программирование по профилю (7)
- Англоязычные термины
- Заменить умножение на \cdot
- Заменить дефисы на тире
- Взять переменные и константы в Tex
- Отформатировать псевдокоды
- Добавить ещё примеров
- Оформить правильно источники информации
- Добавить нормальное объяснение происходящего (и почему это работает)
- !!! Динамика по поддеревьям, задача о паросочетании максимального веса в дереве (5)
- Взять все переменные в Tex
- Убрать определение паросочетания
- Отформатировать псевдокод
- Оформить правильно источники информации
- Убрать первый пункт
- Добавить ещё примеров
8. Теория вероятностей
- Вероятностное пространство, элементарный исход, событие (1)
- Англоязычные термины
- Заменить дефисы на тире
- Определения выделить жирным
- Все константы и переменные взять в Tex
- Убрать точки с запятой из определений
- Оформить правильно см. также и источники информации
- Правильно оформить дроби
- Независимые события (1)
- Оформить правильно англоязычные термины
- Тире в шаблон, переменные и константы в Tex
- Пример несовместных событий
- Определения выделить жирным
- Заменить все дроби на \dfrac
- Оформить правильно источники информации
- Пример Тетраэдра оформить нормально
- Условная вероятность (0.5)
- Англоязычные термины правильно оформить
- Увеличить дроби
- Переменные и константы взять в Tex
- Оформить правильно источники информации
- Формула полной вероятности
- Формула Байеса
- Дискретная случайная величина (3)
- Англоязычные термины
- Примеры
- Исправить знаки неравенств
- Оформить правильно источники информации, См. также, списки, вообще всё
- Добавить про функцию плотности вероятности
- Независимые случайные величины (1)
- Англоязычные термины
- Заменить ссылку примечанием на интервики
- Заменить дефисы на тире, переменные и константы взять в Tex
- Правильно оформить источники информации
- Математическое ожидание случайной величины (0.5)
- Оформить правильно См. также
- Заменить дроби на \dfrac
- !!! Дисперсия случайной величины (5)
- Англоязычные термины
- Дефисы на тире, дроби в \genfrac
- Убрать ; в свойствах
- Если легко показать, то надо показать
- Добавить про центральные моменты
- Оформить по правилам
- Ковариация случайных величин (3)
- Правильно оформить англоязычные термины
- Избавиться от двоеточия в определении
- Пробел перед открывающей скобкой
- Оформить правильно источники информации
- Убрать "что и требовалось доказать"
- Источники информации, см. также
- Cov везде взять в \mathrm
- Корреляция случайных величин (3)
- Заменить дефисы на тире
- Рабить определение на две части — про среднеквадратичное отклонение и ковариацию
- Переменные и константы взять в Tex
- Исправить знаки неравенств
- Оформить правильно источники информации
- Взять Corr и Cov в \mathrm
- Дроби на \dfrac
- Энтропия случайного источника (2)
- воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
- В Романовском добавить издание и страницу, источники информации правильно оформить
- Англоязычные термины
- Убрать треугольники из свойств
- Исправить знаки неравенств
- Оформить по правилам
- !!! Симуляция одним распределением другого (7)
- так и нет нормального определения распределения
- список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
- издания и страницы в источниках информации
- Англоязычные термины
- Увеличить дроби, исправить знаки неравенств
- Зачем-то формулы написаны по центру
- Картинки в общем случае криво расположены
- Вывод оформить правильно
- Увеличить дроби
- Арифметическое кодирование (5)
- раздел "определение" не нужен, перенести в заголовок
- Оформить правильно англоязычные термины
- Отформатировать псевдокод
- Заменить дефисы на тире
- Оформить правильно источники информации
- Описать подробней
- Оформить по правилам
- Парадоксы теории вероятностей
- !!! Схема Бернулли (5)
- запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать
- оформить источник
- Англоязычные термины
- Определение выделить жирным
- Перерисовать картинку
- Исправить знаки неравенств, дроби на \dfrac
- Константы и переменные взять в Tex
- Ссылки на формулы красиво оформить
- Оформить правильно источники информации
- Оформить по правилам
9. Марковские цепи (проверяются)
- !!! Марковская цепь
- два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
- сделать подраздел "циклические классы"
- "для i и j, принадлежащих одному классу эквивалентности" -- классу эквиволентности по какому отношению?
- Интервики на графы
- Англоязычные термины правильно оформить
- Оформить правильно источники информации
- !!! Теорема о поглощении
- определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
- max -> \max
- в конце какая-то муть. Расписать рассуждения чуть подробнее
- Заменить дефисы на тире
- А что такое непоглощающая матрица?
- Источники информации
- !!! Фундаментальная матрица
- написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
- не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
- получше оформить источник, добавить страницу, сделать ссылку на русскую/английскую вики, если есть
- Англоязычные термины
- Определения выделить жирным
- Дефисы на тире, переменные в Tex
- Математическое ожидание времени поглощения
- не везде переменные обернуты в латех
- !!! Расчет вероятности поглощения в состоянии
- куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- оформить псевдокод в виде функций, без всяких println
- оформить нормально источник
- Помёрджить с предыдущим конспектом
- Заголовки первого уровня убрать
- Эргодическая марковская цепь
- определения пересекаются с конспектом про марковские цепи
- Сделать ссылку примечанием
- Заменить дефисы на тире
- Оформить правильно источники информации
- Регулярная марковская цепь
- Переменные взять в Tex
- Оформить правильно источники информации
- Примеры использования Марковских цепей
- Переменные в Tex
- Заменить литературу на источники информации
- !!! Скрытые Марковские модели
- можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров
- Переменные и константы взять в Tex
- Ссылку на вики оформить примечанием
- Оформить правильно источники информации
- Исправить небольшую багу в картинке
- Англоязычные термины
- !!! Алгоритм Витерби
- "правдоподобная последовательность скрытых состояний" — что такое "наиболее правдоподобная"?
- имена переменных в тексте оборачиваются в \mathrm или \mathtt
- а \pi что такое?
- Отформатировать псевдокод
- Англоязычные термины
- Заменить ссылки на источники информации
- Алгоритм "Вперед-Назад"
- Отформатировать псевдокод
- Заменить литературу на источники информации