Лекция 1



Дискретные задачки
принятия решений

НГУ  Механико – математический факультет  4 курс

Лектор: Кочетов Юрий Андреевич

http://www.math.nsc.ru/LBRT/k5/tpr.html


Лекция 1.

Задачки комбинаторной оптимизации.

Методы и сложность


Мотивационный пример

Компания планирует создание и продажу бандерснечей в критериях Лекция 1 жесткой конкуренции.

Нужен способ для проверки способности сотворения узлов бандерснеча с данными техническими чертами.

Вы отвечаете за разработку алгоритмов.



Сумрачная перспектива






Удачный выход






Но подтверждение возможно окажется очень сложной задачей,
если это Лекция 1 вообщем можно обосновать.

^ Теория NP-полных задач дает способы подтверждения того, что
определенная задачка настолько же трудна, как и ряд других задач, общепризнанных очень тяжелыми




Достойный выход

Массовая задачка

Под массовой задачей (либо просто задачей ) будем осознавать некий
общий вопрос, на который следует дать ответ:

Задачка задается последующей информацией:



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

Методы

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

Будем выделять

^ Длина входа персональной задачки

Время работы метода и требующуюся память выражают Лекция 1 в виде функции от «размера» персональной задачки, т. е. объема входных данных.


Входная длина (размер) персональной задачки есть число знаков, нужных для кодировки ее начальных данных.


Пример.

Для задачки коммивояжера требуется задать nn матрицу Лекция 1 расстояний (cij).
При двоичном кодировке чисел длина входа (размер) не превосходит
величины .

^ Полиномиальные методы

Будем гласить, что функция f(n) есть O(g(n)), если существует такая
константа c, что | f(n) |  c Лекция 1 | g(n) | для всех n  0.

Полиномиальным методом (методом полиномиальной временной трудности) именуется метод, у которого временная сложность равна O(p(n)), где p(n) — некая полиномиальная функция, а n Лекция 1 — длина входа.

Методы, временная сложность которых не поддается схожей оценке, именуются экспоненциальными.

Пример. O(n2) — полиномиальная сложность;

O(nlog n) — экспоненциальная сложность.

Сопоставление полиномиальных и экспоненциальных

функций временной трудности



Функция временной трудности

Размер n

10

20

30

40

50

60

n

0,00001
сек.

0,00002
сек Лекция 1.

0,00003
сек.

0,00004
сек.

0,00005
сек.

0,00006
сек.

n2

0,0001
сек.

0,0004
сек.

0,0009
сек.

0,0016
сек.

0,0025
сек.

0,0036
сек.

n3

0,001
сек.

0,008
сек.

0,027 сек.

0,064 сек.

0,125 сек.

0,216 сек.

n5

0,1 сек.

3,2 сек.

24,3 сек.

1,7 мин.

5,2 мин.

13 мин.

2n

0,001
сек.

1,0 сек.

17,9 мин.

12,7 дней

35,7 лет

366
веков

3n

0,059
сек.

58 мин.

6,5 лет.

3855
веков

2108
веков

1,31013
веков



^ Воздействие технического прогресса

Функция

временной

трудности

На современных Лекция 1

PC

На ЭВМ, в 100 раз
более стремительных

На ЭВМ, в 1000 раз
более стремительных

n

N1

100 N1

1000 N1

n2

N2

10 N2

31,6 N2

n3

N3

4,64 N3

10 N3

n5

N4

2,5 N4

3,98 N4

2n

N5

N5 + 6,66

N5 + 9,97

3n

N Лекция 16

N6 + 4,19

N6 + 6,29



Стремительная сортировка

Сортировкой именуют упорядочение огромного количества объектов по неубыванию либо невозрастанию какого-либо параметра.



Сортировка при помощи сравнений

Л
ai < aj ?

нет

да
емма 1. Бинарное дерево высоты h
содержит менее 2h листьев.


Дерево решений:


Лемма 2. Высота хоть какого дерева решений, упорядочивающего последовательность из n Лекция 1 разных частей, более log n!.

Подтверждение. Потому что результатом может быть неважно какая из n! перестановок, то в дереве решений должно быть более n! листьев.
Тогда по лемме 1 высота дерева не Лекция 1 меньше log n!. ∎

Аксиома. В любом методе, упорядочивающем при помощи сравнений, на упорядочивание последовательность из n частей тратится более c n log n сравнений при неком c >0 и довольно большенном n.

