- •Множество. Способы задания множеств (перечислением или списком, порождающей процедурой, описанием характеристического свойства). Привести примеры.
- •Алгебра множеств. Законы алгебры множеств. Доказать один из законов алгебры множеств.
- •Множество. Мощность множества. Нахождение мощности объединения множеств (для двух множеств, для трех множеств, для n-множеств). Привести пример.
- •Векторы. Прямое произведение множеств. Мощности прямого произведения множеств.
- •Отношения. Основные понятия отношений (отношения; унарные, бинарные, n-местные отношения)
- •Отношения. Бинарные отношения. Основные понятия (определение, обозначения, область определения, область значений, способы задания бинарных отношений). Привести примеры.
- •Отношения. Эквивалентность и порядок. Сравнимость элементов множества по отношению порядка.
- •Соответствия. Функции и отображения. Способы задания функций. Привести примеры.
- •Комбинаторика. Основные задачи комбинаторики. История возникновения комбинаторики.
- •Комбинаторика. Основные правила комбинаторики (правило суммы и правило произведения).
- •Комбинаторика. Упорядоченные и неупорядоченные выборки (множества). Понятие выборки (с повторением и без повторения, упорядоченные и неупорядоченные). Привести примеры.
- •Комбинаторика. Размещение без повторения. Перестановки без повторений. Размещение с повторениями. Привести примеры.
- •Комбинаторика. Сочетания без повторений и с повторениями. Свойства сочетаний. Доказать одно из них. Привести примеры.
- •Комбинаторика. Перестановки с повторениями. Циклические перестановки. Подсчет числа беспорядков. Привести примеры.
- •Комбинаторика. Формула включения-исключения.
- •Рекуррентные соотношения. Метод рекуррентных соотношений. Числа Фибоначчи (задача приводящая к числам Фибоначчи).
- •Рекуррентные соотношения. Порядок рекуррентного соотношения. Решение и общее решение рекуррентного соотношения. Привести примеры.
- •Рекуррентные соотношения. Линейные рекуррентные соотношения с постоянными коэффициентами. Два утверждения на которых основывается решение линейных рекуррентных соотношений.
- •Общее решение линейных рекуррентных соотношений второго порядка с постоянными коэффициентами (случай одинаковых корней характеристического уравнения). Привести примеры.
- •Общее решение линейных рекуррентных соотношений с постоянными коэффициентами, порядок которых выше второго. Привести примеры.
- •Решение рекуррентных соотношений, используя производящую функцию. Понятие производящей функции. Алгоритм решения рекуррентных соотношений с помощью производящих функций.
- •Булевы функции от одного аргумента. (Определение. Все булевы функции от одного аргумента).
- •Булевы функции от двух аргументов (Определение булевой функции двух аргументов, тождественный ноль, тождественная единица, конъюнкция, штрих Шеффера, дизъюнкция, стрелка Пирса (функция Вебба)).
- •Свойства дизъюнкции, конъюнкции и отрицания (теорема 4.3).
- •Свойства эквиваленции, импликации и отрицания (теорема 4.4).
- •Выражение одних булевых функций через другие (теорема 4.5).
- •Булевы функции от n аргументов (определение, равенство булевых функций, суперпозиция булевых функций).
- •Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.
- •Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.
- •Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.
- •Графы. Матрицы связности. Утверждение о матрицах связности, матрицы достижимости, матрицы сильной связности.
- •Графы. Выделение компонент связности. Алгоритм нахождения числа компонент сильной связности и матрицы смежности этих компонент.
- •Графы. Поиск путей (маршрутов) с минимальным числом дуг (ребер). Алгоритм фронта волны.
- •Графы. Минимальные пути (маршруты) в нагруженных орграфах (графах). Алгоритм Форда-Беллмана.
- •Графы. Деревья и циклы.
- •Графы. Эйлеровы цепи и циклы.
Соответствия. Функции и отображения. Способы задания функций. Привести примеры.
Соответствие - способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями). Частными случаями соответствий являются функции, отображения, преобразования, операция и др. В соответствии между множествами А и В называется подмножество G: GcAxB;
Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип А®В (обозначается f: А ® В). Каждому элементу а из области определения функция f ставит в соответствие элемент b из области значений. Это обозначается f(а) = b. Элемент а - аргумент функции, элемент b - значение функции на а.
Отображением А в В называется всюду определенная функция f: А ® В. Отображением А на В называется всюду определенное и при этом сюръективное функциональное соответствие f: A ® B.
Способы задания функции:
• графиком;
• таблицей;
• формулой, описывающей функцию как суперпозицию других (исходных) функций;
• рекурсивной вычислительной процедурой.
Например, функция f(x) = 1 × 2 × 3 ×... × (х-1) × х = х! описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами:
1) f(0) = 1; 2) f(х+1) = f(х) × (x+1).
Соответствия. Операции (понятие, бинарные, бинарные операции). Свойства бинарных операций и(ассоциативность, коммутативность, дистрибутивность). Способы задания операций унарных операций (перечень всех аргументов, список всех пар, формула). Способы задания бинарных операций (Таблица Кэли, список всех троек, формулой). Привести примеры.
Соответствие - способ задания взаимосвязей, взаимодействий между элементами множества (наряду с отношениями). Частными случаями соответствий являются функции, отображения, преобразования, операция и др. В соответствии между множествами А и В называется подмножество G: G c A x B;
Операции – функция, все аргументы значения которой принадлежат одному и тому же множеству.
Функция одного аргументаf(x)=y, имеющая тип M – >M называется унарной операцией.
Функция двух аргументов f(x,y)=z, f: M x M – >M бинарные операции.
Дистрибути́вность — свойство согласованности двух бинарных операций, определённых на одном и том же множестве.
Говорят, что две бинарные операции + и × удовлетворяют свойству дистрибутивности, если для любых трех элементов :
— дистрибутивность слева;
— дистрибутивность справа.
Если операция × является коммутативной, то свойства дистрибутивности слева и справа совпадают.
Ассоциативность — свойство любой операции , такое что для неё выполняется равенство:
для любых элементов .
Например, для умножения: .
Коммутативная операция — это бинарная операция , обладающая коммутативностью (от позднелат. commutativus — «меняющийся»), то есть переместительностью:
для любых элементов .
Комбинаторика. Основные задачи комбинаторики. История возникновения комбинаторики.
Комбинато́рика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).
Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр
(Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI—XVII вв.). Следующий этап развития теории вероятностей связан с именем Якоба
Бернулли (1654—1705). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др. Новый, наиболее плодотворный период связан с именами П. Л. Чебышева (1821—1894) и его учеников А.А.Маркова(1856—1922) и А. М.Ляпунова (1857—1918). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математикам (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским математикам.
Основные комбинаторные задачи.
Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:
1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, -
составление перестановок;
2) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний;
3) образование упорядоченных подмножеств - составление размещений.