Конспект лекций

по курсу

 

 

 

Алгоритмы и алгоритмические языки

 

 

 

 

 

 

 

 

 

 

Доцент каф. Вычислительной математики

Механико-Математического ф-та

МГУ им. М.В.Ломоносова

Староверов В.М.

2013г.


 

 

Лекция 1. 5

Представление чисел в ЭВМ... 5

Целые. 5

Вещественные. 5

Ошибки вычислений. 9

Лекция 2. 12

Алгоритмы. Сведение алгоритмов. 12

Нижние и верхние оценки. 12

Сортировки. 14

Постановка задачи. 14

Сортировка пузырьком. 15

Сортировка слиянием с рекурсией. 17

Сортировка слиянием без рекурсии. 19

Лекция 3. 20

Алгоритмы. Сведение алгоритмов. 20

Сортировки и связанные с ними задачи. 20

QuickSort. 20

Доказательство корректности работы алгоритма. 23

Оценки времени работы алгоритма. 24

Некоторые задачи, сводящиеся к сортировке. 27

Лекция 4. 32

Алгоритмы. Сведение алгоритмов. 32

Сортировки и связанные с ними задачи. 32

HeapSort или сортировка с помощью пирамиды. 32

Алгоритмы сортировки за время O(N) 34

Сортировка подсчетом.. 34

Цифровая сортировка. 35

Сортировка вычерпыванием.. 35

Лекция 5. 38

Алгоритмы. Сведение алгоритмов. 38

Порядковые статистики. 38

Поиск порядковой статистики за время Q(N) в среднем.. 38

Поиск порядковой статистики за время Q(N) в худшем случае. 40

Язык программирования C. 41

Переменные. 42

Структуры данных. 44

Вектор. 44

Стек. 45

Лекция 6. 48

Структуры данных ( + в языке С: массивы, структуры, оператор typedef). 48

Стек. 48

Стек. Реализация 1 (на основе массива). 48

Стек. Реализация 2 (на основе массива с использованием общей структуры). 49

Стек. Реализация 3 (на основе указателей). 49

Стек. Реализация 4 (на основе массива из двух указателей). 50

Стек. Реализация 5 (на основе указателя на указатель). 50

Очередь. 51

Дек. 52

Списки. 53

Стандартная ссылочная реализация списков. 54

Ссылочная реализация списков с фиктивным элементом.. 56

Реализация L2-списка на основе двух стеков. 57

Реализация L2-списка с обеспечением выделения/освобождения памяти. 58

Лекция 7. 59

Структуры данных. Графы. 59

Графы.. 59

Поиск пути в графе с наименьшим количеством промежуточных вершин. 59

Представление графа в памяти ЭВМ... 64

Лекция 8. 68

Структуры данных. Графы. 68

Поиск кратчайшего пути в графе. 68

Лекция 9. 73

Бинарные деревья поиска. 73

Поиск элемента в дереве. 74

Добавление элемента в дерево. 74

Поиск минимального и максимального элемента в дереве. 75

Удаление элемента из дерева. 75

Поиск следующего/предыдущего элемента в дереве. 75

Слияние двух деревьев. 75

Разбиение дерева по разбивающему элементу. 76

Сбалансированные и идеально сбалансированные бинарные деревья поиска. 77

Операции с идеально сбалансированным деревом.. 78

Операции со сбалансированным деревом.. 79

Поиск элемента в дереве. 79

Добавление элемента в дерево. 79

Удаление элемента из дерева. 83

Поиск минимального и максимального элемента в дереве. 83

Поиск следующего/предыдущего элемента в дереве. 83

Слияние двух деревьев. 83

Разбиение дерева по разбивающему элементу. 85

Лекция 10. 87

Красно-черные деревья. 87

Отступление на тему языка С. Поля структур. 87

Отступление на тему языка С. Бинарные операции. 89

Высота красно-черного дерева. 89

Добавление элемента в красно-черное дерево. 90

Однопроходное добавление элемента в красно-черное дерево. 92

Удаление элемента из красно-черного дерева. 94

Лекция 11. 97

B-деревья. 97

Высота B-дерева. 98

Поиск вершины в B-дереве. 99

Отступление на тему языка С. Быстрый поиск и сортировка в языке С.. 99

Добавление вершины в B-дерево. 101

Удаление вершины из B-дерева. 102

Лекция 12. 106

Хеширование. 106

Метод многих списков. 106

Метод линейных проб. 107

Метод цепочек. 111

Хэш-функции. 113

Хэш-функции на основе деления. 113

Хэш-функции на основе умножения. 113

CRC-алгоритмы обнаружения ошибок. 114

Лекция 14. 118

Поиск строк. 118

Отступление на тему языка С. Ввод-вывод строк из файла. 118

Алгоритм поиска подстроки с использованием хеш-функции (Алгоритм Рабина-Карпа) 119

Конечные автоматы.. 120

Отступление на тему языка С. Работа со строками. 121

Алгоритм поиска подстроки, основанный на конечных автоматах. 121

Лекция 15. 123

Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции) 123

Алгоритм поиска подстроки Бойера-Мура (на основе стоп-символов/безопасных суффиксов) 125

Эвристика стоп-символа. 125

Эвристика безопасного суффикса. 127

Форматы BMP и RLE.. 130


Лекция 1

Представление чисел в ЭВМ

 

Целые

Беззнаковые целые.

Используется двоичное представление чисел.

x = an-1*2n-1 + an-2*2n-2 + … a1*21 + a0*20

здесь каждый член ai представляет собой 0 или 1 или, иначе говоря, одну цифру в двоичном представлении данных.

            n задается количеством бит (в одном бите хранится одна двоичная цифра), отводящихся под данное число.

 

BCD - Binary Coded Decimal

В одном байте хранятся две цифры десятичного представления. Применяется, например, в СУБД Oracle для хранения вещественных чисел с плавающей точкой.

 

Целые со знаком.

Существует три основных формата:

  • прямой (старший бит служит признаком знака: 1=’-‘; 0=’+’)
  • обратный (для представления отрицательного числа берется представление его модуля, а потом все биты инвертируются)
  • дополнительный (для представления отрицательного числа берется представление его модуля, все биты инвертируются, к результату прибавляется 1)

 

Реально, в основном, используется только дополнительный код.

 

Утверждение 1. Представление чисел в дополнительном коде эквивалентно представлению чисел в кольце вычетов по модулю 2n, где n – количество бит в двоичном представлении числа.

 

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

 

Вещественные

 

Вещественные числа с фиксированной запятой.

 

VB тип Currency - восьмибайтовая переменная, которая содержит вещественное число в формате с фиксированной десятичной запятой (четыре десятичных знака после запятой).

 

C# тип decimal

Вещественные числа с плавающей запятой.

 

Формат закреплен IEEE: Institute of Electrical and Electronics Engineers.

Число представляется в виде

 

x = s * m * 2d

 

где

 s – знак (отводится один бит)

 m – мантисса в виде 1.xxxxx (где x – двоичная цифра; 1 не хранится)

 d – степень (оставшиеся биты)

 

Согласно формату IEEE вместо степени хранится характеристика = d-dmin , где dmin – минимально возможное значение мантиссы. Таким образом, минимально возможное значение характеристики = 0.

На самом деле, по стандарту IEEE  представление более сложное. Пока характеристика положительна поддерживается вышеуказанное представление. Для нулевой характеристики число хранится уже как число с фиксированное запятой в виде

 

x = p * 2-dmin

где  p – число с фиксированной точкой в виде x.xxxxx (где x – двоичная цифра; хранятся все указанные биты!).

 

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

 

  2-122:   1.88079e-037: 0 00000101 00000000000000000000000

  2-123:   9.40395e-038: 0 00000100 00000000000000000000000

  2-124:   4.70198e-038: 0 00000011 00000000000000000000000

  2-125:   2.35099e-038: 0 00000010 00000000000000000000000

  2-126:   1.17549e-038: 0 00000001 00000000000000000000000

  2-127:   5.87747e-039: 0 00000000 10000000000000000000000

  2-128:   2.93874e-039: 0 00000000 01000000000000000000000

  2-129:   1.46937e-039: 0 00000000 00100000000000000000000

  2-130:   7.34684e-040: 0 00000000 00010000000000000000000

  2-131:   3.67342e-040: 0 00000000 00001000000000000000000

  2-132:   1.83671e-040: 0 00000000 00000100000000000000000

  2-133:   9.18355e-041: 0 00000000 00000010000000000000000

  2-134:   4.59177e-041: 0 00000000 00000001000000000000000

  2-135:   2.29589e-041: 0 00000000 00000000100000000000000

  2-136:   1.14794e-041: 0 00000000 00000000010000000000000

  2-148:   5.73972e-042: 0 00000000 00000000000000000000010

  2-149:   2.86986e-042: 0 00000000 00000000000000000000001

  2-150:   1.43493e-042: 0 00000000 00000000000000000000000

Здесь следует отметить, что в Intel-архитектуре байты переставлены в обратном порядке и в вышеописанном представлении байты выводятся в порядке: 3, 2, 1, 0.

Т.о. число 2-150 уже неотличимо от 0.Если вышеуказанные число получались каждый раз путем деления предыдущего числа на 2, то в результате получения последнего число из 2-149 мы получили ситуацию underflow – нижнее переполнение. Как правило, процессоры могут отслеживать underflow, но нижнее переполнение можно расценивать как ошибку, а можно и не расценивать, ведь при многих вычислениях слишком маленькие числа можно расценивать как нулевые. Поэтому, обычно никаких сообщений в ситуации underflow не производится.

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

 

  2118:   3.32307e+035: 0 11110101 00000000000000000000000

  2119:   6.64614e+035: 0 11110110 00000000000000000000000

  2120:   1.32923e+036: 0 11110111 00000000000000000000000

  2121:   2.65846e+036: 0 11111000 00000000000000000000000

  2122:   5.31691e+036: 0 11111001 00000000000000000000000

  2123:   1.06338e+037: 0 11111010 00000000000000000000000

  2124:   2.12676e+037: 0 11111011 00000000000000000000000

  2125:   4.25353e+037: 0 11111100 00000000000000000000000

  2126:   8.50706e+037: 0 11111101 00000000000000000000000

  2127:   1.70141e+038: 0 11111110 00000000000000000000000

  2128:         1.#INF :     0 11111111 00000000000000000000000

  2129:         1.#INF :     0 11111111 00000000000000000000000

  2130:         1.#INF :     0 11111111 00000000000000000000000

 

Будем далее называть представление вещественных чисел с плавающей точкой в диапазоне [2-dmin, 2dmin] стандартным представлением вещественных чисел с плавающей точкой.

 

Итак, стандартом IEEE закреплено наличие дополнительных констант:

 

NAN – not a number. Не число = 0/0   [ (0111 1111)(1100 0000) 0…0]

+INF – плюс бесконечность                [ (0111 1111)(1000 0000) 0…0]

-INF – минус бесконечность               [ (1111 1111)(1000 0000) 0…0]

+0 = 0x00 00 00 00

-0  = 0x80 00 00 00

 

+INF, -INF,+0, -0  можно корректно сравнивать. +0 = = -0 = = 0.

NAN при сравнении возвращает ложь всегда кроме !=. В этом случае возвращается истина.

 

 

Для IBM PC:

 

float  (32bit)

1bit – знак

8bits – степень+127 (127=27-1)

23bits – символы xxxxx из мантиссы (мантисса в виде 1.xxxxxx)

 

пример 1.f=

 

0             = знак

01111111 = степень+127 (занимает 8 бит)

0000…0 = символы xxxxx из мантиссы (мантисса в виде 1.xxxxxx)

Итого: 00111111 10000000 00000000 00000000

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

 

doudle (64bit)

1bit – знак

11bits – степень+210-1

52bits – символы xxxxx из мантиссы (мантисса в виде 1.xxxxxx)

 

пример 1.f=

00111111 11110000 00000000 00000000 00000000 00000000 00000000 00000000

 

long double (80bit)

1bit – знак

15bits – степень+214-1

64bits – символы 1xxxxx из мантиссы (мантисса в виде 1.xxxxxx)

 

В некоторых версиях языка С тип long double присутствует, но является всего лишь синонимом типа double (например, в текущей версии Microsoft C это именно так).

Надо всегда иметь в виду, что выше описан стандарт представления вещественных чисел с плавающей точкой, который поддерживается на архитектуре используемых персональных компьютеров (Intel/AMD), но существуют и другие (нестандартные) реализации вещественных чисел с плавающей точкой.

Например, IBM-формат вещественных чисел с плавающей точкой предполагает, что число представляется в виде: x = s * m * 16d.  Подобный подход расширяет диапазон возможных значений числа, но уменьшает точность представления чисел. Кроме того, данный подход требует хранения всех бит мантиссы (в стандартном представлении старший бит всегда равен 1 и поэтому он не хранится в машинном представлении числа). Числа в данном формате не меняют своего представления для очень маленьких и очень больших по модулю чисел, что упрощает реализацию алгоритмов работы с такими числами. При этом нет проблем с представлением нуля: нулевая мантисса всегда соответствует числу, равному нулю. Данный формат представления чисел до сих пор используется, например, при представлении сейсмических данных в геологической разведке.

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

 

Ошибки вычислений

 

Для экономии времени мы не будем давать точного определения понятий `много больше’ (>>) и `много меньше’ (<<).

 

Определение 1.  e1 = argmin{v>0|1+v != v}

Определение 2.  e2 = argmax{v>0|1+v = = v}

 

Легко видеть, что e1 =[(0011 1111) (1 000 0000)(0000 0000)(0000 0001)]-1=2-23 и что e2  отличается от него на очень мало, поэтому можно говорить об одном числе e =e1 .

 

Определение 3. Назовем абсолютной ошибкой приближения числа x0 с помощью числа x такое  D, что

| x - x0| < D

 

Определение 4. Назовем относительной ошибкой приближения числа x0 с помощью числа x такое  d, что

| x - x0| / | x0 | < d

 

Часто более удобно пользоваться другим определением числа d:

| x - x0| / | x | < d

Это связано с тем, что, как правило, нам известно лишь приближение исследуемого числа ( x ), а не оно само ( x0 ). В ситуации, когда | x - x0| << | x0 | и | x - x0| << | x | эти два Определения отличаются несущественно. Кроме данных допущений, мы также будем предполагать, что все относительные ошибки много меньше 1.

 

Утверждение 2. При сложении/вычитании чисел их абсолютные ошибки складываются, т.е.

| (x+y) (x0+y0) |  £ Dx+Dy

 

| (x y) (x0 y0) |  £ Dx+Dy

где | x x0  |  < Dx  ,  | y y0  |  < Dy  .

 

Доказательство элементарно.

 

Утверждение 3. При умножении/делении чисел их относительные ошибки складываются (с точностью до пренебрежимо малых членов), т.е.

| (x*y x0*y0) / (x*y)|  £» dx+dy

 

| (x/y x0/y0) / (x/y)|  £» dx+dy

 

где | x - x0| / | x | < dx  ,  | y y0  | / | y | < dy  .

 

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

1.

Итак, рассмотрим сумму относительных ошибок:

 

 (x - x0) /  x  + (y y0 ) /  y = (x* y - x0* y + y* x - x* y0) /  (x* y) =

 

= (x* y - x0* y + y* x - x* y0    -  x* y + x0* y0 ) /  (x* y) + ( x* y + x0* y0 ) /  (x* y)

= dx * dy + ( x* y - x0* y0 ) /  (x* y)

 

получаем:

|( x* y - x0* y0 ) /  (x* y)|  £» dx + dy

2.

Перепишем относительную ошибку частного:

 (x/y x0/y0) / (x/y) = (x* y0 x0 y) / (x*y0)

 

Итак, рассмотрим сумму относительных ошибок (незначительно отличающихся от основного определения):

 

 (x - x0) /  x  + (y0 y ) /  y0 = (x* y0 - x0* y0 + y0* x - x* y) /  (x* y0) =

 

= (x* y0 - x0* y0 + y0* x - x* y - x* y0 + x0 y) /  (x* y0) + (x* y0 x0 y) / (x*y0)

»= dx * dy + (x* y0 x0 y) / (x*y0)

 

получаем:

| (x/y x0/y0) / (x/y)|  £» dx+dy

Ч.Т.Д.

 

Легко видеть, что число e  представляет собой абсолютную ошибку представления числа 1. Здесь имеется в виду, что все числа, отличающиеся от 1 менее, чем на e, будут равны 1. Отсюда сразу же вытекает, что e также является и относительной погрешностью представления числа 1 в ЭВМ.

Из представления вещественного числа

x = s * m * 2d  (1≤m<2)

