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

Материал из Викиконспекты
Перейти к: навигация, поиск
(5. Алгоритмы сжатия)
(в процессе проверки Способы оптимизации методв динамического программирования)
Строка 536: Строка 536:
 
## Понизить уровень заголовков первого уровня
 
## Понизить уровень заголовков первого уровня
 
## Оформить правильно источники информации
 
## Оформить правильно источники информации
=== '''в процессе проверки''' Способы оптимизации методв динамического программирования ===
+
=== Способы оптимизации методв динамического программирования ===
 
<ol>
 
<ol>
 
<li value="10">[[Метод четырех русских для умножения матриц]] </li>
 
<li value="10">[[Метод четырех русских для умножения матриц]] </li>
 +
# Взять скобки в Tex
 +
# Заменить дефисы на тире
 +
# Заменить литературу на источники информации
 
<li>[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] </li>
 
<li>[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]] </li>
 +
# Заменить дефисы на тире
 +
# Взять константы в Tex
 +
# Сделать нормальные картинки (или заменить на таблички)
 +
# Заменить источники на источники информации
 
<li>[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] </li>
 
<li>[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]] </li>
<li>[[Meet-in-the-middle]] </li>
+
# Кривая ссылка на оптимальный префиксный код
 +
# Заменить дефисы на тире
 +
# Взять переменные и константы в Tex
 +
# Исправить знаки неравенств
 +
# Оформить правильно источники информации
 +
<li> '''!!!''' [[Meet-in-the-middle]] </li>
 +
# Отформатировать псевдокод
 +
# Добавить примеры задач
 +
# Оформить правильно источники информации
 
</ol>
 
</ol>
 +
 
=== '''в процессе проверки''' Другие задачи ===
 
=== '''в процессе проверки''' Другие задачи ===
 
<ol>
 
<ol>

Версия 00:12, 17 октября 2014

Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект ДНФ из раздела булевых функций имеет тикет 2-3)

Заявки можно подавать только на те конспекты, которые отмечены !!!. Один такой тикет засчитывается за [math] 5 [/math] баллов (в случае исправления, конечно же). Не берите за раз много исправлений — оставляйте своим однокурсникам, да и вдруг вы даже один тикет не осилите .

  • Если вдруг окажется мало исправлений в одной вашей заявке, то дополнительно к ней на моё усмотрение может добавиться ещё несколько тикетов, не помеченных восклицательными знаками.
  • Если не осталось конспектов с !!!, нет желания их делать, нет желания делать новый конспект или разобрали все хорошие темы, то можно взять несколько правок, не отмеченных !!!, но для этого необходимо заранее мне сообщить о своём таком желании, а я уже сам выдам темы. Несколько таких правок будут засчитаны, как одна с !!!.

