Комбинаторика |
Комбинаторика
Скачать презентацию |
||
<< Остовное дерево | Комбинаторика 9 класс >> |
Автор: Joseph V Romanovsky. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Комбинаторика.ppt» со всеми картинками в zip-архиве размером 143 КБ.
Скачать презентациюСл | Текст | Сл | Текст |
1 | Дискретный анализ. Комбинаторика. Перестановки. | 13 | 2. Выпишем несколько следующих перестановок. (4, 2, 1, 7, 5, 3, |
2 | Перестановки. Пусть задано множество из n элементов. | 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, | |
Упорядочение этих элементов называется перестановкой. Иногда | 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, | ||
добавляют «из n элементов». Обычно выделяется одно, основное или | 6, 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, | ||
естественное, упорядочение, которое называется тривиальной | 5, 1, 6, 7). | ||
перестановкой. Сами элементы множества A нас не интересуют. | 14 | Формальное описание алгоритма. Рабочее состояние: | |
Часто в качестве элементов берут целые числа от 1 до n или от 0 | Перестановка p и булев признак isActive. Начальное состояние: В | ||
до n-1. Обозначим множество перестановок из n элементов через Pn | записана тривиальная перестановка и isActive = True. Стандартный | ||
, а его мощность через Pn. Зададим все те же три вопроса: чему | шаг: Если isActive, выдать перестановку в качестве результата. | ||
равно Pn, как перебрать элементы Pn , как их перенумеровать. | Двигаясь с конца, найти в перестановке наибольший монотонно | ||
3 | Теорема о числе перестановок. Число перестановок из n | убывающий суффикс. Пусть k – позиция перед суффиксом. Положить | |
элементов равно n! - произведению чисел от 1 до n. (n! читается | isActive := (k > 0). Если isActive, то найти в суффиксе | ||
n–факториал) Доказательство. По индукции. Для n=1 формула | наименьший элемент, превосходящий pk, поменять его местами с pk, | ||
очевидно верна. Пусть она верна для n-1, докажем, что она верна | а потом суффикс «перевернуть». | ||
и для n. Первый элемент упорядочения можно выбрать n способами, | 15 | Еще алгоритм перебора перестановок. Попробуем теперь | |
а к выбранному первому элементу можно способами приписать | перебрать перестановки так, чтобы две последовательные | ||
остальное. Поэтому верна формула Pn= Pn-1?n. Если Pn-1=(n-1)!, | перестановки мало отличались друг от друга. Насколько мало? На | ||
то Pn=n! | одну элементарную транспозицию, в которой меняются местами два | ||
4 | Нумерация перестановок. Чтобы нумеровать перестановки, мы | соседних элемента. Возможно ли это? Покажем принципиальную схему | |
отобразим множество Pn взаимнооднозначно в другое множество Tn, | такого алгоритма, нам будет интересна именно она. Представьте | ||
на котором ввести нумерацию будет гораздо проще, а затем для | себе n-1 элементарных «механизмов», каждый из передвигает свой | ||
любого элемента p?Pn в качестве его номера возьмем номер его | элемент внутри набора. На каждом шаге механизм делает сдвиг | ||
образа в Tn. Множество Tn– это прямое произведение нескольких | налево или направо. Направление меняется, когда элемент доходит | ||
числовых отрезков Tn =(0:(n-1))?(0:(n-2)? … ?{0}. Т.е. каждый | до края. На смену направления тратится один шаг, во время | ||
элемент Tn– это набор неотрицательных чисел i1, i2, …, in-1, in, | которого шаг делает следующий механизм, который, впрочем, тоже | ||
причем ik?n-k. | может менять направление. | ||
5 | Отображение. Возьмем перестановку и выпишем рядом с ней | 16 | Еще алгоритм перебора перестановок -2. Посмотрим пример. 1 2 |
тривиальную перестановку. В качестве первого индекса возьмем | 3 4 5 Чей ход 1 2 3 4 5 Чей ход a b c d e a c d a b e a b a c d | ||
место первого элемента (считая от нуля) в тривиальной | e a c d b a e a b c a d e a c d b e a b b c d a e a c d e b a a | ||
перестановке. Запишем вместо тривиальной перестановки строку | b c d e a b c d e a b a c b d e a a c d a e b a c b d a e a c a | ||
оставшихся символов. В качестве второго индекса возьмем место | d e b a c b a d e a a c d e b c c a b d e a a d c e b a a c b d | ||
второго элемента перестановки в этой строке. Повторим процесс до | e b d a c e b a a c d b e a d c a e b a c a d b e a d c e a b a. | ||
конца. Очевидно, что k–й индекс будет меньше длины k–й строки, а | 17 | Перебор перестановок. 1. function ExistsNextPerm(var kCh: | |
последний индекс будет равен нулю. Посмотрим этот процесс на | integer): Boolean; var iV,iP,iVC,iPC: integer; begin result := | ||
примере. | False; for iV := nV downto 2 do if count[iV] < iV-1 then | ||
6 | Пример отображения. 0 1 2 3 4 5 6 Индекс c a d f g b e a b c | begin Inc(count[iV]); iP := pos[iV]; iPC := iP+dir[iV]; iVC := | |
d e f g 2 2 a d f g b e a b d e f g 0 2 0 d f g b e b d e f g 1 | perm[iPC]; perm[iP] := iVC; perm[iPC] := iV; pos[iVC] := iP; | ||
2 0 1 f g b e b e f g 2 2 0 1 2 g b e b e g 2 2 0 1 2 2 b e b e | pos[iV] := iPC; kCh := iP; if dir[iV] < 0 then Dec(kCh); | ||
0 2 0 1 2 2 0 e e 0 2 0 1 2 2 0 0 Очевидно, что этот процесс | result := True; exit; end else begin count[iV] := 0; dir[iV] := | ||
обратим и обратное отображение построит по набору индексов | - dir[iV]; end; end; | ||
исходную перестановку. | 18 | Задача о минимуме суммы попарных произведений. Пусть заданы | |
7 | Нумерация множества Tn. Любое прямое произведение | два набора по n чисел, скажем, {ak|k?1:n} и {bk|k?1:n} . Эти | |
упорядоченных множеств можно рассматривать как систему счисления | числа разбиваются на пары (ak,bk) и вычисляется сумма их | ||
с переменным основанием. Вспомните пример с секундами из первой | попарных произведений ?k?1:n akbk. Можно менять нумерацию {ak} и | ||
лекции или рассмотрите какую-либо старую шкалу размеров: 1 ярд = | {bk}. Требуется выбрать такую нумерацию, при которой сумма | ||
3 фута, 1 фут = 12 дюймов, 1 дюйм = 12 линий, 1 линия = 6 | минимальна. В этой задаче можно зафиксировать какие-то нумерации | ||
пунктов. (2, 0, 4, 2, 3) = 2 ярда 0 футов 4 дюйма 2 линии 3 | {ak} и {bk} и искать перестановку ?, для которой достигается | ||
пункта, сколько же это пунктов? Нужно сосчитать (это называется | минимум суммы ?k?1:n akb?(k). Мы выберем нумерации, когда {ak} | ||
схемой Горнера) (((2 ? 3+0) ? 12+4) ? 12+2) ? 6+3. | расположены по возрастанию, а {bk} – по убыванию. | ||
8 | Нумерация множества Tn - 2. Формулу #, находящую номер для | 19 | Теорема о минимуме суммы попарных произведений. Минимум |
набора индексов i1, i2, …, in-1, in, мы предпочтем написать в | суммы попарных произведений достигается на тривиальной | ||
виде рекуррентных выражений #(i1, i2, …, in) = a(i1, i2, …, | перестановке. Доказательство. Предположим, что существуют такие | ||
in-1,n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ | два индекса k и r, что ak < ar и bk < br . В этом случае | ||
ik; a(пусто,0) = 0; По этой формуле #(2,0,1,2,2,0,0) = | (ar?ak)(br ?bk) > 0, т.е. ar br + ak bk > ar bk + ak br . | ||
a(2,0,1,2,2,0,6). Имеем a(2,1)=2; a(2,0,2) = 2?6+0=12; | В нашей нумерации {ak} расположены по возрастанию. Если {bk} | ||
a(2,0,1,3)=12?5+1=61; a(2,0,1,2,4) =61?4+2=246; a(2,0,1,2,2,5) | расположены не по возрастанию, то найдется такая пара k и r, как | ||
=246?3+2=740; a(2,0,1,2,2,0,6) =740?2+0=1480; | сказано выше. Переставив у этой пары bk и br , мы уменьшим | ||
9 | Перебор наборов индексов. Исходя из вышеизложенного, | значение суммы. Значит, в оптимальном решении {bk} стоят по | |
перебрать перестановки просто: нужно перебрать все наборы | возрастанию. Эта простая теорема несколько раз встретится нам в | ||
индексов из и по каждому набору строить соответствующую ему | дальнейшем. | ||
перестановку. Для перебора наборов индексов заметим, что | 20 | Задача о максимальной возрастающей подпоследовательности. | |
фактически каждый набор – это запись числа в особой системе | Задана последовательность {ak|k?1:n} чисел длины n. Требуется | ||
счисления с переменным основанием (система называется | найти ее последовательность наибольшей длины, в которой числа | ||
факториальной). Правила прибавления 1 в этой системе почти так | {ak} шли бы в возрастающем порядке. Например, в | ||
же просты, как в двоичной: двигаясь от последнего разряда | последовательности 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, | ||
пытаться прибавить в текущем разряде 1. Если это возможно, то | 41, 12, 7, 9 максимальной будет подпоследовательность 2, 11, 14, | ||
прибавив 1 остановиться. Если невозможно, записать в разряд нуль | 16, 17, 25, 37, 41 С перестановками эта задача связана тем, что | ||
и перейти к следующему разряду. | исходная последовательность может быть перестановкой. Мы | ||
10 | Перебор наборов индексов - 2. Рассмотрим пример: 7 6 5 4 3 2 | ограничимся тем, что покажем, как решается эта задача, а | |
1 Это переменные основания 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Обратите | формализацию и обоснование алгоритма предоставим слушателям. | ||
внимание, что в 3 4 4 2 2 1 0 каждой строке начало такое 3 4 4 3 | 21 | Нахождение максимальной возрастающей подпоследовательности. | |
0 0 0 же, как в предыдущей, 3 4 4 3 0 1 0 затем идет элемент, | Будем по возможности экономно разбивать нашу на убывающие | ||
строго 3 4 4 3 1 0 0 больший, . . . , а 3 4 4 3 1 1 0 дальнейшее | последовательности (пример изменен) 9 12 11 14 18 16 6 17 15 13 | ||
не существенно. 3 4 4 3 2 0 0 Значит, каждая строка 3 4 4 3 2 1 | 37 19 21 8 7 5 9 6 5 12 11 8 7 14 13 18 16 15 17 37 19 21 Каждое | ||
0 лексикографически больше 3 5 0 0 0 0 0 предыдущей. 3 5 0 0 0 1 | следующее число пишется в самую верхнюю из строчек, где оно не | ||
0. | нарушит порядка. Возьмем число из нижней строчки, 21. Почему оно | ||
11 | Теорема о лексикографическом переборе перестановок. | стоит в 8-й строчке? Ему мешает 19. А числу 19 мешает 17. А ему | |
Описанный алгоритм перебирает перестановки в порядке | 16. И т. д. Последовательность 9, 11, 14, 16, 17, 19, 21 | ||
лексикографического возрастания. Доказательство. Нам достаточно | возрастает и имеет длину 7. Любая последовательность большей | ||
показать, что если мы имеем два набора индексов I1 и I2, и I1 | длины содержит два числа из одной строки (принцип Дирихле) и не | ||
лексикографически предшествует I2, то перестановка ?(I1) | может быть возрастающей. | ||
лексикографически предшествует ?(I2). Эти перестановки | 22 | Задача о минимальном числе инверсий. Задана | |
формируются последовательно, и пока совпадают I1 и I2, совпадают | последовательность {ak|k?1:n} чисел длины n. Инверсией назовем | ||
и их перестановки. А большему значению индекса соответствует и | выполняемое на месте зеркальное отражение какой-либо ее | ||
больший элемент. | подстроки – сплошной подпоследовательности.Требуется за | ||
12 | Прямой алгоритм лексикографического перебора перестановок. | минимальное число инверсий расположить элементы | |
Возьмем какую-либо перестановку p и прямо найдем | последовательности по возрастанию. Например, перестановку | ||
лексикографически следующую. Возьмем начало – первые k | «сплошная» можно преобразовывать так (красные буквы | ||
элементов. Среди его продолжений известны минимальное, в котором | переставлены, большие уже стоят на месте) сплошнаЯ сплоанШЯ | ||
все элементы расположены по возрастанию, и максимальное, в | наолПСШЯ АнолПСШЯ АнлОПСШЯ АЛНОПСШЯ (за пять инверсий). | ||
котором по убыванию. Например, в перестановке p =(4, 2, 1, 7, 3, | 23 | Экзаменационные вопросы. Перестановки. Их перебор и | |
6, 5) все продолжения для (4, 2, 1) лежат между (3, 5, 6, 7) и | нумерация. Задача о минимуме скалярного произведения. Задача о | ||
(7, 6, 5, 3). Имеющееся продолжение меньше максимального, и 3-й | наибольшей возрастающей подпоследовательности. | ||
элемент еще можно не менять. И 4-й тоже. А 5-й нужно сменить. | 24 | Задание. 1. Двусторонний переход перестановка ? число 2. | |
Для этого из оставшихся элементов нужно взять следующий по | Найти перестановку, отстоящую от данной на данное число шагов. | ||
порядку, поставить его 5-м и приписать минимальное продолжение. | 3. Перебор перестановок элементарными транспозициями. 4. | ||
Получится (4, 2, 1, 7, 5, 3, 6). | Выполнить пример для задачи о минимуме скалярного произведения. | ||
13 | Прямой алгоритм лексикографического перебора перестановок - | ||
«Перестановки элементов» | Комбинаторика.ppt |
«Системы счисления» - Перевод из двоичной системы счисления в восьмеричную и шестнадцатеричную. Десятичная система счисления. Позиционные системы счисления. Системы счисления. Перевод из десятичной системы счисления в двоичную вычитанием степеней двойки. Позиция цифры в числе называется ее разрядом, а количество цифр в числе его разрядностью.
«Перестановки элементов» - Нумерация множества. Отображение. Задача о минимуме скалярного произведения. Комбинаторика. Задача о наибольшей возрастающей подпоследовательности. Экзаменационные вопросы. Теорема о лексикографическом переборе перестановок. Перебор перестановок элементарными транспозициями. Прямой алгоритм лексикографического перебора перестановок.
«Производная функции» - Найдите производные функций. Разностное отношение. Приращение функции. Задания. Формулы для вычисления производных. Правила вычисления производных. Производная. Приращение аргумента.
«Изобретатель логарифма» - Основное логарифмическое тождество. Возведение в степень имеет два обратных действия. Определение логарифма можно записать так: a log a b = b. Логарифмы были придуманы для ускорения и упрощения вычислений. Правильное решение примеров. Логарифмы и их свойства. Для чего были придуманы логарифмы? Орпеделение.
«Логарифмические функции» - Логарифм частного. В зависимости от значения основания приняты два обозначения. Свойства функции. Решение логарифмических неравенств. Если основанием является 10, то вместо log10 x пишут lg x. Переход от одного показателя к другому. Свойства натуральных логарифмов. Свойства логарифмов. Решения логарифмических уравнений.
«Нахождение производной» - Работа по учебнику. Пользуясь определением производной, найдите производную функции в точке х. Алгоритм нахождения производной. Найдите значение выражения. Алгоритм нахождения производной.