сразу вытекает, что значение вещественного числа по порядку задается только его степенью. Здесь имеется в виду, что при одной и той же степени, изменение мантиссы числа может изменить значение числа не более, чем вдвое:

1≤x /( s  * 2d )<2 (где x = s * m * 2d)

т.е.

x = s * m * 2d  =» s * 2d

Но легко видеть, число x = s * m * 2d   имеет абсолютную погрешность представления, равную  e * 2d , т.к. эта величина равна значению последнего бита мантиссы при заданном значении степени. Отсюда сразу вытекает, что относительная ошибка представления числа x = s * m * 2d   , равная

e * 2d / (m * 2d) = e  / m

не более, чем вдвое отличается от e. Т.о. мы получили следующую важную теорему

 

Теорема. Любое вещественное число x в стандартном представлении числа с плавающей точкой (т.е. не являющееся слишком большим или слишком маленьким по модулю в вышеописанном смысле) имеет относительную ошибку представления порядка e (точнее, не более, чем вдвое отличающуюся от e) и имеет абсолютную ошибку представления порядка x*e (точнее, не более, чем вдвое отличающуюся от x*e).

 

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

 


Лекция 2

Алгоритмы. Сведение алгоритмов.

Нижние и верхние оценки.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989

 

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

Алгоритмом m называется формально описанная процедура, имеющая некоторый набор входных данных In(m) и выходных данных Out(m). Вводится некоторый параметр, оценивающий объем входных данных N=N(In(m)).  Будем называть этот параметр размером входных данных. Заметим, что, на самом деле, алгоритм решает некоторую формально поставленную задачу z, имеющую те же самые входные и выходные данные.

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

Для оценки времени работы алгоритма с каждой допустимой операцией ассоциируется время ее выполнения. Временем выполнения реализации алгоритма T(m) для определенных начальных данных называется сумма времен выполнения всех операций алгоритма при выполнении данной реализации.

Верхней оценкой времени выполнения алгоритма m называется такая функция F(N), что для любого набора входных данных In(m) размером не более N время выполнения алгоритма не будет превосходить F (N). Будем говорить, что задача z  имеет верхнюю  оценку времени решения F (N), если существует алгоритм m с верхней оценкой времени выполнения F (N).

Разумно задаться вопросом: а для любого ли алгоритма существует его верхняя оценка времени работы? Элементарно привести пример, для которого верхней оценки времени работы не существует (например, можно рассмотреть задачу выписывания всех десятичных знаков обычного целого числа). Однако, если количество различных вариантов входных данных объема N алгоритма для любого N конечно, то легко показать, что верхняя оценка времени работы алгоритма существует. Нас интересуют алгоритмы, которые можно реализовать на компьютере. Но у компьютера конечное количество ячеек памяти, поэтому и количество их комбинаций конечно. В таком случае на компьютере можно задать только конечное количество вариантов входных данных для любой задачи.

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

Итак, мы получили, что для всех алгоритмов, которые можно реализовать на компьютере существует верхняя оценка времени работы. На самом деле, этот факт не стоит ничего, т.к., с одной стороны, функция F (N)  может очень быстро расти, а с другой, конечность количества ячеек компьютера всегда вступает в противоречие с бесконечностью мира. Например, конечность количества ячеек делает бессмысленным рассмотрение функции  F (N)  для любого натурального N.

Нижней оценкой времени выполнения алгоритма m  называется такая функция j(N), что для любого N найдется такой набор входных данных алгоритма размером N, что время работы данного алгоритма на указанных данных будет не меньше j(N).

Нижней оценкой времени решения задачи z  называется такая функция j(N), что для любого алгоритма, решающего данную задачу,  j(N) будет нижней оценкой времени работы данного алгоритма.

 

Будем говорить, что задача z1 сводится к задаче z2 за время g(N), если

·         входные данные задачи z1, имеющие объем N, могут быть приведены к входным данным задачи z2, при этом входные данные задачи z2 тоже имеют объем N;

·         выходные данные задачи z2 могут быть приведены к выходным данным задачи z1,

и все это за суммарное время g(N) (т.е. суммарное время выполнения алгоритмов приведения = g(N)). По аналогии, можно говорить, что алгоритм m1 сводится к алгоритму m2 за время g(N) (определение аналогично).

 

Теорема 1. Если задача z1 сводится к задаче z2 за время g(N) и задача z2 имеет верхнюю оценку времени решения F2(N), то задача z1  имеет верхнюю оценку времени решения F1(N) = F2(N) + g(N).

 

Доказательство теоремы тривиально.

 

Теорема 2. Если задача z1 сводится к задаче z2 за время g(N) и задача z1 имеет нижнюю оценку времени решения j1(N), то задача z2  имеет нижнюю оценку времени решения j2(N) = j1(N) - g(N).

Доказательство. Выпишем аккуратно условие того, что j2(N) является нижней оценкой времени решения задачи z2:

" алгоритма m2 :  j2(N) -  нижняя оценка времени решения задачи z2.

или:

" алгоритма m2 и "N>0 $ In(m2) с размером, равным N:  T(m2 (In(m2)))≥j2(N)  = j1(N) - g(N).

Поведем доказательство от противного. Допустим это не так, т.е. выполняется условие:

$ алгоритм m2 и N>0: " In(m2) :  T(m2 (In(m2)))<j2(N)  = j1(N) - g(N).

Тогда существует алгоритм (заключающийся в сведении задачи m1 к задаче m2 за время g(N)), для которого на всех исходных данных размера N задача решается за время, меньшее j1(N) - g(N)+ g(N)= j1(N) , что противоречит условию теоремы.

¢

 

 

 

 

 

Введем обозначения.

 

g(n)=O(f(n))  если $ N0>0 и С>0, такие что " n>N0 :| g(n) | £ C| f(n) |

 

g(n)=o(f(n)) если " С>0 $ N0>0,  такое что " n>N0 : |g(n) | £ C |f(n) |

 

g(n)=Q(f(n)) если $ N0>0 и С1, С2>0, такие что " n>N0 :

С1 |f(n) | £ |g(n) | £ С2 |f(n) |

 

g(n)=W(f(n)) если $ N0>0 и С>0, такие что " n>N0 : |g(n) | ³ C |f(n) |

 

 

Сортировки

Постановка задачи

Для элементов некоторого множества P введены соотношения сравнения. Под этим будем подразумевать следующее: для каждых двух элементов a,b Î P  верно ровно одно из  трех соотношений: a<b, a>b, a=b. Эти соотношения должны обладать свойствами транзитивности:

a<b, b<c  Þ  a<c

a>b, b>c  Þ  a>c

a=b, b=c  Þ  a=c

и аналогом свойства симметричности:

a<b Û  b>a

 

Пусть дано некоторое упорядоченное подмножество (последовательность) элементов из P : {a1, …, aN}, aiÎ P. Требуется найти такую перестановку (x1,…,xN), что ax1, …, axN – будет неубывающей последовательностью, т.е. axi < ax(i+1) или axi = ax(i+1)  . Напомним, что перестановкой n элементов мы называем некоторое взаимно-однозначное соответствие множества чисел {1,…,N} с таким же множеством чисел {1,…,N}, т.е. такую функцию s: {1,…,N} -> {1,…,N}, для которой если i¹j , то s(i)¹s(j).

Здесь, конечно, надо сразу задаться вопросом: а возможно ли это сделать при данных ограничениях на приведенные операции сравнения? Другим разумным вопросом будет: а если это можно сделать, то единственным ли (с точностью до перестановок подряд идущих элементов, между которыми выполняется соотношение =) способом? Ответы на оба вопросы положительны.

Доказательства утверждения, кроющегося в первом вопросе (о существовании перестановки), легко провести по индукции по n.

Для доказательства утверждения, кроющегося во втором вопросе (о единственности перестановки), можно сначала показать, что в упорядоченном множестве элементы, между которыми выполняется соотношение = должны идти подряд, что дает возможность заменить их одним элементом. Далее можно ввести функцию M(i) – количество элементов из {a1, …, aN}, меньших ai. Отметим, что для любых ij  выполняется: M(i)≠M(j) (действительно: выполняется либо ai < aj, либо ai > aj, откуда легко вывести, что, соответственно, M(i)<M(j) , либо M(i)>M(j)), из чего сразу вытекает (учитывая, что 0≤M(i)<n), что функция M(i) принимает все возможные значения от 0 до n-1. Легко показать, что эта функция однозначно определяет положение элемента ai в упорядоченном множестве.

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

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

·         вычисляется некоторая функция от входных данных алгоритма,

·         производится сравнение полученной величины с 0 (одной из операций: <, > или =)

·         от каждой вершины дерева, в зависимости от полученного результата, происходит переход к левой или правой ветви дерева

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

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

 

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

 

Если исходные данные задачи принадлежат k-мерному Евклидову пространству и если вычисляемая в узлах функция является многочленом степени n, то говорят, что алгоритм представим в виде алгебраического дерева степени n.

Сортировка пузырьком.

Алгоритм:

 

N-1 раз выполняется следующая процедура:

    Для всех i  от 1 до N-1 c шагом 1:

        если axi > ax(i+1)   то поменять местами axi и ax(i+1)

 

Легко видеть, что алгоритм требует порядка O(N2) арифметических операций.

 

Теорема. Алгоритм сортировки пузырьком является оптимальным по порядку времени выполнения среди алгоритмов, основанных на операции сравнения, если обмен местами двух элементов последовательности требует O(N) времени.

 

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

 

Доказательство. Рассмотрим следующую последовательность:

N, N-1, N-2, … 2, 1

Для любой сортировки этой последовательности следует первый в ней элемент поставить на последнее место (=порядка O(N-1) операций), второй элемент поставить на предпоследнее место (=порядка O(N-2) операций) и т.д. Итого, только перестановки займут не менее O(N2) времени, откуда мы получаем нижнюю оценку времени выполнения алгоритмов данного класса. Данная оценка достигается на предложенном алгоритме.

¢

 

 

 


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

 

Теорема.  Нижней оценкой времени решения задачи сортировки в рамках алгоритмов, основанных на операции сравнения, является Q (N log2 N). Т.е. существует функция g(N)=Q (N log2 N), являющаяся нижней оценкой решения задачи сортировки в рамках алгоритмов, основанных на операции сравнения.

 

Замечание. На самом деле, не обязательно ограничивать операции, допустимые после сравнения элементов в дереве решения, лишь одной транспозицией. Можно разрешить выполнять произвольную перестановку всех N элементов за 1 единицу времени. Теорема останется верной. 

 

Доказательство. Рассмотрим решение задачи о сортировке набора из N целых чисел от 1 до N. Решение можно представить как дерево решения. Исключим из этого дерева все ветки, начиная с элемента, в который нельзя попасть и до завершающего элемента дерева. Удаление данных веток никак не повлияет на реальный алгоритм.

Теперь каждой перестановке s(1,…,N)  (здесь под s подразумевается перестановка элементов множетва {1,…,N}) соответствует своя концевая вершина в дереве решения (соответствующая только этой перестановке), такая что ветка дерева решения от корня до данной вершины задает перестановку p, обратную s.: p(s(i))=i "iÎ{1,…,N}.  Т.е. данная ветка задает решение задачи сортировки для последовательности исходных данных {s(1), s(2,)… s(N)}.

Действительно, в силу определения дерева решений, для каждой последовательности исходных данных {s(1), s(2,)… s(N)} мы имеем ровно одну ветвь дерева решений (от корня до завершающей дерево вершины), сортирующую данную последовательность. Причем, каждая завершающая дерево вершина является концевой ровно для одной перестановки s(1,…,N). Действительно, мы исключили вершины, до которых нельзя в принципе добраться, поэтому осталось исключить ситуацию, когда вершина соответствует сразу двум различным перестановкам s(1,…,N) и r(1,…,N). Но в последнем случае мы имеем: p(s(i))=i и p(r(i))=i "iÎ{1,…,N}, где перестановка p описана выше. Из чего сразу получаем, что перестановки s и r совпадают.

Таким образом, мы доказали, что количество завершающих вершин дерева решений равно количеству перестановок множества {1,…,N}, равно n!.

Будем называть глубиной дерева количество вершин в его самой длинной ветке. Для дерева глубины h мы имеем, что хотя бы в одной ветви дерева количество сравнений равно h-1, из чего сразу получаем, что h-1 является нижней оценкой времени работы всех алгоритмов, описываемых деревьями сравнения глубины h (мы задаем время сравнения равное 1).

Дерево глубины h не может иметь количество концевых вершин K более чем

2h-1: K2h-1, откуда получаем: h  ³ (log2 K) +1.

Итого, в нашем случае:

 

h  ³ (log2 K) +1 = (log2 N!) + 1 ~N log2 N.

Здесь мы использовали известную формулу Стирлинга:

n! = nne-nsqrt(2pN) ( 1+o(1) )

из которой сразу следует, что

log2 N! = (N log2 N  -N log2 e + log2 sqrt(2pN) )( 1+o(1) ) = (N log2 N)( 1+o(1) )

¢

 

Приведем примеры, показывающие, что приведенная нижняя оценка времени решения задачи сортировки достижима.

 

Сортировка слиянием с рекурсией.

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

 

Теорема. Пусть даны два упорядоченных множества {A1,…,AN } и {B1,…,BN }.       В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2N-1 сравнение в худшем случае. Т.е. 2N-1 является нижней оценкой времени работы алгоритма, если учитывать только время, расходуемой на сравнения элементов множеств, и если положить время одного сравнения равным 1.

 

Доказательство. Пусть для конкретных заданных множеств выполняются соотношения Ai< Bi и Ai+1> Bi. Тогда отсортированное объединение множеств выглядит следующим образом: {A1, B1, A2, B2 ,…, AN,BN }.  Если хотя бы одно из приведенных 2N-1 соотношений не будет проверено, то найдется еще хотя бы одна перестановка элементов множества, удовлетворяющая всем приведенным соотношениям. Например, если не будет проверено соотношение A2> B1, то следующая последовательность будет удовлетворять всем остальным соотношениям:

{A1, A2, B1, B2 ,…, AN,BN }.

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

 

¢

 

Дословно так же доказывается следующая теорема

 

Теорема. Пусть даны два упорядоченных множества {A1,…,AN +1} и {B1,…,BN }.       В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2N сравнений элементов множества в худшем случае.

 

Алгоритм слияния. Пусть даны два упорядоченных множества {A1,…,AM} и {B1,…,BN }. Введем индексы i, j и k . Изначально i=1, j=1 и k=1 .

 


Пока  i£M и j£N:

     Если Ai < Bj  то

       Сk++ = Ai++

       иначе

      Сk++ = Bi++

    Конец Если

 Конец Цикла

Пока  I £ M:

       Сk++ = Ai++

Конец Цикла

Пока  j £ N:

      Сk++ = Bi++

Конец Цикла

 

 


Легко увидеть,  что в данном алгоритме элементы множества сравниваются не более M+N-1 раз. Т.о. данный алгоритм оказывается строго оптимальным по числу сравнений элементов сортируемого множества (по крайней мере в алгоритмах, основанных на простых сравнениях).

 

Вопрос на понимание: можно ли два упорядоченных множества {A1,…,AN } и {B1,…,BN} слить быстрее чем за 2N-1 операций сравнения в каком либо алгоритме, основанном операциях сравнения? … на операциях простого сравнения?

 

Алгоритм сортировки слиянием. Обозначим данный алгоритм Z(A1,…,AM ), где {A1,…,AN } – сортируемое множество элементов. Алгоритм имеет следующий вид

 


Если число обрабатываемых элементов  £ 1  то ВЫЙТИ

M1 = [ M/2 ]; M2 = M-M1; // размеры половин массива

Z(A1,…,AM1 )

Z(AM1+1,…,AM )

Слить упорядоченные множества {A1,…,A M1 } и { AM1+1,…,AM } в массив B.

Скопировать массив B в массив {A1,…,AN }.

 

 


Легко видеть, что данный алгоритм решает задачу за время O(N log2 N), где N – количество элементов в сортируемом массиве.

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

 

Сортировка слиянием без рекурсии.

 

Предыдущий алгоритм можно модифицировать так, что он уже не будет использовать рекурсию. Действительно. Рассмотрим последовательно все пары элементов в сортируемом массиве. Каждый из элементов в паре представляет собой уже отсортированный массив длины 1, поэтому эти массивы (пока длины 1) можно слить в упорядоченные куски длины 2. Далее мы рассматриваем уже пары упорядоченных массивов длины 2 и сливаем их в массивы длины 4. И т.д.