1. Отношения

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

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

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

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

  1. Реализация булевой функции схемой из функциональных элементов
    1. англоязычных терминов (на схемную сложность, глубину схемы)
    2. Оформить красивее определения из логических элементов
  2. Простейшие методы синтеза схем из функциональных элементов
    1. Изменить знаки неравенств
    2. Ссылку на метод синтеза схем Шэннона сделать примечанием
  3. Метод Лупанова синтеза схем
    1. Заменить литературу на источники информации
    2. Изменить знаки неравенств
    3. Запятые криво стоят в определении функции g
  4. Cумматор
    1. англоязычных терминов
    2. Переменные и константы взять в tex
  5. !!! Каскадный сумматор
    1. англоязычных терминов
    2. Оформить источники информации нормально
    3. Добавить более простое и понятное построение из обсуждений
  6. Двоичный каскадный сумматор
    1. англоязычных терминов
    2. из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать
  7. Реализация вычитания сумматором
  8. Матричный умножитель
    1. пункт "определение" не нужен
    2. англоязычных терминов
    3. надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга
    4. Называть логические операции не по-русски
    5. Нижние индексы у всех переменных проставить
  9. Дерево Уоллеса
    1. пункт "определение" не нужен
    2. англоязычных терминов
    3. надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга

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

  1. fixed Кодирование информации
    1. Англоязычные термины
    2. Странные точки в определения кода
    3. Зачем-то описание однозначно декодируемого кода оформлено как псевдокод
    4. Все примеры кодирования/декодирования нормально оформить
    5. Непонятный минус префиксных кодов про то, что их надо считывать побитово — никто не мешает считать блок, а потом уже декодировать этот блок
    6. В примере плохого декодирования префиксного выделить ошибку чуть понаглядней
    7. Добавить в плюсы (или в минусы) размер префиксного кода
    8. Заменить литературу на источники информации
  2. взяли Представление целых чисел: прямой код, код со сдвигом, дополнительный код
    1. Англоязычные термины нормально оформить
    2. Все константы взять в Tex
    3. Выделить и красиво оформить достоинства и недостатки
    4. Тип unsigned char для хранения чисел выглядит очень странно
    5. Источники информации нормально оформить
    6. В дополнительных кодах не всегда верно задаётся определение — вместо положительных нужно писать неотрицательные
    7. Обобщить дополнительный код с дополнение до двух на длинную арифметику (это делается тривиально, но пару слов сказать надо, всё-таки так иногда бывает полезно делать)
  3. взяли Представление вещественных чисел (все правки стоят 10 баллов)
    1. Добавить простой способ хранения вещественных чисел
    2. Переменные и константы взять в Tex
    3. Англоязычные термины
    4. Дефис заменить на Шаблон:Тире
    5. Добавить описание экспоненциальной формы записи чисел, а то сразу непонятно, что это такое (особенно читающим конспект на первом курсе)
    6. Зачем-то картинка Half Precision два раза дублируется
    7. Пример операции умножения плохо оформлен
    8. Сделать нормальную табличку диапазона значений чисел
    9. Добавить, что Extended Precision есть в сопроцессоре Intel
    10. Добавить про способы округления
    11. Добавить минимальную точность чисел в таком представлении
    12. Ссылку на pdf сделать примечанием
    13. Добавить см. также
    14. Таблички в алгоритме получения числа красиво оформить (а лучше всего картинками сделать, как в примерах до этого)
  4. !!! Представление символов, таблицы кодировок
    1. Добавить информации про code point, code unit, surrogate pair и прочие радости в юникоде
    2. Константы и переменные обернуть в Tex
    3. Оформить красиво источники информации

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

  1. взяли Алгоритм Хаффмана
    1. Переменные и константы внести в Tex
    2. В определении кода пропущено обозначение кода символа
    3. Интервики на реализацию за O(N) и очередь с приоритетами
    4. Красиво оформить описание алгоритма
    5. Кто сделает картинку примера с английскоим словом, тот молодец :)
    6. ? Альтернативное доказательство через теорию матроидов оценивается дополнительно
    7. Заменить знаки неравенств
    8. Правильно оформить ссылки на источники информации
  2. !!! Оптимальное хранение словаря в алгоритме Хаффмана
    1. Все константы и переменные взять в Tex
    2. Добавить доказательство факта, что после удаления вершин всё будет хорошо в наивном решении
    3. Заменить дефис на тире
    4. Добавить псевдокоды обходов дерева
    5. Передача информации для восстановления листьев кривовата описана
  3. !!! Алгоритм Хаффмана за O(n)
    1. Описание сумм чуточку невнятное — исправить
    2. Таблички более полными сделать
    3. Структурировать описание
    4. Добавить категории, см. также, источники информации
    5. Добавить псевдокод
  4. !!! Алгоритм Ху-Таккера
    1. Англоязычные термины
    2. Заменить дефис на тире
    3. Сделать красивый список в определении
    4. Переменные и константы взять в Tex
    5. Добавить доказательство пропущенных лемм и теорем (если там много, то всё может суммарно оцениться)
    6. Исправить знаки неравенств
    7. Правильно оформить источники информации
  5. !!! Неравенство Крафта
    1. Зачем-то дублируются определения с статьей про кодирование информации. Убедиться, что они совпадают, выпилить и сделать внутренние ссылки.
    2. А зачем оно нужно? Просто интересный факт?
    3. Исправить знаки неравенств
    4. Правильно оформить источники информации
    5. Англоязычные термины
    6. max заменить \max
    7. Увеличить дроби
    8. Правильно оформить источники информации
  6. !!! Неравенство Макмиллана
    1. То же самое, что и в предыдущем
  7. !!! Алгоритмы LZ77 и LZ78
    1. Переменные и константы взять в Tex
    2. Добавить примеры итоговых таблиц
    3. Рассказать, как декодировать
    4. Правильно оформить источники информации
    5. ? Добавить оценку степени сжатия
  8. взяли Алгоритм LZW
    1. Слишком много пустых строк
    2. Все переменные и константы внести в Tex
    3. Достоинства и недостатки красиво оформить
    4. Нормально оформить источники информации
    5. Добавить пример "хитрости"
  9. !!! Преобразование Барроуза-Уиллера и обратное ему
    1. Все переменные и константы в тексте взять в Tex
    2. Красиво таблички оформить
    3. Англоязычные названия
    4. Заменить log на \log
    5. Доказательство корректности наивного алгоритма
    6. Отформатировать псевдокод
  10. !!! Преобразование MTF
    1. Англоязычные термины оформить правильно
    2. Переменные и константы взять в Tex
    3. Оформить правильно источники информации
    4. Описание понятней сделать
    5. Ссылку на bzip сделать примечанием
  11. Расстояние Хэмминга
    1. Англоязычные термины правильно оформить
    2. Причём там куб?
    3. Оформить правильно источники информации
    4. Исправить знаки неравенств
  12. !!! Избыточное кодирование, код Хэмминга
    1. Англоязычные термины
    2. Заменить дефис на тире
    3. Все константы и переменные взять в Tex
    4. Добавить пару слов о том, как часто нам нужно заботиться о сохранении целостности данных
    5. Исправить знаки неравенств в Tex
    6. Увеличить дроби
    7. Перерисовать последние две картинки (какие-то они слишком пиксельные)
    8. Правильно оформить источники информации

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

