Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: Pn = n!

ДИСКРЕТНАЯ МАТЕМАТИКА КОМБИНАТОРНЫЕ ОБЪЕКТЫ. СОЧЕТАНИЯ, РАЗБИЕНИЯ, ПЕРЕСТАНОВКИ В разделе математики, который называется комбинаторикой, решаются некоторые задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. Например, если взять 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 – число элементов, входящих в каждую перестановку. Число перестановок можно вычислить по формуле ^ Pn = n*(n-1)*(n-2)*…*3*2*1 Или с помощью факториала: 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!, а знаменатель равен (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) как диаграмму Карно-Вейче x3x4 00 01 11 10 x1x2 00 1 1 01 1 11 1 10 1 Единица, стоящая в определенной ячейке, означает, что для данного набора значений переменных функция принимает значение 1. Методы минимизации ФАЛ (функций алгебры логики) имеют важное значение при проектировании схем ЭВМ. Минимальные формы ФАЛ фактически экономят оборудование. Рассмотрим задачу минимизации в булевском базисе, предположим, что функция для минимизации задана в ДСНФ (дизъюнктивная совершенная нормальная форма) – это значит, что она представлена через конъюнкции ранга n – такая конъюнкция – элементарная. Задача минимизации состоит в том, чтобы найти ДНФ (дизъюнктивную нормальную форму), имеющую минимальный ранг, т.е. наименьшее число входящих в нее букв. ^ Алгоритм Квайна – Мак Класки Этот алгоритм основан на применении закона склеивания и включает в себя несколько этапов. нахождение первичных импликант: осуществляет попарное склеивание конъюнкций n-го ранга, все склеенные конъюнкции отмечаются, затем полученное множество конъюнкций (n-1)-го ранга также попарно склеивается, склеенные конъюнкции отмечаются и т.д. Те конъюнкции, которые остались неотмеченными, образуют множество первичных или простых импликант; расстановка меток: рисуется таблица Конъюнкции из ДСНФ Первичные импликанты Если первичная импликанта входит в некоторую конъюнкцию в соответствующем месте таблицы ставится метка. нахождение существенных импликант: существенные импликанты – это те, которые имеют метку только в одном столбце; из таблицы вычеркиваются строки с существенными импликантами и все столбцы, в которых имеются метки, соответствующие этим существенным импликантам; вычеркивание лишних столбцов: если в таблице имеются столбцы с одинаковыми метками, то оставляем только 1 из них, вычеркивая остальные; вычеркивание лишних первичных импликант: если в таблице появились строки, в которых нет меток, то соответствующие импликанты вычеркиваются; выбор покрытия оставшихся столбцов импликантами, имеющими минимальный суммарный ранг. При склеивании применяются правила:

Похожие:

	Сварка с помощью нагревательных элементов По ошибке сваркой называют способ холодного соединения или соединения с набуханием пластика, который не подпадает под данное понятие,...		Федеральное агентство железнодорожного транспорта Так же с помощью наружной рекламы можно выработать у потенциального потребителя позитивное (или не очень) отношение к бренду или...
	Пермский государственный технический университет Выполните задания 1-4 с помощью двойного интеграла, задания 5-7 с помощью тройного интеграла, задания 8-11 с помощью криволинейных...		О программе iTunes Создавайте плейлисты на любой случай жизни. Записывайте плейлисты на компакт-диск и воспроизводите их на домашней или автомобильной...
	Форматирование текста Текстовый курсор и символ конца текста. Текстовый курсор передвигается с помощью клавиш управления курсором или с помощью щелчка...		Урока, дата Главная тема Важнейшие подтемы Умение работать с историческими источниками- работа и анализ текста с помощью маркировки ( статьи о новых научных открытиях или просмотр...
	Йогическая садхана под редакцией уттара йоги Волю, с помощью Воли воспитайте знание, с помощью знания очистите сердце, установите контроль над энергиями тела и успокойте ум....		Шаг Утечка информации Раскрутка нового бренда с помощью рекламы и с помощью пиара совсем не одно и то же. Если вы хотите раскрутить бренд с помощью пиара,...
	Услуги междугородной и международной телефонной связи Orange Business... Автоматическая телефонная связь позволяет абоненту без предварительного заказа, в любой момент времени установить соединение по телефону...		Многие дети проходят период между двумя и четырьмя годами, когда... Дети, которые, подрастая, не научатся подавлять свою агрессивность и общаться с окружающими с помощью устной речи, часто превращаются...