- •Обобщённый алгоритм Евклида
- •Второй способ нахождения линейного представления наибольшего общего делителя
- •Линейные диофантовы уравнения с двумя неизвестными
- •Решение уравнений в кольце остатков по данному модулю
- •Китайская теорема об остатках (теория)
- •Непрерывные дроби и перевод рационального числа в конечную дробь
- •Наилучшие приближения
- •Разбор типовых примеров к первому индивидуальному домашнему заданию по теме «Делимость целых чисел и многочленов»
- •Правило сложения
- •Перестановки
- •Треугольник Паскаля
- •Серия задач по комбинаторике на различные методы решения
- •Определение
- •Упражнение 1. Приведите пример двудольного графа с 6 вершинами. Упражнение 2. Докажите признаки двудольных графов:
- •Булевы функции
- •Многочлен Жегалкина
- •Двойственная функция
- •Нахождение таблицы значений функции, двойственной к данной булевой функции
- •Исследование булевой функции на принадлежность к основным классам замкнутости
- •Применение теоремы Пóста
- •Представление конъюнкции и отрицания через данную функцию f (X, y, z) и её отрицание
Треугольник Паскаля
Рассмотрим задачу, сочетающую правило сложения и нахождение числа сочетаний. Вывести рекуррентную формулу для подсчета биномиальных коэффициентов.
Выделим из n элементов один и разобьем все k-элементные подмножества на два класса:
- содержащие выделенный элемент и
- не содержащие его.
Первых будет , так как один элемент уже выбран, и из оставшихся n-1 элементов надо выбрать еще k-1 элемент.
Вторых будет , так как один элемент запрещается выбирать, и надо выбрать все k элементов из оставшихся n-1.
Так как любое подмножество (сочетание) принадлежит либо одному, либо другому классу и классы не пересекаются, получаем рекуррентную формулу:
Процесс вычислений по этому рекуррентному соотношению можно представить в виде пирамиды, которая называется треугольником Паскаля:
В этом треугольнике каждое число по выведенной рекуррентной формуле есть сумма двух, стоящих над ним, а по границам треугольника стоят единицы.
1
-
1
1 2 1
1 3 3 1
1 4 6 4 1
………………..
Например, (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4.
Серия задач по комбинаторике на различные методы решения
1. При одном бросании монеты возможно 2 исхода: орел или решка. Сколько исходов возможно при 5 бросаниях монеты?
2. На конференции каждый из 30 участником обменялся рукопожатием со всеми остальными. Сколько было сделано рукопожатий?
3. Сколько диагоналей в 100-угольнике?
4. Сколько делителей у числа ?
5. Сколькими нулями оканчивается число 100!? (имеется в виду факториал).
6. Сколькими способами можно выбрать 3 дежурных в классе из 25 человек?
7. На сколько частей делят плоскость 20 прямых, никакие две из которых не параллельны и никакие три не пересекаются в одной точке?
8. На какое наибольшее количество частей можно разделить круг n прямыми?
9. На какое наименьшее число прямых можно разделить круг n прямыми?
10. Сколько вариантов трехцветного флага из трех горизонтальных полос можно составить, если имеется выбор из шести цветов материи?
11. Пять писем разложены по пяти конвертам, по одному в каждом. Сколько способов разложить их так, чтобы ровно два письма попали не в тот конверт?
12. Сколько способов разложить их так, чтобы ровно одно письмо попало не в тот конверт?
13. Есть 10 школьников: 5 мальчиков и 5 девочек. Сколько способов рассадить их на 10 стульев, стоящих в ряд, чтобы мальчики чередовались с девочками?
14. Сколько существует шестизначных чисел, в записи которых все цифры нечетны?
15. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра?
Ответы к серии задач на различные сюжеты.
1. .
2. .
3.
4. делителей.
5. 24.
6. .
7. 211.
8. .
9. Ответ: n + 1.
10. .
11. .
12. Ни одного способа.
13. .
14. .
15. .
Материалы для семинаров
(Задача 6 – это ознакомительный материал!)
ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ
В задаче номер 4 решение аналогично решению для систем счисления (вспомните тему «Целые числа»!), а в задаче номер 3 надо воспользоваться правилом произведения, а в некоторых случаях – и правилом перехода к дополнению.
Графы (ДОПОЛНИТЕЛЬНЫЙ МАТЕРИАЛ)
Определение
Граф — это совокупность непустого множества вершин и множества пар его вершин.
Обычно связи между вершинами представляют как дуги, соединяющие эти вершины.
Граф называют ориентированным, если отмечено направление всех дуг (от одной вершины к другой).
Граф называют планарным, если можно изобразить его на плоскости.
Пример.
Квадрат с диагоналями является планарным графом (проверьте!). А пятиугольник с диагоналями не является планарным графом.
Деревья *
Дерево или древовидный граф – это связный граф без циклов.
Такое название дано потому, что любой древовидный граф можно нарисовать так, что он будет похож на дерево-растение. На таком изображении видны «корень» и «ветви». Листьями в дереве называются вершины, соединённые с графом только одной дугой.
В деревьях число вершин всегда на единицу меньше числа дуг. В самом деле, если мы будем отстригать от дерева листья вместе с дугами, на которых они висят, то разность между числом вершин и числом дуг меняться не будет. В конце стрижки останется одинокая вершина. Следовательно, эта разность равна единице.
В ориентированном дереве, в котором дуги идут от корня к ветвям, выходящие дуги связывают родительскую вершину с дочерними, а входящие – с родительскими.
Особую популярность имеют двоичные деревья, в которых у каждой вершины может быть не более двух детей – правая ветвь и левая. Информацию об этом дереве можно хранить, например, так: каждая вершина содержит ссылку на своих детей и своего родителя.
Применение древовидных графов.
1. Древовидная файловая система, или дерево директорий.
2. Дерево поиска, при котором все потомки с левой стороны всегда меньше родителя, а в правом не меньше.
3. Дерево для вычисления математических формул – например, префиксной и постфиксной формы записи.
Задачи по теме «Деревья»
1. Какое максимальное количество листьев может быть у дерева из n вершин? А минимальное?
2. Могут ли в дереве две вершины соединяться двумя различными путями?
3. Существует ли дерево, у которого одна вершина является и листом, и корнем?
4. Докажите, что в ориентированном дереве у каждой вершины не более одного родителя.
Связные графы
Определение
Если из каждой вершины можно попасть в каждую, то граф отношения называют связным.
Подмножество графа, в котором из каждой вершины можно попасть в каждую, называют компонентой связности.
Из определения можно увидеть, что если граф состоит из одной компоненты связности, он называется связным. Если из более чем одной компоненты связности, он называется несвязным.
Двудольные графы