- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
Пусть задано конечное множествомощности. Обозначим черезмножество всех- элементных подмножеств множества.
Теорема: Число всех - элементных подмножеств множества вычисляется по формуле
Доказательство:Будем строить- элементные подмножества множествадействием из двух этапов. На первом этапе построим- элементное подмножество, тогда число способов осуществления первого этапа будет равно. На втором этапе к полученному- элементному подмножеству присоединим один изэлементов множества, которые не входят в это подмножество; ясно, что. Значит, согласно принципу умножения, в результате описанного действия получим- элементных подмножеств. Но не все они будут разными, так как каждое- элементное подмножество можно так построитьспособами: присоединением каждого изего элементов к остальнымего элементам. Поэтому найденное число враз больше, чем число- элементных подмножеств множества. Следовательно,Отсюда находим
Но число одноэлементных подмножеств множества равнот.е.. Следовательно,
Теорема доказана.
Определение:Произвольное- элементное подмножество множества изэлементов в комбинаторике называетсясочетаниемизэлементов поэлементов. Порядок элементов в подмножестве не имеет значения, поэтому часто вместо слова «сочетание» употребляется терминкомбинацияили соединение изэлементов поэлементов, которые отличаются, по крайней мере одним элементом, но не порядком элементов.
Пример 4.1:Сколькими способами из 7 человек можно выбрать комиссию, состоящую из 3 человек?
Решение:Чтобы определить все возможные комиссии, нужно рассмотреть все возможные трёхэлементные подмножества множества, состоящего из семи элементов. Следовательно, искомое число способов равно
Пример 4.2:Рассмотрим на плоскости с декартовой прямоугольной системой координат «шахматный город», состоящий изпрямоугольных кварталов, границами которых являются частигоризонтальных ивертикальных улиц. Требуется определить число различных кратчайших путей в пределах этого города, ведущих из левого нижнего угла (точки) в правый верхний угол (точку).
Решение:Каждый кратчайший путь из точкив точкусостоит изотрезков, причём среди них естьгоризонтальных ивертикальных отрезков. Разные пути отличаются лишь порядком чередования горизонтальных и вертикальных отрезков. Поэтому искомое число путей равно числу способов, которыми изотрезков можно выбратьотрезков, т.е.или числу способов, которыми изотрезков можно выбратьотрезков, т.е.. Итак, число кратчайших путей равно
Замечание:Заметим, что полученное равенство установлено при решении геометрической задачи. Заметим так же, что рассмотренный пример даёт интересную геометрическую интерпретацию для чисел.
Определение:Сочетаниями с повторениями, содержащимиэлементов, выбранных изэлементов заданного множества, называются всевозможные множества изэлементов, отличающиеся хоть одним элементов (порядок не учитывается), при этом допускается неединичное вхождение элементов. Обозначаем.
Теорема: Число
Доказательство:Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора. Нам не важен порядок номеров элементов множества, то есть мы учитываем только, сколько раз в нашем наборе изэлементов появился элемент номер 1, элемент номер 2, … , элемент номер. То есть результат выбора можно представить набором чисел, в котором– число появлений элемента номерв выборке, и. При этом два результата эксперимента различны, если соответствующие им наборыне совпадают.
Представим себе другой эксперимент, имеющий точно такие же результаты (и, следовательно, их столько же). Есть ящиков, в которых размещаетсяшариков. Нас интересует только количество шариков в каждом ящике. То есть, результатом эксперимента снова является набор чисел, в котором– число шариков в ящике с номером, и. Числапо-прежнему принимают натуральные значения или равны 0.
Атеперь изобразим результат такого размещения в виде схемы, в которой вертикальные линии обозначают перегородки между ящиками, а кружки – находящиеся в ящиках шарики:
Мы видим результат размещения 9 шариков по 7 ящикам. Здесь 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках есть по 2 шарика. Переложим один шарик из первого ящика во второй и изобразим таким же образом ещё один результат размещения:
И ещё один:
Видим, что все размещения можно получить, меняя между собой шарики и перегородки, или расставляяшариков наместе. Числополучается так: уящиков есть ровноперегородка, считая крайние, илиперегородка, если не считать крайние, которые двигать нельзя. И естьшариков. Перебрав все возможные способы расставитьшариков на этихместах (и ставя на оставшиеся места перегородки), переберём все нужные размещения.
Но способов расставить шариков наместах ровно– это в точности число способов выбрать изномеров местномеров мест, на которые нужно поместить шарики. Заметим, что равенствоверно в силу того, что можно вместо выборамест для шариков выбиратьместо для перегородок ящиков, заполняя шариками оставшиеся места.