3622
правки
Изменения
м
Заявки можно подавать только на те конспекты, которые отмечены Обозначением '''!!!'''. Один такой тикет засчитывается за <tex> помечены те конспекты, которые точно дадут 5 </tex> баллов (в случае исправления, конечно же)при их успешном выполнении. Не берите за раз много исправлений {{---}} оставляйте своим однокурсникамПросто выделены, да и вдруг вы {{Acronym | даже один тикет не осилите | Случаи уже бывали}}. * Если вдруг окажется мало исправлений в одной вашей заявке, то дополнительно к ней чтобы сразу можно было на моё усмотрение может добавиться ещё несколько тикетов, не помеченных восклицательными знаками.* Если не осталось конспектов с '''!!!''', нет желания их делать, нет желания делать новый конспект или разобрали все хорошие темы, то можно взять несколько правок, не отмеченных '''!!!''', но для этого необходимо заранее мне сообщить о своём таком желании, а я уже сам выдам темы. Несколько таких правок будут засчитаны, как одна с '''!!!'''них обратить внимание.
## англоязычных терминов
## Заменить знаки неравенств в tex
## Убрать ; в списках
## Заменить в некоторых местах НЕ на \neg (то же самое про И и ИЛИ) {{---}} или заменить на англоязычные названия операций
## Избавиться от сокращений т.е. и т.к.
## Все переменные взять в tex
## Добавить доказательство пропущенных лемм и теорем (если там много, то всё может суммарно оцениться)
## Исправить знаки неравенств
## Правильно оформить источники информации
# '''взяли''' [[Неравенство Крафта]]
## Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
## А зачем оно нужно? Просто интересный факт?
## '''?''' Добавить оценку степени сжатия
# Исправить знаки неравенств# Заменить max на \max# Добавить определение L через фигурные скобки# Взять константы в Tex# Заменить дефисы на тире# Отформатировать псевдокодыШаблон:Задача
## Правильно оформить англоязычные термины
## Избавиться от двоеточия в определении
## Пробел перед открывающей скобкой
## Оформить правильно источники информации
## Убрать "что и требовалось доказать"
## Источники информации, см. также
## Заменить дефисы на тире## Рабить определение на две части {{---}} про среднеквадратичное отклонение и ковариацию## Переменные и константы взять в Tex## Исправить знаки неравенств## Оформить правильно источники информации# [[Энтропия случайного источника]](2)
## Помёрджить с предыдущим конспектом
Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 1ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))
Тикеты индексируются как "X-Y", где X {{---}} номер раздела, Y {{---}} номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)
== 1. Отношения ==
# [[Определение отношения]](0.5)## Дефисы заменить на тире## Оформить красиво источники информации## Английские термины к видам отношений# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]](0.5)## Отформатировать свойства красиво## Оформить правильно источники информации## Англ. термины# ''fixed'' [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]## Объединить ссылки с источниками## Не везде присутствует tex, где должен быть# ''fixed'' [[Симметричное отношение]]## Объединить источники и ссылки# ''fixed'' [[Антисимметричное отношение]]## Объединить источники и ссылки## Исправить знаки неравенств в техе## Увеличить картинки## Заменить тире на шаблон
# [[Транзитивное отношение]]
# [[Отношение порядка]]
# [[Отношение эквивалентности]]
# ''fixed'' [[Транзитивное замыкание|Транзитивное замыкание отношения]]## Заменить тире на шаблон## Исправить кривой местами tex## Заменить ссылки на источники информации# '''!!!''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]## Отформатировать псевдокод## Добавить ссылок в источники информации## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.## Нужен пример, картинка# '''!!!fixed''' [[Транзитивный остов]](5)
## Отформатировать псевдокод
## Добавить категории
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
## Отформатировать конспект по правилам
== 2. Булевы функции ==
# [[Определение булевой функции]]
# [[Побитовые операции]]
# ''fixed'' [[Суперпозиции]] (0.5)
## англоязычных терминов
## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.## Исправить неравенства в tex## Обернуть в tex все константы в тексте## Определение двойственной сделать жирным## Объединить литературу и источники информации## Красиво оформить таблицы# [[Суперпозиции]]## англоязычных терминов# ''fixed'' [[ДНФ]](0.5)
## англоязычных терминов
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
## Убрать странные скобки в формулировке теоремы
## Не то выделено жирным в определениях
# ''fixed'' [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]](2.5)
## англоязычных терминов
## Жирные определения
## Непонятно, как работает метод Карно, возможно в таблице ошибка
## Двойной номер в одной из табличек Квайна
## Обернуть в tex бинарные операции в методе Квайна
## Все константы и переменные взять в tex
# '''fixed''' [[КНФ]]## англоязычных терминов## писать каждое слово с большой буквы (типа Конъюнктивная Нормальная Форма) не надо## Определения жирным## Все константы и переменные взять в tex## Выделить в табличке нужные формы цветом, как в ДНФ[[2SAT]]# '''взяли'fixed'' [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]](3)
## англоязычных терминов
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
## Добавить ссылки, изменить См. также
## Исправить странное форматирование в форме Крома
# '''fixed''' [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]## англоязычных терминов## "Предпосылки" — странное название, переименовать в "Полнота", например## Все константы взять в tex## Исправить странное форматирование в преобразовании ДНФ## Написать, что означает <tex> \succ </tex> в преобразовании Мёбиуса## Пару слов о том, чем удобен полином Жегалкина
# [[Полные системы функций. Теорема Поста о полной системе функций]]
# [[Представление функции класса DM с помощью медианы]]
# ''fixed'' [[Пороговая функция]]## Англоязычные термины## Исправить знаки неравенств в tex## Взять все константы в tex[[Троичная логика]]
== 3. Схемы из функциональных элементов ==
# ''fixed'' [[Реализация булевой функции схемой из функциональных элементов]](1)
## англоязычных терминов (на схемную сложность, глубину схемы)
## Оформить красивее определения из логических элементов
## Сделать красивую табличку## Источники информации и См. также# [[Простейшие методы синтеза схем из функциональных элементов]](0.5)
## Изменить знаки неравенств
## Ссылку на метод синтеза схем Шэннона сделать примечанием
## Определение жирным## Оформить правильно См. также и Источники информации## Увеличить дроби# [[Метод Лупанова синтеза схем]](0.5)
## Заменить литературу на источники информации
## Изменить знаки неравенств
## Запятые криво стоят в определении функции g
# ''fixed'' # Увеличить дроби# [[Cумматор]]## англоязычных терминов ## Переменные и константы взять в tex# ''fixed'' [[Каскадный сумматор]](0.5)
## англоязычных терминов
## Оформить источники информации нормально
# '''!!!''' [[Двоичный каскадный сумматор]]## англоязычных терминов ## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать## Добавить более простое и понятное построение из обсуждений[[Троичный сумматор]]
# [[Реализация вычитания сумматором]]
# [[Матричный умножитель]]
# ''fixed'' [[Дерево Уоллеса]] (1)
## пункт "определение" не нужен
## англоязычных терминов
## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
## Называть логические операции не поОформить правильно Источники информации## См. также## Увеличить дроби## Как-русскинибудь нормально назвать depth, size и sum## Нижние индексы у всех переменных проставитьЧуть-чуть увеличить картинки# [[Дерево УоллесаКонтактная схема]]## пункт "определение" не нужен[[Триггеры]]## англоязычных терминов## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга[[Квантовые гейты]]
== 4. Представление информации ==
# '''fixed''' [[Кодирование информации]]## Англоязычные термины## Странные точки в определения кода## Зачем-то описание однозначно декодируемого кода оформлено как псевдокод## Все примеры кодирования/декодирования нормально оформить## Непонятный минус префиксных кодов про то, что их надо считывать побитово {{---}} никто не мешает считать блок, а потом уже декодировать этот блок## В примере плохого декодирования префиксного выделить ошибку чуть понаглядней## Добавить в плюсы (или в минусы) размер префиксного кода## Заменить литературу на источники информации# '''взяли''' [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]## Англоязычные термины нормально оформить## Все константы взять в Tex## Выделить и красиво оформить достоинства и недостатки## Тип unsigned char для хранения чисел выглядит очень странно## Источники информации нормально оформить## В дополнительных кодах не всегда верно задаётся определение {{---}} вместо положительных нужно писать неотрицательные## Обобщить дополнительный код с дополнение до двух на длинную арифметику (это делается тривиально, но пару слов сказать надо, всё-таки так иногда бывает полезно делать)# '''взяли''' [[Представление вещественных чисел]] ''(все правки стоят 10 баллов)''## Добавить простой способ хранения вещественных чисел## Переменные и константы взять в Tex## Англоязычные термины## Дефис заменить на Шаблон:Тире## Добавить описание экспоненциальной формы записи чисел, а то сразу непонятно, что это такое (особенно читающим конспект на первом курсе)## Зачем-то картинка Half Precision два раза дублируется## Пример операции умножения плохо оформлен## Сделать нормальную табличку диапазона значений чисел## Добавить, что Extended Precision есть в сопроцессоре Intel## Добавить про способы округления## Добавить минимальную точность чисел в таком представлении## Ссылку на pdf сделать примечанием## Добавить см. также## Таблички в алгоритме получения числа красиво оформить (а лучше всего картинками сделать, как в примерах до этого)# '''fixed''' [[Представление символов, таблицы кодировок]]## Добавить информации про code point, code unit, surrogate pair и прочие радости в юникоде## Константы и переменные обернуть в Tex## Оформить красиво источники информации## Добавить особенности ASCII-таблицы## Рассказать по big-endian и little-endian подробней
== 5. Алгоритмы сжатия ==
# '''взяли''' [[Алгоритм Хаффмана]]## Переменные и константы внести в Tex## В определении кода пропущено обозначение кода символа## Интервики на реализацию за O(N) и очередь с приоритетами## Красиво оформить описание алгоритма## Кто сделает картинку примера с английскоим словом, тот молодец :)## '''?''' Альтернативное доказательство через теорию матроидов оценивается дополнительно## Заменить знаки неравенств## Правильно оформить ссылки на источники информации# '''fixed''' [[Оптимальное хранение словаря в алгоритме Хаффмана]]## Все константы и переменные взять в Tex## Добавить доказательство факта, что после удаления вершин всё будет хорошо в наивном решении## Заменить дефис на тире## Добавить псевдокоды обходов дерева## Передача информации для восстановления листьев кривовата описана# '''взяли''' [[Алгоритм Хаффмана за O(n)]](1)## Описание сумм чуточку невнятное {{---}} исправить## Таблички более полными сделать## Структурировать описание## Добавить категорииМутное доказательство после разбора случаев, надо понятней написать, см. такжеа то сейчас не ясно, источники информации## Добавить псевдокодпочему будет всё ок# '''!!!'fixed'' [[Алгоритм Ху-Таккера]](1)
## Англоязычные термины
## Заменить дефис на тире
## Сделать красивый список в определении
## Переменные и константы взять в Tex
## Исправить знаки неравенств
## Правильно оформить источники информации
## Англоязычные термины[[Неравенство Крафта]]## max заменить \max## Увеличить дроби## Правильно оформить источники информации# '''!!!''' [[Неравенство Макмиллана]]#[[Код Шеннона]]# То же самое, что и в предыдущем[[Оптимальный префиксный код с длиной кодового слова не более L бит]]# '''взяли''' [[Алгоритмы LZ77 и LZ78]](2)
## Переменные и константы взять в Tex
## Добавить примеры итоговых таблиц
## Рассказать, как декодировать
## Правильно оформить источники информации
## Получше расписать описание алгоритма
## Таблицы сделать красивыми
## Интервики
# '''fixed''' [[Алгоритм LZW]]## Слишком много пустых строк## Все переменные и константы внести в Tex## Достоинства и недостатки красиво оформить[[Алгоритм LZSS]]## Нормально оформить источники информации## Добавить пример "хитрости"## Подробное описание хитрости## Исправить пример в алгоритме# '''взяли''' [[Преобразование Барроуза-Уилера | Преобразование Барроуза-Уиллера и обратное ему]]## Все переменные и константы в тексте взять в Tex## Красиво таблички оформить## Англоязычные названия## Заменить log на \log## Доказательство корректности наивного алгоритма## Отформатировать псевдокод# '''взяли''' [[Преобразование MTF]]## Англоязычные термины оформить правильно## Переменные и константы взять в Tex## Оформить правильно источники информации## Описание понятней сделать## Ссылку на bzip сделать примечанием# [[Расстояние Хэмминга]](1)
## Англоязычные термины правильно оформить
## Причём там куб?
## Оформить правильно источники информации
## Исправить знаки неравенств
# '''fixed''' [[Избыточное кодирование, код Хэмминга]]## Англоязычные термины## Заменить дефис на тире## Все константы [[Гамма-, дельта- и переменные взять в Tex## Добавить пару слов о том, как часто нам нужно заботиться о сохранении целостности данных## Исправить знаки неравенств в Tex## Увеличить дроби## Перерисовать последние две картинки (какиеомега-то они слишком пиксельные)## Правильно оформить источники информациикод Элиаса]]
== 6. Комбинаторика ==
=== Комбинаторные объекты ===
# '''взялиfixed''' [[Комбинаторные объекты]](6)
## Правильно оформить англоязычные термины
## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
## Заменить ссылку на числа Стирлинга ссылкой на конспект
## Заменить дефисы на тире
# ''fixed'' [[Лексикографический порядок]]## Англоязычные термины правильно оформить## Отформатировать псевдокод## Список в определении криво выглядит## Оформить правильно источники информации## Добавить примеры порядка интересных комбинаторных объектов {{---}} перестановок, сочетаний.# '''взяли''' [[Коды Грея]]## Правильно оформить англоязычные термины## Все константы и переменные взять в Tex## Перерисовать кривую картинку## Отформатировать псевдокод## Доказательства по индукции нормально оформить.## Исправить "Беккета" на "Баркера" и кинуть ссылку примечанием на все виды кодов, а на код грея для перестановок сделать интервики## Не надо везде писать "Код" в коде Грея с большой буквы## Добавить применение кода Грея из обсуждений## Исправить знаки неравенств## Кое-где пропущены пробелы в Tex в формулах явных кодов Грея## Заменить источники на источники информации, добавить больше ссылок## Заменить log на \log## Примение кодо Грея как-то криво оформлено## Написать решение задачи о Ханойских башнях## Заменить дефисы на тире# ''fixed'' [[Коды Грея для перестановок]]## Англоязычные термины## Первое Определение разнести на два определения, хотя бы пояснить, что такое просто транспозиция## Табличку сделать красивой## Отформатировать псевдокод## Местами есть лишние скобки## Правильно оформить источники информации## Поправить ссылку на гамильтонов путь## Убрать пункт определение# '''fixed''' [[Коды антигрея]]## Правильно оформить англоязычные термины## Отформатировать псевдокоды## Убрать странные рамки в доказательствах корректности## Зачем-то увеличена буква G## Что-то странное написано в алгоритме генерации троичных кодов антигрея {{---}} надо исправить## Добавить категории и см. также# '''fixed''' [[Цепные коды]]## Англоязычные термины## Отформатировать псевдокод## Обозначения в псевдокоде перенести до псевдокода## Заменить \cdots на \dots## Добавить применение цепных кодов## Добавить источники информации и см. также## Исправить картинку# '''fixed''' [[Правильные скобочные последовательности]]## Англоязычные термины## Убрать лишние пропуски строк## Отформатировать псевдокоды## "а если ее нет, то — "No solution"" {{---}} оформить по-человечески## Убрать доллары из заголовков## Лексикографическое сравнение скобок красиво оформить {{---}} убрать кавычки, а знаки неравенства внести в Tex## Таблички сделать красивыми## Почему бы не написать про лексикографический порядок и алгоритм генерации сразу?## Добавить простой рекурсивный алгоритм генерации всех правильных скобочных последовательностей в лексикографическом порядке (там 5 строк буквально)## Что за result(s) в получении лексикографического порядка?## Добавить см. также
=== Генерация комбинаторных объектов ===
<ol>
<li value="8"> '''fixed''' [[Генерация комбинаторных объектов в лексикографическом порядке]] </li># Убрать генерацию из определенияЗаменить скобки "больше-меньше" на угловые# Обозначения перед псевдокодом обернуть в \mathrm или \mathttНормальную красивую картинку нарисовать<li> [[Получение номера по объекту]] </li><li> [[Получение объекта по номеру]] </li><li> [[Получение следующего объекта]] </li><li> [[Получение предыдущего объекта]] </li><li> ''fixed'' [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (1) </li>
# Отформатировать псевдокоды
# Правильно оформить источники информации# Картинку сделать векторной<li> '''fixed''' [[Получение номера Мелочи по объекту]] </li># Отформатировать псевдокоды# Обозначения обернуть в Tex# Константы взять в Tex# Оформить правильно источники информации и см. также# Добавить примеры сочетаний# Добавить асимптотику битовых векторов<li> '''взяли''' [[Получение объекта по номеру]] </li># То же самое, что и в предыдущей заявке<li> '''fixed''' [[Получение следующего объекта]] </li># Ссылки в заголовках ужасно смотрятся# Отформатировать псевдокоды# Все константы и переменные взять в Texтеху# Оформить правильно источники информации и см. также<li> '''взяли''' [[Метод генерации случайной перестановки, алгоритм ФишераКакие-Йетса]] </li># Отформатировать псевдокоды# Обернуть имена функций то пропуски в \mathrm или \mathttобосновании# Убрать обозначение массива как a[]# Все переменные взять в Tex# Оформить правильно источники информации и см. также# Добавить английские имена создателей алгоритма# Добавить доказательства неправильных способов реализацииДефисы на тире<li> '''fixed''' [[Методы генерации случайного сочетания]] </li># Заменить дефисы на тире# Все переменные и константы взять в Tex# Отформатировать псевдокоды# Убрать обозначение массива с квадратными скобками# Заменить \times на \cdot# Оформить правильно источники информации
</ol>
=== Подсчёт числа объектов ===
<ol>
<li value="14"> '''!!!''' [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li># Английские термины правильно оформить# "множеств через мощности и мощности всех" {{---}} опечатка# Тут надо в формуле включения-исключения заменить тире на дефис# Увеличить размеры сочетаний# Интервики# Ссылку на википедию сделать примечанием# Добавить реккурентную формулу числа беспорядков# Добавить ссылок на источники информации<li> '''fixed''' [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li># Задачу оформить шаблоном# Ссылки сделать примечаниями# Добавить нахождение числа разбиений методом динамического программирования за O(n^3) и за O(n^2)# Картинку диаграмы сделать побольше# Заменить знаки неравенств# Заменить используемые материалы на источники информации# Разбить конспект на заголовки<li> ''fixed'' [[Производящая функция]] (3) </li>
# Оформить правильно англоязычные термины
# Убрать точки с запятыми из определения
# Ссылки и литературу заменить на источники информации
<li> [[Лемма Бёрнсайда и Теорема Пойа]] </li>
<li> '''!!!''' [[Задача об ожерельях]] </li>: ''Эти две заявки принимаются вместе. Суммарно за них можно получить 15 баллов.''# Помёрджить с соответствующими конспектами из теории чисел# Аккуратно всё оформить# Заменить дефисы на тире# Формулировки задач внести в шаблон# Оформить правильно источники информации<li> '''взяли''' [[Числа Стирлинга первого рода]] </li># Оформить правильно англоязычные термины# Переменные и константы взять в Tex# Ссылки на википедию сделать примечаниями# Добавить доказательство факта: числа Стирлинга 1 рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней# Оформить правильно источники информации<li> '''!!!''' [[Числа Стирлинга второго рода]] </li># Англоязычные термины правильно оформить# Добавить доказательство факта: числа Стирлинга 2 рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней# Оформить правильно источники информации<li> '''!!!''' [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]] </li># Правильно оформить англоязычные термины# Увеличить обозначения чисел Эйлера# Все переменные и константы взять в Tex# Дефисы заменить на тире# Ссылки сделать примечаниями# Заменить =<li> [[Числа Каталана]] </li> на нормальный теховский символ# Добавить доказательство леммы# Оформить правильно источники информации
</ol>
=== Свойства комбинаторных объектов ===
<ol>
<li value="22"> '''!!!взяли''' [[Умножение перестановок, обратная перестановка, группа перестановок]] (5) </li>
# Определение выделить жирным
# Англоязычные термины
# Добавить примеров из конспекта групп по теории чисел
# Добавить реккурентную формулу числа инволюций c доказательством
<li> '''fixed''' [[Действие перестановки на набор из элементов, представление в виде циклов]] </li># Определения выделить жирным# Добавить ссылку на действие группы на множество из конспекта теории чисел# Все константы и переменные взять в Tex# Оформить правильно источники информации# Добавить псевдокод поиска всех циклов в перестановке<li> '''взяли''' [[Таблица инверсий]] </li># Англоязычные термины# Отформатировать псевдокоды# Разбить алгоритм построения на два подзаголовка {{---}} наивный и за O(n log n)# Имена функция в тексте взять в Tex# "единица стоит на T_i-ом месте" {{---}} непонятно, откуда тут взялось i# Интервики# Табличку красиво оформить# Оформить правильно источники информации, добавить см. также<li> ''fixed'' [[Теорема Кэли]] (1) </li>
# Бинарную операцию в группе обозначают не звёздочкой, а кружочком
# Интервики
# Оформить правильно источники информации, добавить см. также
# Добавить словесных пояснений происходящего
<li> '''!!!fixed''' [[Матричное представление перестановок]] (5) </li>
# Англоязычные термины
# Заменить дефисы на тире
# Оформить правильно источники информации
# Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
<li> ''fixed'' [[Задача о минимуме/максимуме скалярного произведения]] (2) </li>
# Оформить задачу шаблоном Задача
# Ссылку в примечании сделать на самом деле примечанием
# Оформить правильно источники информации
# Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться
<li> ''fixed'' [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li>
# Англоязычные термины
# Определение взять в шаблон
== 7. Динамическое программирование ==
:0. '''!!!fixed''' [[Динамическое программирование]](5)
:# Добавить известную цитату про ДП
:# Интервики на NP-полноту
:# Добавить про мемоизацию (и желательно что-нибудь разумное)
=== Классические задачи динамического программирования ===
# '''fixed''' [[Кратчайший путь в ациклическом графе]]## Добавить интервики## Переменные и константы взять в Tex## Отформатировать псевдокод## Написать в примере, что дана матрица смежности## Перерисовать картинку на нормальную## Оформить правильно источники информации и см. также## Добавить пару слов про то, что эту задачу можно решить поиском в ширину# [[Задача о числе путей в ациклическом графе]](4)
## Взять задачу в шаблон
## Отформатировать псевдокод
## Заменить дефисы на тире
## Добавить см. также и источники информации
## Добавить пример простого ациклического графа в виде прямоугольной матрицы с препятствиями# '''!!!''' [[Задача о расстановке знаков в выражении]](6)
## Взять задачу в шаблон
## Исправить знаки неравенств
## Источники информации правильно оформить
## Добавить решение задачи без возможности использования скобок
# '''fixed''' [[Задача о порядке перемножения матриц]](3)
## Взять переменные и константы в Tex
## Обернуть задачу в шаблон
## Оформить правильно источники информации
## Убрать про мемоизацию
# '''взяли''' [[Задача о наибольшей общей подпоследовательности]]## Англоязычные термины правильно оформить## Взять задачу в шаблон## Заменить НОП на LCS в тексте## Отформатировать псевдокоды## Оформить правильно источники информации## Добавить примеры решения различных задач с использованием LCS# '''fixed''' [[Задача о наибольшей возрастающей подпоследовательности]]## Оформить правильно англоязычные термины## Исправить знаки неравенств## Заменить дефисы на тире## Отформатировать псевдокод и исправить в нём ошибку## Взять задачу в шаблон## Взять все переменные и константы в Tex## Заменить max на \max## Решение через табло Юнга вообще криво оформлено## Правильно оформить источники информации и см. также## Заменить дефисы на тире# '''взяли''' [[Задача коммивояжера, ДП по подмножествам]]## Оформить правильно англоязычные термины## Задачу взять в шаблон## Интервики на NP-полноту## Угловые скобки в паре сделать правильно## Отформатировать псевдокоды## Оформить правильно источники информации и см. также## Добавить какие-нибудь способы оптимизации## Можно добавить фактов про шахматные доски и обход конём# '''взяли''' [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]## Англоязычные термины## Исправить знаки неравенств## Взять переменные и константы в Tex## Пояснить про eps в функции## Отформатировать псевдокоды## Оформить правильно источники информации# '''взяли!!!''' [[Задача о рюкзаке]](8)
## Взять задачу в шаблон
## Отформатировать псевдокоды
## Оформить правильно источники информации
=== Способы оптимизации методв методов динамического программирования ===
<ol>
<li value="10">''fixed'' [[Метод четырех русских для умножения матриц]] (0.5) </li>
# Взять скобки в Tex
# Заменить дефисы на тире
# Заменить литературу на источники информации
<li>''fixed'' [[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] (3.5) </li>
# Заменить дефисы на тире
# Взять константы в Tex
# Сделать нормальные картинки (или заменить на таблички)
# Заменить источники на источники информации
<li>''fixed'' [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] (1) </li>
# Кривая ссылка на оптимальный префиксный код
# Заменить дефисы на тире
# Исправить знаки неравенств
# Оформить правильно источники информации
<li> '''!!!fixed''' [[Meet-in-the-middle]] (5) </li>
# Отформатировать псевдокод
# Добавить примеры задач
=== Другие задачи ===
<ol>
<li value="14"> '''fixed''' [[Задача о расстоянии Дамерау-Левенштейна]] </li># Оформить правильно англоязычные термины# Оформить ссылки примечанием правильно или заменить на интервики# Заменить min на \min# Взять переменные в Tex# Отформатировать псевдокод# Оформить правильно источники информации<li> '''fixed''' [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li># Помёрджить аккуратно с конспектом из ТФЯ<li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li><li> '''fixed''' [[Задача о наибольшей подпоследовательности-палиндромеНаибольшая общая возрастающая подпоследовательность]] (2) </li># Задачу взять Переименовать в шаблон"Задача о ..."# Отформатировать псевдокоды
# Англоязычные термины
# Оформить правильно источники информации
<li> [[Задача о наибольшей общей палиндромной подпоследовательности]] </li><li> '''взяли!!!''' [[Динамическое программирование по профилю]] (7) </li>
# Англоязычные термины
# Заменить умножение на \cdot
# Добавить ещё примеров
# Оформить правильно источники информации
# Добавить нормальное объяснение происходящего (и почему это работает)<li> '''fixed''' [[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] (5) </li>
# Взять все переменные в Tex
# Убрать определение паросочетания
# Отформатировать псевдокод
# Оформить правильно источники информации
# Убрать первый пункт
# Добавить ещё примеров
</ol>
== 8. Теория вероятностей ==
# [[Вероятностное пространство, элементарный исход, событие]](1)
## Англоязычные термины
## Заменить дефисы на тире
## Убрать точки с запятой из определений
## Оформить правильно см. также и источники информации
## Правильно оформить дроби# [[Независимые события]](1.5)
## Оформить правильно англоязычные термины
## Тире в шаблон, переменные и константы в Tex
## Пример несовместных событий
## Определения выделить жирным
## Заменить все дроби на \genfracdfrac
## Оформить правильно источники информации
## Пример Тетраэдра оформить нормально
# [[Условная вероятность]](0.5)
## Англоязычные термины правильно оформить
## Увеличить дроби
## Переменные и константы взять в Tex
## Оформить правильно источники информации
# [[Формула полной вероятности]]## примеры перечислить как подразделы # '''!!!''' [[Формула Байеса]]## Англоязычные термины## Добавить словесное описание использование формулы перед определением## Дроби взять в \genfrac## Все переменные и константы обернуть в Tex## Добавить пример с неинтуитивным пониманием формулы Байеса {{---}} тест на болезнь даёт правильный ответ с вероятностью 95%, человек получил положительный результат, с какой вероятностью он болен, если этим заболеванием болеет 1% населения?## Кинуть ссылку на Байесовский классификатор спама## Оформить правильно см. также и источники информации# '''!!!''' [[Дискретная случайная величина]](3)
## Англоязычные термины
## Примеры
## Исправить знаки неравенств
## Оформить правильно источники информации, См. также, списки, вообще всё
## Добавить про функцию плотности вероятности
# [[Независимые случайные величины]](1)
## Англоязычные термины
## Заменить ссылку примечанием на интервики
## Заменить дефисы на тире, переменные и константы взять в Tex
## Правильно оформить источники информации
# '''взяли''' [[Математическое ожидание случайной величины]](2)## Англоязычные термины Оформить правильно оформитьСм. также## Заменить дефисы дроби на тире## Дроби оформить как \genfrac## Сделать нормальный список в линейности математического ожиданияdfrac## Переменные и константы взять в TexДоказать содержательные утверждения## Источники информации, см. также## Добавить свойств и матожиданий других распределений# '''!!!''' [[Дисперсия случайной величины]]## Англоязычные термины## Дефисы на тире, дроби в \genfrac## Убрать ; в свойствах## Если легко показать, то надо показать## Добавить про центральные моменты
# [[Ковариация случайных величин]]
# [[Корреляция случайных величин]]
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
## В Романовском добавить издание и страницу, источники информации правильно оформить
## Убрать треугольники из свойств
## Исправить знаки неравенств
## Оформить по правилам# '''!!!''' [[Симуляция одним распределением другого]](7)
## так и нет нормального определения распределения
## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
## Увеличить дроби
# [[Арифметическое кодирование]]
## раздел "определение" не нужен, перенести в заголовок## Оформить правильно англоязычные термины## Отформатировать псевдокод## Заменить дефисы на тире## Оформить правильно источники информации# '''!!!''' [[Парадоксы теории вероятностей]]## "Пусть p - предельно ненулевая вероятность" — а что это такое?## для предела использовать \limits## Англоязычные термины## Заменить дефисы на тире## Константы взять в Tex## Увеличить дроби## Заменить ссылки на источники информации## Добавить ещё парадоксов (например, парадокс мальчика и девочки)# '''!!!''' [[Схема Бернулли]](5)
## запихать примеры в один раздел "Примеры", и оформить каждый как подраздел, да и вообще нормальную структуру конспекту придать
## оформить источник
## Определение выделить жирным
## Перерисовать картинку
## Исправить знаки неравенств, дроби на \dfrac
## Константы и переменные взять в Tex
## Ссылки на формулы красиво оформить
## Оформить правильно источники информации
## Оформить по правилам
== 9. Марковские цепи ==
# '''!!!''' [[Марковская цепь]](6)
## два раза встречается определение поглощающего состояния (второе определение эквивалентно первому)
## сделать подраздел "циклические классы"
## Англоязычные термины правильно оформить
## Оформить правильно источники информации
# '''!!!''' [[Теорема о поглощении]](6)
## определение поглощающего состояния есть в предыдущем конспекте, его не надо приводить еще раз, сделать внутреннюю ссылку.
## max -> \max
## А что такое непоглощающая матрица?
## Источники информации
# '''!!!''' [[Фундаментальная матрица]](5)
## написать что-то нормальное про то, зачем вообще нужна эта матрица. Сделать ссылки туда, где она применяется.
## не сразу понятно, что такое «матрица переходов между непоглощающимися состояниями»
## Определения выделить жирным
## Дефисы на тире, переменные в Tex
# [[Математическое ожидание времени поглощения]](2)
## не везде переменные обернуты в латех
## Оформить правильно Источники информации## Добавить См. также## Пояснить подробней переходы# '''!!!''' [[Расчет вероятности поглощения в состоянии]](5)
## куча разного псевдокода, не относящегося непосредственно к расчету вероятности поглощения, его надо разнести в соответствующие конспекты. Писать код нахождения обратной матрицы вообще не осмысленно и к делу не относится.
## имена переменных из псевдокода в тексте оборачиваются в \mathrm или \mathtt
## оформить псевдокод в виде функций, без всяких println
## оформить нормально источник
## Заголовки первого уровня убрать
# [[Эргодическая марковская цепь]](1)
## определения пересекаются с конспектом про марковские цепи
## Сделать ссылку примечанием
## Заменить дефисы на тире
## Оформить правильно источники информации
# [[Регулярная марковская цепь]](1)
## Переменные взять в Tex
## Оформить правильно источники информации
## Дефисы на тире## Добавить См. также# [[Примеры использования Марковских цепей]](1)
## Переменные в Tex
## Заменить литературу на источники информации
## Оформить по правилам# '''!!!''' [[Скрытые Марковские модели]](7)
## можно добавить сюда каких-нибудь полезных примеров из распознавания речи и биоинформатики, или просто любых примеров
## Переменные и константы взять в Tex
## Исправить небольшую багу в картинке
## Англоязычные термины
## Категории# '''!!!''' [[Алгоритм Витерби]](5)
## "правдоподобная последовательность скрытых состояний" {{---}} что такое "наиболее правдоподобная"?
## имена переменных в тексте оборачиваются в \mathrm или \mathtt
## Англоязычные термины
## Заменить ссылки на источники информации
# [[Алгоритм "Вперед-Назад"]](5)
## Отформатировать псевдокод
## Заменить литературу на источники информации
## Оформить по правилам
