231

Комбинаторные конфигурации и их приложения

Лекция

Математика и математический анализ

Комбинаторные конфигурации в алгебре и анализе. Алгоритм генерации перестановок с повторениями. Принцип включения и исключения. Примеры использования формулы обращения, дифференцирование и интегрирование.

Русский

2012-11-14

321.5 KB

82 чел.

Комбинаторные конфигурации и их приложения

Тема 1. Математическая комбинаторика

Комбинаторика  – это область математики, в которой изучаются различные комбинации элементов дискретных (в основном – конечных) множеств, подчиненных тем или иным условиям.

Как наука комбинаторика возникла в 16 веке, и первоначально основной областью ее приложения являлись азартные игры. Однако, за последние несколько десятков лет комбинаторные методы трансформировались из разделов “досуговой” математики в инструмент решения огромного числа практически важных задач, таких как составление расписаний, планирование производства, размещение объектов на данной территории и многое другое. Не последнюю роль комбинаторика играет и при решении задач разработки технического и программного обеспечения современных информационных систем – проектирование интегральных схем, кодирование информации, организация структур данных – вот далеко не полный перечень проблем “компьютерной” математики, решаемых средствами комбинаторики.

1. Основные задачи, обозначения и правила

Среди многочисленных проблем, решаемых средствами комбинаторики,  основное внимание уделим следующим задачам.

1. Выбор из некоторого, обычно конечного, множества некоторого подмножества (комбинации) элементов, обладающих заданными свойствами.

2. Подсчет числа таких комбинаций.

3. Определение элемента комбинации, обладающего оптимальными свойствами.

Введем следующие понятия и обозначения.

n-множество – множество из n различных элементов:

Х = {х1, х2, …, хn},   хi  хj, при i  j.

(n)-множество – множество, содержащее n различных типов элементов:

Х = {х1, х1, …, х1, х2, х2, …, хn}.

r-выборка множества – совокупность из r элементов данного множества (если выборка из n-множества, то повторяющихся элементов нет, если из (n)-множества, то есть повторения).

Размещения – упорядоченные r-выборки (элементы прямого произведения Х1  Х2  Х r).

Сочетания – неупорядоченные r-выборки (r-элементные подмножества данного множества).

Пример 1.1.

а) На диске секретного замка 12 букв. Замок открывается после набора пароля из 5 букв.

В пароле буквы могут повторяться. Следовательно, каждый пароль – это 5-размещение из (12)-множества, т.е. размещение с повторениями.

б) Из 25 человек, членов комитета, надо выбрать: председателя, вице-председателя, секретаря и казначея (4 человека). Совмещение должностей не допускается.

В задаче повторение элементов невозможно, т.к. не допускается совмещение должностей. Кроме того, в данной 4-выборке важен порядок выбора, т.к. надо не просто выбрать заданное число человек, но необходимо связать каждого выбранного с определенной должностью. Следовательно, здесь речь идет о размещении без повторений.

в) Из 125 человек надо выбрать 6 делегатов на конференцию.

В данном случае порядок выбора не играет роли, следовательно, имеет место 6-сочетание из 125-множества.

Многие простые задачи комбинаторики решаются с помощью двух основных аксиоматических правил.

1. Правило суммы. Если все комбинации можно разбить на несколько непересекающихся классов, то общее число комбинаций равно сумме чисел комбинаций во всех классах:

.

2. Правило произведения. Пусть объект А можно выбрать n способами, а при каждом таком выборе объект В можно выбрать m способами. Тогда выбор упорядоченной пары (А, В) можно сделать nm способами. В общем случае:

.

На практике оба правила часто используются в комбинации.

Пример 1.2. Сколькими способами можно из 28 костей домино выбрать 2 кости, которые можно приложить друг к другу?

Решение. 1-ю кость можно выбрать 28-ю способами. Из них в 7 случаях кость будет дублем, а в 21 случаях – с различными числами. Если 1-я кость является дублем, 2-ю кость можно выбрать 6-ю способами, а если – нет, то 12-ю способами. В соответствии с правилами суммы и произведения общее число случаев равно N = 76 + 2112 = 294.

2. Простейшие конфигурации

2.1. Размещения с повторениями. Так называются упорядоченные r-выборки из (n)-множества.

Дадим более подробное определение. Пусть дано неограниченное число предметов, относящихся к n различным видам. r-размещениями с повторениями называются различные расстановки из этих предметов по r штук в каждой, образованные по следующим правилам.

1. 2 расстановки считаются различными, если они отличаются либо видом входящих в них предметов, либо порядком следования этих видов.

2. В каждую расстановку может входить несколько предметов одного вида.

Свойство. Число r-размещений с повторениями из предметов n типов обозначается и равно nr.

Доказательство. На 1-м месте может быть предмет одного из n видов. Следовательно, существует n способов выбрать 1-й предмет. При каждом фиксированном таком способе имеется n способов выбрать 2-й предмет, и т.д. В соответствии с правилом произведения всю группу из r предметов можно выбрать nr способами, что и требовалось доказать.

В примере 1.1.а) существует 125  250 тыс. различных паролей. (Если взломщик будет тратить по 1 секунде на проверку комбинации, то ему понадобиться 69 часов для проверки всех паролей).

Пример 1.3. В азбуке Морзе самый длинный код буквы состоит из 5 символов. Можно ли использовать коды длиной не более 4-х символов?

Решение. В соответствии с правилом суммы число различных кодов длиной не более 4 символов при использовании 2 видов символов (точка и тире) равно = 2 + 4 + 8 + 16 = 30. Значит, 4-х символьных кодов не хватит для кодирования даже всех букв кириллицы, не говоря о служебных символах. При использовании же 5-ти символьных кодов N = 30 +  = 62, т.е. такой длины кода достаточно.

2.2. Размещения и перестановки без повторений. Размещениями без повторений называются упорядоченные r-выборки из n-множества. Такие расстановки по r элементов  составляются из n неповторяющихся предметов.

Свойство. Число r-размещений без повторений из n предметов обозначается  и равно n(n – 1)…(nr + 1) = .

Доказательство. 1-й предмет можно выбрать n способами, 2-й – (n – 1) способами, т.к. число кандидатов на это место уже    n – 1, и т.д. В соответствии с правилом произведения получаем  выражение из r сомножителей:

.

В примере 1.1.б) число способов выбора 4-х членов в руководство комитета из 25 человек равно  = 25242322 = 303600.

