Правило умножения и сложения.

Элементы комбинаторики.

Комбинаторика - раздел математики, в котором изучают задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: "Сколькими способами?"

Правило умножения и сложения.

Правило умножения — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Естественным образом обобщается на произвольную длину последовательности. Правило сложения — одно из основных правил комбинаторики, утверждающее, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.

 

Размещения, перестановки, сочетания.

Размещение. В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n -элементного множества.

Например, — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.

Перестановки. В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i -й элемент из набора. Число n при этом называется порядком перестановки.

Сочетания.

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-элементные сочетания, подмножества, k = 3) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (n = 6) являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

 

Бином Ньютона.

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

,

где — биномиальные коэффициенты, n — неотрицательное целое число.

Булевы функции. Определение.

.Бу́лева фу́нкция от n переменных — в отображение Bⁿ и B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения Bⁿ называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается P ₂, а от n переменных — P ₂(n). Булевы функции названы так по фамилии математика Джорджа Буля. Если n=1, то существует 4 простейших булевых функции: константа тождественная 0, константа тождественная 1, тождественная функция, отрицание.

Реализация булевых функций

1)отрицание, 2)конъюнкция 3)дизъюнкция 4)импликация 5)отрицание импликации 6) эквиваленция 7)стрелка пирса 8)штрих Шеффера

СКНФ.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке.

СДНФ

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .

8. Переключательные функции. Способы задания.

Основные переключательные функции заложил Дж. Буль.

Переключательную функцию можно задать аналитически, геометрически. Атак же ее можно задать матричным способом и с помощью логической схемы системы.

Граф

Граф или неориентированный граф G — это упорядоченная пара G: = (V, E), для которой выполнены следующие условия:

§ V это непустое множество вершин или узлов,

§ E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

V обычно считаются конечными множествами. Виды графов:1)ориентированный;2)неоринтированный;3)смешанный;4)мультиграф;

Изоморфи́зм — это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: Пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.).Биекция между ними называется изоморфизмом, если она сохраняет эту структуру. Если между такими множествами существует изоморфизм, то они называются изоморфными.

16.

Матрица смежности - Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Матрица инцидентности - Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i -ой строки с j -м столбцом матрицы записывается:

в случае, если связь j «выходит» из вершины i,

−1,

если связь «входит» в вершину,

во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален | E | | V |) для хранения, но облегчает нахождение циклов в графе.

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер. Теорема Понтрягина—Куратовского

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу из пяти вершин (K ₅) или графу «домики и колодцы» (K _3,3).

 

20. Формула Эйлера утверждает, что для любого вещественного числа x выполнено следующее равенство:

,

где e — основание натурального логарифма,

i — мнимая единица.

21.

Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

Иначе говоря, показать, что хроматическое число плоского графа не превосходит 4.

23. Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

24. Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

25. Алгори́тм Де́йкстры (Dijkstra’s algorithm) —алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёберотрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

Понятие потока в сети.

Ориентированный граф называется сетью, если он удовлетворяет следующим условиям:1) он связный граф без петель 2) существует ровно одна вершина, степень входа равна нулю(источник) 3) существует ровно одна вершина, степень входа равна нулю(сток) 4) каждой дуге поставлено в соответствие неотрицательное число, называемое пропускной способностью.

Элементы комбинаторики.

Комбинаторика - раздел математики, в котором изучают задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: "Сколькими способами?"

Правило умножения и сложения.

Правило умножения — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Естественным образом обобщается на произвольную длину последовательности. Правило сложения — одно из основных правил комбинаторики, утверждающее, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.