Отметим, что при этих операциях на k-том проходе по упорядочиваемому массиву на правом конце массива мы будем получать либо ситуацию, когда у правого оставшегося куска (длины £ 2k ) вообще нет парного куска для слияния, либо кусок есть и его длина £ 2k. В первом случае делать вообще ничего не нужно, а во втором следует стандартным способом сливать куски, возможно, существенно различной длины.

Легко видеть, что данный алгоритм решает задачу за время O(N log2 N), где N – количество элементов в сортируемом массиве.

 

 


Лекция 3

Алгоритмы. Сведение алгоритмов.

Сортировки и связанные с ними задачи.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989

 

QuickSort.

Определение. Медианой множества А = {a1 ,…, aN } называется элемент с индексом (N+1)/2 в отсортированном по возрастанию множестве А.

 

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

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

В следующей реализации в комментариях показаны соотношения на значения элементов, которые выполняются после каждого шага алгоритма. Эти соотношения доказывают, что каждый раз массив разбивается на части, левая из которых не превосходит медианы, а правая – не меньше медианы. Здесь для простоты множество элементов { A s  , A s+1 , …  ,  A t } будем обозначать {s,t}. Медиану будем обозначать M.

 

QuickSort(A,p,q)

Если  q-p < 1 то ВЫЙТИ

Вечный цикл

   i=p; j=q; // пусть M=A j

//цикл 1:

   Пока Ai  < A j :  i + +;

//{p,i-1}<=M<={j,q}, Ai>=M

   поменять местами A i  и A j ;//x -> Ai

//{p,i}<=M<={j,q}

   j --;

//{p,i}<=M<={j+1,q}

   Если  i >= j то

//либо i==j                  то {p, j}<=M<={ j+1,q}

// либо i==j+1             то M== Aj+1  => {p, j}<=M<={ j+1,q}

     { QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ }

//цикл 2:

   Пока A j  > Ai :  j - -;

//{p,i}<=M<={j+1,q}, A j<=M

   поменять местами A i  и A j ;//x -> A j

//{p,i}<=M<={j,q}

   i + +;

//{p,i-1}<=M<={j,q}

   Если  i >= j то

//либо i==j                  то M== Aj  => {p, j}<=M<={ j+1,q}

// либо i==j+1             то {p, j}<=M<={ j+1,q}

     { QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ }

Конец вечного цикла

 

В силу построения алгоритма j не может стать меньше 0 и не может быть больше или равным q, поэтому гарантируется, что мы не попадем в бесконечную  рекурсию и границы рассмотрения массива корректны.

 

Отметим, что после первого цикла также имеем:

   Если  i >= j то

//либо i==j                  то {p, i}<=M<={ i+1,q}

// либо i==j+1             то M== Aj+1  => {p, i}<=M<={ i+1,q}

 т.е. рекурсию можно было бы организовать в виде:

{ QuickSort(A, p, i ); QuickSort(A, i+1, q );ВЫЙТИ }

но в этом случае мы можем попасть в бесконечную рекурсию, т.к. в цикле i может дойти вплоть до q.

После второго цикла также имеем:

   Если  i >= j то

//либо i==j                  то {p, i-1}<=M<={ i,q}

// либо i==j+1             то {p, i-1}<=M<={ i,q}

 т.е. рекурсию можно было бы организовать в виде:

{ QuickSort(A, p, i-1 ); QuickSort(A, i, q );ВЫЙТИ }

В этом случае i не может стать меньше 1 и не может быть больше q, поэтому такой вариант алгоритма также возможен.

 

--------------------------------------------------------------------------------

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

 


QuickSort(A,p,q)

Если  q-p < 1 то ВЫЙТИ

 i=p; j=q; x=Ai

Вечный цикл

   Пока A i  < x :  i + +;//{p,i-1}<=x, Ai >=x

   Пока A j  > x :  j - -;//{j+1,q}>=x, Aj <=x

 

   Если  i < j то

      поменять местами A i  и A j ; //{p,i}<=x, {j,q}>=x

   иначе

     {

//либо i==j      то Ai ==x => {p,j}<=x, {j+1,q}>=x

//либо i==j+1 то {p,j}<=x, {j+1,q}>=x

      QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ

     }

   i + +; j - -;//{p,i-1}<=x, {j+1,q}>=x

Конец вечного цикла

 

Замечание 1. При работе алгоритм индексы массива i и j никогда не выйдут за его границы p и  q.

 

Замечание 2. В алгоритме никогда не произойдет вечной рекурсии, т.е. при рекурсивном вызове

p £  j < q

 

Замечание 3. Алгоритм гарантирует корректное разбиение массива, т.е. после разбиения массива выполняются соотношения

Ak £ x для всех k:  p £ k £  j

Al ³ x для всех k:  j+1 £ k £ qj

 

Тонкость алгоритма характеризует следующее наблюдение. Давайте попробуем ``обезопасить алгоритм’’ и включим обеспечение условия i £  j  в циклы алгоритма Пока…  . Т.е. приведем алгоритм к следующему виду:

 

 


QuickSort*(A,p,q)

Если  q-p < 1 то ВЫЙТИ

 i=p; j=q; x=Ai

Вечный цикл

   Пока A i  < x  и  i <  j :  i + +;

   Пока A j  > x  и  i <  j :  j - -;

   Если  i < j то

      поменять местами A i  и A j ;

   иначе

     { QuickSort(A, p, j ); QuickSort(A, j+1, q );ВЫЙТИ }

   i + +; j - -;

Конец вечного цикла

 

Алгоритм QuickSort* оказывается неверным !!! Это легко увидеть на простейшем примере:  {3,4,2,5}.

Доказательство корректности работы алгоритма.

Доказательство корректности работы алгоритма сводится к доказательству Замечаний 1-3 для каждого тела вечного цикла алгоритма.

 

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

1. Случай Ap=min{ Ap , Ap+1 , ..., Aq }. Все остальные элементы массива больше Ap.

В конце первого выполнения тела вечного цикла алгоритма i=p, j=p. Все элементы в первой половине множества (она, в данном случае, состоит из одного элемента) оказываются меньше  элементов из второй половины. Массив разбивается на половины размерами 1:N-1, где N=q-p+1количество элементов в массиве.

2. Все остальные случаи.

 

Доказательство Замечания 1. При работе алгоритм индексы массива i и j никогда не выйдут за его границы p и  q.

Выход за границы массива, потенциально, может произойти только в результате выполнения циклов Покаили при выполнении операций   i + +; j - -;  в конце тела вечного цикла алгоритма.

Изначально на первом месте массива стоит Ap = x. В конце выполнения первого тела вечного цикла алгоритма  Ap может поменяться местами с элементом меньше либо равным x и в дальнейшем элемент Ap не изменится. Т.о. на первом месте массива всегда будет стоять элемент £ x и в процессе выполнения цикла Пока… j не сможет оказаться меньше p. В результате выполнения операций i + +; j - -;  выхода за левую границу массива также не может произойти, т.к. если бы это произошло, то это означало бы, что перед этой операцией выполнялось бы  j=p. Но в этом случае оказывается неверным соотношение  i < j  (т.к. i³p ) и, следовательно, попасть в данную точку алгоритма при этих условиях оказывается невозможным.

Разберемся с правой границей. Если в первый момент Aq ³ x, то j сразу же уменьшится на 1 и впоследствии Aq не изменится. Это гарантирует, что в процессе выполнения цикла Пока… i не сможет оказаться больше q. Если же Aq < x, то после циклов Пока…  i  и  j не изменятся и Ap и Aq сразу же поменяются местами. Далее Aq не изменится и i  не сможет превысить q. В результате выполнения операций i + +; j - -;  выхода за правую границу массива не сможет произойти по причинам аналогичным обсужденным ранее. Замечание доказано.

Доказательство Замечания 2. В алгоритме никогда не произойдет вечной рекурсии, т.е. при рекурсивном вызове

p £  j < q

 

Первое из требуемых неравенств доказано выше. Второе также легко доказать. Действительно, если при первом входе в тело вечного цикла алгоритма Aq ³ x, то j сразу же уменьшится, и мы получим требуемое. Иначе, при первом выполнении тела вечного цикла алгоритма в циклах Пока… , i и j  не изменятся, поэтому после этих циклов  i < j  и  j обязано уменьшится в конце тела цикла. Замечание доказано.

Доказательство Замечания 3. Алгоритм гарантирует корректное разбиение массива, т.е. после разбиения массива выполняются соотношения

Ak £ x для всех k:  p £ k £  j

Al ³ x для всех k:  j+1 £ l £ q

Согласно построению алгоритма в конце выполнения тела вечного цикла алгоритма гарантируется, что

Ak £ x для всех k < i

Al ³ x для всех l > j

 

Т.о. мы сразу же получаем выполнение второго из неравенств Замечания 3. Первое неравенство оказывается более хитрым (именно оно не выполняется при работе алгоритма QuickSort*). В рассматриваемом случае среди элементов правее первого найдется элемент меньше первого, из чего следует, что после первого выполнения циклов Пока…  в тела вечного цикла алгоритма  i останется строго меньше  j, после чего Ai  поменяется местом с Aj и выполнится  i + +; j - - . Т.о. элемент со значением x далее останется в правой половине массива (этот факт мы используем далее в доказательстве теоремы о среднем времени работы алгоритма QuickSort).

Если после выполнения циклов Пока..  в некотором теле вечного цикла алгоритма окажется, что i > j, то из приведенных соотношений сразу следует первое неравенство Замечания 3. Случай i < j говорит о незавершенности алгоритма. Осталось рассмотреть случай i = j. Этот вариант может реализоваться только в случае, когда Aj = x, тогда получаем, что Ak £ x для всех   k <  j  и Ak = x для всех   k =  j. Итого, получаем первое неравенство Замечания 3 (в алгоритме QuickSort* этот случай создается искусственно и поэтому первое неравенство из Замечания 3 остается невыполненным).

¢

Оценки времени работы алгоритма.

Оценим временя работы приведенного алгоритма в худшем случае.

Теорема. Время работы алгоритма  QuickSort  равно O(N 2), где N – количество элементов в сортируемом массиве.

Доказательство. После каждого разбиения массива на две части длина самой большой из двух образовавшихся половин оказывается меньше либо равной длине разбиваемого массива –1. Поэтому на каждой ветви алгоритма будет не более N узлов (разбиений массива). На каждом уровне дерева разбиений присутствуют не более N сортируемых элементов, поэтому время, затрачиваемое на слияние их подмножеств равно O( N ). Итого, суммарное время работы алгоритма равно O( N ) * N = O( N 2).

Данная оценка достижима на массиве {N,N-1,…,1}.

¢

 

Оказывается, что число ``неприятных’’ случаев, т.е. таких расположений массивов чисел, при которых  время работы алгоритма QuickSort велико, оказывается, относительно, небольшим. Вообще, верна теорема

 

Теорема. Среднее время работы алгоритма QuickSort равно Q(N log2 N), где N – количество элементов в сортируемом массиве. Под средним временем подразумевается среднее время по всем перестановкам любого массива входных данных длины N, состоящего из различных элементов.

 

Данная теорема объясняет, в каком смысле данный алгоритм является оптимальным. В то же время, в реальной жизни, часто поток входных данных не является случайным, поэтому в качестве медианы следует брать случайно выбранный элемент. Для этого внесем в алгоритм QuickSort следующее дополнение. Перед присваиванием x=Ai поменяем местами i-ый элемент массива со случайно выбранным элементом среди элементов с индексами от p до q. Назовем получившийся алгоритм QuickSortP. Приведенная теорема верна также и для алгоритма QuickSortP. Докажем ее именно для последнего алгоритма. Будем, кроме того, предполагать, что все элементы входной последовательности различны, или, что то же самое, на входе подается последовательность различных элементов из множества {1,…,N}.

В рассматриваемом случае если x=1, то перед входом в рекурсию алгоритма QuickSort множество разобьется на части размером 1 и N-1. В любом другом случае, как отмечалось выше в доказательстве Замечания 3, элемент x останется в правой половине массива и размер левой половины массива, поэтому, будет равен x-1.

Выпишем рекуррентное соотношение на среднее время работы алгоритма

 

            

T(N) =  [ (T( 1 ) +T( N-1 )) + Si=2i£N (T( i-1 ) +T( N-i+1 ))]/N + Q(N) =

=  [ (T( 1 ) +T( N-1 )) + Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) =

 

= [ (T( 1 ) +T( N-1 ) ]/N + [  Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) =

= [  Si=1i<N (T( i ) +T( N-i ))]/N + Q(N)

 

Предположим, для  i<N верно:

T( i )<a i log i +c для некоторых a>0,  c>0 ,

тогда задача сводится к нахождению таких a>0,  c>0 , что для них всегда бы выполнялось соотношение

 

[  Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) < a N log N +c

Итак

[  Si=1i<N (T( i ) +T( N-i ))]/N < [  Si=1i<N (a i log i +c + a (N-i)  log (N-i) +c ))]/N =

= [  Si=1i<N (a i log i +c ))]2/N < a [  Si=1i<N i log i ]2/N +2 c

 

Оценим сумму из соотношения:

 

Si=1i<N i log i = Si=1i<N i log N + Si=1i<N i log (i/N) = N 2 log N / 2 - Si=1i<N i log (N/i) £  N 2 log N / 2 - Si=1i<N/4 i log (N/i) £  N 2 log N / 2 - Si=1i<N/4 i 2 £  N 2 log N / 2 - N 2/ 8

 

Т.о. имеем

 

[  Si=1i<N (T( i ) +T( N-i ))]/N + Q(N) < a (N  log N  - N / 4) + 2 c + Q(N) =

= a N log N  +  c + (Q(N) + c – a N / 4 )

Осталось взять такое большое a, что  (Q(N) + ca N / 4 )<0, после чего мы получаем требуемое соотношение.

¢

 

 


К сожалению, обе приведенные реализации алгоритма QuickSort не являются жизнеспособными. Это связано с тем, что в обоих алгоритмах максимально возможная глубина рекурсии равна N. В этом случае требуется порядка O(N) байт дополнительной памяти, что не фатально, но проблема в том, что эта память будет выделяться в стеке задачи, а стек задачи всегда имеет маленький (относительно) размер. Поэтому, например, в Microsoft Visual Studio мы может ожидать ситуации stack overflow при размерах целочисленного массива порядка 100000 (размер стека здесь по умолчанию равен 1M).

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

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

 


QuickSortR1(A,p,q)

Если  q-p < 1 то ВЫЙТИ

Вечный цикл

Метка:

   i=p; j=q; x=Ai

   Пока A i  < x :  i + +;

   Пока A j  > x :  j - -;

   Если  i < j то

      поменять местами A i  и A j ;

   иначе

     {

      if(j-p<q-(j+1))

      {

       QuickSort(A, p, j );

        p=j+1;q=q;goto Метка;

      }

      иначе

      {

       QuickSort(A, j+1, q );

        p=p;q=j;goto Метка;

      }

      ВЫЙТИ

     }

   i + +; j - -;

Конец вечного цикла

 

Здесь добавлены:

- метка (может быть заменена еще одним вечным циклом),

- проверка, какая часть массива больше,

- переназначение p,q в каждом случае.

 

 


Некоторые задачи, сводящиеся к сортировке.

К задачам сортировки могут быть за линейное время  сведены следующие классические задачи

 

Задача 1. Найти все различные элементы множества {A1,…,AN }, где – Ai , например, целые или вещественные числа.

 

Задача 2. Определить, все ли элементы в множестве A={A1,…,AN } различаются, где – Ai , например, целые или вещественные числа.

 

 

Задача 3. Определить, совпадают ли два множества {A1,…,AN } и {B1,…,BN } с учетом количества одинаковых элементов в каждом множестве, где  Ai , Bi , например, – целые или вещественные числа.

 

Т.о., мы получаем, что для всех трех приведенных задач верхняя оценка времени решения равна Q (N log N).

Можно задаться вопросом: а можно ли решить эти задачи быстрее? Заметим, что Задача 2 может быть за линейное время сведена к Задаче 1, поэтому если мы докажем, что нижняя оценка времени решения Задачи 2 есть Q(N log N), то тем мы докажем неулучшаемость полученной оценки для Задачи 1.

Задача 2 относится к классу задач о принятии решения. Это значит, что на выходе таких задач выдается всего один бит информации, т.е. ответ `да’ или `нет’. Мы будем рассматривать алгоритмы решения задач о принятии решений, которые сводятся к бинарному дереву принятия решений. Под деревом принятия решений имеется в виду следующее. Пусть на входе нашего алгоритма находится вектор входных данных aÎIR   N.  Рассмотрим бинарное дерево, в каждой вершине которого вычисляется некоторая функция от вектора a и в зависимости от знака этой функции происходит переход на правую или левую ветвь дерева. Каждая конечная вершина дерева будет называться либо принимающей либо отвергающей, в зависимости от приписанного ей соответствующего атрибута. Достижение принимающей вершины означает выдачу алгоритмом ответа  `да’, а отвергающей, соответственно, -  `нет’.

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

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