Подтверждение Лекция 1. При n ≥ 4 имеем

n! ≥ n(n – 1) (n – 2)…(  ) ≥ ,

тогда

log n! ≥ () log () ≥ () log n. ∎

Метод Фон–Неймана

На вход подается последовательность чисел a(1),…, a(n). Метод работает log2 n итераций. До итерации с номером k (k = 1, 2, …, log2 n) имеется Лекция 1 последовательность a(i (1)), …, a(i (n)) тех же чисел, разбитая на группы по 2k–1 частей (последняя группа может быть неполной). Снутри каждой группы элементы упорядочены по неубыванию. Итерация заключается в том Лекция 1, что эти группы разбиваются на пары примыкающих групп, и элементы упорядочиваются снутри этих новых вдвое огромных групп. При всем этом употребляется то, что снутри начальных групп элементы уже упорядочены.



слияние за линейное время

O Лекция 1(m)



Упражнение. Показать, что метод Фон–Неймана употребляет O(nlog n) сравнений.

Пирамидальный метод

Два шага:

  1. п
    a1
    остроение пирамиды: для каждого i


a2

ai
и

  1. с
    a4
    ортировка массива при помощи
    пирамиды Лекция 1


a2i

a2i+1



a8


1-ый шаг

(
ai
i, n)–операция состоит в последующем:

Сравниваем a2i и a2i+1,

п
a2i

a2i+1
усть x — наименьшее из их.

Если ai > x, то меняем Лекция 1 местами ai и x.


(j, n)–процедура: исполняем (j, n)–операцию; если aj переместилось вниз, скажем, стало a2j+1, то производим (2j +1, n)–операцию и т.д., пока наш элемент aj Лекция 1 не остановится.

1-ый шаг состоит в поочередном выполнении (j, n)–процедуры для j =n/2, n/2 – 1,…, 1.


Упражнение. Обосновать, что 1-ый шаг просит менее 2n (i, n)–операций.

2-ой шаг

Н
an–j+1

a1
а Лекция 1 j-й итерации (j – 1) самых малых чисел уже найдены и лежат на «полочке» в подходящем
порядке. Другие находятся в пирамиде
(ai ≤ min(a2i, a2i +1)). Итерация заключается в том, что элемент a Лекция 11 из пирамиды кладется на «полку», а на его место ставится элемент an – j +1 из пирамиды и производится (1, n–j)–процедура.

После выполнения n-й итерации все числа лежат на полке в полном Лекция 1 порядке.

Время — O(n log n).


Замечание. «Полку» можно организовать прямо в пирамиде.

Равновесные деревья

Для массива данных требуется

  1. Отыскать элемент

  2. Отыскать k-й по порядку элемент

  3. Воткнуть элемент

  4. Удалить элемент



Если упорядочить массив, то 1 и Лекция 1 2 требуют O(log n) операций, но 3, 4 — O(n).

Если хранить данные в виде перечня, то 3, 4 — O(log n), 1, 2 — O(n).

Равновесные деревья требуют O(log n) для 1 – 4.

Определение 1. Высотой дерева именуется наибольшая длина пути от Лекция 1 корня до листа.


Определение 2.  Бинарное дерево именуется равновесным (либо AVL–деревом), если для хоть какой его верхушки высота правого
поддерева отличается от высоты левого поддерева менее чем на единицу.


Аксиома. Длина Лекция 1 веток в n-вершинном равновесном дереве
заключена меж log2n и log2n.

Подтверждение.

  1. Бинарное дерево высоты h не может содержать больше 2h +1
    верхушки, другими словами n ≤ 2h + 1 либо h + 1 ≥ log2 n.

  2. Более Лекция 1 ассиметричное AVL–дерево Th высоты h имеет более ассиметричное AVL–дерево Th –1 высоты h–1 в качестве 1-го из собственных поддеревьев и более ассиметричное AVL–дерево Th –2 в качестве другого. Обозначим через n Лекция 1(h) число вершин в дереве Th. Тогда

n(h) = n(h–1) + n(h–2) + 1; n(0) = 1, n(–1) = 0.

Для h=3,4 можно конкретно проверить, а потом по индукции обосновать, что n(h)>  h+1, где Лекция 1  = .