Комбинаторные объекты

  1. !!! Комбинаторные объекты
    1. Правильно оформить англоязычные термины
    2. Привести формулы каждого объекта — общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
    3. Под каждый комбинаторный объект сделать свой подзаголовк уровня ниже
    4. Все переменные и константы взять в Tex
    5. Добавить ссылок по всем объектам в источники информации
    6. Заменить ссылку на числа Стирлинга ссылкой на конспект
    7. Заменить дефисы на тире
  2. Лексикографический порядок
    1. Англоязычные термины правильно оформить
    2. Отформатировать псевдокод
    3. Список в определении криво выглядит
    4. Оформить правильно источники информации
    5. Добавить примеры порядка интересных комбинаторных объектов — перестановок, сочетаний.
  3. !!! Коды Грея
    1. Правильно оформить англоязычные термины
    2. Все константы и переменные взять в Tex
    3. Перерисовать кривую картинку
    4. Отформатировать псевдокод
    5. Доказательства по индукции нормально оформить.
    6. Исправить "Беккета" на "Баркера" и кинуть ссылку примечанием на все виды кодов, а на код грея для перестановок сделать интервики
    7. Не надо везде писать "Код" в коде Грея с большой буквы
    8. Добавить применение кода Грея из обсуждений
    9. Исправить знаки неравенств
    10. Кое-где пропущены пробелы в Tex в формулах явных кодов Грея
    11. Заменить источники на источники информации, добавить больше ссылок
    12. Заменить log на \log
    13. Примение кодо Грея как-то криво оформлено
    14. Написать решение задачи о Ханойских башнях
    15. Заменить дефисы на тире
  4. Коды Грея для перестановок
    1. Англоязычные термины
    2. Первое Определение разнести на два определения, хотя бы пояснить, что такое просто транспозиция
    3. Табличку сделать красивой
    4. Отформатировать псевдокод
    5. Местами есть лишние скобки
    6. Правильно оформить источники информации
    7. Поправить ссылку на гамильтонов путь
    8. Убрать пункт определение
  5. !!! Коды антигрея
    1. Правильно оформить англоязычные термины
    2. Отформатировать псевдокоды
    3. Убрать странные рамки в доказательствах корректности
    4. Зачем-то увеличена буква G
    5. Что-то странное написано в алгоритме генерации троичных кодов антигрея — надо исправить
    6. Добавить категории и см. также
  6. !!! Цепные коды
    1. Англоязычные термины
    2. Отформатировать псевдокод
    3. Обозначения в псевдокоде перенести до псевдокода
    4. Заменить \cdots на \dots
    5. Добавить применение цепных кодов
    6. Добавить источники информации и см. также
  7. !!! Правильные скобочные последовательности
    1. Англоязычные термины
    2. Убрать лишние пропуски строк
    3. Отформатировать псевдокоды
    4. "а если ее нет, то — "No solution"" — оформить по-человечески
    5. Убрать доллары из заголовков
    6. Лексикографическое сравнение скобок красиво оформить — убрать кавычки, а знаки неравенства внести в Tex
    7. Таблички сделать красивыми
    8. Почему бы не написать про лексикографический порядок и алгоритм генерации сразу?
    9. Добавить простой рекурсивный алгоритм генерации всех правильных скобочных последовательностей в лексикографическом порядке (там 5 строк буквально)
    10. Что за result(s) в получении лексикографического порядка?
    11. Добавить см. также

