Скачать 249.94 Kb.
|
ДИСКРЕТНАЯ МАТЕМАТИКА КОМБИНАТОРНЫЕ ОБЪЕКТЫ. СОЧЕТАНИЯ, РАЗБИЕНИЯ, ПЕРЕСТАНОВКИ В разделе математики, который называется комбинаторикой, решаются некоторые задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. Например, если взять 10 различных цифр 0, 1, 2, 3, … , 9 и составлять из них комбинации, то будем получать различные числа, например, 345, 534, 1036, 5671, 45 и т.п. Мы видим, что некоторые из таких комбинаций отличаются только порядком цифр (например, 345 и 534), другие – входящими в них цифрами (например, 1036 и 5671), третьи различаются и числом цифр (например, 345 и 45). Т.о., полученные комбинации удовлетворяют различным условиям. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания. ^ Произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут n! = 1*2*3*…*(n-1)*n. Перестановки Пусть даны три буквы A, B, C. Составим все возможные комбинации из этих букв: ABC; ACB; BCA; CAB; CBA; BAC (всего комбинаций). Мы видим, что они отличаются друг от друга только порядком расположения букв. Комбинации из n элементов, которые отличаются друг от друга только порядком элементов, называются перестановками. Комбинации обозначаются символом Pn, где n – число элементов, входящих в каждую перестановку. Число перестановок можно вычислить по формуле ^ Размещения Пусть имеются четыре буквы A, B, C, D. Составив все комбинации только из двух букв, получим: AB, AC, AD; BA, BC, BD; CA, CB, CD; DA, DB, DC. Мы видим, что все полученные комбинации отличаются или буквами или их порядком (комбинации BA и AB считаются различными). Комбинации из m элементов по n элементов, которые отличаются друг от друга или самими элементами или порядком элементов, называются размещениями. Размещения обозначаются символом Amn, где m – число всех имеющихся элементов, n – число элементов в каждой комбинации. При этом полагают, что n ≤ m. Число размещения можно вычислить по формуле ![]() т.е. число всех возможных размещений из m элементов по n равно произведению n последовательных целых чисел, из которых большее есть m. При нахождении числа размещений мы перемножаем n последовательно убывающих целых чисел, т.е. до полного факториала не хватает (m-n) последовательно убывающих целых множителей. Поэтому формулу числа размещений можно записать в виде ![]() ![]() Сочетаниями называются все возможные комбинации из m элементов по n, которые отличаются друг от друга по крайней мере хотя бы одним элементом (здесь m и n – натуральные числа, причем n ≤ m). Так, из четырех различных букв A, B, C, D можно составить следующие комбинации, отличающиеся друг от друга хотя бы одним элементом: AB, AC, AD, BC, BD, CD. Значит, число сочетаний из четырех элементов по два равно 6. Это кратко записывается так: C42=6. В каждой комбинации сделаем перестановки элементов: AB, AC, AD, BC, BD, CD; BA, CA, DA, CB, DB, DC. В результате мы получили размещения из четырех элементов по два. ![]() В общем случае число сочетаний из m элементов по n равно числу размещений из m элементов по n, деленному на число перестановок из n элементов: ![]() Используя для чисел размещений и перестановок факториальные формулы, получим формулу числа размещений в виде: ![]() МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ ^ Существует 2 графических способа задания ФАЛ: 1 ![]() Кружками обозначены наборы значений букв, при которых ФАЛ принимает значение 1. 4-х мерный куб можно представить как два 3-х мерных куба. Одному соответствует x4=0, другому – x4=1. 5-ти мерный куб – два 4-х мерных куба и т.п. 2) как диаграмму Карно-Вейче
Единица, стоящая в определенной ячейке, означает, что для данного набора значений переменных функция принимает значение 1. Методы минимизации ФАЛ (функций алгебры логики) имеют важное значение при проектировании схем ЭВМ. Минимальные формы ФАЛ фактически экономят оборудование. Рассмотрим задачу минимизации в булевском базисе, предположим, что функция для минимизации задана в ДСНФ (дизъюнктивная совершенная нормальная форма) – это значит, что она представлена через конъюнкции ранга n – такая конъюнкция – элементарная. Задача минимизации состоит в том, чтобы найти ДНФ (дизъюнктивную нормальную форму), имеющую минимальный ранг, т.е. наименьшее число входящих в нее букв. ^ ![]() Этот алгоритм основан на применении закона склеивания и включает в себя несколько этапов.
Если первичная импликанта входит в некоторую конъюнкцию в соответствующем месте таблицы ставится метка.
П ![]() |
![]() | По ошибке сваркой называют способ холодного соединения или соединения с набуханием пластика, который не подпадает под данное понятие,... | ![]() | Так же с помощью наружной рекламы можно выработать у потенциального потребителя позитивное (или не очень) отношение к бренду или... |
![]() | Выполните задания 1-4 с помощью двойного интеграла, задания 5-7 с помощью тройного интеграла, задания 8-11 с помощью криволинейных... | ![]() | Создавайте плейлисты на любой случай жизни. Записывайте плейлисты на компакт-диск и воспроизводите их на домашней или автомобильной... |
![]() | Текстовый курсор и символ конца текста. Текстовый курсор передвигается с помощью клавиш управления курсором или с помощью щелчка... | ![]() | Умение работать с историческими источниками- работа и анализ текста с помощью маркировки ( статьи о новых научных открытиях или просмотр... |
![]() | Волю, с помощью Воли воспитайте знание, с помощью знания очистите сердце, установите контроль над энергиями тела и успокойте ум.... | ![]() | Раскрутка нового бренда с помощью рекламы и с помощью пиара совсем не одно и то же. Если вы хотите раскрутить бренд с помощью пиара,... |
![]() | Автоматическая телефонная связь позволяет абоненту без предварительного заказа, в любой момент времени установить соединение по телефону... | ![]() | Дети, которые, подрастая, не научатся подавлять свою агрессивность и общаться с окружающими с помощью устной речи, часто превращаются... |