Как следует, n ≥ n(h) >  h+1, откуда h+1 ≤ log n / log  ≈ 1,44 log n. ∎

Пусть в верхушках AVL–дерева размещены элементы массива так, что для хоть какой верхушки в левом ее поддереве размещены элементы Лекция 1 не больше чем в данной верхушке, а в правом поддереве — не меньше, чем в этой верхушке.


ai


aj ≥ ai

aj ≤ ai

Пример. Поиск в AVL–дереве востребует более 25 сравнений, только если дерево состоит из более 196 417 вершин.

^ Случайные Лекция 1 деревья

Для равновесного дерева длина пути из корня в лист не превосходит 1,44 log n.

Для случайного дерева средняя длина пути из корня в лист составляет 1,39 log n, но в худшем случае Лекция 1 возможно окажется равной n.

Для равновесного дерева средняя длина пути составляет c  log  n,
c ≈1,04.

Включение новейшей верхушки в AVL–дерево

При добавлении новейшей верхушки vnew к AVL–дереву мы «скатываем» ее от корня повдоль Лекция 1 ветвей и получаем новый лист (висящую верхушку).
Дерево остается бинарным, но баланс может нарушиться. Эти нарушения могут появиться только у вершин, лежащих на пути от корня к новейшей верхушке Лекция 1.

Будем поочередно подниматься от новейшей верхушки к корню и восстанавливать баланс, если это нужно.

Пусть v  — самая нижняя верхушка дисбаланса, другими словами более удаленная от корня верхушка такая, что ее поддерево с верхушкой Лекция 1 vnew имеет высоту k+2, а другое поддерево — высоту k:



Будем восстанавливать баланс в v  последующим образом. Если 1-ые два шага на (единственном пути) от v к vnew делаются в одном направлении Лекция 1 (оба на право, либо оба на лево), то применяем правило обычного вращения (ППВ).



Если 1-ые два шага делаются в различных направлениях, то
применяем правило двойного вращения (ПДВ):



^ Удаление верхушки

На место удаленной верхушки v ставим Лекция 1 или самую правую верхушку vrL левого поддерева, или самую левую верхушку vLr правого поддерева

Аспект. Любая из вершин vrL и vLr может быть или висящей, или
предвесячей, другими словами имеющей в качестве потомков только Лекция 1 одну верхушку
(очевидно, висящую):




Если на место удаленной верхушки встает предвисячая верхушка y, то ее (верхушки y) потомок x подключается к ее предку z:




Итак, можно считать, что всегда удаляем лист Лекция 1. Поочередно поднимаемся от удаленной верхушки v к корню и исправляем структуру дерева, если нужно.

Пусть к текущей верхушке x на пути от v к корню мы пришли справа по недлинной ветке Лекция 1. Тогда может быть три варианта:

а) В верхушке y высоты поддеревьев равны:



б) В верхушке y высота левого поддерева больше высоты правого поддерева:



в) В верхушке y высота левого поддерева меньше Лекция 1 высоты правого поддерева



Отметим, что устранение дисбаланса в одной из вершин, может нарушить баланс в вышестоящих верхушках. На рисунке показан предельный случай этого явления. При исходном дисбалансе только в одной верхушке (лежащей конкретно Лекция 1 под v) приходится, все же, создавать перестройку дерева во всех верхушках на пути к корню.


Пример. Выстроить последовательность AVL–деревьев для данных, поступающих в последующем порядке: 29, 19, 9, 1, 4, 14, 39, 18, 36, 24, 15, 12.

Удалить из приобретенного дерева 24, а потом 19.




Упражнение Лекция 1. Выстроить последовательность AVL–деревьев для данных, поступающих в последующем порядке: 15, 7, 17, 5, 4, 3, 56, 23, 22, 6, 10, 25, 26.

Удалить из приобретенного дерева 6 и 10, а потом 15 и 25.



lekciya-15-ekonomicheskaya-i-yuridicheskaya-otvetstvennost-predpriyatij-zagryaznyayushih-okruzhayushuyu-sredu.html
lekciya-15-immunnij-status-makroorganizma-metodi-ocenki-kratkij-kurs-lekcij-po-medicinskoj-mikrobiologii-virusologii.html
lekciya-15-osvobozhdenie-ot-ugolovnogo-nakazaniya-konspekt-lekcij-ministerstvo-obrazovaniya-i-nauki-rossijskoj-federacii.html