Введем два определения.

Разделимые множества. Множества A, B Ì IR   N называются разделимыми  (линейно-разделимыми) если " aÎ A, bÎ B найдется cÎ [a,b], такое что сÏ A, сÏ B.

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

Теорема. Пусть W Ì IR   N – множество точек, на которых решением задачи будет `да’. Пусть #W – количество разделимых связных компонент множества W. Тогда, в рамках алгоритмов, описывающихся алгебраическими деревьями степени 1, нижняя оценка времени решения задачи равна W(log 2 #W).

Доказательство. Докажем, что количество принимающих вершин дерева принятия решений не меньше  #W.  Для этого докажем, что все элементы R   N, относящиеся к одной принимающей вершине дерева решений находятся внутри одной разделимой связной компоненты W.

Предположим противное: существует  принимающая вершина дерева принятия решений, в которую попадает алгоритм при использовании двух различных a,bÎ W ,  таких что a и b принадлежат различным разделимым связным компонентам Va , Vb Ì W,  соответственно. Рассмотрим [a,b]. Линейные функции от N переменных обладают свойством монотонности на отрезке, поэтому все функции, вычисляющиеся в вершинах дерева принятия решений, сохраняют свой знак на [a,b].  Т.о. весь отрезок [a,b] Ì W (т.к. все точки из отрезка обязаны попасть в одно и ту же принимающую вершину). Это противоречит предположению о принадлежности a и b различным разделимым компонентам.

Итак, мы получили, что количество концевых вершин бинарного дерева принятия решений не меньше #W, из чего сразу следует, что высота дерева не меньше [log 2 #W].

¢

 

Вернемся к решению Задачи 2. Рассмотрим множество W для Задачи 2. Легко увидеть, что W – открыто. Для точки P Î IR   N будем называть связной компонентой, содержащей P, множество WP Ì W, состоящее из таких точек R Î W, для которых существует ломаная, соединяющая P и R , содержащаяся в W. В силу открытости W каждая такая точка R имеет окрестность OR Ì W, а значит OR Ì WP . Но тогда WP  можно представить как объединение всех описанных окрестностей OR , а объединение любого количества открытых множеств открыто. Т.о. множество WP открыто, а значит (в силу определения множества) и связно.

Рассмотрим в качестве различных вариантов входных данных задачи все перестановки последовательности {1,2,…,N}. Т.е.

Ap= {p(1), p(2),…, p(N)}, где pнекоторая перестановка.

Докажем, что каждая последовательность Ap принадлежит своей связной компоненте WAP множества W и что все WAP линейно разделимы. Тогда мы докажем, что каждая Ap принадлежит своей разделимой связной компоненте. Действительно, допустим противное, т.е. пусть две различные последовательности Ap1  и  Ap2 принадлежат одной связной компоненте W. Тогда найдутся 1 £ i, j £ N, такие что (p1(i)- p1(j)) (p2(i)- p2(j))<0, т.е. (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки. Но тогда для любой ломаной S, соединяющей точки Ap1  и  Ap2 Î IR   N , найдется x Î S такая, что xi = xj , что противоречит принадлежности Ap1  и  Ap2 одной связной компоненте множества W.

Аналогично доказывается, что компоненты WP1 и WP2 линейно разделимы. Действительно, рассмотрим произвольные точки p1Î WP1 и p2Î WP2. Для тех же самых индексов i, j получим, что (p1(i)- p1(j)) (p2(i)- p2(j))<0 (здесь мы использовали следующее утверждение: для любой пары i, j внутри одной открытой связной компоненты W знак p(i)- p(j) для всех точек одинаков), из чего сразу получаем, что на отрезке, соединяющем p1 и p2, найдется точка, не принадлежащая W.

В приведенном доказательстве требует объяснения следующий факт: для двух различных перестановок множества {1,2,…,N}  всегда найдутся 1 £ i, j £ N, такие что (p1(i)- p1(j)) и (p2(i)- p2(j)) имеют разные знаки. Пусть для каждой перестановки p:  tk – количество чисел p(i) больших p(k) для i>k. Легко увидеть, что p и t однозначно задают друг друга.

Действительно, для p(i)=N имеем t(i)=0, причем для j<i выполняется: t(j)>0. (отметим, что t(i)=0 может выполняться и для других i) Поэтому если мы найдем минимальное i такое, что t(i)=0, то сразу получим, что p(i)=N; далее положим p(i)=-1, что потребует уменьшить на 1 все t(j) для j<i, а t(i) тоже положим равной -1, чтобы исключить из рассмотрения. Для нахождения i такого, что p(i)=N-1, мы опять ищем минимальное i такое, что t(i)=0. После исключения из рассмотрения найденного i и уменьшения на 1 всех t(j) для j<i мы можем перейти к поиску i такого, что p(i)=N-2, и т.д.

Пример:

p={4,5,3,1,2} => t={1,0,0,1,0}

Ищем p по заданной t:

1)Ищем минимальное i, для которого t(i)=0: i=2 => p(2)=5

Для всех j<2 уменьшаем t на 1 и кладем t(i)=-1:

t={0,-1,0,1,0}

2) Ищем минимальное i, для которого t(i)=0: i=1 => p(1)=4

Для всех j<1 уменьшаем t на 1 (таковых нет) и кладем t(i)=-1:

t={-1,-1,0,1,0}

3) Ищем минимальное i, для которого t(i)=0: i=3 => p(3)=3

Для всех j<3 уменьшаем t на 1 и кладем t(i)=-1:

t={-2,-3,-1,1,0}

4) Ищем минимальное i, для которого t(i)=0: i=5 => p(5)=2

Для всех j<5 уменьшаем t на 1 и кладем t(i)=-1:

t={-3,-4,-2,0,-1}

5) Ищем минимальное i, для которого t(i)=0: i=4 => p(4)=1

 

Т.о. для двух различных перестановок  p1 и p2  мы получим различные соответствующие t1 и t2 . Выберем i: t1(i)  ¹ t2(i). Пусть, например, t1(i)  > t2(i), но тогда найдется j>i, такое что p1(j)> p1(i), но  p2(j)< p2(i). Получили требуемое.

¢

 

Итак, мы доказали, что  верна следующая

Теорема. Задачи 1 и 2 имеют нижнюю оценку времени решения W (NlogN) на алгоритмах, основанных на алгебраическом дереве принятия  решения первой степени.

 

Для Задачи 3 также можно доказать аналогичную теорему:

 

Теорема. Задача 3 имеет нижнюю оценку времени решения W (NlogN) на алгоритмах, основанных на алгебраическом дереве принятия  решения первой степени.

Для доказательства рассмотрим все пары последовательностей {1,2,…,N} и {s1,s2,…,sN} для всех перестановок s. Назовем эти последовательности A и Bs. Покажем, что количество принимающих вершин любого алгебраического дерева принятия решения первой степени, решающего заданную задачу, не меньше, чем количество всевозможных пар {A, Bs}. В этом случае мы сразу получим, что высота дерева принятия решения будет не меньше Q (log(N!))= Q (N log N), что докажет нашу теорему.

Доказательство требуемого факта тривиально. Нам достаточно доказать, что никакие две различные пары {A, Bs} и {A, Br} не могут попасть в одну принимающую вершину данного дерева принятия решений. Докажем данный факт от противного.

Пусть есть две различные пары {A, Bs} и {A, Br}, на которых данный алгоритм попадает в одну принимающую вершину алгебраического дерева принятий решений первой степени. Тогда найдется индекс i для которого risi. Рассмотрим пары последовательностей {A, Bst}, для которых Bst=tBs+(1-t) Br , где tÎ(0,1). Значения Bst для tÎ[0,1] образуют собой отрезок в пространстве IR   2N. В данных парах последовательностей элемент Bst с индексом i должен принимать все возможное значения в интервале (Min(ri,si), Max(ri,si)). Тогда, с одной стороны  любая пара {A, Bst} должна попасть в ту же принимающую вершину (в силу проверки линейных соотношений в каждой вершине дерева и сохранения знака линейной функции на отрезке), а с другой, среди возможных значений t обязательно найдется значение, не встречающееся в последовательности A. Получаемое противоречие завершает доказательство.

¢

Заметим, что Задача 3 также, как и Задача 2, может быть сведена к Задаче 1.

 

 


Лекция 4

Алгоритмы. Сведение алгоритмов.

Сортировки и связанные с ними задачи.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989

 

 

 

К вопросу о понимании предыдущих лекций. Найти ошибку.
``Доказательство'' того, что любое натуральное число можно однозначно получить с помощью алгоритма, задаваемого не более, чем 20-тью словами (имеется в виду, можно использовать только существующие в языке слова, а не что-нибудь вроде "ШестьсотШестьдесятШесть"). 
Пусть это не так. Тогда существует множество, являющееся подмножеством натуральных чисел, каждый элемент которого невозможно получить с помощью алгоритма, задаваемого не более, чем 30 словами. У всякого подмножества натуральных чисел есть наименьший элемент.
Получаем: "Наименьшее натуральное число, которое нельзя получить с помощью алгоритма, задаваемого не более, чем 30 словами, имеющимися в русском языке" - итого 20 слов потребовалось, дабы назвать данное число, которое принадлежит этому великолепному множеству => противоречие.
 
 

 

 

HeapSort или сортировка с помощью пирамиды.

Алгоритм основан на промежуточном упорядочивании массива входных данных {A1 ,…, AN }.  Мы докажем, что промежуточно-упорядоченный массив (мы будем его называть пирамидально-упорядоченным) обладает свойством максимальности своего первого элемента. Тогда мы отрезаем от массива первый элемент и восстанавливаем утраченное свойство пирамидально-упорядоченности у оставшегося куска. Так, отрезая по одному (максимальному из оставшихся) элементу, мы можем `набрать’ полный упорядоченный массив.

Определение. Массив {A1 ,…, AN } называется пирамидально-упорядоченным, если для всех допустимых i:  A[i/2] ³ Ai .

Иначе данное соотношение можно выписать следующим образом:

Ai ³ A2i и Ai ³ A2i+1                                                   (*)

Легко видеть, что данные соотношения задают древообразную структуру, в вершине которой находится первый элемент дерева. Его потомками являются элементы с номерами 2 и 3, и т.д. В получившемся дереве все слои заполнены, кроме, быть может, последнего. Поэтому глубина дерева равна [log N]+1, где N – количество элементов в множестве.

Пусть для некоторого поддерева пирамиды, начинающегося с элемента с индексом i   и заканчивающегося элементом с индексом N, выполнено свойство  (*) для всех элементов поддерева, кроме вершины поддерева. Т.е. свойство выполняется для всех элементов, имеющих индексы больше  i (здесь имеется в виду возможное невыполнения условий Ak ³ A2k и Ak ³ A2k+1  для k=i и его выполнение при k>i).

Определим процедуру Heapify(A,i,N), которая в данном случае подправляет элементы поддерева до полной пирамидально-упорядоченности элементов с индексами от i до N. Здесь Aрассматриваемый массив, iиндекс массива с которого начинается рассматриваемое поддерево, Nколичество элементов во всем дереве.

Процедура Heapify(A,i,N) осуществляет следующие действия. Она проверяет условия

Ai ³ A2i    в случае 2i£N  

Ai ³ A2i+1  в случае 2i+1£N.

Если они выполняются (случаи 2i³N, 2i+1³N легко рассмотреть отдельно), то дальше ничего делать не надо, происходит выход из процедуры. Иначе, выбирается максимальный из элементов Ai , A2i, A2i+1 и выбранный элемент меняется местами с Ai . Не ограничивая общности рассуждений, допустим, что максимальным оказался элемент A2i , тогда после перестановки имеем Ai ³ A2i+1  , при этом элемент A2i+1  не изменился, поэтому свойство пирамидально-упорядоченности будет выполняться и дальше в данном (правом) поддереве. Далее рекурсивно вызываем процедуру Heapify(A,2i,N).

Исходя из построения процедуры Heapify, имеем следующее утверждение

Утверждение 1. Процедура Heapify(A,i,N) выполняется за время O( h(i,N) ), где h(i,N) – глубина поддерева в пирамиде из N элементов, начинающегося с элемента с индексом i.

 

Алгоритм Heapsort(A,N) выглядит следующим образом

 

Heapsort(A,N)

 


Для всех i от N-1 до 1 с шагом –1 выполнить: Heapify(A,i,N)

Для всех i от 1 до N-1  с шагом 1 выполнить

    Поменять местами элементы A1 и  AN-i+1

    Heapify(A,1,N-i)

 

 

Первый цикл в алгоритме создает пирамиду, а второй, используя ее свойство максимальности первого элемента, создает упорядоченный массив. Согласно Утверждению 1, каждый цикл состоит из N процедур, каждая из которых выполняется за время O(log 2 N), из чего вытекает теорема

Теорема. Время работы алгоритма Heapsort(A,N) равно O(N log 2 N).

 

На самом деле, оказывается, что время работы первого из двух циклов алгоритма равно O(N). Действительно, процедура Heapify(A,i)  для каждого i из последнего уровня дерева выполняется за время O(1) (а в этом уровне содержится половина всех элементов!). Для следующего уровня время выполнения процедуры равно уже O(2). И т.д.

Т.о. суммарное время работы алгоритма вычисляется по формуле

T(N) =  O(Si=0i£h (h-i+1) 2i)

где высота дерева равна h+1 (т.е. дерево имеет уровни с номерами от 0 до h).

Докажем соотношение T(N)/2h = Q (1). Отсюда и из того, что количество элементов в дереве высотой h+1 находится между 2h-1 и 2h, мы сразу получим, что время работы алгоритма равно O(N).

Рассмотрим следующие равенства для некоторого x¹1

1 + x + x2 + … + xN = ( 1- xN+1 )/(1-x),  тогда, взяв производную по x, получим

1 +2x + 3x2 + … + NxN-1 = (- (N+1)xN(1-x) + ( 1- xN+1 )  )/(1-x)2=Q (1),  если x =1/2.

C другой стороны, положим  j=h-i+1, тогда

 T(N)/2h= O(Si=0 i £ h (h-i+1) 2i-h)= O(Sj=1 j £ h+1 j 2 - j+1)= O(Sj=1 j £ h+1 j 2 - j) =Q (1).

¢

Из вышесказанного вытекает, что мы имеем возможность получить упорядоченный подмассив, состоящий из довольно большого количества самых больших элементов исходного массива, за время O(N), где N – количество элементов в массиве. Более строго, верна теорема

Теорема. Получить упорядоченный массив из N / log 2 N самых больших элементов массива можно за время O(N).

 

 


Алгоритмы сортировки за время O(N)

 

Итак, мы рассмотрели алгоритмы, основанные на операциях сравнения, и для них получили нижнюю оценку времени выполнения. Возникает вопрос, а можно ли на ЭВМ выполнять операцию сортировки быстрее? Здесь следует отметить, что на ЭВМ есть операция, которая принципиально не вписывается в множество рассмотренных операций. Это – операция индексации массива с использованием в качестве индекса функций, вычисляемых от упорядочиваемых элементов. Все алгоритмы, выполняющиеся за время O(N) используют эту операцию.

Сортировка подсчетом

Пусть мы хотим отсортировать N целых чисел A={A1,…, AN}, каждое из которых не превосходит K, при этом K=O(N). Тогда мы можем создать временный массив B размером K, в который можно поместить для каждого i  количество чисел в массиве A, не превосходящих i. Тогда для каждого 1 £ i £ N: в отсортированном массиве в элементе с индексом BA i  лежит элемент, равный Ai .

Итак, приведем реализацию данного алгоритма. Результат будем помещать в третий массив C

CountingSort (A,C, N,K,  B)

 


Для всех i от 1 до K с шагом 1 выполнить: B[i]=0

Для всех i от 1 до N с шагом 1 выполнить: B[A[i]] ++

Для всех i от 1 до N с шагом 1 выполнить: B[A[i]]= B[A[i]]+ B[A[i-1]] 

Для всех i от N до 1 с шагом -1 выполнить: C[B[A[i]]] = A[i]; B[A[i]]- -

 

 