Генерация комбинаторных объектов

  1. !!! Генерация комбинаторных объектов в лексикографическом порядке
    1. Убрать генерацию из определения
    2. Обозначения перед псевдокодом обернуть в \mathrm или \mathtt
    3. Отформатировать псевдокоды
    4. Правильно оформить источники информации
    5. Картинку сделать векторной
  2. !!! Получение номера по объекту
    1. Отформатировать псевдокоды
    2. Обозначения обернуть в Tex
    3. Константы взять в Tex
    4. Оформить правильно источники информации и см. также
    5. Добавить примеры сочетаний
    6. Добавить асимптотику битовых векторов
  3. !!! Получение объекта по номеру
    1. То же самое, что и в предыдущей заявке
  4. !!! Получение следующего объекта
    1. Ссылки в заголовках ужасно смотрятся
    2. Отформатировать псевдокоды
    3. Все константы и переменные взять в Tex
    4. Оформить правильно источники информации и см. также
  5. !!! Метод генерации случайной перестановки, алгоритм Фишера-Йетса
    1. Отформатировать псевдокоды
    2. Обернуть имена функций в \mathrm или \mathtt
    3. Убрать обозначение массива как a[]
    4. Все переменные взять в Tex
    5. Оформить правильно источники информации и см. также
    6. Добавить английские имена создателей алгоритма
    7. Добавить доказательства неправильных способов реализации
  6. !!! Методы генерации случайного сочетания
    1. Заменить дефисы на тире
    2. Все переменные и константы взять в Tex
    3. Отформатировать псевдокоды
    4. Убрать обозначение массива с квадратными скобками
    5. Заменить \times на \cdot
    6. Оформить правильно источники информации

Подсчёт числа объектов

  1. !!! Формула включения-исключения, подсчет числа беспорядков
    1. Английские термины правильно оформить
    2. "множеств через мощности и мощности всех" — опечатка
    3. Тут надо в формуле включения-исключения заменить тире на дефис
    4. Увеличить размеры сочетаний
    5. Интервики
    6. Ссылку на википедию сделать примечанием
    7. Добавить реккурентную формулу числа беспорядков
    8. Добавить ссылок на источники информации
  2. !!! Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера
    1. Задачу оформить шаблоном
    2. Ссылки сделать примечаниями
    3. Добавить нахождение числа разбиение методом динамического программирования за O(n^3) и за O(n^2)
    4. Картинку диаграмы сделать побольше
    5. Заменить знаки неравенств
    6. Заменить используемые материалы на источники информации
    7. Разбить конспект на заголовки
  3. Производящая функция
    1. Оформить правильно англоязычные термины
    2. Убрать точки с запятыми из определения
    3. Все переменные и константы в Tex взять
    4. Исправить знаки неравенств
    5. Оформить ссылки примечаниями
    6. Ссылки и литературу заменить на источники информации
  4. Лемма Бёрнсайда и Теорема Пойа
  5. !!! Задача об ожерельях
  6. Эти две заявки принимаются вместе. Суммарно за них можно получить 15 баллов.
    1. Помёрджить с соответствующими конспектами из теории чисел
    2. Аккуратно всё оформить
    3. Заменить дефисы на тире
    4. Формулировки задач внести в шаблон
    5. Оформить правильно источники информации
  7. !!! Числа Стирлинга первого рода
    1. Оформить правильно англоязычные термины
    2. Переменные и константы взять в Tex
    3. Ссылки на википедию сделать примечаниями
    4. Добавить доказательство перехода к базису; ещё некоторые тождества доказать было бы неплохо
    5. Оформить правильно источники информации
  8. !!! Числа Стирлинга второго рода
    1. Англоязычные термины правильно оформить
    2. Добавить доказетьство перехода к базису
    3. Оформить правильно источники информации
  9. !!! Числа Эйлера первого и второго рода. Подъемы в перестановках
    1. Правильно оформить англоязычные термины
    2. Увеличить обозначения чисел Эйлера
    3. Все переменные и константы взять в Tex
    4. Дефисы заменить на тире
    5. Ссылки сделать примечаниями
    6. Заменить => на нормальный теховский символ
    7. Добавить доказательство леммы
    8. Оформить правильно источники информации

