Викиконспекты - Вклад участника [ru]

Дискретная математика и алгоритмы

2010-12-17T02:47:58Z

Elena Podgornova:

== Отношения ==
*Определение отношения
*Степень отношений
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Примеры булевых функций|Примеры булевых функций: все функции от нуля, одной и двух переменных]]
*[[Подстановка одной функции в другую, отождествление переменных]]
*[[Представление функции формулой, полные системы функций]]
*[[СДНФ]]
*[[СКНФ]]
*[[Полином Жегалкина]]
*[[Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Изменение размера оптимальной схемы при переходе к другому базису]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]
*[[Алгоритм Хаффмана]]

== Алгоритмы сжатия ==
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]

== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера об объекту и объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Цепные коды]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Поиск наибольшей возрастающей подпоследовательности и т. д.]]

== Динамическое программирование ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о перемножении матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]

== Теория вероятности ==
*[[Независимые события]]
*[[Формула Байеса]]
*[[Дискретная случайная величина]]
*[[Условная вероятность]]
*[[Формула полной вероятности]]
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Линейность математического ожидания]]

Независимые события

2010-12-17T02:46:32Z

Elena Podgornova: Новая страница: «{{Определение |definition = Два события A и B называются независимыми, если <tex> p(A \cap B) = p(A)p(B) </tex> }} …»

{{Определение
|definition =
Два события A и B называются независимыми, если <tex> p(A \cap B) = p(A)p(B) </tex>
}}

Примеры:
*Игральная кость
<tex> A = \{2,4,6\}\ p(A)=\frac{1}{2} </tex> - вероятность выпадения чётной цифры

<tex> B=\{1,2,3\}\ p(B)=\frac{1}{2} </tex> - вероятность выпадения одной из первых трёх цифр

<tex> p(A \cap B)=p(\{2\})=\frac{1}{6}</tex>

<tex>p(A)p(B)=\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}</tex>

Получаем, что <tex>p(A \cap B) \neq p(A)p(B)</tex>, значит эти события не независимы.
*Карты
<tex> A = \{(1,j)\}\ p(A)=\frac{1}{4} </tex> - вероятность выпадения карты заданной масти

<tex> B=\{(i,1)\}\ p(B)=\frac{1}{13} </tex> - вероятность выпадения карты заданного достоинства

<tex> p(A \cap B)=p(\{(1,1)\})=\frac{1}{52}</tex> - вероятность выпадения карты заданной масти и заданного достоинства

<tex>p(A)p(B)=\frac{1}{4}\cdot\frac{1}{13}=\frac{1}{52}</tex>

Получаем, что <tex>p(A \cap B)=p(A)p(B)</tex>, значит эти события независимы.

КНФ

2010-12-17T01:49:06Z

Elena Podgornova:

{{Определение
|definition =
КНФ (Конъюнктивная Нормальная Форма) — нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y) = (x \lor y) \land (y \lor \overline{z})</tex>

{{Определение
|definition =
СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждый из аргументов функции.
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \overline{y} \lor z) \land (x\lor y \lor \overline{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\overline{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\overline{f}(\vec x)</tex> можно записать следующим образом:
<tex> \overline{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \overline{\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})} </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\overline{\sigma_{1}}} \vee x_{2}^{\overline{\sigma_{2}}} \vee ... \vee x_{n}^{\overline{\sigma_{n}}}) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
}}
==Алгоритм построения СКНФ по таблице истинности==
*В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
*В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
*Полученные дизъюнкции связываем операциями конъюнкции

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})</tex>

Медиана трёх: <tex>f(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})</tex>