Единственным дополнением к вышеприведенному описанию в этом алгоритме является добавка в его конец `B[A[i]]- -’ . Эта добавка гарантирует, что если в массиве A есть элементы с равными значениями, то они будут положены в различные ячейки массива C. Более того, каждый следующий элемент со значением, равным некоторому x (при обратном проходе!), будет помещаться в ячейку левее предыдущей. Поэтому данная сортировка сохраняет взаимное расположение равных элементов. Этой свойство сортировки называется устойчивостью. Это свойство имеет смысл, когда равенство элементов в смысле сравнения не влечет тождественного равенства элементов. Например, это происходит если сортировка идет по ключу.

Цифровая сортировка

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

Теорема. Алгоритм цифровой сортировки требует O(nd) операций, где n – максимальное количество операций для одной внутренней сортировки, d – количество цифр.

Этот алгоритм облегчает использование сортировки подсчетом. Действительно, если есть большой массив 32-битных целых чисел без приемлемых ограничений на их величину,  то можно разбить их на 2 либо 4 части и рассмотреть каждую часть как одну цифру в алгоритме цифровой сортировки.

Сортировка вычерпыванием

Пусть требуется отсортировать массив из N вещественных чисел A={A1,…, AN}, равномерно распределенных на интервале [0,1). Идея алгоритма заключается в следующем. Разобьем интервал [0,1) на N равных частей и каждой части сопоставим свой контейнер элементов (например, в самом простом случае, массив вещественных чисел длины N). Каждое число x положим в контейнер с номером [x*N]. После этого отсортируем элементы в каждом контейнере и соберем по порядку элементы из всех контейнеров вместе.

Более конкретно, для реализации контейнеров мы сначала посчитаем, сколько элементов попадет в каждый контейнер, а потом для распределения элементов по контейнерам нам достаточно будет иметь один массив вещественных чисел длины N. Итак, для сортировки массива A, состоящего из N элементов, мы должны завести массивы целых чисел M, I длины N и массив вещественных чисел B длины N.  Пусть функция Sort(B,i0,n) выполняет сортировку пузырьком части массива B , начинающейся с элемента с индексом i0, состоящей из n элементов. Тогда алгоритм имеет следующий вид

SortB (A, N, M, B)

 


Для всех i от 1 до N с шагом 1 выполнить: M[i]=0; I[i]=0; B[i]=0

Для всех i от 1 до N с шагом 1 выполнить: M[A[i]*N+1] ++

Для всех i от 2 до N с шагом 1 выполнить: M[i] = M[i]+ M[i-1]

Для всех i от N до 2 с шагом -1 выполнить: M[i] = M[i-1]

M[0]=0

Для всех i от 1 до N с шагом 1 выполнить: B[M[i]+I[i]+A[i]*N+1]= A[i]; I[i]++

Для всех i от 1 до N с шагом 1 выполнить: Sort(B,M[i],I[i])

Для всех i от 1 до N с шагом 1 выполнить:

    Для всех j от 1 до I[i] с шагом 1 выполнить: A[k]= B[ M[i]+j ]; k++

 

 


Во втором цикле алгоритма мы подсчитываем количество элементов, попавших в i-ый интервал. В третьем и четвертом циклах мы помещаем в M[i] индекс первого элемента части массива B, относящейся к контейнеру с номером i. В пятом цикле мы помещаем элементы в соответствующие контейнеры. В шестом цикле происходит сортировка элементов в контейнерах. Далее мы последовательно выбираем элементы в результирующий массив A.

 

Теорема. Алгоритм SortB работает за время O(N) в среднем, где N – количество сортируемых элементов.

Доказательство. Пусть p=1/N. Вероятность попадания в один контейнер k элементов равна pkNk pk (1-p)N-k  (биноминальное распределение).  Время работы алгоритма сортировки в одном контейнере равно S O(k2), где k – количество элементов, попавших в i-ый контейнер.

Согласно свойствам биномиального распределения, среднее (математическое ожидание) количество элементов в контейнере равно M(k)= Sk  pkk=Np=1.  Средне-квадратичное отклонение от среднего значения (дисперсия) количества элементов в контейнере равно D(k)= S k  pk(k- M(k))2=S  k pk(k-1)2=Np(1-p)=1-1/N.

D(k)=M(k2) – (M(k))2  из чего сразу следует M(k2)=D(k) +(M(k))2=2-1/N. Итого, среднее время сортировки одного контейнера равно O(1), а среднее время сортировок N контейнеров равно O(N).

¢

 



Лекция 5

Алгоритмы. Сведение алгоритмов.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989

 

 

 

Порядковые статистики.

Определение. Медианой множества А = {a1 ,…, aN } называется элемент с индексом (N+1)/2 в отсортированном по возрастанию множестве А.

 

Определение. k-той порядковой статистикой множества из N вещественных чисел A={A1,…, AN} называется k-тое число в упорядоченном множестве A. Легко увидеть, что [(N+1)/2]-ая порядковая статистика является медианой множества. В свою очередь, если бы мы могли эффективно искать медиану множества, то это дало бы хорошую модификацию алгоритма QuickSort.

Из предыдущей главы следует, что верхней оценкой  времени поиска k-той порядковой статистикой является O(N log2 N). Оказывается, что эту оценку можно улучшить.

Поиск порядковой статистики за время Q(N) в среднем

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

 


 QFindStatP (A,p,q,k,N)

Если  q-p < 1 то return Ap

Вечный цикл

   i=p; j=q;

  Поменять местами Ap и случайно выбранный элемент Al , где p £ l £ q

   x=Ai

   Пока A i  < x :  i + +;

   Пока A j  > x :  j - -;

   Если  i < j то

      поменять местами A i  и A j ;

   иначе

     {Если k £ j

       то  return QFindStatP (A, p, j, k,N )

       иначе return QFindStatP (A, j+1, q, k,N ) 

     }

   i + +; j - -;

Конец вечного цикла

 

 

Теорема. Время работы алгоритма  QFindStatP  равно O(N 2), где N – количество элементов в обрабатываемом массиве.

Доказательство. После каждого разбиения массива на две части длина самой большой из двух образовавшихся половин оказывается меньше либо равной длине разбиваемого массива –1. Поэтому на каждой ветви алгоритма будет не более N узлов (разбиений массива). На каждом уровне дерева разбиений присутствуют не более N элементов, по которым производится поиск, поэтому суммарное время работы на одном уровне дерева равно O( N ). Итого, суммарное время работы алгоритма равно O( N ) * N = O( N 2).

Данная оценка достижима на массиве {1, …, N-1,N} при поиске, например, N-ой порядковой статистики и при том, что в качестве псевдомедианы каждый раз будет выбираться первый элемент в подмассиве.

 

Теорема. Среднее время работы алгоритма QFindStatP равно Q(N), где N – количество элементов в обрабатываемом массиве. Под средним временем подразумевается среднее время по всем перестановкам любого массива входных данных длины N.

Доказательство. Выпишем рекуррентное соотношение на среднее время работы алгоритма

 

            

T(N) £ [ T( N-1 )  + Si=2i£N MAX(T( i-1 ), T( N-i+1 )) ]/N + O(N) =

=  [ T( N -1)  + Si=1i<N MAX(T( i ), T( N-i )) ]/N + O(N) £

£  [ T( N -1)  + 2Si=N/2i<N T( i ) ]/N + O(N) £

£  [ 2 Si= N/2i<N T( i ) ]/N + O(N) 

 

Предположим, для  i<N верно:

T( i )<a i + c для некоторых a>0,  c>0 ,

тогда задача сводится к нахождению таких a>0,  c>0 , что для них всегда бы выполнялось соотношение

[ 2 Si= N/2i<N T( i ) ]/N + O(N)  < a N + c

Итак

T(N) £  [ 2 Si= N/2i<N T( i ) ]/N + O(N)   £ a 3/4 * N + c + O(N)

 

Осталось взять такое большое a, что  a 3/4 * N  + O(N) < a N , после чего мы получаем T(N) = O(N). Осталось заметить, что первое же разбиение массива на две части (а в лучшем случае оно же будет и последним) требует времени Q(N),  из чего мы получаем, что T(N) =Q(N).

¢

 

Поиск порядковой статистики за время Q(N) в худшем случае

Зададимся целью написать алгоритм нахождения k-ой порядковой статистики, требующий  Q(N) операций в худшем случае. Это было бы возможным, если бы в алгоритме QFindStatP  на каждом этапе разбиения множества на две части мы бы получали части размером не менее sL, где L – длина разбиваемой части множества, s<1. Для этой цели мы построим алгоритм QFindStat5, который перед разбиением множества на две части разбивает его на пятерки последовательных элементов, в каждой пятерке ищет медиану и на полученном множестве медиан пятерок чисел запускает самого себя для поиска медианы полученного множества. Полученную медиану медиан x алгоритм использует для разбиения множества на две части, состоящих, соответственно, из элементов меньше или равных x, и из элементов больше или равных x. Далее, в зависимости от k, следует применить QFindStat5 к одной из полученных половин множества.

QFindStat5(A,1,N,k)

 


Если N £ 5 то найти медиану x любым методом; return x

Разбить массив A[1…N] на пятерки элементов и

отсортировать элементы внутри пятерок

 x= QFindStat5 (A,1,[(N+4)/5], ([(N+4)/5]+1)/2), где A – массив медиан пятерок

Выполнить один шаг QuickSortP для псевдомедианы x

     => массив разбит на куски длиной L и N-L

Если k £ L то return QFindStat5 (A,1,L,k)

                    иначе return QFindStat5 (A,L+1,N,k)

 

 


Теорема. Время работы алгоритма QFindStat5 равно Q(N), где N – количество элементов в обрабатываемом массиве.

Доказательство. В массиве медиан пятерок [(N+4)/5] элементов. Нахождение медианы x этого множества гарантирует, что в каждой пятерке справа от x , включая пятерку с x (см. рисунок ниже), и кроме последней пятерки, 3 элемента больше или равны x (на рисунке эти элементы выделены серой областью). Количество всех указанных пятерок не менее [([(N+4)/5]+1)/2], последняя пятерка может быть не полной и в ней, в худшем случае, может быть всего один элемент больше или равный x. Если теперь исключить из описанного множества x, то получается, что мы имеем 3[([(N+4)/5]+1)/2] - 3 элементов больше или равных x. Легко показать, что такое же количество элементов меньше или равны x. Т.о. после выполнения одного шага QuickSortP  останется не более N - 3[([(N+4)/5]+1)/2] + 3 £ N – 3N/10 + 3 = 7N/10 + 3  элементов.

Оценим время выполнения алгоритма QFindStat5 : T(N).  Оно складывается из времени поиска медианы медиан пятерок элементов (T([(N+4)/5])), времени поиска медианы в отрезанном куске множества длиной не более 7N/10 + 3  (T(7N/10 + 3)) и всего остального (O(N)).

 

 

T(N) £ T(N/5+1) + T(7N/10 + 3) + O(N)

Теперь, если предположить, что T(i) £ c i, для i<N, то получим

T(N) £  с(N/5+1) + с(7N/10 + 3) + O(N) £ с( 9N/10 + 4 ) + O(N) =

= сN + (O(N) – c(N/10 - 4))

Выбрав достаточно большое c получим, что для N>40

O(N) – c(N/10 - 4) £ 0

Далее, выбрав еще большее c можно получить, что для N£40

T(N) £ сN

 

Т.о. мы получим, что T(N) £ сN для любого N.

¢

 

 


Язык программирования C.

 

Б.В. Керниган, Д.М. Ричи. Язык программирования С.

 

 

 

Переменные

 

Основные типы

В языке С есть две основные разновидности базовых типов: целые и вещественные. К целым типам относятся типы

char

short

int

long

Перед каждым вышеупомянутым типом может присутствовать слово signed или unsigned. Идентификатор signed указывает на то, что переменная имеет знак, а unsigned – на отсутствие знака у переменной. По умолчанию, все переменные имеют знак. Исключением является переменная типа char. Полагаться на наличие/отсутствие знака у переменной данного типа нельзя, т.к., как правило,  данное свойство может быть изменено с помощью ключей компилятора.

Известно, что в данном списке указанные типы располагаются по неубыванию их размеров. Если требуется узнать конкретный размер переменной в байтах, то он может быть получен с помощью оператора sizeof(): sizeof(char).

К вещественным типам относятся

float

double

Известно, что sizeof(float) £ sizeof(double).

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

 

Базовые понятия

Ø  описание и определение

Ø  время жизни

Ø  область видимости или область действия

Одними из основных понятий программирования являются описание и определение объектов.

Описание переменной задает ее тип и указывает на то, что переменная где-то определена. Признаком описания переменной служит наличие ключевого слова extern перед оператором, ее задающим. Отсутствие ключевого слова extern говорит об определении переменной.

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

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

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

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

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

Автоматические переменные разрешается определять только в начале блока, перед выполняемыми операторами.

Автоматические переменные используют память, выделяемые в системном стеке, что делает процедуру отведения/очистки памяти под них весьма быстрой. Однако, как правило, системный стек имеет ограниченный размер и, поэтому, нельзя создавать автоматические переменные слишком большого размера. Причиной переполнения стека (stack overflow) может также служить бесконечная рекурсия, случайно созданная в программе.

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

Осталось упомянуть о внешних статических переменных – глобальных переменных, область видимости которых ограничена данным файлом. Как и все глобальные переменные, эти переменные определяются вне всех блоков программы, но перед их определением написано ключевое слово static.

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

Изначально в языке С присутствуют регистровые переменные. Наличие ключевого слова register перед определением переменной служит указанием компилятору использовать внутренние машинные регистры для хранения данной переменной. На данный момент, при использовании оптимизирующих компиляторов наличие данного типа, как правило, не может служить для ускорения работы программы. Более того, обязательное использование регистра для хранения данной переменной запрещает его использование для других целей, что может послужить поводом к замедлению работы программы.

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

 


Структуры данных.

 

Структурой данных является реализация понятия множества элементов определенного типа. Под реализацией понимается способ хранения данных. Вместе со способом хранения  задается набор операций (=алгоритмов) по добавлению, поиску, удалению элементов множества.

 

Вектор.

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

Создание исполнителя вектор предполагает наличие следующих функций

Ø  создать вектор длины n

Ø  положить элемент в вектор по индексу i

Ø  взять элемент из вектора по индексу i

Ø  уничтожить вектор

При использовании массивов для реализации структуры данных вектор, создание/уничтожение объекта происходит в соответствующие моменты автоматически. Если же этим процессом надо управлять, то следует использовать функции malloc() / free().

Возможна ситуация, когда размер вектора становится известным уже после написания программы, но до ее компиляции (или мы для одной программы хотим получать ее различные версии для различных длин вектора). В этой ситуации можно задать размер массива константой препроцессора. Значение константы можно передать через ключи компилятора. Например, в программе (в файле prog.c) можно записать следующий набор операторов :

 

#ifndef N

#define N  100

#endif

int Array[N] ;

 

Если константа N  не определена, то ее значение полагается равным 100. Далее создается массив из N элементов. У большинства компиляторов значение константы препроцессора можно передать через ключ `D’, например, для компилятора gcc это будет выглядеть так:

 

gccDN=200  prog.c

 

В получившейся программе с именем ./a.out везде вместо идентификатора N будет подставляться 200.

 

Стек.

 Стеком называется структура данных, организованная по принципу LIFOlast-in, first-out , т.е. элемент, попавшим в множество последним, должен первым его покинуть. При практическом использовании часто налагается ограничение на длину стека, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя стек предполагает наличие следующих функций

Ø  инициализация

Ø  добавление элемента на вершину стека

Ø  взятие/извлечение элемента с вершины стека

Ø  проверка: пуст ли стек?

Ø  очистка стека

 

Стек можно реализовать на базе массива или (в языке С ) это можно сделать на базе указателей.

Стек. Реализация 1.

Для реализации стека целых чисел, состоящего не более чем из 100  чисел, на базе массива в языке С  следует определить массив целых, состоящий из 100  чисел и целую переменную, указывающую на вершину стека (ее значение будет также равно числу элементов в стеке)

int stack[100], i0=0;

 

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

Стек. Реализация 2.

Для группировки различных переменных в один объект (например, чтобы впоследствии, так или иначе, передавать этот объект в функции за один прием) в языке С следует использовать структуры. Например, все данные, относящиеся к стеку можно поместить в структуру struct SStack:

 

struct SStack

{

int stack[100];

int i0;

};

 

Здесь создан новый тип с именем struct SStack. Далее можно создать переменную этого типа:

struct SStack st2;

 

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

 

 void InitStack(struct SStack *ss){ ss->i0=0 ;}

 

Вызов функции осуществляется следующим способом :

 

InitStack(&st2) ;

 

Стек. Реализация 3.

 

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

int *stack, *head;

 

Как и ранее, эти переменные можно объединить в структуру:

 

struct SStack3{ int *stack, *head; };

 

Тогда соответствующую переменную st3 можно определить оператором

 

struct SStack3 st3;

 

Стек. Реализация 4.

 