Свойства комбинаторных объектов

  1. !!! Умножение перестановок, обратная перестановка, группа перестановок
    1. Определение выделить жирным
    2. Англоязычные термины
    3. Тут вообще неправильно описано умножение перестановок (не путать с подстановками)
    4. Отформатировать псевдокоды
    5. Все переменные и константы взять в Tex
    6. Оформить правильно источники информации
    7. Добавить примеров из конспекта групп по теории чисел
  2. !!! Действие перестановки на набор из элементов, представление в виде циклов
    1. Определения выделить жирным
    2. Добавить ссылку на действие группы на множество из конспекта теории чисел
    3. Все константы и переменные взять в Tex
    4. Оформить правильно источники информации
    5. Добавить псевдокод поиска всех циклов в перестановке
  3. !!! Таблица инверсий
    1. Англоязычные термины
    2. Отформатировать псевдокоды
    3. Разбить алгоритм построения на два подзаголовка — наивный и за O(n log n)
    4. Имена функция в тексте взять в Tex
    5. "единица стоит на T_i-ом месте" — непонятно, откуда тут взялось i
    6. Интервики
    7. Табличку красиво оформить
    8. Оформить правильно источники информации, добавить см. также
  4. Теорема Кэли
    1. Бинарную операцию в группе обозначают не звёздочкой, а кружочком
    2. Интервики
    3. Оформить правильно источники информации, добавить см. также
    4. Добавить словесных пояснений происходящего
  5. !!! Матричное представление перестановок
    1. Англоязычные термины
    2. Заменить дефисы на тире
    3. Добавить подробные доказательства утвеждений (или пояснить получше уже существующие)
    4. Оформить правильно источники информации
    5. Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
  6. Задача о минимуме/максимуме скалярного произведения
    1. Оформить задачу шаблоном Задача
    2. Ссылку в примечании сделать на самом деле примечанием
    3. Добавить использование этой теоремы (в теории матроидов и теории расписаний)
    4. Оформить правильно источники информации
    5. Доказательство плохо разбито на пункты — от нумерации в доказательстве вообще можно избавиться
  7. Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
    1. Англоязычные термины
    2. Определение взять в шаблон
    3. Заменить дефисы на тире
    4. Оформить правильно источники информации

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

0. !!! Динамическое программирование
  1. Добавить известную цитату про ДП
  2. Интервики на NP-полноту
  3. Картинки криво расположены
  4. Добавить больше примеров
  5. Добавить описание принципа оптимальности на подмножествах
  6. Оформить правильно источники информации
  7. Добавить про мемоизацию (и желательно что-нибудь разумное)