В частном случае при r = n получаем  = Рn = n! Данная конфигурация называется перестановкой из n неповторяющихся предметов – упорядоченная n-выборка из n-множества.

2.3. Перестановки с повторениями. Так называют упорядоченные n-выборки из (m)-множества (n > m). Если некоторые элементы такой выборки совпадают, то могут существовать неразличимые (совпадающие) перестановки.

Найдем количество различных перестановок. Обозначим a, b,…, z – переставляемые объекты; nj – количество повторений j-го элемента, j = 1,…,m, ; Р(n1, n2,…, nm) – число таких перестановок. Рассмотрим 1-ю перестановку:                     .

Объекты “а” можно переставлять n1! способами, но поскольку все они одинаковы, то такие перестановки не дают новых комбинаций. Следовательно, число действительно различных перестановок за счет совпадения первых n1 элементов будет в n1! раз меньше, чем в случае всех различающихся элементов. Аналогично, совпадение n2 элементов “b” уменьшает число различных перестановок в n2! раз, и т.д. Поскольку при несовпадении всех n элементов количество перестановок было бы равно n!, то

Р(n1, n2,…, nm) = .

Пример 1.4. Найти все перестановки букв в слове “мама”.

Решение. В данном слове есть объекты 2-х типов – “м” и “а”. Всего множество содержит 4 элемента. Следовательно, число перестановок равно . Действительно, имеем следующие комбинации: ”аамм”, “мама”, “амам”, “ммаа”, “амма”, “маам”.

Пример 1.5. Найти число перестановок букв в слове “Миссисипи”.

Решение. Длина этого слова – 9 букв. Из них буква “м” встречается 1 раз, “и” – 4 раза, “с” – 3, “п” – 1. Следовательно, число перестановок равно

Р(1, 4, 3, 1) =  = 2520.

2.4. Сочетания без повторений. Так называются неупорядоченные r-выборки из n-множества (r < n).

Свойство. Число r-сочетаний без повторений из n предметов обозначается и равно .

Доказательство. Каждое неупорядоченное r-сочетание можно упорядочить r! способами и получить r-размещение. Следовательно, сочетаний в r! раз меньше, чем размещений, т.е.

= Р(r, nr).

В примере 1.1.в) 6 делегатов из 125 человек можно выбрать  = 4.69110 9 способами

Пример 1.6. В лотерее из 36 номеров будут выбраны 5. Какова вероятность угадать ровно 3 номера из 5?

Решение. 3 номера из 5 верных можно выбрать способами. На каждый угаданный номер могут приходиться любые 2 из 31 невыбранных номеров, т.е.  сочетаний. Окончательное число благоприятных случаев равно . Общее же число случаев равно количеству выпадения 5 номеров из 36, т.е. .

Отсюда вероятность угадывания равна 0.0123 – немногим более 1%.

2.5. Сочетания с повторениями. Это неупорядоченные r-выборки из (n)-множества. Они получаются, например, если необходимо r неразличимых предметов разместить по n ящикам, в частности возможно n > r.

Свойство. Число r-сочетаний с повторениями из n предметов обозначается и равно .

Доказательство. Обозначим rj  0 – количество элементов j-го типа в сочетании,    (rj можно интерпретировать как количество предметов в j-м ящике). Набор значений rj однозначно определяет текущее сочетание. Представим этот набор в виде следующей бинарной последовательности. Числа rj отобразим в группы из rj единиц, каждую такую группу отделим от соседних одним нулем (если rj = 0, то несколько нулей могут стоять подряд). Число промежутков равно n – 1. Например, набор (2, 0, 3, 1), n = 4, r = 6 соответствует последовательности   (1, 1, 0, 0, 1, 1, 1, 0, 1).

Построенная конструкция – не что иное, как набор перестановок с повторениями объектов 2-х видов – 0 и 1. Число нулей в этих сочетаниях равно  n – 1, а единиц – r. Следовательно, , что и требовалось доказать.

Пример 1.7. Определить количество N возможных сочетаний из 8 пирожных 4-х сортов.

Решение. В данном случае rj– число пирожных j-го сорта. Следовательно,  r = 8, n = 4 и N = = = 165.

Другой вариант доказательства основан на построении взаимно-однозначного отображения напрямую между элементами повторных и бесповторных сочетаний. Свяжем каждый набор r1, r2, …, rn с элементами n – 1-сочетаний без повторений из множества чисел {1, 2,…, n + r – 1}. Обозначим Кj,   j = 1,…, n –1– число, стоящее на j-м месте в отбираемом сочетании  (Кj > Кj–1), формально положим К0 = 0. Построим взаимно-однозначное отображение

f : (r1, r2, …, rn) (K1, K2, …, Kn–1)

по следующему правилу:

rj = Кj – Кj – 1 – 1,     j = 1,…, n – 1;                              (1.1)

rn = (n + r – 1) – Кn –1.

Очевидно, обратное отображение строиться по формуле

Кj = ,     j = 1,…, n –1.                                  (1.2)

Покажем, что числа, найденные по формулам (1.1) являются элементами r-сочетаний с повторениями. Действительно, т.к. при любом j и , то .  Кроме того  

.

Несложно также убедиться, что числа Кj, полученные по формуле (1.2) являются натуральными, и обладают всеми свойствами элементов сочетаний:

;     

Следовательно, отображение f действительно устанавливает взаимно однозначное соответствие между элементами r-сочетания из (n)-множества и элементами n – 1-сочетания из n + r – 1-множества. Отсюда = = . Последнее равенство вытекает из формулы числа сочетаний.

2.6. Свойства чисел сочетаний

1. =. Это свойство вытекает из формулы числа сочетаний.

2. =  + .

Доказательство. Разобьем все r-сочетания на два класса. К первому классу отнесем сочетания, содержащие объект an, ко второму классу – не содержащие an. Так как в первом классе меняются только r – 1 элементов из n – 1 возможных, то он содержит r – 1-сочетания из n – 1-множества, следовательно, в нем  элементов. Второй класс содержит все r-сочетания из n – 1-множества, т.к. в них нет одного элемента –  an. Следовательно, в нем  элементов. Общее число сочетаний, согласно правилу суммы равно  + , что и требовалось доказать.