Однако, можно поступить и по-другому. Т.к. элементы stack и head имеют один тип, то их можно объединить в один массив объектов соответствующего типа (т.е. типа int* ). Массив, естественно, должен быть длины 2:

 

int *st4[2];

 

Здесь следует заметить, что при определении/описании переменных квадратные скобки имеют приоритет больший, чем *, поэтому переменная st4  имеет тип `массив указателей’, а не `указатель на массив’.

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

 

void StackCreate4(int n, int *st[2] ) {st[1]= st[0] = (int*)malloc(n*sizeof(int));}

 

а ее вызов будет выглядеть так: StackCreate4(n,st4);

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

 

void StackAdd4(int v, int * st[2] ) { (*(st[1]++)) = v;}

 

а ее вызов будет выглядеть так: StackAdd4 (v, st4);

Проверка стека на пустоту выглядит следующим образом :

 

int StackIsEmpty4 ( int * st[2] ) { return st[1]<=st[0] ; }

 

Стек. Реализация 5.

 

У Реализации 4 есть существенный недостаток. Допустим, что стек создан внутри некоторой функции  и требуется использовать его вне данной функции. Тогда у нас есть единственная возможность осуществить данную реализацию, это - сделать переменную st4 глобальной или локальной статической. В противном случае, при выходе из данной функции переменная st4 утратит свое существование и указателями st4[0], st4[1] уже нельзя будет пользоваться. Но, как уже писалось, подобный способ реализации является дурным стилем.

Собственно, вся наша проблема состоит в том, что память под переменную st4 отводится и очищается автоматически. В качестве альтернативы, отведение/очистку памяти под указатели можно взять на себя. Для этого следует использовать указатель на указатель на целую переменную:

int **st5;

 

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

 

int ** StackCreate5(int n )

 {int **st; st = (int**)malloc(2*sizeof(int*)); st[1]= st[0] = (int*)malloc(n*sizeof(int));}

 

а ее вызов будет выглядеть так: st5=StackCreate5(n);

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

 

void StackDelete5(int  **st ) { free(st[0]); free(st);}

а ее вызов будет выглядеть так:  StackDelete5 (st5);

 

 



Лекция 6

 

Структуры данных ( + в языке С: массивы, структуры, оператор typedef).

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

 

 

Структурой данных является реализация понятия множества элементов определенного типа. Под реализацией понимается способ хранения данных. Вместе со способом хранения  задается набор операций (=алгоритмов) по добавлению, поиску, удалению элементов множества.

 

Стек.

 Стеком называется структура данных, организованная по принципу LIFOlast-in, first-out , т.е. элемент, попавшим в множество последним, должен первым его покинуть. При практическом использовании часто налагается ограничение на длину стека, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя стек предполагает наличие следующих функций

Ø  инициализация

Ø  добавление элемента на вершину стека

Ø  взятие/извлечение элемента с вершины стека

Ø  проверка: пуст ли стек?

Ø  очистка стека

 

Стек можно реализовать на базе массива или (в языке С ) это можно сделать на базе указателей.

Стек. Реализация 1 (на основе массива).

Для реализации стека целых чисел, состоящего не более чем из 100  чисел, на базе массива в языке С  следует определить массив целых, состоящий из 100  чисел и целую переменную, указывающую на вершину стека (ее значение будет также равно числу элементов в стеке)

int stack[100], i0=0;

 

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

Стек. Реализация 2 (на основе массива с использованием общей структуры).

Для группировки различных переменных в один объект (например, чтобы впоследствии, так или иначе, передавать этот объект в функции за один прием) в языке С следует использовать структуры. Например, все данные, относящиеся к стеку можно поместить в общую структуру struct SStack:

 

struct SStack

{

int stack[100];

int i0;

};

 

Здесь создан новый тип с именем struct SStack. Далее можно создать переменную этого типа:

struct SStack st2;

 

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

 

 void InitStack(struct SStack *ss){ ss->i0=0 ;}

 

Вызов функции осуществляется следующим способом :

 

InitStack(&st2) ;

 

Стек. Реализация 3 (на основе указателей).

 

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

int *stack, *head;

 

Как и ранее, эти переменные можно объединить в структуру:

 

struct SStack3{ int *stack, *head; };

 

Тогда соответствующую переменную st3 можно определить оператором

 

struct SStack3 st3;

 

Стек. Реализация 4 (на основе массива из двух указателей).

 

Однако, можно поступить и по-другому. Т.к. элементы stack и head имеют один тип, то их можно объединить в один массив объектов соответствующего типа (т.е. типа int* ). Массив, естественно, должен быть длины 2:

 

int *st4[2];

 

Здесь следует заметить, что при определении/описании переменных квадратные скобки имеют приоритет больший, чем *, поэтому переменная st4  имеет тип `массив указателей’, а не `указатель на массив’.

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

 

void StackCreate4(int n, int *st[2] ) {st[1]= st[0] = (int*)malloc(n*sizeof(int));}

 

а ее вызов будет выглядеть так: StackCreate4(n,st4);

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

 

void StackAdd4(int v, int * st[2] ) { (*(st[1]++)) = v;}

 

а ее вызов будет выглядеть так: StackAdd4 (v, st4);

Проверка стека на пустоту выглядит следующим образом :

 

int StackIsEmpty4 ( int * st[2] ) { return st[1]<=st[0] ; }

 

Стек. Реализация 5 (на основе указателя на указатель).

 

У Реализации 4 есть существенный недостаток. Допустим, что стек создан внутри некоторой функции  и требуется использовать его вне данной функции. Тогда у нас есть единственная возможность осуществить данную реализацию, это - сделать переменную st4 глобальной или локальной статической. В противном случае, при выходе из данной функции переменная st4 утратит свое существование и указателями st4[0], st4[1] уже нельзя будет пользоваться. Но, как уже писалось, подобный способ реализации является дурным стилем.

Собственно, вся наша проблема состоит в том, что память под переменную st4 отводится и очищается автоматически. В качестве альтернативы, отведение/очистку памяти под указатели можно взять на себя. Для этого следует использовать указатель на указатель на целую переменную:

int **st5;

 

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

 

int ** StackCreate5(int n )

 {int **st; st = (int**)malloc(2*sizeof(int*));

  st[1]= st[0] = (int*)malloc(n*sizeof(int));

}

 

а ее вызов будет выглядеть так: st5=StackCreate5(n);

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

 

void StackDelete5(int  **st ) { free(st[0]); free(st);}

а ее вызов будет выглядеть так:  StackDelete5 (st5);

Если мы хотим уменьшить накладные расходы при отведении  памяти и ускорить создание/уничтожение стека, то имеет смысл изменить несколько скорректировать функции StackCreate5 и StackDelete5. Действительно, память можно отвести всего один раз. Размер отведенной памяти должен быть достаточен для хранения (последовательно) массива из двух указателей и для массива из n элементов стека. В таком случае функции отведения/освобождения памяти могут выглядеть следующим образом

int ** StackCreate5x(int n )

 {int **st; st = (int**)malloc(2*sizeof(int*)+ n*sizeof(int));

  st[1]= st[0] = (int*)(st+2);

}

void StackDelete5x(int  **st ) {free(st);}

 

 

 


Очередь.

 Очередью называется структура данных, организованная по принципу FIFOfirst-in, first-out , т.е. элемент, попавшим в множество первым, должен первым его и покинуть. При практическом использовании часто налагается ограничение на длину очереди, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя очередь предполагает наличие следующих функций

Ø  инициализация

Ø  добавление элемента в конец очереди

Ø  взятие/извлечение элемента с начала очереди

Ø  проверка: пуста ли очередь?

Ø  очистка очереди

 

Обычно, используется реализация циклической очереди. Т.е. под очередь отводится некоторый непрерывный кусок памяти (массив) и при подходе хвоста очереди к концу массива хвост автоматически перебрасывается на противоположный конец массива. Например, для реализации стандартной очереди из менее чем 100 целых чисел на базе массива в языке С следует определить следующие данные

#define  N  100

int array[N], begin=N-1,end=N-1;

 

Было бы логичным объединить все эти данные в единую структуру:

struct SQueue

{

 int Array[N];

 int  Begin, End;

};

 

Тогда функция инициализации очереди может выглядеть

void  Init(struct SQueue *queue){ queue->Begin=queue->End=N-1;}

Функция добавления элемента может выглядеть следующим образом

 

int  Add(struct SQueue *queue, int value)

{

 if(queue->End - queue->Begin == 1 ||

     queue->Begin - queue->End == N-1)return -1;

  queue->Array[queue->End-- ]=value;

  if(queue->End<0) queue->End=N-1;

return 0;

}

 

Отметим, что при данной реализации один элемент в очереди всегда будет не использован.

Функция извлечения элемента с уничтожением может выглядеть следующим образом

int  Get(struct SQueue *queue, int *value)

{

 if(queue->Begin== queue->End)return -1;

 *value= queue->Array[queue->Begin];

 if((--queue->Begin)<0) queue->Begin=N-1;

 return 0;

}

 

В функции сначала проводится проверка очереди на пустоту, далее из нее извлекается элемент. Если необходимо, индекс начала очереди перебрасывается на конец массива.

Дек.

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

Создание исполнителя дек предполагает наличие следующих функций

Ø  инициализация

Ø  добавление элемента в начало дека

Ø  добавление элемента в конец дека

Ø  взятие/извлечение элемента из начала дека

Ø  взятие/извлечение элемента с конца дека

Ø  проверка: пуст ли дек?

Ø  очистка дека

 

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

Списки

 

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

Более конкретно, создание исполнителя односвязный список (L1-список) предполагает наличие следующих функций

Ø  инициализация

Ø  установка текущего элемента в начало списка

Ø  перемещение текущего элемента к следующему элементу списка

Ø  взятие значения текущего элемента

Ø  уничтожение текущего элемента с автоматическим перемещением текущего элемента к следующему элементу списка

Ø  вставка нового элемента после текущего

Ø  проверка: пуст ли список?

Ø  проверка: текущий элемент в конце списка?

Ø  очистка списка

 

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

Ø  перемещение текущего элемента к предыдущему элементу списка

Ø  вставка нового элемента перед текущим

Ø  проверка: текущий элемент в начале списка?

 

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

Ø  инициализация

Ø  установка текущего элемента в первый элемент списка

Ø  перемещение текущего элемента к следующему элементу списка

Ø  перемещение текущего элемента к предыдущему элементу списка

Ø  взятие значения текущего элемента

Ø  уничтожение текущего элемента с автоматическим перемещением текущего элемента к следующему элементу списка

Ø  вставка нового элемента после текущего

Ø  вставка нового элемента перед текущим

Ø  проверка: пуст ли список?

Ø  проверка: текущий элемент первый в списке?

Ø  очистка списка

 

Стандартная ссылочная реализация списков

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

 

struct SList2

{

 int value;

struct SList2 *prev, *next;

};

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

Для сокращения имени типа в языке С можно использовать оператор typedef. Принцип работы данного оператора следующий. Если перед определением некоторой переменной с именем NAME написать оператор typedef, то NAME из имени переменной превратится в имя нового типа. Т.о. следующий оператор создает новый тип TList2, который можно использовать вместо типа struct SList2:

typedef struct SList2 TList2;

 

Для работы со списком следует определить два указателя: указатель на головной элемент списка и указатель на текущий элемент списка:

TList2 *head=NULL, *current=NULL;

Признаком пустоты списка служит нулевое значение указателя head. Установка текущего элемента на начало списка сводится к присвоению

current=head;

Вставка элемента со значением value после текущего может быть произведена следующим образом:

TList2 *InsertData(int value, TList2 **head, TList2 **current)

{

 TList2 *New=( TList2 *)malloc(sizeof(TList2));

 New->value = value;

 if(*head == NULL) //Случай пустого списка

 {*current =*head = New; (*head)->next= (*head)->prev=NULL; return New;}

 if(*current==NULL) //Случай вставки в начало списка

 {

  (*current)=New; (*current)->next=*head; (*current)->prev=NULL;

  (*head)->prev=New;

  (*head)=New;

  return New;

 }

 New->next = (*current)->next; New->prev=*current;

 if((*current)->next != NULL) (*current)->next->prev = New;

 (*current) ->next = New;

return New;

}

 

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

 

current = InsertData( value, &head, &current);

 

Здесь следует отметить, что в функции могут изменяться значения указателей на головной и текущий элементы списка. Особенностью языка С является то, что параметры передаются в функции исключительно по значению, т.е. в функцию передаются копии переменных. Альтернативой, в других языках программирования (например С++) служит передача параметров по ссылке. При передаче параметров по ссылке реально передается не значение переменной, а ее адрес. При этом внешний вид (синтаксис) как формальных, так и фактических параметров не отличается от случая передачи параметров по значению (фактическими параметрами называются параметры, передаваемые снаружи при вызове функции, а формальными – параметры, встречающиеся в определении функции).  Для указания того, что переменная передается по ссылке, в языке С++ используется символ & перед именем переменной в описании параметров функции. Поэтому в языке С++ вышеуказанная функция может выглядеть чуть проще

 

TList2 *InsertData(int value, TList2 *&head, TList2 *&current)

{

 TList2 *New=( TList2 *)malloc(sizeof(TList2));

 New->value = value;

 if(head == NULL) //Случай пустого списка

 {current =head = New; head->next= head->prev=NULL; return New;}

 if(current==NULL) //Случай вставки в начало списка

 {

  current=New; current->next=head; current->prev=NULL;

  head->prev=New;

  head=New;

  return New;

 }

 New->next = current->next; New->prev=current;

 if(current->next != NULL) current->next->prev = New;

 current ->next = New;

return New;

}

Вызывать эту функцию надо следующим образом

InsertData( value, head, current);

 

Для полноты описания следует отметить, что в языке С++ структуры можно передавать в функции по значению.

Возможно, в силу невозможности передачи параметров по ссылке, в зыке С нельзя передавать структуры в функции в качестве параметров. Вместо этого, естественно,  можно передавать указатели на структуры. Ситуация с массивами выглядит несколько двусмысленно. С одной сторону, массивы, в чистом виде, передаются по ссылке (т.е. при указании массива в качестве параметров функции передается не копия массива а адрес его нулевого элемента), но, с другой стороны, если вспомнить, что массивы, по всем своим свойствам являются постоянными указателями, то все сразу становится ясным: передавая массив в качестве параметра, мы передаем указатель на нулевой элемент массива и, при этом, сам указатель передается по значению.

Для правильного понимания понятия `структура’ следует иметь представление о выравнивании в структурах. Имеется в виду следующее. При определении структуры гарантируется, что первый член структуры будет располагаться по адресу самой структуры и все члены структуры располагаются в памяти в порядке их расположения в структуре. Однако, размер структуры может не  совпадать с суммой размеров членов структуры. Это объясняется тем, что, обычно, адреса всех элементов в структуре должны иметь определенную четность – т.е. они должны быть кратны одному из значений 1, 2, 4, 8 и т.д. Это значение определяет выравнивание элементов в структуре (Structure Alignment). Например, если создать структуру

struct SS{char a; int b;};

то, с большой вероятностью, по умолчанию, ее размер будет равен 8 (т.е. sizeof(struct SS) = = 8). Поведение по умолчанию, как правило, можно изменить с помощью соответствующих ключей компилятора. Но это можно сделать не на всех машинах и не на всех компиляторах.

Ссылочная реализация списков с фиктивным элементом

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

Для локализации всех данных, относящихся к одному списку, можно завести следующую структуру

typedef struct TList_

{

 TList2 temp;

 TList2 *current;

}TList;

В данном определении типа мы объединили определение типа struct TList_ и определение нового типа TList с помощью оператора typedef. При этом в большинстве реализаций языка С (но не во всех!!!) идентификатор TList_можно вообще не писать.

В качестве инициализации списка можно использовать следующую функцию

void ListInit(TList *list)
{list->temp.next=list->temp.prev=&list->temp; list->current=&list->temp;} 

 

Вставка элемента со значением value после текущего может быть произведена следующим образом:

TList2 *InsertData(int value, TList *list)

{

 TList2 *New=( TList2 *)malloc(sizeof(TList2));

 New->value = value;

 New->next = list->current->next;  New->prev=list->current;

 list->current->next->prev = New;  list->current ->next = New;

 return New;

}

 

Реализация L2-списка на основе двух стеков

Интересной реализацией L2-списка является его реализация на основе двух стеков, расположенных `вершиной друг к другу’. Первый из стеков представляет начало списка (часть от начала списка до текущего элемента включительно), а второй – конец (часть после текущего элемента). Текущий элемент списка лежит на вершине первого стека. При необходимости переместиться к следующему элементу, значение вершины второго стека извлекается и помещается на вершину первого стека. При необходимости переместиться к предыдущему элементу, значение вершины первого стека извлекается и помещается на вершину второго стека.

