Презентация «Дискретный анализ Комбинаторика. Перестановки»

Смотреть слайды в полном размере
Презентация «Дискретный анализ Комбинаторика. Перестановки»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 24 слайда и доступен в формате ppt. Размер файла: 216.00 KB

Просмотреть и скачать

Pic.1
Дискретный анализ Комбинаторика. Перестановки
Дискретный анализ Комбинаторика. Перестановки
Pic.2
Перестановки Пусть задано множество из n элементов. Упорядочение этих элементов называется перестано
Перестановки Пусть задано множество из n элементов. Упорядочение этих элементов называется перестановкой. Иногда добавляют «из n элементов». Обычно выделяется одно, основное или естественное, …
Pic.3
Теорема о числе перестановок Число перестановок из n элементов равно n! - произведению чисел от 1 до
Теорема о числе перестановок Число перестановок из n элементов равно n! - произведению чисел от 1 до n. (n! читается n–факториал) Доказательство. По индукции. Для n=1 формула очевидно верна. Пусть …
Pic.4
Нумерация перестановок Чтобы нумеровать перестановки, мы отобразим множество Pn взаимнооднозначно в
Нумерация перестановок Чтобы нумеровать перестановки, мы отобразим множество Pn взаимнооднозначно в другое множество Tn, на котором ввести нумерацию будет гораздо проще, а затем для любого элемента …
Pic.5
Отображение Возьмем перестановку и выпишем рядом с ней тривиальную перестановку. В качестве первого
Отображение Возьмем перестановку и выпишем рядом с ней тривиальную перестановку. В качестве первого индекса возьмем место первого элемента (считая от нуля) в тривиальной перестановке. Запишем вместо …
Pic.6
Пример отображения 0 1 2 3 4 5 6 Индекс c a d f g b e a b c d e f g 2 2 a d f g b e a b d e f g 0 2
Пример отображения 0 1 2 3 4 5 6 Индекс c a d f g b e a b c 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 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 0 2 0 1 2 2 …
Pic.7
Нумерация множества Tn Любое прямое произведение упорядоченных множеств можно рассматривать как сист
Нумерация множества Tn Любое прямое произведение упорядоченных множеств можно рассматривать как систему счисления с переменным основанием. Вспомните пример с секундами из первой лекции или …
Pic.8
Нумерация множества Tn - 2 Формулу #, находящую номер для набора индексов i1, i2, …, in-1, in, мы пр
Нумерация множества Tn - 2 Формулу #, находящую номер для набора индексов i1, i2, …, in-1, in, мы предпочтем написать в виде рекуррентных выражений #(i1, i2, …, in) = a(i1, i2, …, in-1,n-1); a(i1, …
Pic.9
Перебор наборов индексов Исходя из вышеизложенного, перебрать перестановки просто: нужно перебрать в
Перебор наборов индексов Исходя из вышеизложенного, перебрать перестановки просто: нужно перебрать все наборы индексов из и по каждому набору строить соответствующую ему перестановку. Для перебора …
Pic.10
Перебор наборов индексов - 2 Рассмотрим пример: 7 6 5 4 3 2 1 Это переменные основания 3 4 4 2 1 1 0
Перебор наборов индексов - 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 0 0 0 же, …
Pic.11
Теорема о лексикографическом переборе перестановок Описанный алгоритм перебирает перестановки в поря
Теорема о лексикографическом переборе перестановок Описанный алгоритм перебирает перестановки в порядке лексикографического возрастания. Доказательство. Нам достаточно показать, что если мы имеем два …
Pic.12
Прямой алгоритм лексикографического перебора перестановок Возьмем какую-либо перестановку p и прямо
Прямой алгоритм лексикографического перебора перестановок Возьмем какую-либо перестановку p и прямо найдем лексикографически следующую. Возьмем начало – первые k элементов. Среди его продолжений …
Pic.13
Прямой алгоритм лексикографического перебора перестановок - 2 Выпишем несколько следующих перестанов
Прямой алгоритм лексикографического перебора перестановок - 2 Выпишем несколько следующих перестановок. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, …
Pic.14
Формальное описание алгоритма Рабочее состояние: Перестановка p и булев признак isActive. Начальное
Формальное описание алгоритма Рабочее состояние: Перестановка p и булев признак isActive. Начальное состояние: В записана тривиальная перестановка и isActive = True. Стандартный шаг: Если isActive, …
Pic.15
Еще алгоритм перебора перестановок Попробуем теперь перебрать перестановки так, чтобы две последоват
Еще алгоритм перебора перестановок Попробуем теперь перебрать перестановки так, чтобы две последовательные перестановки мало отличались друг от друга. Насколько мало? На одну элементарную …
Pic.16
Еще алгоритм перебора перестановок -2 Посмотрим пример. 1 2 3 4 5 Чей ход 1 2 3 4 5 Чей ход a b c d
Еще алгоритм перебора перестановок -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 …
Pic.17
Перебор перестановок. 1 function ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: integ
Перебор перестановок. 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 begin …
Pic.18
Задача о минимуме суммы попарных произведений Пусть заданы два набора по n чисел, скажем, {ak|k1:n}
Задача о минимуме суммы попарных произведений Пусть заданы два набора по n чисел, скажем, {ak|k1:n} и {bk|k1:n} . Эти числа разбиваются на пары (ak,bk) и вычисляется сумма их попарных произведений …
Pic.19
Теорема о минимуме суммы попарных произведений Минимум суммы попарных произведений достигается на тр
Теорема о минимуме суммы попарных произведений Минимум суммы попарных произведений достигается на тривиальной перестановке. Доказательство. Предположим, что существуют такие два индекса k и r, что ak …
Pic.20
Задача о максимальной возрастающей подпоследовательности Задана последовательность {ak|k1:n} чисел
Задача о максимальной возрастающей подпоследовательности Задана последовательность {ak|k1:n} чисел длины n. Требуется найти ее последовательность наибольшей длины, в которой числа {ak} шли бы в …
Pic.21
Нахождение максимальной возрастающей подпоследовательности Будем по возможности экономно разбивать н
Нахождение максимальной возрастающей подпоследовательности Будем по возможности экономно разбивать нашу на убывающие последовательности (пример изменен) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6 …
Pic.22
Задача о минимальном числе инверсий Задана последовательность {ak|k1:n} чисел длины n. Инверсией на
Задача о минимальном числе инверсий Задана последовательность {ak|k1:n} чисел длины n. Инверсией назовем выполняемое на месте зеркальное отражение какой-либо ее подстроки – сплошной …
Pic.23
Экзаменационные вопросы Перестановки. Их перебор и нумерация. Задача о минимуме скалярного произведе
Экзаменационные вопросы Перестановки. Их перебор и нумерация. Задача о минимуме скалярного произведения. Задача о наибольшей возрастающей подпоследовательности.
Pic.24
Задание 1. Двусторонний переход перестановка  число 2. Найти перестановку, отстоящую от данной на д
Задание 1. Двусторонний переход перестановка  число 2. Найти перестановку, отстоящую от данной на данное число шагов. 3. Перебор перестановок элементарными транспозициями. 4. Выполнить пример для …


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

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!