Данное свойство позволяет легко построить рекуррентный процесс вычисления всех чисел сочетаний. Положим по определению для любого n  0 (ноль элементов из любого множества, в том числе – пустого, можно выбрать 1 способом, кроме того, по определению 0! = 1 – см. формулу из 2.4) и  (отрицательное количество элементов выбрать невозможно). Организуем двойной цикл для вычисления всех ,  r  m  n:

    for  m := 1 to  n  do

               for  r := 0  to  m  do  :=  +

Описанный процесс удобно представить в виде таблицы, называемой треугольником Паскаля:

1

1   1

1   2   1

1   3   3   1

1   4   6   4   1

1   5   10   10   5   1

…………………….

В таблице каждая m-я строка состоит из чисел , r = 0, … m, каждый элемент равен сумме двух элементов, расположенных над ним (пустое место считается нулем).  

3.

Доказательство. Пусть имеем последовательность из n двоичных разрядов, содержащих 0 или 1. Очевидно, что каждую такую последовательность можно рассматривать, как n-размещение с повторениями из элементов 2-х типов, значит, количество этих размещений равно 2n.

Теперь рассмотрим некоторое множество из n объектов – а1, … аn, из которого будем образовывать все возможные сочетания без повторений, включая: 0-сочетания (не выбирается ни один объект), 1-сочетания и т.д., n-сочетания. При этом любую из упомянутых выше последовательностей из 0 и 1 можно интерпретировать, как перечень элементов, отбираемых в сочетание – если на k-м месте последовательности стоит 1 – элемент аk отобран, если 0 – не отобран.      Очевидно, что таким образом будут перечислены все бинарные n-последова-тельности. По правилу суммы общее число таких сочетаний, а, значит – и бинарных последовательностей равно  Свойство доказано.

Замечание. Каждая отбираемая в сочетание группа элементов представляет собой некоторое подмножество исходного множества из n объектов. Следовательно, число всех подмножеств (включая пустое) множества из n элементов равно 2n.

3. Комбинаторные конфигурации в алгебре и анализе

Многие важные формулы алгебры и математического анализа (и других разделов математики) имеют наглядную комбинаторную интерпретацию или доказываются с использованием правил комбинаторики.

3.1. Бином Ньютона.  – формула бинома Ньютона. В частности, (х + у)2 = х2 + 2ху + у2;  (х + у)3 = х3 + 3х2у + 3ху2 + у3 и т.д.

Доказательство. Раскроем скобки выражения (х + у) n =   (x + y)(x + y)…(x + y). В результате получим сумму членов вида . Например (х + у) 3 = ххх + хху + хух + хуу + ухх + уху + уух + ууу. Приведем подобные члены, подсчитав число таких произведений при каждом k = 0,…, n. Каждое такое выражение – не что иное, как перестановка повторениями из 2-х элементов. Полагая n1 = k, n2 = nk, получим, что число этих перестановок равно Р(k, nk) =  (см. пп. 2.3, 2.4), т.е. множитель при хkуnk совпадает с , что и требовалось доказать. 

С помощью формулы бинома легко получить новые свойства чисел сочетаний.

5. . Доказать легко с использованием бинома Ньютона на основе тождества (1 – 1)n = 0.

6. .

Доказательство. Имеем:  n2n–1 = n(1 + 1)n –1 = . В свою очередь при любом р выполняется равенство:

=  = .

Следовательно, . Переобозначим индекс суммирования, положив p + 1 = k. Имеем:

,

что и требовалось доказать. В последнем равенстве формально введено равное нулю слагаемое при k = 0.

3.2. Полиномиальная формула. Формулу бинома можно обобщить на случай нескольких слагаемых: (х1 + х2 + … + хk)n.

Запишем эту формулу в виде произведения одинаковых сомножителей и перемножим. Получим все возможные n-размещения с повторениями из объектов х1, х2 , … , хk. Приведем подобные, сосчитав число повторений каждого слагаемого вида . Для этого надо определить число слагаемых, в которых символ х1 повторяется n1 раз, х2n2 раз, и т.д., хk повторяется nk раз. Каждое такое слагаемое – это перестановка с повторением nj  раз элемента хj,    j = 1,…k. Число таких перестановок равно Р(n1, n2 ,…, nk),  nj = n. Следовательно

1 + х2 + … + хk)n  = .

Выражение n1 + … + nk  = n в значке суммы означает, что перебираются все (целые неотрицательные) значения n1,…, nk, удовлетворяющие данному условию.

Например: (x + y + z)4 = P(4, 0, 0)x4 + P(0, 4, 0)y4 + P(0, 0, 4)z4 + P(3, 1, 0)x3y + P(3, 0, 1)x3z + P(2, 2, 0)x2 y2 +  P(2, 1, 1)x2 y z + P(2, 0, 2)x2 z2 + P(1, 3, 0)x y3 + P(1, 0, 3)x z3 + P(1, 1, 2)x y z2 + P(1, 2, 1)x y2 z + P(0, 3, 1)y3 z + P(0, 1, 3)y z3 + P(0, 2, 2)y2 z2.

Напоминаем, что здесь Р(a, b, c) = , например Р(2, 1, 1) =  = 12.

3.3. Ряд Ньютона. Формулу бинома можно обобщить на случай нецелой степени, в результате получим выражение:

(у + х) = у + у–1х + + … +   + +…

При целом значении формула содержит конечное число слагаемых, т.к. для    k > коэффициенты при уkхk  обращаются в ноль. При нецелом получается бесконечный степенной ряд. Найдем радиус его сходимости. Представим бином в виде:

(у + х) =  = у (1 + z) =

у .

Воспользуемся формулой Даламбера:

, где  .

Имеем: = –1 +   – 1. Отсюда R = 1. Следовательно, ряд сходится при |z| < 1, т.е. при |x| < |y|. Если разложение в ряд происходит по степеням у, то ряд сходится при |у| < |х|.

Пример 1.8.          = (1 – х)–1 = 1 + ( – 1)( – х) +

+  = 1 + х + х2 +…

– формула бесконечно убывающей геометрической прогрессии, которая сходится при |x| < 1.

Тема 2. Комбинаторные алгоритмы

При поиске оптимального варианта из некоторого допустимого набора часто приходится перебирать все возможные альтернативы. Во многих задачах перебираемые варианты являются членами сочетаний, размещений и других комбинаторных конфигураций. Поэтому большое значение имеют алгоритмы генерации элементов соответствующих конечных множеств.

Главная сложность составления таких ”генераторов” состоит в необходимости сделать их структуру независимой от размерности порождаемых ими множеств, которая может очень сильно варьироваться в различных задачах. Например, алгоритм генерации r-размещений с повторениями очень легко реализовать с помощью r вложенных циклов:

for  j1 := 1 to  n do

for  j2 := 1 to  n do

     …………………..

for  jR := 1 to  n do  writeln (j1, j2, … jR);

Ясно, что всякий раз при изменении значения r такую программу пришлось бы переделывать, добавляя или удаляя циклы, и на самом деле алгоритм генерации должен быть другим.

Другой особенностью предлагаемых алгоритмов является то, что в них вместо комбинаций самих объектов генерируются комбинации из их номеров. Очевидно, что такие расстановки легко преобразовать в манипуляции, например, с названиями объектов, введя в программу массив из строк символов соответствующей размерности.

Многие из комбинаторных конфигураций удобно генерировать с помощью алгоритма поиска с возвратом.

Общая схема рекурсивного поиска с возвратом. Пусть дано n упорядоченных множеств В1, В2,… Вn. Требуется найти набор векторов вида Х = (х1, х2,… хn), где xiВi, удовлетворяющих некоторым дополнительным условиям. Иными словами Х В1В2 Вn.

В алгоритме поиска с возвратом каждый вектор Х строится покомпонентно слева направо. Предположим, что уже найдены первые k – 1 компонент х1, х2,… хk1. Тогда их значения определяют некий набор условий, ограничивающих выбор  k-й компоненты некоторым множеством Sk  Вk. Если Sk не пусто, мы вправе выбрать в качестве хk первый по порядку элемент из Sk, присоединить его к уже выбранным компонентам, и перейти к выбору хk+1 и так далее. Однако, если набор условий таков, что Sk пусто, то мы возвращаемся к выбору k–1-й компоненты. При этом мы отбрасываем хk1 и выбираем в качестве новой k–1-й составляющей вектора Х тот элемент из Sk1, который непосредственно следует за только что отброшенным хk1.

Предположим теперь, что в процессе поиска новых компонент мы дошли до конца, т.е. выбрали хn. Теперь надо как-то использовать полученный вектор Х, в соответствие с условием задачи. Например, если в задаче требуется найти лучший из векторов, то нам следует сравнить построенный вектор Х с решением, которое до данного момента считалось оптимальным и если Х окажется лучше, то надо обновить текущее оптимальное решение, вернуться на шаг назад и продолжить поиски новых решений.

Этот процесс продолжается, пока не будут рассмотрены все возможные вектора решений.

Данная схема легко реализуется посредством рекурсивной процедуры.

procedure Solve ( k );

           { k – номер подбираемой координаты (номер глубины рекурсии) }

           { Х – вектор текущего решения }

begin if  Х – решение  then  Использовать Х

        else

 begin  Определить Sk  ;         

           for у  Sk  do

           begin Xk:= y;

Сузить  Sk+1 с учетом выбранного Xk ;

                   Solve(k+1);

Sk := Sk \ {y};

Расширить Sk+1 с учётом сужения Sk ;

 end;

 end;

end;

{ Головная программа }

begin   Solve ( 1);

end.

Конкретный набор требований, которым должны удовлетворять сгенерированные векторы, определяются множествами Sk, а также правилом проверки того, что Х – решение.

1. Алгоритм генерации r-размещений с повторениями. В размещениях с повторениями на k-месте должно стоять число из набора 1,…, n независимо от чисел, стоящих на предыдущих позициях. То есть для любого k всегда будет Sk= {1, …, n }.

Пример 2.1. Пусть r = 3; n =2. Надо получить следующие векторы Х:        (1 1 1), (1 1 2), (1 2 1), (1 2 2), (2 1 1),  … (2 2 2).

Обозначим А[j] – номер предмета, находящегося на j-м месте, j = 1,…r. Предлагается следующий алгоритм.

Procedure Razm_P(k);

begin

     if k=r+1 then write(A[1],…A[r]);

        else

      for y:=1 to n do

      begin  A[k]:=y;  Razm_P(k+1);

      end;  

end;

begin

     Razm_P(1);

end.

Назначение процедуры Razm_P(k)– получение k-й компоненты вектора Х =(A[1],…A[r]). Если k = r+1 – это означает, что вектор полностью получен, и надо его использовать (вывести на экран). В противном случае надо получить следующую компоненту. Так как на ее месте может стоять любое число от 1 до n, то Sk = {1, … n}, перебор элементов этого множества обеспечивается циклом  for y:=1 to n do

2. Алгоритм генерации r-размещений без повторений. Отличие данного алгоритма от предыдущего в том, что каждое из возможных значений 1, … n элементов размещений можно использовать только один раз. Поэтому в процедуре Razm_BP используется массив dop[j], j = 1,…n, в котором dop[j] = 1, если значение j не было использовано и dop[j] = 0, в противном случае. При продвижении вглубь рекурсии значение j блокируется, чтобы его нельзя было использовать повторно, а при откате – восстанавливается.

 Procedure Razm_BP(k);

begin

if k=r+1 then write(A[1],…A[r]);           

          else

        for y:=1 to n do

          if dop[y] > 0 then

          begin A[k]:=y;       dop[y]:=dop[y]-1;

                Razm_BP(k+1);  dop[y]:=dop[y]+1;

          end;    

end;

begin for i:=1 to n do dop[i]:= 1;

     

     Razm_BP(1);

end.

Данный алгоритм можно также использовать для генерации перестановок без повторений при r = n.

3. Алгоритм генерации перестановок с повторениями. Этот алгоритм  похож на предыдущий, только первоначально dop[j]=n[j] число повторений j-го значения, j = 1,…m. По мере использования этого значения переменная dop[j] уменьшается, пока не станет равной 0. Это будет означать, что данное значение уже нельзя использовать. Предлагается следующий алгоритм генерации перестановок из m объектов при .

Procedure Perest_P(k);

begin  if k=n0+1 then write(P[1],…P[n0]);           

        else

      for y:=1 to m do

          if dop[y] > 0 then

          begin P[k]:=y;   dop[y]:=dop[y]-1;

                Lex(k+1);  dop[y]:=dop[y]+1;

          end;      

begin n0=0;

     for j:=1 to m do

     begin dop[j]:=n[j]; n0:=n0+n[j]; end;

     Lex(1);  

     

end.

4. Алгоритм генерации r-сочетаний без повторений. Алгоритм похож на генерацию размещений без повторений, отличие в том, что в каждом сочетании не допускаются перестановки элементов, т.е. каждый следующий элемент больше предыдущего.