Данная реализация активно применялась, например, при создании текстовых редакторов. Текстовый редактор представляет собой двунаправленный список строк. Работа с каждой строкой может быть представлена как работа с простым вектором символов. Операции вставки, редактирования, удаления символов в строке могут быть реализованы за время = O(N), где N – количество символов в строке.

Список строк реализуется в виде двух стеков, каждый из которых может быть реализован в виде временного файла. Текущая строка (и, возможно несколько соседних строк) хранятся в оперативной памяти, начало файла – в виде одного временного файла, конец (в обратном порядке) – в виде второго временного файла.

 

Реализация L2-списка с обеспечением выделения/освобождения памяти

 

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

Теперь для добавления элемента в список требуется взять его из списка свободного места и добавить в основной список. Для извлечения элемента из списка элемент извлекается из основного списка и добавляется в список свободного места.

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

Итак, для хранения всех данных, относящихся к подобному списку можно использовать следующую структуру

typedef struct

{

 TList2 *array;

 TList data, empty;

 int NMax;

} SListMem;

 

Функция инициализации может выглядеть следующим образом

void SListMemInit( SListMem *list)

{int i;

 list->NMax=1000;

 list->array=(TList2*)malloc(list->NMax*sizeof(TList2));

 ListInit(&(list->data));

 list->empty.current=list->empty.temp.next=list->array+0;

 list->empty.temp.prev=list->array+ list->NMax-1;

 list->array[0].prev=&(list->empty.temp); 

 for(i=1;i<list->NMax;i++)

 {

  list->array[i-1].next=list->array+i; 

  list->array[i].prev=list->array+i-1;

 }

 list->array[list->NMax-1].next=&(list->empty.temp); 

}


Лекция 7

 

Структуры данных. Графы.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

 

 

Графы

Определение. Графом называется пара G=(V,E), где V - множество объектов произвольной природы, называемых вершинами (vertices, nodes), а E - семейство пар ei=(vi1, vi2), vijÎV, называемых ребрами (edges). В общем случае множество V и/или семейство E могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т.е. графы, у которых как V, так и E конечны. Отметим, что, вообще говоря, для каждой пары вершин ребра в семействе E могут быть неуникальными, что не дает возможности назвать E множеством.

Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). Ребра орграфа называются дугами (arcs).

Некоторая вершина и некоторое ребро графа называются инцидентными, если вершина является одной из вершин ребра. Соответственно, пара вершин инцидентна ребру, если эти вершины являются вершинами одного ребра, а сами вершины называются смежными. Два ребра графа называются смежными, если они инцидентны одной вершине.

 

Поиск пути в графе с наименьшим количеством промежуточных вершин

Пусть дан некоторый конечный граф G=(V,E) и две его вершины a,bÎV. Требуется найти путь между вершины графа a и b с минимальным количеством промежуточных вершин, т.е. требуется найти последовательность {a1,…,an}, где aiÎV, (ai, ai+1)ÎE  с минимально возможным n.

Стандартным решением данной задачи является алгоритм волны. Базовым понятием в нем является волна степени n – множество вершин графа, до которых можно добраться из вершины a за n шагов и нельзя добраться за меньшее количество шагов. Будем называть это множество вершин Sn . Для точки a волной степени 0 является множество, состоящее из одной точки a.

Основная идея алгоритма заключается в том, что волной степени n+1, при известной волне степени n, будет являться множество точек Sn+1, состоящее изо всех точек, смежных к точкам из волны степени n, которые при этом не состоят в волнах степени меньше или равной n. Т.о. утверждается, что Sn+1= Sn+1.

Доказательство этого факта тривиально. Докажем, что Sn+1Ì Sn+1. Действительно, до точек  из Sn+1 можно добраться за n+1 шаг по построению. За меньшее количество шагов добраться нельзя, т.к. для любого i£n  выбранные точки не принадлежат Si .

Докажем, что Sn+1Ì Sn+1. Допустим, что найдется точка x, которую мы не включили в созданное множество Sn+1, но xÎSn+1. По условию xÎSn+1 имеем, что существует путь к данной точке за n+1 шагов, а значит, у данной точки есть смежная вершина из Sn. По определению Sn+1 , до точки x нельзя добраться за n или менее шагов, поэтому x должна быть включена в создаваемое множество, согласно его построению.

¢

 

Осталось завести два исполнителя множество S0 и S1 (например, на базе вектора, количество элементов в котором не превосходит количество вершин графа) и добавить в каждую вершину графа x дополнительную целую переменную lx, которая будет указывать длину кратчайшего пути от вершины a до данной вершины. В начальный момент S0 и S1 должны быть пусты, а все значения l=-1. Первая часть алгоритма состоит в определении для каждой вершины x, до которой можно добраться из a медленнее, чем до b, значения lx:

Алгоритм волны. Часть 1.

 


n=0; S1= {(a,0)}

Вечный цикл

n++

S0= S1

S1=Æ

          Для всех xÎ S0

                      Для всех точек, смежных x: y, таких что ly==-1

                                  ly=n; занести y в S1;

                                  Если b==x  то ВЫЙТИ ИЗ ВЕЧНОГО ЦИКЛА

Если S1  пусто то ВЫЙТИ ИЗ ВЕЧНОГО ЦИКЛА

 


Если после выхода из алгоритма  S1  пусто, то это говорит о том, что из a в b добраться нельзя.

Иначе, во второй части алгоритма следует по результатам построений из первой части алгоритма определить кратчайший (один из кратчайших) путь из b в a. Для этого следует заполнить искомую последовательность {x1,…,xn}.

xn=b;  x1=a

Далее для каждого i от n до 3 ищется вершина xi-1, смежная к xi, такая что lx(i-1)==i-1. Такая вершина существует из соображений, приведенных выше.

¢

Если в постановке задачи рассматривается ориентированный граф, то ничего принципиального в алгоритме не изменяется.

В каждой вершине можно хранить дополнительную информацию о том, откуда мы в нее пришли, тогда вторая часть алгоритма будет выполняться за время O(n), где n – длина минимального пути из a в b (в случае возможности дойти из a в b), или за время O(N) , где N – количество вершин в графе (в любом случае).

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

Теорема 1. Верны оценки для графа, состоящего из N вершин

1. Если в графе отсутствуют петли и кратные ребра, то алгоритм волны работает за время O(N2).

2. Если каждая вершина графа имеет не более M1  инцидентных ребер, то алгоритм волны работает за время O(M1 N).

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

Доказательство теоремы сводится к тому, что время работы алгоритма волны равно O(M+N) , где N – количество вершин, M – количество ребер в графе (точнее, не ребер, а пар смежных вершин, но в условиях теоремы это – одно и тоже). Последний факт следует из того, что каждое ребро при взятии смежной вершины в алгоритме может встретиться не более двух раз.

Чтобы получить более оптимистичную оценку введем несколько новых понятий.

Пусть дан некоторый граф G=(V,E), пусть каждой его вершине сопоставлена точка в некотором евклидовом пространстве, причем точки, соответствующие различным вершинам не совпадают. Пусть каждому ребру графа сопоставлена некоторая непрерывная кривая, соединяющая соответствующие вершины графа, причем кривые, соединяющие различные пары точек не пересекаются нигде, кроме вершин графа. Такое представление графа называется его геометрическим представлением.

Теорема 2.  Для любого конечного графа существует его геометрическое представление в R3.

Доказательство. Рассмотрим произвольный отрезок [a,b]Ì R3. Сопоставим всем вершинам графа различные точки на отрезке [a,b]. Сопоставим каждому ребру графа свою плоскость, проходящую через [a,b]. Плоскости, соответствующие ребрам, пересекаются только вдоль отрезка [a,b], поэтому в каждой плоскости можно нарисовать кривую, соединяющую вершины, инцидентные соответствующему ребру, которая не пересекается с другими построенными кривыми нигде, кроме как в вершинах графа.

¢

Граф называется планарным, если существует его геометрическое представление в R2. Плоской укладкой планарного графа называется такое его геометрическое представление, при котором каждое ребро представляется отрезком на плоскости.

Верна следующая известная теорема, которой мы не будем пользоваться и которую мы представим без доказательства

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

Иногда в литературе последнее утверждение выступает в виде определения планарного графа, а не его свойства.

Геометрическое представление планарного графа разбивает плоскость на некоторое количество связных областей (одна из них - бесконечна). Эти области называются гранями.

Путем в графе называется такая последовательность {x1,…,xn} вершин графа, что для всех i: (xi,xi+1)ÎE.

Циклом в графе называется такой путь, что крайние вершины в нем совпадают. Т.е. последовательность {x1,…,xn} вершин графа называется циклом, если для всех i: (xi,xi+1)ÎE  и x1=xn.

Граф называется связным, если для любых двух вершин графа a и b существует путь по ребрам графа от a до b, т.е. существует последовательность {x1,…,xn} вершин графа, такая что x1=a, xn=b и для всех i: пара (xi, xi+1) инцидентна некоторому ребру графа.

Связный граф без циклов называется деревом. Вершины, инцидентные не более чем одному ребру дерева называются конечными вершинами. Иногда в литературе такие вершины называют листьями, но нам такое определение листьев неудобно. Отметим, что понятия ориентации ребер в этом определении нет!

Ориентированным деревом называется ориентированный граф, являющийся деревом, для которого ровно одна вершина имеет нулевую степень захода (степень захода = количество ребер заходящих в вершину), а все остальные вершины имеют степень захода, равную 1. Для случая ориентированного графа конечной вершиной называется вершина, имеющая нулевую степень исхода (степень исхода  = количество ребер выходящих из вершины). Это определение отличается от определения для неориентированного дерева!

Лемма 1. Любое конечное дерево имеет плоскую укладку.

Доказательство. Возьмем произвольную вершину дерева. Поместим ее в точку плоскости с координатами (0,0) и назовем корнем дерева. Пусть ей инцидентно k ребер. Поместим вторые вершины, инцидентные данным ребрам в точки (-1,i). Каждой из вновь размещенных точек сопоставим полосу плоскости со сторонами, параллельными оси Y, не имеющую общих точек с полосами соседних точек. 

Пусть для каждой вершины x, помещенной на плоскость в точку с координатой y=-h найдутся lx парных ей вершин, которые еще не размещены на плоскости.  Будем называть эти вершины потомками вершины x, а вершину x – их родителем. Разобьем полосу, соответствующую вершине x на  lx непересекающихся полос и разместим в них потомков x на координате y=-h-1.

Для потомков x рекурсивно выполним процедуру, описанную в предыдущем абзаце.

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

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

¢

 

Доказательство Леммы 1 одновременно служит конструктивным доказательством того, что верна следующая

Лемма 2. В любом конечном дереве можно ввести ориентацию, т.е. для ребер произвольного дерева можно задать ориентацию так, что дерево станет ориентированным.

Верна следующая известная теорема

Теорема 4 (формула Эйлера). Пусть задан связный планарный граф, имеющий в некотором геометрическом представлении p вершин, q ребер, r граней, тогда верна формула

p-q+r=2

 

            Лемма 3. Пусть в некотором графе p вершин и q ребер, то  в графе содержится не менее p-q связных компонент. Если в графе нет циклов, то в графе ровно p-q связных компонент. Если в графе есть циклы, то в графе строго больше p-q связных компонент.

Доказательство леммы. Любой конечный граф G=(V,E) без циклов может быть получен из графа G0=(V,Æ) путем последовательного добавления ребер, при этом каждый промежуточный граф не будет содержать циклов. Для графа G0 данная лемма выполняется (количество связных компонент равно количеству вершин).

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

Теперь, если разрешить наличие связных компонент, то в предыдущем доказательстве станет возможным соединение вершин из одной связной компоненты, но тогда количество связных компонент будет строго больше p-q. Лемма доказана.

Следствием Леммы 3 является простой критерий наличия циклов в графе:

 p-q=количеству связных компонент в графе Û в графе нет циклов.

Доказательство формулы Эйлера. Исходя из леммы, получаем, что теорема Эйлера верна для деревьев. Действительно, по Лемме 1, каждое дерево с конечным числом вершин имеет плоскую укладку. Количество граней в этой укладке равно1 (иначе существует хотя бы одна конечная грань, а значит существует последовательность ребер на ее границе, образующая цикл). Количество граней в геометрическом представлении дерева равно 1 и  в силу Леммы 3 

p-q+r=1+1=2.

Рассмотрим произвольный связный граф с циклами с q0 ребрами. По Лемме 3  p-q0>1. Зафиксируем p и предположим, что для всех q<q0 теорема доказана. Заметим, что для случая p-q=1 мы уже доказали теорему. По предположению, в графе есть цикл, возьмем одно ребро в этом цикле и исключим из графа. Ребро было в цикле графа, поэтому связность нарушена не была. Т.к. ребро содержалось в цикле, то оно было общим для двух граней, поэтому при исключении ребра количество граней и количество ребер уменьшились на 1. По предположению индукции для урезанного графа теорема выполняется, следовательно, она выполняется и для исходного графа.

¢

Рассмотрим планарный граф без кратных ребер и петель. В его геометрическом представлении для каждой грани i количество ребер на ее границе qi³3. Т.о. имеем

S qi ³ 3r

С другой стороны каждое ребро принадлежит не более, чем двум граням, поэтому

2q ³ S qi

Итого имеем

2q ³3r

r £ 2/3 q.

Тогда по формуле Эйлера

q=p+r-2£ p+2/3 q -2.

q/3£p-2

q£3p

В силу последнего соотношения верна следующая

Терема 5. Для случая планарного графа без кратных ребер и петель, состоящего из N вершин, алгоритм волны работает за время O(N).

 

Отметим, что параллельно мы доказали, что в планарном графе количество ребер и граней оценивается через количество вершин, т.е. верна

Терема 6. Для случая планарного графа, имеющего в плоском представлении p вершин, q ребер, r граней верны оценки

q£3p

r£2p

 

 

Представление графа в памяти ЭВМ

Пусть имеется граф G=(V,E), имеющий N вершин и M ребер. Вершинам и ребрам можно сопоставить их номера от 1 до N и от 1 до M, соответственно. Рассмотрим различные варианты хранения данных об этом графе. Отметим, что для работы с графом требуются следующие операции

  • перечисление всех ребер, инцидентных вершине i
  • перечисление вершин, инцидентных ребру j
  • перечисление всех вершин, смежных с  вершиной i
  • проверка смежности двух вершин
  • проверка смежности двух ребер

 

Массив ребер

Для хранения информации о графе можно использовать массив ребер, в каждом элементе которого хранятся номера вершин, инцидентных ребру

#typedef  MMax 100

int edges[MMax][2], n_edges;

здесь предполагается, что в графе содержится не более MMax ребер;

Имеем следующие времена выполнения интересующих нас операций

  • перечисление всех ребер, инцидентных вершине i          T=O(M)
  • перечисление вершин, инцидентных ребру j                    T=O(1)
  • перечисление всех вершин, смежных с  вершиной i        T=O(M)
  • проверка смежности двух вершин                                                 T=O(M)
  • проверка смежности двух ребер                                         T=O(1)

 

Матрица смежности

Для хранения информации о графе можно использовать матрицу смежности из N строк и N столбцов, в (i,j) – элементе которой хранится количество ребер, инцидентных паре вершин с номерами i  и  j.

Имеем следующие времена выполнения интересующих нас операций

  • перечисление всех ребер, инцидентных вершине i          -------
  • перечисление вершин, инцидентных ребру j                    -------
  • перечисление всех вершин, смежных с  вершиной i        T=O(N)
  • проверка смежности двух вершин                                                 T=O(1)
  • проверка смежности двух ребер                                         -------

 

Матрица инцидентности

Для хранения информации о графе можно использовать матрицу инцидентности из N строк и М столбцов, в (i,j) – элементе которой хранится 1, если вершина i инцидентна ребру j, и 0 – если нет.

Имеем следующие времена выполнения интересующих нас операций

  • перечисление всех ребер, инцидентных вершине i          T=O(M)
  • перечисление вершин, инцидентных ребру j                    T=O(N)
  • перечисление всех вершин, смежных с  вершиной i        T=O(N M)
  • проверка смежности двух вершин                                                 T=O(N M)
  • проверка смежности двух ребер                                         T=O(N+M)

 

Списки смежных вершин

Для хранения информации о графе можно для каждой вершины хранить множество смежных вершин. Множество можно реализовать либо в виде массива:

#typedef  NMax 100

typedef struct CVertex1_

{

  int AdjacentVertices[NMax];

  int NAdjacentVertices;

} CVertex1;

