3622
правки
Изменения
м
## Правильно оформить англоязычные термины
## Избавиться от двоеточия в определении
## Пробел перед открывающей скобкой
## Оформить правильно источники информации
## Убрать "что и требовалось доказать"
## Источники информации, см. также
## Заменить дефисы на тире## Рабить определение на две части {{---}} про среднеквадратичное отклонение и ковариацию## Переменные и константы взять в Tex## Исправить знаки неравенств## Оформить правильно источники информации# [[Энтропия случайного источника]](2)
## Помёрджить с предыдущим конспектом
Изменён уровень защиты страницы «Участник:Shersh/Тикеты к 1ому терму» ([edit=autoconfirmed] (бессрочно) [move=autoconfirmed] (бессрочно))
## Оформить красиво источники информации
## Английские термины к видам отношений
# [[Композиция отношений|Композиция отношений, степерь отношения, обратное отношение]](0.5)## Отформатировать свойства красиво## Оформить правильно источники информации## Англ. термины
# [[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
# [[Симметричное отношение]]
# [[Отношение эквивалентности]]
# [[Транзитивное замыкание|Транзитивное замыкание отношения]]
# '''!!!''' [[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] (5)## Отформатировать псевдокод## Добавить ссылок в источники информации## интересно, что алгоритм работает только для конечных отношений, хотя транзитивно замкнуть можно и бесконечное бинарное отношение. Кто сделает модификацию для бесконечных, молодец :) (можно считать, что у нас есть "бесконечная матрица" бинарного отношения, и что мы такую же "бесконечную матрицу" заполняем, впринципе). Понятно, что всю таблицу мы никогда не заполним, но важно, чтобы каждый конкретный элемент таблицы был заполнен через какое-то конечное время.## Нужен пример, картинка# '''!!!fixed''' [[Транзитивный остов]] (5)
## Отформатировать псевдокод
## Добавить категории
## возможно, мне показалось, но там, где "ацикличен", надо писать "без петель"
## если кто-то будет способен значительно упростить доказательство алгоритма, тот молодец
## Отформатировать конспект по правилам
== 2. Булевы функции ==
# ''взяли'' [[Определение булевой функции]] (1.5)## англоязычных терминов## термины вроде "самодвойственная и т.п." встечаются в табличке и больше нигде. Сделать ссылки вперед на соответствующие определения.## Исправить неравенства в tex## Обернуть в tex все константы в тексте## Определение двойственной сделать жирным## Объединить литературу и источники информации## Красиво оформить таблицы[[Побитовые операции]]# ''fixed'' [[Суперпозиции]] (0.5)
## англоязычных терминов
# ''fixed'' [[ДНФ]] (0.5)
## англоязычных терминов
## писать каждое слово с большой буквы (типа Дизъюнктивная Нормальная Форма) не надо
## Убрать странные скобки в формулировке теоремы
## Не то выделено жирным в определениях
# ''fixed'' [[Сокращенная и минимальная ДНФ | Сокращенная и минимальная ДНФ, минимизация ДНФ методами гиперкубов, карт Карно, Квайна]] (2.5)
## англоязычных терминов
## Жирные определения
## Все константы и переменные взять в tex
# [[КНФ]]
# [[2SAT]]# ''fixed'' [[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] (3)
## англоязычных терминов
## написать, почему факт того, что существует полиномиальный алгоритм, интересен
## Исправить странное форматирование в форме Крома
# [[Полином Жегалкина | Полином Жегалкина, преобразование Мёбиуса]]
# ''взяли'' [[Полные системы функций. Теорема Поста о полной системе функций]] (3.5)## англоязычных терминов## Заменить знаки неравенств в tex## Убрать ; в списках## Заменить в некоторых местах НЕ на \neg (то же самое про И и ИЛИ) {{---}} или заменить на англоязычные названия операций## Избавиться от сокращений т.е. и т.к.## Все переменные взять в tex## Красиво и понятно отформатировать доказательство
# [[Представление функции класса DM с помощью медианы]]
# [[Пороговая функция]]
# [[Троичная логика]]
== 3. Схемы из функциональных элементов ==
# ''fixed'' [[Реализация булевой функции схемой из функциональных элементов]] (1)
## англоязычных терминов (на схемную сложность, глубину схемы)
## Оформить красивее определения из логических элементов
## Увеличить дроби
# [[Cумматор]]
# ''fixed'' [[Каскадный сумматор]] (0.5)
## англоязычных терминов
## Оформить источники информации нормально
# [[Двоичный каскадный сумматор]] (1)## англоязычных терминов ## из определения не ясно, чем двоичный каскадный отличается от просто каскадного, надо это в определение запихать## Табличку оформить красиво## Источники информации## Увеличить картинку## Список в обозначениях оформить правильно
# [[Троичный сумматор]]
# [[Реализация вычитания сумматором]]
# [[Матричный умножитель]] (4)## пункт "определение" не нужен## англоязычных терминов## надо писать в определении схем, за сколько они работают, а то не ясно их отличие друг от друга## Называть логические операции не по-русски## Нижние индексы у всех переменных проставить## Картинку про умножение в столбик сделать красивой векторной## Вторую картинку подписать## Третью картинку прокомментировать## Источники информации и См. также# ''fixed'' [[Дерево Уоллеса]] (1)
## пункт "определение" не нужен
## англоязычных терминов
## Чуть-чуть увеличить картинки
# [[Контактная схема]]
# [[Триггеры]]
# [[Квантовые гейты]]
== 4. Представление информации ==
# [[Кодирование информации]]
# '''fixed''' [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]] (7)## Англоязычные термины нормально оформить## Все константы взять в Tex## Выделить и красиво оформить достоинства и недостатки## Тип unsigned char для хранения чисел выглядит очень странно## Источники информации нормально оформить## В дополнительных кодах не всегда верно задаётся определение {{---}} вместо положительных нужно писать неотрицательные## Обобщить дополнительный код с дополнение до двух на длинную арифметику (это делается тривиально, но пару слов сказать надо, всё-таки так иногда бывает полезно делать)
# [[Представление вещественных чисел]]
# [[Представление символов, таблицы кодировок]]
== 5. Алгоритмы сжатия ==
# '''fixed''' [[Алгоритм Хаффмана]] (5)## Переменные и константы внести в Tex## В определении кода пропущено обозначение кода символа## Интервики на реализацию за O(N) и очередь с приоритетами## Красиво оформить описание алгоритма## Картинка с английским словом## Заменить знаки неравенств## Правильно оформить ссылки на источники информации
# [[Оптимальное хранение словаря в алгоритме Хаффмана]]
# [[Алгоритм Хаффмана за O(n)]] (1)
## Мутное доказательство после разбора случаев, надо понятней написать, а то сейчас не ясно, почему будет всё ок
# ''fixed'' [[Алгоритм Ху-Таккера]] (1)
## Англоязычные термины
## Заменить дефис на тире
# [[Алгоритм LZW]]
# [[Алгоритм LZSS]]
# '''взяли''' [[Преобразование Барроуза-Уилера | Преобразование Барроуза-Уиллера и обратное ему]] (5)## Все переменные и константы в тексте взять в Tex## Красиво таблички оформить## Англоязычные названия## Заменить log на \log## Доказательство корректности наивного алгоритма## Отформатировать псевдокод## Оформить правильно источники информации
# [[Преобразование MTF]]
# [[Расстояние Хэмминга]] (1)
== 6. Комбинаторика ==
=== Комбинаторные объекты ===
# '''взялиfixed''' [[Комбинаторные объекты]] (6)
## Правильно оформить англоязычные термины
## Привести формулы каждого объекта {{---}} общее количество, формулы с повторениями (для сочетаний, размещений и перестановок) с доказательством
=== Генерация комбинаторных объектов ===
<ol>
<li value="8"> [[Генерация комбинаторных объектов в лексикографическом порядке]] (3) </li>
# Заменить скобки "больше-меньше" на угловые
# Нормальную красивую картинку нарисовать
<li> [[Получение объекта по номеру]] </li>
<li> [[Получение следующего объекта]] </li>
<li> [[Получение предыдущего объекта]] (3) </li># Добавить специализацию для получения предыдущего разбиения на множества<li> '''!!!'fixed'' [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] (51) </li># Добавить Шаблон:Задача# Переименовать '''Тасование'''
# Отформатировать псевдокоды
# Обернуть имена функций в \mathrm или \mathtt# Убрать обозначение массива как a[]Мелочи по теху# Все переменные взять Какие-то пропуски в Tex# Оформить правильно источники информации и см. также# Добавить английские имена создателей алгоритмаобосновании# Добавить доказательства неправильных способов реализацииДефисы на тире
<li> [[Методы генерации случайного сочетания]] </li>
</ol>
<li value="14"> [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]] </li>
<li> [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]</li>
<li> ''fixed'' [[Производящая функция]] (3) </li>
# Оформить правильно англоязычные термины
# Убрать точки с запятыми из определения
# Оформить ссылки примечаниями
# Ссылки и литературу заменить на источники информации
<li> ''взяли'' [[Лемма Бёрнсайда и Теорема Пойа]] </li><li> '''взяли''' [[Задача об ожерельях]] (10) </li>: ''Эти две заявки принимаются вместе. Суммарно за них можно получить 15 баллов.''# Помёрджить с соответствующими конспектами из теории чисел# Аккуратно всё оформить# Заменить дефисы на тире# Формулировки задач внести в шаблон# Оформить правильно источники информации
<li> [[Числа Стирлинга первого рода]] </li>
<li> [[Числа Стирлинга второго рода]] </li>
<li> '''!!!''' [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]] (5) </li># Правильно оформить англоязычные термины# Увеличить обозначения чисел Эйлера# Все переменные и константы взять в Tex# Дефисы заменить на тире# Ссылки сделать примечаниями# Заменить => на нормальный теховский символ# Добавить доказательство леммы# Оформить правильно источники информации
<li> [[Числа Каталана]] </li>
</ol>
=== Свойства комбинаторных объектов ===
<ol>
<li value="22"> '''!!!взяли''' [[Умножение перестановок, обратная перестановка, группа перестановок]] (5) </li>
# Определение выделить жирным
# Англоязычные термины
<li> [[Действие перестановки на набор из элементов, представление в виде циклов]] </li>
<li> [[Таблица инверсий]] </li>
<li> ''fixed'' [[Теорема Кэли]] (1) </li>
# Бинарную операцию в группе обозначают не звёздочкой, а кружочком
# Интервики
# Оформить правильно источники информации, добавить см. также
# Добавить словесных пояснений происходящего
<li> '''!!!fixed''' [[Матричное представление перестановок]] (5) </li>
# Англоязычные термины
# Заменить дефисы на тире
# Оформить правильно источники информации
# Добавить жизненное применение матриц перестановок, если возможно (примеры решения каких-нибудь задач)
<li> ''fixed'' [[Задача о минимуме/максимуме скалярного произведения]] (2) </li>
# Оформить задачу шаблоном Задача
# Ссылку в примечании сделать на самом деле примечанием
# Оформить правильно источники информации
# Доказательство плохо разбито на пункты {{---}} от нумерации в доказательстве вообще можно избавиться
<li> ''fixed'' [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] (0.5) </li>
# Англоязычные термины
# Определение взять в шаблон
== 7. Динамическое программирование ==
:0. '''!!!fixed''' [[Динамическое программирование]] (5)
:# Добавить известную цитату про ДП
:# Интервики на NP-полноту
# [[Задача о наибольшей общей подпоследовательности]]
# [[Задача о наибольшей возрастающей подпоследовательности]]
# '''взяли''' [[Задача коммивояжера, ДП по подмножествам]]
# [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
# '''!!!''' [[Задача о рюкзаке]] (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>
# Отформатировать псевдокод
# Добавить примеры задач
<li> [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]] </li>
<li> [[Задача о наибольшей подпоследовательности-палиндроме]] </li>
<li> ''fixed'' [[Наибольшая общая возрастающая подпоследовательность]] (2) </li>
# Переименовать в "Задача о ..."
# Отформатировать псевдокоды
# Оформить правильно источники информации
# Добавить нормальное объяснение происходящего (и почему это работает)
<li> '''!!!fixed''' [[Динамика по поддеревьям|Динамика по поддеревьям, задача о паросочетании максимального веса в дереве]] (5) </li>
# Взять все переменные в Tex
# Убрать определение паросочетания
</ol>
== 8. Теория вероятностей (проверяется) ==# [[Вероятностное пространство, элементарный исход, событие]](1)
## Англоязычные термины
## Заменить дефисы на тире
## Убрать точки с запятой из определений
## Оформить правильно см. также и источники информации
## Правильно оформить дроби# [[Независимые события]](1.5)
## Оформить правильно англоязычные термины
## Тире в шаблон, переменные и константы в Tex
## Пример несовместных событий
## Определения выделить жирным
## Заменить все дроби на \genfracdfrac
## Оформить правильно источники информации
## Пример Тетраэдра оформить нормально
# [[Условная вероятность]](0.5)
## Англоязычные термины правильно оформить
## Увеличить дроби
## Переменные и константы взять в Tex
## Оформить правильно источники информации
# [[Формула полной вероятности]]## примеры перечислить как подразделы # '''fixed''' [[Формула Байеса]]## Англоязычные термины## Добавить словесное описание использование формулы перед определением## Дроби взять в \genfrac## Все переменные и константы обернуть в Tex## Добавить пример с неинтуитивным пониманием формулы Байеса {{---}} тест на болезнь даёт правильный ответ с вероятностью 95%, человек получил положительный результат, с какой вероятностью он болен, если этим заболеванием болеет 1% населения?## Кинуть ссылку на Байесовский классификатор спама## Оформить правильно см. также и источники информации# '''!!!''' [[Дискретная случайная величина]](3)
## Англоязычные термины
## Примеры
## Исправить знаки неравенств
## Оформить правильно источники информации, См. также, списки, вообще всё
## Добавить про функцию плотности вероятности
# [[Независимые случайные величины]](1)
## Англоязычные термины
## Заменить ссылку примечанием на интервики
## Заменить дефисы на тире, переменные и константы взять в Tex
## Правильно оформить источники информации
# '''fixed''' [[Математическое ожидание случайной величины]](2)## Англоязычные термины Оформить правильно оформитьСм. также## Заменить дефисы дроби на тире## Дроби оформить как \genfrac## Сделать нормальный список в линейности математического ожиданияdfrac## Переменные и константы взять в TexДоказать содержательные утверждения## Источники информации, см. также## Добавить свойств и матожиданий других распределений# '''!!!''' [[Дисперсия случайной величины]]## Англоязычные термины## Дефисы на тире, дроби в \genfrac## Убрать ; в свойствах## Если легко показать, то надо показать## Добавить про центральные моменты
# [[Ковариация случайных величин]]
# [[Корреляция случайных величин]]
## воообще говоря, это не свойства энтропии, а аксиомы, так что надо и написать, что аксиомы, наверное.
## В Романовском добавить издание и страницу, источники информации правильно оформить
## Убрать треугольники из свойств
## Исправить знаки неравенств
## Оформить по правилам# '''!!!''' [[Симуляция одним распределением другого]](7)
## так и нет нормального определения распределения
## список примеров распределений есть, а самих распределений нет; надо дать описание и кинуть формулы
## Увеличить дроби
# [[Арифметическое кодирование]]
## раздел "определение" не нужен, перенести в заголовок## Оформить правильно англоязычные термины## Отформатировать псевдокод## Заменить дефисы на тире## Оформить правильно источники информации# '''fixed''' [[Парадоксы теории вероятностей]]## "Пусть 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)
## Отформатировать псевдокод
## Заменить литературу на источники информации
## Оформить по правилам