Пример 2.2. Подобные 3-сочетания из 5 выглядят так: (1 2 3), (1 2 4), (1 2 5), (1 3 4), … (1 4 5), (2 3 4), … – т.е. генерируется возрастающая последовательность 3-значных чисел.

Для обеспечения этого условия в генерации сочетаний используется цикл for y:=t to n do, а не for y:=1 to n do, как в размещениях, где переменная t подбирается по правилу if k<=1 then t:=1 else t:=А[k-1]+1.

Procedure Sochet_BP(k);

begin if k=r+1 then write(А[1],…А[r]);           

          else

     begin if k<=1 then t:=1 else t:=А[k-1]+1;

           for y:=t to n do

               if dop[y] > 0 then

               begin А[k]:=y;   dop[y]:=dop[y]-1;

                    Sochet_BP(k+1);

                    dop[y]:=dop[y]+1;

               end;

      end;

end;

begin for i:=1 to n do dop[i]:= 1;

     

     Sochet_BP(1);

end.

5. Разгадка числовых ребусов. В числовых ребусах зашифровывают некоторое арифметическое действие, буквами обозначают цифры. Разным цифрам соответствуют разные буквы. Требуется разгадать, какая цифра скрывается за каждой буквой. Это возможно, если воспользоваться программой генерации размещений без повторений.

Пример 2.3. ТОРГ  Г = ГРОТ. Имеем 4 различных цифры: Т, О, Р, Г. Следовательно, необходимо сгенерировать 4-размещения из 10 (всего 10 цифр), т.е. массив а[1], … , а[4], удовлетворяющий следующим условиям:

1) а[1] 0, а[4] 0 – т.к. число не может начинаться с 0.

2) (а[1]1000 + а[2]100 + а[3]10 + а[4])a[4] = а[4]1000 + а[3]∙100 + а[2]∙10 + а[1] – это запись зашифрованного действия.

В процессе генерации каждое полученное сочетание проверяют на выполнение перечисленных условий и отбирают подходящие. В общем случае решений может быть несколько. В данном примере ТОРГ = 1089 (10899 = 9801).

Тема 3. АНАЛИТИЧЕСКИЙ АППАРАТ

КОМБИНАТОРИКИ

Формулы и алгоритмы, рассмотренные в теме 1, дают способы вычисления комбинаторных чисел для некоторых распространенных конфигураций. Однако практические задачи далеко не всегда непосредственно сводятся к ним. В этом случае чрезвычайно важно знание методов сведения одних конфигураций к другим, либо общих методов, не столь зависящих от конкретных комбинаторных структур. Рассмотрим наиболее популярные из таких методов.

1. Принцип включения и исключения

1.1. Вывод формулы. Пусть имеем N объектов и некоторый набор свойств а1, …, аn, которыми могут обладать эти объекты. Обозначим N(i) – число объектов, обладающих свойством аi, и вообще N(i1, …, ik) – число объектов, обладающих одновременно всеми свойствами . Пусть N(0) – число объектов, не обладающих ни одним из свойств аi. Справедлива формула включения и исключения:

N(0) = N –   +  + …

+ (– 1)k + … + (–1)n N(1, 2, … , n).           (3.1)

Символ 1  i1 < i2 <…< ik  n под знаком суммы означает, что суммирование ведется по всем комбинациям  i1, i2,…, ik так, чтобы выполнялось указанное соотношений. Доказательство проведем с помощью индукции по n – число свойств.

10. n = 1. N(0) = NN(1). Всего существует одно свойство. От общего числа объектов отнимем количество объектов, обладающих этим свойством – узнаем, сколько объектов этим свойством не обладают.

20. Пусть для n – 1 свойств справедлива формула

N(0) = N –   +  + …

+ (– 1)k + … + (–1)n N(1, 2, … , n – 1).           (3.2)

Пусть теперь имеем множество, все элементы которого обладают свойством аn, и, возможно, обладают свойствами а1, …, аn–1. Очевидно, для этого множества формула (3.2) также верна и имеет вид:

N(0, n) = N(n)   – + … +

+(–1)n–2+ (–1)n–1N(1, 2, … , n – 1, n).        (3.3)

В (3.3) везде в скобках дописано n, т.к. все элементы множества свойством аn обладают. Вычтем (3.3) из (3.2):

N(0) – N(0, n) = N –   +  + … –    (–1)n–1 N(1, 2, … , n – 1, n).

Отсюда

N(0) – N(0, n) = N – ++… + (–1)n N(1, 2,…,n).

Справа мы получили требуемую формулу. А что слева? N(0) – число элементов, не обладающих свойствами а1, …, аn–1, но, возможно, обладающих свойством аn. N(0, n) – число элементов, не обладающих свойствами а1, …, аn–1, но обязательно обладающих свойством аn. Следовательно, N(0) – N(0, n) – число элементов, не обладающих ни одним из свойств а1, …, аn, т.е. требуемая величина. Формула доказана.

Пример 3.1. Староста класса подал следующие сведения о классе. Всего в классе 45 учеников, из них 25 мальчиков. 30 человек учится без троек, из них – 16 мальчиков; 28 человек занимаются спортом, из них – 18 мальчиков и 17 хорошистов и отличников; 15 мальчиков учатся без троек и одновременно занимаются спортом. Классный руководитель внимательно посмотрел список и сказал, что в сведениях есть ошибка. Как он это узнал?

Решение. Обозначим a1 – свойство принадлежности к мужскому полу; a2 – хорошая успеваемость; a3 – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка.

1.2. Модификации формулы включения и исключения 

2.а. Формулу (2.1) можно обобщить для определения числа элементов, обладающих в точности k свойствами (0  k  n):

N(k) =  + …+ (– 1)s–k+ …

+  (–1)n–k N(1, 2, … , n).                                 (3.4)

Пример 3.2. В отделе НИИ каждый сотрудник владеет хотя бы одним иностранным языком. Известно, что английским языком владеют 6 человек, немецким – 6, французским – 7, английским и немецким – 4, немецким и  французским – 3, английским и французским – 2, все три языка знает 1 человек. Определить, сколько всего человек в отделе, сколько человек владеют только английским, только немецким, только французским, и сколько человек знает только 1 иностранный язык.

Решение. Согласно условиям задачи N(0) = 0, т.к. в отделе нет сотрудников, не владеющих иностранными языками. Следовательно, по формуле (3.1) получаем:

N =   –  + N(1, 2, 3)                             (3.5)

N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек всего в отделе.

Для вычисления остальных показателей также воспользуемся формулой (3.5). Найдем, например N(только А) – число человек, не владеющих никаким другим языком, кроме английского. Для этого формулу (3.5) надо применить только к множеству людей, владеющих  английским языком. В этом случае        n = 2. Тогда N = N(A), N(1) и N(2) – число людей, владеющих помимо английского еще  немецким и французским, соответственно,  N(1, 2) – число людей, владеющих помимо английского еще одновременно немецким и французским. Отсюда

N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) =

6 – 4 – 2 + 1 = 1.

Аналогично

N(только Н) = N(Н) – N(А и Н) – N(Н и Ф) + N(А и Н и Ф) =

6 – 4 – 3 + 1 = 0.

N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) =

7 –2 – 3 + 1 = 3.

Вычислим теперь N(1) – число людей, владеющих только 1 языком. Воспользуемся формулой (3.4) при k = 1.

N(1) = N(А) + N(Н) + N(Ф) + (–1)2–1 [N(А и Н) + N(Н и Ф) + N(А и Ф)] +   (–1)3–1 N(А и Н и Ф) = 6 + 6 + 7 – 2(4 + 3 + 2) + 31 = 4.

Такой же результат получим, если сложим N(только A) + N(только Н) + N(только Ф).

2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений различных множеств, т.е. дать  теоретико-множественное представление принципа включения и исключения. Пусть имеем некоторое конечное множество А и его подмножества Аj, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид:

= |A| –  +   + …

+ (– 1)k+ …+ (–1)n .

2. Формулы обращения

2.1. Теорема обращения. Пусть имеем два семейства комбинаторных чисел {an,k} и {bn,k}, зависящих от целочисленных параметров n, k, причем 0  k  n.

Теорема 3.1. Пусть для любых n и k,  0  k  n справедливы зависимости  и пусть существуют такие числа n,k,i, что для любых       k  n и m  n выполняются равенства

Тогда для всех k  n имеет место формула обращения:

.

Доказательство.

= == bn,k,

что и требовалось доказать.

2.2. Примеры использования формулы обращения. Зависимость между числами n,k,i и n,k,i, фигурирующая в условиях теоремы 3.1, по сути означает, что эти числа образуют систему взаимно обратных матриц, т.е. смысл теоремы весьма прост, если не сказать – тривиален. Для произвольных чисел an,k и bn,k она не дает никакой ценной информации, поскольку найти требуемые числа n,k,i в общем случае столь же трудно, как и решить исходную систему уравнений относительно bn,k. Однако, для многих специальных случаев, в частности, комбинаторных чисел, удается найти n,k,i в явном виде. В этом особенность данной формулы. Рассмотрим ее применение для обращения биномиальных коэффициентов.

Лемма 3.1.   

Доказательство. Имеем:

=  =

=  = .

Следовательно,

= = В.

Так как при k < 0 и при k > n , то в полученном выражении можно суммировать не от i = 0, i = m. То есть

В = = .

Но при m < n имеем:

=  = 0.

Последнее равенство следует из свойства 5 чисел сочетания.

А при m = n имеем:

=  = 1,

что и требовалось доказать.

Теорема 3.2. Если , то  .

Доказательство. Здесь  и  . При k  n, m  n имеем:

= = = =

Это означает, что выполнены условия теоремы 3.1, а, следовательно, теорема доказана.

Теорема 3.3. Если , то  .

Доказательство аналогично.

3. Рекуррентные соотношения

В комбинаторных задачах искомым решением часто является числовая последовательность u1, u2, …, un, … Например, если мы ищем число подмножеств m-элементного множества, то . В данном разделе рассмотрим ситуацию, при которой свойства членов искомой последовательности определяются некоторым рекуррентным соотношением, которому удовлетворяют числа un:

un + k + b1 un + k – 1 + b2 un + k – 2 +…+ bk un = 0,                  (3.6)

где b1, b2, …, bk – некоторые коэффициенты. Выражение (3.6) называется еще разностным линейным уравнением k-го порядка с постоянными коэффициентами.

Одной из наиболее известных последовательностей, задаваемых линейным рекуррентным соотношением, является последовательность Фибоначчи {Fn}, определяемая следующими условиями: F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn. Отсюда получаем    F2 = 1; F3 = 2; F4 = 3; F5 = 5; F6 = 8 и т.д.

Воспользовавшись уравнением (2.8) всегда можно вычислить значения un для любых n, если знать первые k членов последовательности. Однако, часто необходимо знать явную формулу для вычисления un.

Теорема 3.4. Пусть 1, 2,…, s – корни соответствующих кратностей m1, m2,…, ms характеристического уравнения для выражения (3.6):

k + b1 k–1 + b2 k–2 +…+ bk  = 0                                 (3.7)

Тогда общее решение уравнения (3.6) определяется по формуле:

un = ( C11 + C12 n + C13n2 + … + )+

( C21 + C22 n + C23n2 + … + )+ …               (3.8)

( Cs,1 + Cs,2 n + Cs,3n2 + … + ),

где C11,…, – константы (их число равно k), определяемые начальными условиями.

Пример 3.3. Решим уравнение Фибоначчи Fn+2Fn+1Fn = 0.  Его характеристическое уравнение имеет вид:  2 – 1 = 0. Корни равны – некратные. Обозначим Ф1 = 1  1.618; Ф2 = 2  – 0.618. Общее решение равно:

.

Из начальных условий F0 = 0; F1 = 1 получаем систему уравнений для вычисления С1 и С2 = 1:

.

Отсюда С1 = – С2 = .

Использование рекуррентных соотношений дает эффективный метод решения многих комбинаторных задач.

Пример 3.4. Найти число бинарных n-последовательностей, в которых никакие две единицы не стоят рядом.

Решение. Обозначим:

zn – число искомых последовательностей;

хn – число последовательностей, заканчивающихся 0;

уn – число последовательностей, заканчивающихся 1.

Назовем для краткости последовательность, заканчивающуюся 0 – х-последовательностью, а заканчивающихся 1 – у-последовательностью.

Очевидны следующие их свойства.

1) х-последовательность длиной n можно получить, приписав 0 в конец либо у-последовательности либо х-последовательности  длиной n – 1.

2) у-последовательность длиной n можно получить, приписав 1 только в конец х-последовательности длиной n – 1.