CVertex1 vertices[NMax];

здесь предполагается, что в графе содержится не более NMax вершин;

либо в виде списка:

#typedef  NMax 100

typedef struct CAdjVertex_

{

  int i;               //номер текущей вершины

  int i_next;      //номер следующей вершины

} CAdjVertex;

typedef struct CVertex2_

{

CAdjVertex *AdjacentVerticesList_Head; //голова списка  смежных вершин                             int i;                  //номер текущей вершины

} CVertex2;

CVertex2 vertices[NMax];

 

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

Имеем следующие времена выполнения интересующих нас операций

  • перечисление всех ребер, инцидентных вершине i          -------
  • перечисление вершин, инцидентных ребру j                    -------
  • перечисление всех вершин, смежных с  вершиной i        T=O(N)
  • проверка смежности двух вершин                                                 T=O(N)
  • проверка смежности двух ребер                                         -------

Реберный список с двойными связями (РСДС) (для плоской укладки планарных графов)

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

typedef struct SEdge_

{

 int vertex0, vertex1;

 int edge0,edge1;

 int face0,face1;

}SEdge;

            здесь vertex0, vertex1 – номера первой и второй вершины ребра. Порядок вершин задает ориентацию. edge0 – номер первого ребра (в массиве элементов Sedge), выходящего из вершины vertex0, взятого против часовой стрелки (при обходе ребер из вершины vertex0), edge1 – первое ребро, выходящее из вершины vertex1, взятое против часовой стрелки (при обходе ребер из вершины vertex1). face0 – номер грани, находящейся слева от направленного отрезка (vertex0, vertex1), face1 – номер грани, находящейся справа от направленного отрезка (vertex0, vertex1).

Вместо структуры можно использовать массив из шести целых чисел.

На следующем рисунке показан пример графа. Стрелками на ребрах указан порядок вершин в узлах РСДС, соответствующих ребрам. Стрелками между ребрами указаны ссылки на ребра из соответствующих узлов РСДС.

 

Для данного графа РСДС будет представлен следующим массивом улов:

{

{1,2, 5,2, 1,4},

{2,4, 1,7, 1,4},

{1,3, 1,4, 4,2},

{3,4, 6,5, 3,2},

{1,4, 3,2, 2,1},

{5,3, 7,3, 3,4},

{4,5, 4,6, 3,4}

}

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


Лекция 8

 

Структуры данных. Графы.

 

Д.Кнут. Искусство программирования  для ЭВМ. тт 1-3. Москва. Мир. 1996-1998

Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999.

 

 

Поиск кратчайшего пути в графе

Пусть дан некоторый конечный граф G=(V,E), состоящий из N  вершин, и две его вершины a, bÎV. Пусть для каждого ребра графа e задано положительное вещественное число l(e), которое будем называть длиной ребра. Требуется найти путь между вершинами графа a и b  минимальной длины, т.е. требуется найти последовательность {x1,…,xn}, где xiÎV, x1=a, xn=b, (xi, xi+1)ÎE  с минимально возможной S l(xi,xi+1).

Стандартным решением данной задачи является алгоритм Дейкстры.

Основная идея алгоритма заключается в следующем.

Пусть множество Qn представляет собой множество n ближайших вершин к вершине a вместе с длинами пути от a до этих вершин. Т.е. в каждом элементе множества  qiÎQn содержится номер соответствующей вершины xi и длина пути от a до этой вершины li: qi=(xi,li). Можно предполагать, что последовательность {li} является неубывающей.

Утверждается, что ближайшая вершина графа к a из вершин, не внесенных в Qn , задается следующим соотношением:

argmin(v,wÎV, wÎ Qn , vÏ Qn , (w, v) ÎE:  lw+|(w,v)| )                (*)

здесь и далее под wÎ Qn , vÏ Qn имеется в виду, что w встречается среди вершин, внесенных в Qn, а v – нет; длина ребра (w, v) обозначается |(w,v)|. Т.о. элемент qn+1 складывается из вершины v, на которой достигается указанный минимум и соответствующей длины ln+1 = lw+|(w,v)|.

Доказательство. Допустим, найдена вершина sÏ Qn с минимальной длиной до a. Пусть кратчайший путь от a до s проходит по последовательности вершин графа {a,x2,…,xn,s}. Длина пути {a,x2,…,xn} меньше длины пути до s, поэтому xnÎ Qn, но тогда длина пути {a,x2,…,xn,s} должна совпадать с длиной кратчайшего пути от a до найденного выше w.

¢

 

При поиске значения (*), формально, требуется перебрать все вершины wÎ Qn и для каждой из них требуется перебрать все смежные вершины. Будем далее предполагать, что в графе отсутствуют кратные ребра и петли, тогда  процедура (*) требует выполнения O(N2) операций, из чего следует, что суммарное время работы алгоритма есть O(N3).

На самом деле, для выполнения процедуры (*) можно обойтись O(N) операциями. Для этого заметим, что за один поиск значения  (*) к множеству Qn добавляется всего одна точка и, поэтому, на следующем шаге значения lx изменятся только у вершин, смежных этой новой точке. Т.о. для пересчета в (*) всех значений lx требуется пересчитать lx только для точек, смежных одной точке, полученной при предыдущем выполнении (*). В силу введенных предположений, это можно сделать за O(N) операций. Искать же минимум lx можно по всем вершинам графа, не принадлежащим Qn, что тоже требует O(N) операций. Т.о. процедуру (*) можно реализовать за O(N) операций.

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

Для упрощения дальнейшей жизни (т.е. для поиска, собственно, кратчайшего пути при определенных значения lw) можно в каждом элементе также хранить ссылку на вершину, из которой мы в данную вершину пришли. Для текущей вершины w будем эту ссылку называть backw. Т.о. элементы Qi представляются в виде q=(w, lw, sw, backw).

Будем предполагать, что конкретная техника нам позволяет инициализировать все  lw  значением = плюс бесконечность (+INF), что мы и сделаем. Инициализируем все sw  значением = FALSE.

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

Алгоритм Дейкстры

 


n=0; c=a; sc=TRUE; lc=0; backc=NULL         //Q0={(a,0, true,NULL)}

Вечный цикл

   Для всех вершин v, смежных с

Если sc==FALSE и (lv==+INF или  lc+|(c,v)|< lv) то

 lv = lc+|(c,v)|; backv=c

l=+INF

Для всех вершин графа v

Если sc==FALSE и lv< l то l = lv; z=v

 

            Если l==+INF то ВЫЙТИ// в графе не осталось элементов

            Если z==b то ВЫЙТИ        // дошли до конца пути

   sz=TRUE; c= z                        // Qn+1= Qn È {(z,l,true)}

Конец вечного цикла

 


Если после завершения первой части алгоритма l==+INF , то это означает, что от a до b дойти по ребрам невозможно. Иначе, мы можем по ссылкам backw добраться от b до a.

Проанализировав алгоритм для случая планарных графов без кратных ребер и петель, мы сможем заметить, что его можно улучшить. Действительно, при коррекции lv для каждой вершины перебираются все смежные ребра и это происходит ровно один раз. Поэтому суммарное количество операций по коррекции lv не превосходит O(q), где – q количество ребер, а для рассматриваемого случая O(q)= O(p), где – q количество вершин графа.

Допустим, что мы сможем создать структуру данных, содержащую вещественные числа, в которую можно добавлять элементы, удалять из нее минимальный элемент, искать минимум элементов, модифицировать положение элемента при изменении его значения, причем каждая из этих операций должна выполняться за время O(log N), где – N количество элементов, занесенных в данную структуру. Назовем множество, реализованное с помощью указанной структуры данных, P.

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

 

Алгоритм Дейкстры модифицированный

 


n=0; c=a; sc=TRUE; lc=0; backc=NULL         //Q0={(a,0, true,NULL)}

P={Æ }

Вечный цикл

Для всех вершин v, смежных с

Если sc==FALSE и lv==+INF то

 Добавить ссылку на  v в P

            Если P пусто то lz =+INF; ВЫЙТИ// в графе не осталось элементов

   Для всех вершин v, смежных с

Если sc==FALSE и (lv==+INF или  lc+|(c,v)|< lv) то

 lv = lc+|(c,v)|; backv=c;

Скорректировать положение ссылки на  v в P

            Извлечь из P ссылку на  минимальный элемент и

            поместить минимальный элемент в z

l = lz

            Если z==b то ВЫЙТИ        // дошли до конца пути

   sz=TRUE; c= z                        // Qn+1= Qn È {(z,l,true)}

Конец вечного цикла

 


Осталось заметить, что для корректировки положения ссылки на v в P нам еще необходимо уметь находить эту ссылку на v в P, поэтому в каждом элементе исходного множества v еще придется хранить ссылку на ссылку на v в P. Т.о. при всех перемещениях элементов в P ссылки на эти элементы в исходном множестве придется модифицировать.

Итак для случая планарных графов без кратных ребер и петель, в каждом переборе смежных вершин на протяжении всего алгоритма каждое ребро встречается только два раза, поэтому суммарное время работы первого цикла Для всех… равно O(p log p), суммарное время работы второго цикла Для всех… имеет такую же ассимптотику. Наконец, извлечение из P ссылки на  минимальный элемент выполняется за время O(log p), а т.к. таких элементов O(p), то суммарное время этих извлечений = O(p log p). Таким образом, доказана следующая

Теорема 1.  Для случая планарных графов без кратных ребер и петель алгоритм Дейкстры работает за время O(p2), а модифицированный алгоритм Дейкстры работает за время O(p log p), где p – количество вершин в графе.

 

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

·      добавлять элемент,

·      удалять минимальный элемент,

·      искать минимум элементов,

·      модифицировать положение элемента при изменении его значения,

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

В качестве подобной структуры данных может выступать пирамида, определенная для сортировки Heapsort. При ее определении мы требовали, чтобы в ее вершине лежал максимальный элемент (исходя из того, что A[i/2] ³ Ai ). Мы можем не менять определения пирамиды, потребовав, чтобы в нее заносились исходные элементы, умноженные на –1, в таком случае в вершине будет храниться минимальный элемент исходного множества (умноженный на –1).

Удалять максимальный элемент из пирамиды за время O(log N) мы научились в алгоритме Heapsort. Находить максимальный элемент за время O(1) можно элементарно – он лежит в первом элементе массива пирамиды. Осталось научиться вставлять новый элемент в пирамиду и корректировать его положение при изменении значения.

 

Добавление элемента

Пусть дан пирамидально-упорядоченный массив Ai, (i=1,…,N). Требуется добавить к нему еще один элемент Ai+1 и переупорядочить массив. Для этого введем текущий номер элемента в массиве k. В начальный момент положим k= N+1.

Свойство пирамидально-упорядоченности выполняется для всех соответствующих пар элементов, кроме, быть может, пары (k,k/2). Если для этой пары свойство A[k/2] ³ Ak  выполняется, то массив пирамидально упорядочен и ничего больше делать не надо. Иначе поменяем местами пару элементов с индексами k и k/2. При этом элемент с индексом k/2 не уменьшится, поэтому поддерево, с него начинающееся, но идущее по другой ветке, чем (k,k/2) останется пирамидально-упорядоченным (т.е., например для четного k, останется верным A[k/2] ³ Ak+1).

Перед обменом местами элементов с индексами (k,k/2), элемент A[k/2] был не меньше всех элементов в поддереве, начинающегося с A[k/2], кроме, быть может, Ak. Поэтому, после обмена местами элементов с индексами (k,k/2), элемент Ak будет не меньше всех элементов в поддереве, начинающегося с Ak. Осталось присвоить k=[k/2], и выполнить те же самые действия для нового k.

Таким образом, мы произведем не более [log N]+1 обменов местами соседних элементов, из чего следует, что процедура добавления элемента в пирамиду может быть произведена за время O(log N).

 

Корректировка положения элемента

Пусть дан пирамидально-упорядоченный массив Ai, (i=1,…,N). Для текущего элемента в массиве с номером k изменим значение элемента Ak. Требуется переупорядочить массив.

Если Ak³ A2k и Ak³ A2k+1, то задача полностью сводится к предыдущей.

Пусть, для определенности, Ak< A2k. Но тогда A[k/2] ³ Ak (т.к. A[k/2] ³ A2k> Ak), из чего получаем, что все элементы из поддерева, начинающегося с k-го элемента массива не превосходят A[k/2] . В этом случае возможно применить процедуру Heapify(A,k,N). Время ее работы O(log N).

¢

 

 



Лекция 9

 

Бинарные деревья поиска

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

typedef struct STree_

{

 int value;

struct STree_ *prev;

struct STree_ *left, *right;

} STree;

здесь указатель prev указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Величина value называется ключом вершины.

Бинарное дерево называется деревом поиска, если для любой вершины дерева a ключи всех вершин в правом поддереве больше или равны ключа a, а в левом – меньше. Неравенства можно заменить на строгие, если известно, что в дереве нет равных элементов.

Далее мы постараемся придерживать синтаксиса языка С, т.е., как правило, мы будем использовать в качестве вершины дерева a переменную типа

STree *a;

Отсутствие потомка обозначается нулевым значением соответствующего указателя.

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

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

Длиной ветви дерева называется количество элементов в ветви.

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

Основные операции, которые можно совершать с бинарными деревьями:

·                  поиск элемента в дереве (т.е. элемента с ключом, равным заданному)

·                  добавление элемента в дерево

·                  удаление элемента из дерева

·                  поиск минимального и максимального элемента в дереве

·                  если рассмотреть дерево поиска, как упорядоченную по возрастанию последовательность элементов, то: для текущего элемента поиск следующего/предыдущего

·                  для данной вершины дерева v разбиение дерева поиска T на два дерева поиска T1 и T2 таких, что все элементы в T1  меньше или равны v, и все элементы в T2  больше или равны v

·                  для двух деревьев поиска T1 и T2 таких, что все элементы в T1  меньше или равны всех элементов в T2  (будем далее для таких деревьев говорить, что дерево T1 меньше или равно дерева  T2:  T1 £ T2): слияние деревьев в одно дерево поиска T

 

Покажем, что все эти операции можно совершить за время O(h), где h – высота рассматриваемого дерева.

Поиск элемента в дереве

Требуется найти элемент, равный v, в дереве. Введем понятие текущей вершины дерева c. Сначала в качестве c выберем корень дерева. Рекурсивно вызывается следующая процедура:

 


Если c==NULL то ИСКОМЫЙ ЭЛЕМЕНТ В ДЕРЕВЕ НЕ СОДЕРЖИТСЯ

Если v==c то return c

Если v³c то выполнить эту же процедуру для c->right

  иначе выполнить эту же процедуру для c->left

 


На языке С это будет выглядеть следующим образом

STree *Find(STree *root, int v)

{

  if(root==NULL)return NULL;

  if(root->value==v)return root;

  if(root->value>=v)return Find(root->right,v);

  else return Find(root->left,v);

}

или более коротко:

STree *Find(STree *root, int v)

{

 return root==NULL?NULL: root->value==v? root: v>=root->value?

   Find(root->right,v): Find(root->left,v);

 }

 

Добавление элемента в дерево

Требуется добавить в дерево вершину v.

Для этого ищем лист, после которого следует вставить v и вставляем v после него.

Алгоритмом, аналогичным поиску элемента, найдем лист c, после которого следует вставить элемент v и вставим его. На языке С вставка вершины в дерево может быть выполнена следующим образом:

STree *Insert(STree *root, STree *v)

{

 if(v->value>=root->value)

    return root->right==NULL ?

   (v->back=root,v->right=v->left=NULL,root->right=v) : Insert(root->right, v);

 else

    return root->left==NULL ?

    (v->back=root,v->right=v->left=NULL,root->left=v) : Insert(root->left, v);

}

 

Отметим, что здесь активно используется разделитель выражений – запятая. Напомним, что, если несколько арифметических выражений в языке С разделены запятой, то значение всего выражения равно последнему из них.

Поиск минимального и максимального элемента в дереве

STree *SearchMin(STree *root)

{ return root->left==NULL?root: SearchMin(root->left);}

 

STree *SearchMax(STree *root)

{ return root->right==NULL?root: SearchMin(root-> right);}

Удаление элемента из дерева

Удаление вершины v из дерева поиска не представляет проблем, если данная вершина является листом или имеет всего одного потомка. Иначе, например, из правого поддерева v можно изъять минимальный элемент (самый левый) и поместить его на место удаленного. При этом, дерево останется деревом поиска.

Поиск следующего/предыдущего элемента в дереве

Если у текущего элемента v есть правый потомок, то следующим элементом будет минимальный элемент в поддереве, которое имеет корень v->right. Иначе мы должны подниматься вверх по дереву, пока не встретиться вершина