Классические задачи динамического программирования

  1. !!! Кратчайший путь в ациклическом графе
    1. Добавить интервики
    2. Переменные и константы взять в Tex
    3. Отформатировать псевдокод
    4. Написать в примере, что дана матрица смежности
    5. Перерисовать картинку на нормальную
    6. Оформить правильно источники информации и см. также
    7. Добавить пару слов про то, что эту задачу можно решить поиском в ширину
  2. Задача о числе путей в ациклическом графе
    1. Взять задачу в шаблон
    2. Отформатировать псевдокод
    3. Обернуть имя функции в тексте в mathrm
    4. Заменить дефисы на тире
    5. Добавить см. также и источники информации
  3. !!! Задача о расстановке знаков в выражении
    1. Взять задачу в шаблон
    2. Исправить знаки неравенств
    3. Ссылку примечанием оформить нормально
    4. Взять все переменные и константы в тексте в Tex
    5. Отформатировать псевдокод
    6. Табличку нормально оформить
    7. Описать восстановление ответа
    8. Источники информации правильно оформить
  4. !!! Задача о порядке перемножения матриц
    1. Взять переменные и константы в Tex
    2. Обернуть задачу в шаблон
    3. Интервики на конспект правильных скобочных последовательностей
    4. Написать, почему нас не устраивает число Каталана в асимптотике
    5. Отформатировать псевдокоды
    6. Оформить правильно источники информации
    7. Убрать про мемоизацию
  5. !!! Задача о наибольшей общей подпоследовательности
    1. Англоязычные термины правильно оформить
    2. Взять задачу в шаблон
    3. Заменить НОП на LCS в тексте
    4. Отформатировать псевдокоды
    5. Оформить правильно источники информации
    6. Добавить примеры решения различных задач с использованием LCS
  6. !!! Задача о наибольшей возрастающей подпоследовательности
    1. Оформить правильно англоязычные термины
    2. Исправить знаки неравенств
    3. Заменить дефисы на тире
    4. Отформатировать псевдокод и исправить в нём ошибку
    5. Взять задачу в шаблон
    6. Взять все переменные и константы в Tex
    7. Заменить max на \max
    8. Решение через табло Юнга вообще криво оформлено
    9. Правильно оформить источники информации и см. также
    10. Заменить дефисы на тире
  7. !!! Задача коммивояжера, ДП по подмножествам
    1. Оформить правильно англоязычные термины
    2. Задачу взять в шаблон
    3. Интервики на NP-полноту
    4. Угловые скобки в паре сделать правильно
    5. Отформатировать псевдокоды
    6. Оформить правильно источники информации и см. также
    7. Добавить какие-нибудь способы оптимизации
    8. Можно добавить фактов про шахматные доски и обход конём
  8. !!! Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
    1. Англоязычные термины
    2. Исправить знаки неравенств
    3. Взять переменные и константы в Tex
    4. Пояснить про eps в функции
    5. Отформатировать псевдокоды
    6. Оформить правильно источники информации
  9. !!! Задача о рюкзаке
    1. Взять задачу в шаблон
    2. Отформатировать псевдокоды
    3. Заменить дефисы на тире
    4. Исправить знаки неравенств
    5. Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему
    6. Сделать итоговую формулу для А c помощью фигурной скобки
    7. Предложить вариант замены картинок на вики-таблички с сохранением обозначения пути
    8. Понизить уровень заголовков первого уровня
    9. Оформить правильно источники информации

Способы оптимизации методв динамического программирования

  1. Метод четырех русских для умножения матриц
    1. Взять скобки в Tex
    2. Заменить дефисы на тире
    3. Заменить литературу на источники информации
  2. Применение метода четырех русских в задачах ДП на примере задачи о НОП
    1. Заменить дефисы на тире
    2. Взять константы в Tex
    3. Сделать нормальные картинки (или заменить на таблички)
    4. Заменить источники на источники информации
  3. Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
    1. Кривая ссылка на оптимальный префиксный код
    2. Заменить дефисы на тире
    3. Взять переменные и константы в Tex
    4. Исправить знаки неравенств
    5. Оформить правильно источники информации
  4. !!! Meet-in-the-middle
    1. Отформатировать псевдокод
    2. Добавить примеры задач
    3. Оформить правильно источники информации

в процессе проверки Другие задачи

  1. Задача о расстоянии Дамерау-Левенштейна
  2. Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
  3. Задача о наибольшей подпоследовательности-палиндроме
  4. Динамическое программирование по профилю
  5. Динамика по поддеревьям, задачо о паросочетание максимального веса в дереве

в процессе проверки 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. Алгоритм "Вперед-Назад"