Отсюда имеем следующую систему уравнений:

.

Уравнение (a) отражает свойство 1), уравнение (b) – свойство 2), а уравнение (а) соответствует очевидному равенству.

Из уравнения (b) при замене n на  n – 1 имеем: уn–1 = хn–2.

Подставим это равенство в (a), получим: хn = хn–1 + хn–2, т.е. числа хn образуют последовательность Фибоначчи. Вычтем (b) из (a), получим:

хn – уn = уn–1    хn = уn + уn–1    уn+1 = уn + уn–1

– тоже последовательность Фибоначчи. В соответствие с формулой общего решения и уравнением (c) получим:

.

Для нахождения констант запишем начальные условия. z1 = 2, т.к. существует  2 последовательности длиной 1: 0 и 1. z2 = 3, т.к. существует 3 последовательности длиной 2: (0 0), (0 1), (1 0). Отсюда ; .  Следовательно

.

Например, z9 = 89,  z19 = 10946.

4. Производящие функции

4.1. Определение производящих функций. Последовательности {un}, фигурирующей в какой-либо задаче, например, комбинаторной, удобно поставить в соответствие формальный степенной ряд

u(x) = ,

который называется производящей функцией данной последовательности. Слова “формальный ряд” означает, что эту формулу мы трактуем только как удобную запись последовательности. Для нас сейчас несущественно, при каких значениях х ряд сходится и сходится ли вообще, т.к. вычислять значение u(x) мы никогда не будем.

Пример 3.5. Известно, что  = 1 + х + х2 + … + хn + … Следовательно, функция  является производящей для последовательности 1,…, 1.

Пример 3.6. Согласно формуле бинома Ньютона (1 + х)n = . Следовательно, функция (1 + х)n является производящей для конечной последовательности .

4.2. Операции с производящими функциями. Рассмотрим основные технические приемы, применяемые в работе с производящими функциями.

4.2.а. Линейная комбинация. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функция au(x) + bv(x) (a и b – константы) является производящей для последовательности { aun + bvn}.

4.2.б. Сдвиг. Если функция u(x) соответствует последовательности {un}, то функции хmu(x) соответствует последовательность … – сдвиг вправо.

Аналогично, функция  является производящей для последовательности um, um+1, … – сдвиг влево.

4.2.в. Умножение.  Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функции u(x)v(x) соответствует последовательность {wn}, где

– формула Коши.  Например,  w0 = u0v0; w1 = u0 v1 + u1 v0;         w2 = u0 v2 + u1 v1 + u2 v0.

Пример 3.7. Пусть u(x) соответствует последовательности {un}, а v(x) =  – производящая функция для последовательности 1,…, 1 (см. пример 3.5). Тогда функция

= u0 + (u0 + u1) x + (u0 + u1 + u2) x2 +…                    (3.9)

является производящей для последовательности частичных сумм.

4.2.г. Дифференцирование и интегрирование.  Если u(x) соответствует последовательности {un}, то по правилу дифференцирования рядов

u(x) = 0 + u1 + 2 u2 x + 3 u3 x2 + ….

То есть u(x) является производящей функцией для последовательности {k uk}.

Аналогично . То естьявляется производящей функцией для последовательности .

Пример 3.8.  = . Следовательно, функция  является производящей для последовательности {k}.

Далее,

                   (3.10)

Следовательно,  является производящей функцией для последовательности .

Сопоставляя (3.10) с (3.9) получаем

,

где  – гармонические числа.

4.3. Пример использования производящих функций

Решим с помощью производящих функций следующую комбинаторную задачу.

Пример 3.9. На окружности находится 2n точек. Сколькими способами можно их попарно соединить так, чтобы полученные отрезки не соединялись друг с другом?

Решение. Обозначим un – число способов соединить 2n точек. Построим рекуррентное соотношение.

Формально положим u0 = 1 (нет точек, нет пересечений, следовательно, способ единственный). u1 = 1 – очевидно, т.к. две точки соединяются единственным способом, и пересечений нет. u2 = 2. Способы соединения изображены на рис. 3.1.

Пусть n > 1. Выберем одну из 2(n + 1) точек, обозначим ее А. Соединим А с вершиной В, выбрав ее так, чтобы с обеих сторон от соединяющей их линии находилось четное число точек. Пусть слева будет 2k точек, справа – 2(nk). 2k точек можно соединить между собой uk способами, 2(nk) точек – unk способами. При этом линии не пересекутся, т.к. 2k и 2(nk) точек расположены по разные сторона от АВ.

Следовательно, при фиксированном k получим ukunk способов соединения. Но k меняется от 0 до n. Следовательно,

un +1 = u0un + u1un–1 + … + unu0.                       (3.11)

Получили искомое нелинейное рекуррентное соотношение, формула общего решения которого нам, к сожалению, неизвестна.

Чтобы получить явную формулу для un, построим для этой последовательности производящую функцию.

u(x) = u0 + u1х + u2 x2 + u3 x3 + ….                     (3.12)

Имеем, согласно формуле Коши:

[ u(x) ]2 = (u0)2 + (u0u1 + u1u0 ) х + (u0u2 + u1u1 + u2u02 + …

Видно, что коэффициенты для разложения [ u(x) ]2 можно получить с помощью формулы (3.11).

Из (3.12) имеем: = u1 + u2 x + u3 x2 + ….

Подставим в эту формулу выражение uk согласно (3.11). С учетом того, что u1 = (u0)2 получим: . Следовательно, имеем квадратное уравнение относительно u(х). Решив его, получим .

По формуле бинома имеем:

++…= 1 –.

Умножим каждое k-е слагаемое на 1 = . Тогда коэффициент k-го члена ряда равен:

 =  =   = .

Отсюда

.

Для того, чтобы коэффициенты ряда были положительными, надо перед корнем в формуле u(x) брать знак “–”. Заменим индекс суммирования k на k +1. В результате получим:

u(x) = == .

Окончательно – это так называемые, числа Каталана.

5. Связь производящих функций с линейными рекуррентными

соотношениями

Пусть имеем дробно-рациональную функцию

f(x) = = ,

которая разлагается в ряд f0 + f1x + f2 x + …. Отсюда A(x) = B(x)f(x). Подставим вместо f(х) ее ряд – получим систему уравнений:

b0 f0  =  a0;

b0 f1 + b1 f0 =  a1;

b0 f2 + b1 f1 + b2 f0  =  a2;

………………………..

b0 fm –1 + b1 fm –2 +… + bm –1 f0  =  am – 1;

b0 fm + b1 fm –1 +… + bm f0 = 0;

………………………………..

b0 fm + n + b1 fm –1 + n +… + bm fn  =  0;

……………………………

Во всех уравнениях, начиная с m+1-го, правая часть равна 0, т.к. am + 1 = … = am + n =…= 0. Следовательно, имеем линейное рекуррентное соотношение

b0 fm + n + b1 fm –1 + n +… + bm fn = 0,                           (3.13)

которому удовлетворяют члены ряда для функции f(x). Таким образом, мы получили теорему о связи производящих функций с линейными рекуррентными соотношениями:

Теорема 3.5. Для того, чтобы производящая функция числовой последовательности была правильной рациональной дробью необходимо и достаточно, чтобы члены этой последовательности удовлетворяли линейному рекуррентному соотношению, характеристическое уравнение  которого совпадает со знаменателем этой дроби, записанным в обратном порядке.

Пример 3.10. Найдем производящую функцию для чисел Фибоначчи.

Решение. Имеем рекуррентное соотношение: Fn+2F n+1Fn = 0. Следовательно, f(x) = . A и В легко найти с помощью деления многочленов:

Следовательно, 0 = F0 = B; 1 = F1 = A + B, т.е. В = 0; А = 1 или .

Литература

1. Новиков Ф.А, Дискретная математика для программистов. – Санкт-Петербург: Питер, 2004. – 304 с.

2. Липский В.  Комбинаторика для программистов.  М.:  Мир, 1988,- 213 С.

3. Комбинаторика. [Компьют] : Учеб. пособие – 2 файла (Комб_1_пособ, Комб_2_пособ)


 

А также другие работы, которые могут Вас заинтересовать

37721. Специфікування предметної галузі проекту засобами мови uml. Кількісна оцінка діаграм 108 KB
  кількісна оцінка діаграм Мета: дослідження класів та отримання навиків у побудові діаграми класів UML для специфікування предметної галузі використання стереотипів UML та структурування моделі UML за допомогою пакетів. Опис класів. Побудова діаграми класів Діаграма класів Clss digrm призначена для відображення статичної структури ПЗ проекту що проектується. Діаграма містить класи і взаємозв’язки між ними та дозволяє описати їх структуру та типи відношень.
37722. ІМПІЧМЕНТ (АМЕРИКАНСЬКА ЗА ПОХОДЖЕННЯМ МОДЕЛЬ) 99.5 KB
  Тема даної роботи досить актуальна, адже складність процедури імпічменту зумовлює те, що в історії відбувалися лише окремі успішні випадки відсторонення посадових осіб з посад, а імпічмент главі держави вважається резонансною подією.
37723. Подготовка изображений для WEB 3.35 MB
  Изображения в сети также важны как и в любом печатном издании. Изображения должны быть правильно отмасштабированы иметь хорошую четкость и сохранены в цветовом пространстве sRGB. Поэтому для получения хороших результатов при сайтостроительстве нужно корректно отмасштабировать изображения перед помещением их в сеть. В Интернет используются изображения с цветовым пространством sRGB.
37724. Создание Форм В INKSCAPE 874 KB
  Для этого щелкните по верхней линейке и перетащите вниз чтобы создать горизонтальную направляющую и щелкните по левой линейке и перетащите вправо чтобы создать вертикальную направляющую см. Выберите инструмент Рисовать круги эллипсы и дуги F5 и щелкните на значке Заливка в правом верхнем углу. Щелкните правой кнопкой мышки на круг и нажмите Продублировать CtrlD. Затем в окне трансформации установите 80 в поле Ширина и щелкните по кнопке pply.
37725. Создание трехмерного Текста в Inkscape 787 KB
  Выберите инструмент Создавать и править текстовые объекты F8 и введите на лист Вашу фамилию. Теперь добавим эффект перспективы к тексту и придадим трехмерность. Инструментом Выделять и трансформировать объекты F1 можно нажать пробел выделите текст и выполните команду Контуры Оконтурить объект ShiftCtrlС.
37726. ВИМІРЮВАННЯ ПАРАМЕТРІВ ІМПУЛЬСНИХ СИГНАЛІВ МЕТОДОМ ДИСКРЕТНОГО РАХУНКУ 132 KB
  ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Методи вимірювання частоти і інтервалів часу різноманітні. Застосовуються методи безпосереднього вимірювання методи засновані на порівнянні частоти зі зразковою частотою за допомогою осцилографа гетеродинний нульове биття і резонансний методи. Метод вимірювання Вхідний сигнал В Відносна нестабільність частоти кварцового ген. Похибка вимірювання частоти Електродинамічний логометричний частотомір 36 127 220 __  1.
37727. Программирование на ассемблере MASM32. Изучение среды разработки RADasm и отладчика OllyDbg 584.5 KB
  Они необходимы программе для обработки и хранения в памяти команд и данных а также получения информации о собственном текущем состоянии и состоянии процессора.1: пространство адресуемой памяти до 2х в 32й степени байт 4 Гбайт для Pentium II и выше до 2х в 36 степени байт 64 Гбайт; регистры для хранения данных общего назначения; сегментные регистры; регистры состояния и управления; регистры устройства вычислений с плавающей запятой сопроцессора; набор регистров целочисленного MMXрасширения отображенных на регистры...
37728. Исследование линейных электрических цепей постоянного тока 309.11 KB
  1 ток в цепи и падения напряжения на участках цепи определяются по закону Ома: Разветвленная цепь с одним источником э. Сущность метода наложения основывается на принципе суперпозиции заключающегося в том что ток в отдельной ветви линейной разветвленной цепи равен алгебраической сумме...
37729. ИССЛЕДОВАНИЕ РАЗВЕТВЛЕНОЙ ЛИНЕЙНОЙ ЭЛЕКТРИЧЕСКОЙ ЦЕПИ ПОСТОЯННОГО ТОКА 48 KB
  1 за точные то абсолютная погрешность метода эквивалентного генератора таб.4 по сравнению с этими данными для тока I3 составляет 14 мА а абсолютная погрешность при использовании принципа наложения таб.3 мА так как данный ток будет течь в противоположную сторону по сравнении с указанным на схеме при включенном Е2 абсолютная погрешность составляет 34. Таким образом общая абсолютная погрешность для тока I3 составит 3.