Обсуждение:Дискретная математика и алгоритмы

Требования к написанию вики-конспектов 1 курса.

Главное

• Внимательно читайте свои конспекты перед тем, как совершать попытку их сдачи.
• Перед отправкой на проверку перечитайте эти требования.
• В конспекте не должно быть недочетов, связанных с требованиями.

Общение с редакторами

• Список занятых конспектов
• Будет лучше, если вы зарегистрируетесь на сайте вики-конспектов и напишете в информации о себе имя, фамилию и группу.
• Не забывайте сообщать редакторам о том, что конспект нужно проверить.
• При общении с редактором, представляйтесь и давайте ссылку на конспект, который вы пишете. При использовании электронной почты в теме письма указывайте “Вики-конспекты: Название вики-конспекта”. Отсутствие словосочетания "Вики-конспекты" может сказаться на времени проверки конспекта.
• Ставить замечания к конспекту может не только ваш куратор конспекта, в том числе и после принятия конспекта. Их тоже надо учитывать.
• Не помечайте замечания, эти метки — для кураторов конспектов.

Викификация

1. Смотрите в качестве примера на конспекты, которые отмечены как хорошие.
2. В конспекте не должно быть орфографических, пунктуационных, речевых, фактических, логических и других ошибок. Используйте spell checker.
3. Используйте вики-шаблоны Шаблон: Определение, Шаблон: Теорема, Шаблон: Лемма, Шаблон: Утверждение (Справка по шаблонам).
4. Приводите английские названия терминов, теорем, имен алгоритмов и т.д. Их лучше писать в скобках курсивом после их русских названий.
5. Вместо черточки “-” используйте тире “—”. Для этого можно использовать Шаблон:---. Про правила использования читать здесь
6. Редактировать можно не только свои конспекты — используйте “концепцию вики”
7. Не используйте тег <br> . Для перевода строки в вики надо вставлять пустую строку. Видимо, единственное место, где можно использовать его — внутри шаблонов — там переводы строки почему-то не работают.
8. Ставьте категорию [[Категория: Дискретная математика и алгоритмы]] и подкатегорию с названием подтемы (например, [[Категория: Динамическое программирование]]). Список подкатегорий тут.
9. Оформляйте ссылки на источники правильно. Пример хорошего оформления — конспекты Алгоритм Хаффмана и Сокращенная и минимальная ДНФ.
10. Не используйте сокращения.

Картинки

• Картинки, где только возможно, надо делать в векторе.

Источники

1. Используйте ссылки на другие конспекты.
2. В конспекте должны быть указаны источники или литература. Причем указывать ссылки не просто на википедию, а на конкретную статью (как Википедия — Экспоненциальная запись, на английскую — как Wikipedia — Scientific notation). Для книг достаточно указать автора, название, издание и номер страницы.
3. Нарушения авторского права недопустимы.

TeX

Вот тут хорошая справка по использованию TeX

1. Использование тега <tex> вместо <math> обязательно. Везде.
2. По согласованию с куратором: если лень постоянно писать <tex> </tex> , можно обернуть всю статью в <wikitex> </wikitex> , а потом обособлять формулы в $ $(например, <wikitex> Для любого $ \alpha $ верно $\sin^2 \alpha + \cos^2 \alpha = 1 $ </wikitex> ), но лучше так не делать. В частности, проблемы возникают если внутри тега wikitex находится несколько заголовков — ломается их редактирование по отдельности.
3. Формулы с дробями нужно увеличивать для повышения читаемости, особенно, если их много в конспекте. Для этого используйте параметр dpi в теге tex. Пример: <tex dpi = "180">\frac {\omega_n(x)} {(x - x_j) \cdot \omega_n'(x_j)}</tex>
4. В качестве знака умножения нужно использовать \times или \cdot, а не звездочку. Сравните: [math]2 * 2 = 2 \times 2 = 2 \cdot 2 = 4[/math].
5. Не опускайте знаки умножения и конъюнкции, если это может привести к неоднозначности.

Псевдокод

(правила, в основном, отсюда Участник: Kirelagin/Оформление#Псевдокод)

1. Используйте максимально компактный и читаемый псевдокод.
2. Не ставьте фигурные скобки. Угадайте, для чего они нужны? Чтобы парсер языка было легче писать. Человеку они только мешают. Используйте отступы для группировки. (Python-style)
3. Не ставьте круглые скобки вокруг внешнего условия if'а, while'а и т.п.
4. Обозначайте присвоение нормально, с помощью знака «=», а сравнение как «==» (всё равно придётся слезать с паскаля).
5. Не вводите какие-то левые операторы. Например, если кладёте что-то в очередь, так и напишите: q.push(a).
6. TeX в псевдокоде можно использовать только в случае какого-то нестандартного оператора(а перед этим хорошо подумать и посмотреть предыдущий пункт)
7. Не надо описывать ввод данных и вывод данных. Оформляйте псевдокод как функцию, принимающую входные данные и возвращающую результат.
8. Обычные правила хорошего кода:
   • Ставим пробелы между операндами и бинарными операторами(«1 + 2», а не «1+2»). После унарных операторов перед операндом пробел ставить не нужно.
   • Не ставим пробел перед скобкой - вызовом функции(«f(x)», а не «f (x)»)
   • Пробел после запятой, разделяющей аргументы функции
   • Используем какой-то определённый стиль именования переменных(я бы рекомендовал lowerCamelCase для переменных и функций и UpperCamelCase для классов)

correlation coefficient

Теорема:

[math]Cov^2(\eta, \xi) \le \sigma_\eta ^2\sigma_\xi ^2[/math] (где[math]\sigma[/math] — среднеквадратическое отклонение)

Доказательство:

[math]\triangleright[/math]

Для этого предположим, что [math] t [/math] некоторое вещественное число, которое мы выберем позже, и рассмотреть очевидное неравенство [math] E((V+tW)^2) \ge 0 [/math], где [math] V = \eta - E\eta [/math] и [math] W = \xi - E\xi [/math]. Используя линейность математического ожидание, мы получим эту неравенству [math] E(V^2)+2tE(VW)+t^2E(W^2) \ge 0 [/math] Обратите внимание, что левая часть квадратный трехчлен зависимо на [math] t [/math]. Мы имеем [math] E(V^2)=\sigma_\eta ^2[/math], [math] E(W^2)=\sigma_\xi ^2[/math] и [math] E(VW)=Cov(\eta,\xi); [/math] И так, наш квадратный трехчлен выглядит так [math]\sigma_\xi ^2t^2+2Cov(\eta,\xi)t+\sigma_\eta ^2 \ge 0[/math] Из этого неравенства мы видим, что единственный способ левой стороне может быть 0 , если многочлен имеет двойной корень (т.е. это касается оси [math]x[/math] в одном точкe), которая могла произойти только если дискриминант равен 0. Таким образом, дискриминант всегда должен быть отрицательным или 0, что означает [math] 4Cov^2(\eta,\xi)-4\sigma_\eta ^2\sigma_\xi ^2 \le 0[/math] [math]Cov^2(\eta,\xi) \le \sigma_\eta ^2\sigma_\xi ^2[/math] что и нужно было доказывать.

[math]\triangleleft[/math]