Комбинаторика

Комбинаторика Скачать презентацию
<< Остовное дерево		Комбинаторика 9 класс >>

Дискретный анализ	Перестановки	Теорема о числе перестановок	Нумерация перестановок	Отображение
Пример отображения				Нумерация множества Tn
Нумерация множества Tn - 2	Перебор наборов индексов	Перебор наборов индексов - 2	Теорема о лексикографическом переборе перестановок	Прямой алгоритм лексикографического перебора перестановок
Прямой алгоритм лексикографического перебора перестановок - 2	Формальное описание алгоритма	Еще алгоритм перебора перестановок	Еще алгоритм перебора перестановок -2	Перебор перестановок
Задача о минимуме суммы попарных произведений	Теорема о минимуме суммы попарных произведений	Задача о максимальной возрастающей подпоследовательности	Нахождение максимальной возрастающей подпоследовательности	Задача о минимальном числе инверсий
Экзаменационные вопросы	Задание

Картинки из презентации «Комбинаторика» к уроку алгебры на тему «Комбинаторика»

Автор: Joseph V Romanovsky. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Комбинаторика.ppt» со всеми картинками в zip-архиве размером 143 КБ.

Скачать презентацию

Комбинаторика

содержание презентации «Комбинаторика.ppt»

Сл	Текст	Сл	Текст
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

http://900igr.net/kartinki/algebra/Kombinatorika/Perestanovki-elementov.html

cсылка на страницу

Комбинаторика

другие презентации о комбинаторике

«Системы счисления» - Перевод из двоичной системы счисления в восьмеричную и шестнадцатеричную. Десятичная система счисления. Позиционные системы счисления. Системы счисления. Перевод из десятичной системы счисления в двоичную вычитанием степеней двойки. Позиция цифры в числе называется ее разрядом, а количество цифр в числе его разрядностью.

«Перестановки элементов» - Нумерация множества. Отображение. Задача о минимуме скалярного произведения. Комбинаторика. Задача о наибольшей возрастающей подпоследовательности. Экзаменационные вопросы. Теорема о лексикографическом переборе перестановок. Перебор перестановок элементарными транспозициями. Прямой алгоритм лексикографического перебора перестановок.

«Производная функции» - Найдите производные функций. Разностное отношение. Приращение функции. Задания. Формулы для вычисления производных. Правила вычисления производных. Производная. Приращение аргумента.

«Изобретатель логарифма» - Основное логарифмическое тождество. Возведение в степень имеет два обратных действия. Определение логарифма можно записать так: a log a b = b. Логарифмы были придуманы для ускорения и упрощения вычислений. Правильное решение примеров. Логарифмы и их свойства. Для чего были придуманы логарифмы? Орпеделение.

«Логарифмические функции» - Логарифм частного. В зависимости от значения основания приняты два обозначения. Свойства функции. Решение логарифмических неравенств. Если основанием является 10, то вместо log10 x пишут lg x. Переход от одного показателя к другому. Свойства натуральных логарифмов. Свойства логарифмов. Решения логарифмических уравнений.

«Нахождение производной» - Работа по учебнику. Пользуясь определением производной, найдите производную функции в точке х. Алгоритм нахождения производной. Найдите значение выражения. Алгоритм нахождения производной.

Урок