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

по курсу

 

 

 

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

 

 

 

 

 

 

 

 

 

 

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

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

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

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

2018г.


 

 

Лекция 1. 6

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

Целые. 6

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

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

Лекция 2. 17

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

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

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

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

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

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

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

Лекция 3. 26

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

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

QuickSort. 26

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

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

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

Лекция 4. 38

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

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

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

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

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

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

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

Лекция 5. 44

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

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

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

Поиск порядковой статистики массива целых чисел за время Q(N) для случая |ai|<O(N) 46

Поиск порядковой статистики в большой окрестности каждой точки серого изображения  46

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

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

Переменные. 50

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

Вектор. 52

Стек. 53

Лекция 6. 56

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

Стек. 56

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

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

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

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

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

Стек. Реализация 6 (на основе указателя на указатель с одинарным выделением памяти). 59

Очередь. 60

Дек. 61

Списки. 62

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

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

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

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

Лекция 7. 69

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

Графы.. 69

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

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

Лекция 8. 79

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

Поиск кратчайшего пути в графе. Алгоритм Дейкстры (Dijkstra's algorithm). 79

Алгоритм Дейкстры на основе STL. 84

Лекция 9. 88

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 10. 103

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

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

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

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

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

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

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

Лекция 11. 114

B-деревья. 114

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

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

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

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

Добавление вершины в B-дерево за один проход. 120

Удаление вершины из B-дерева за один проход. 120

B+-деревья. 124

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

Добавление вершины в B+-дерево в два прохода. 125

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

Лекция 12. 125

STL.. 125

Реализации структур данных. Контейнеры.. 126

Последовательные контейнеры.. 127

Ассоциативные контейнеры.. 128

Итераторы.. 129

Максимально упрощенный подход. 129

Итераторы ввода. 130

Итераторы вывода. 131

Последовательные итераторы.. 131

Двунаправленные итераторы.. 131

Итераторы произвольного доступа. 131

Итераторы вставки. 132

Функциональные объекты.. 133

Алгоритмы.. 133

Потоки. 135

Лекция 13. 137

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

Закрытая адресация. Метод многих списков (он же – метод цепочек) 137

Открытая адресация. Метод линейных проб. 139

Метод цепочек для открытой адресации. 143

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

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

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

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

Лекция 14. 152

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

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

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

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

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

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

Лекция 15. 157

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

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

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

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

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

Лекция 16. 167

Операционные системы.. 167

Эволюция операционных систем.. 169

Последовательная обработка данных. 169

Простые пакетные системы.. 169

Многозадачные пакетные системы.. 170

Системы, работающие в режиме разделения времени. 170

Системы реального времени. Многопоточность. Потоки и процессы.. 171

Режимы адресации оперативной памяти в Intel-совместимых компьютерах. 172

Процесс выполнения нити. 174

Лекция 17. 175

Вызов функций. Механизмы передачи параметров в функции. Функции с переменным количеством параметров. 175

Алгоритмы динамического выделения памяти. 177

Использование стека задачи. 177

Списки блоков фиксированного размера. 178

Алгоритм близнецов (для блоков размером 2k) 178

Списки блоков свободной памяти в общем случае. 180

Модифицированные списки блоков свободной памяти в общем случае (алгоритм парных меток) 181

Сборка мусора. 183

Лекция 18. 185

Прерывания. 185

Кэш-память. 186

Организация Кэш-памяти и ассоциативная память в IBM PC-совместимых ЭВМ... 188

Основные принципы параллельных вычислений. 191

Конкуренция процессов в борьбе за ресурсы.. 192

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

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

Семафоры.. 194

Задача о производителях и потребителе. 196


Лекция 1

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

 

Целые

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

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

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

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

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

Принято считать, что в представлении байта старший бит всегда находится слева.

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

  • Big-endian      - от старшего байта к младшему (IBM-формат)
  • Little-endian   - от младшего байта к старшему (Intel-формат)

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

 

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

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

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

 

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

 

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

Для доказательства Утверждения достаточно доказать, что вышеприведенное определение отрицательного числа в дополнительном коде эквивалентно следующему: пусть x>0, то -x получается с помощью операции 2n-x. В исходном определении число -x получается из x>0 следующим образом: сначала производится инверсия числа, что эквивалентно операции 2n-x-1. Это следует из того, что (2n-x-1)+x=2n-1=числу, состоящему из n единиц, а это возможно только если на месте единичных бит числа 2n-x-1 стоят нули в представлении числа x и наоборот (на  месте нулевых бит числа 2n-x-1 стоят единицы в представлении числа x). Осталось прибавить 1 и мы получим требуемые 2n-x.

 

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

 

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

 

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

 

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 – символы Xxxxxx из мантиссы (мантисса в виде X.xxxxxx)

 

В некоторых версиях языка С тип long double присутствует, но является всего лишь синонимом типа double (например, в текущей версии Microsoft C это именно так). В gcc разрядность типа long double зависит от ключей компилятора и, конечно же, от архитектуры. По умолчанию в 64-битных системах используется 128-битная реализация long double (64 бита мантиссы, 15 бит степени, 1 бит знака, остальные младшие 6 байт биты не используются). Отметим, что данная реализация удовлетворяет IEEE стандарту лишь частично (поведение вблизи нуля аналогично стандартному, но старшая единичка мантиссы в представлении числа присутствует). На самом деле, легко увидеть, что данная реализация основана на 80-битной реализации вещественных чисел с дополнением пустых байт для правильной четности. Разрядность (здесь надо понимать, что 128-битная и 80-битная реализации long double отличаются, фактически, только четностью выравнивания) типа long double зависит от ключей компилятора mlong-double-64, –mlong-double-80, –mlong-double-128.

Ясно, что использование 80-битного представления вещественных чисел бывает редко оправданным. Примером, когда это имеет смысл, служит блестящая задача из online-олимпиады Физтеха: Вычислить logx (x4-64x+4) если известно: x9-4x5+16x-1=0. Задача достаточно просто делается с помощью чистой математики (на что она и рассчитана), однако если попытаться ее сделать с помощью компьютера, то выяснится, что точности double для ее решения недостаточно. Т.е. в компиляторе Microsoft получить решение задачи не получится. С помощью некоторой возни решение задачи можно получить на gcc, используя long double. Отмечу, что задача была первой в олимпиаде и с помощью нее великолепно отсеивались люди, которые пытались получить решения задач на компьютере. В качестве конкретного наезда J можно отметить, что в Ломоносовской олимпиаде подобных задач до сих пор не было.

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

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

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

 

BCD - Binary Coded Decimal.

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

 

Формат NUMBER из СУБД Oracle.

Данный формат похож на упакованный BCD формат. В нем в одном байте хранятся две цифры десятичного представления в т.н. стоичной системе счисления.

Число в данном формате хранится как число с плавающей точкой, но его длина не фиксирована.

Данный формат обладает несомненным преимуществом – возможностью точного представления в ЭВМ дробных десятичных чисел. Другим преимуществом данного формата является возможность хранения (передачи) чисел в таком формате в текстовой строке, в которой конец строки помечается символом с нулевым кодом (во внутреннем представлении чисел в формате NUMBER нет байт с нулевым значением). Наконец, числа в данном представлении можно сравнивать лексикографически (как обычные строки). Основной недостаток – использование программной реализации для работы с числами в данном формате, т.е. отсутствие поддержки данного формата на уровне процессора. Такой формат является весьма удобным при полном отсутствии встроенных в железо операций с вещественными числами, но при их наличии для других форматов формат NUMBER им сильно проигрывает.

Разберем подробно формат представления числа в формате NUMBER из СУБД Oracle. Число в таком формате может занимать различное количество байт, в зависимости от величины числа, поэтому во внутреннем представлении числа сначала хранится байт с длиной числа в байтах, а потом само число. Далее разберем формат хранения самого числа (без байта с его длиной).

Ноль хранится в виде одного байта 0x80.

Для хранения любого другого числа x оно представляется в виде x=s*y*100n, где s=1 или -1, 1≤y<100 называется мантиссой, n целая степень числа. Все незначащие нули в конце y отбрасываются. Например: 1234.56=1*12.3456*1001, 1000. =1*10. *1001. Если количество цифр до/после точки нечетное, то дополним цифры нулем до/после числа. Например: 234.5=1*02.3450*1001. Будем далее работать с этим нормализованным представлением числа.

В начале представления числа хранится байт со степенью в виде: если х положительно, то байт имеет вид  n+65+128=n+0x41+0x80= (n+0x41)|0x80=n+0xC1 т.е. берется n+65 и в старший бит прописывается 1. Если х отрицательно, то делается все то же самое, но потом число еще инвертируется. Т.о. старший бит первого байта числа будет хранить знак числа: если бит = 1, то число положительно, иначе – отрицательно.

Отметим, что нулевая степень для положительного числа хранится как 65+128=193=1100 0001b, а для отрицательно – как ~1100 0001b=0011 1110b=62, и от этих чисел (193 и 62) можно вести отсчет при расчете внутреннего представления степени.

 Например, для x>0, n=1 имеем внутреннее представление степени 1+65+128=1+193=194. Для  x<0, n=1 имеем внутреннее представление степени ~(1+65+128)=~(1+193)=~194=~1100 0010b=0011 1101b=61=62-1. Для  x<0, n=-2 имеем внутреннее представление степени 62+2=64. И т.д.

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

Далее каждая пара цифр (назовем число из этих двух цифр t) мантиссы нормализованного представления числа записывается в соответствующий байт представления числа в виде t+1 для положительного x и в виде 101-t для отрицательного x. Для отрицательного x в конец представления числа дописывается байт 102. Утверждается, что это облегчает процесс сравнения отрицательных чисел.

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

Приведем примеры представления чисел в формате NUMBER (первые два числа=два байта – длина и представление степени; далее две цифры мантиссы = один байт).

110=01.10*1001:         3 194 02 11

1100=11.*1001:           2 194 12  (заметим, что число больше предыдущего!)

1101=11.01*1001:       3 194 12 02

-1101=-11.01*1001:    4 61 90 100 102

-1=-01.*1000    :           3 62 100 102

-1.01=-01.01*1000:     4 62 100 100 102

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

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

1)Положительное+положительное. Выполняется обычное сложение байт столбиком с переносом переполнения в следующий байт. Пример (первый столбец: слагаемые и сумма в десятичной системе; столбцы далее: представление байт слагаемых и суммы в формате NUMBER с вычтенной 1).

 8989      89  89

 1212      12 12

1 02  01

10201

 

2)Отрицательное+положительное. Выполняется обычное сложение байт столбиком с переносом переполнения в следующий байт. Знак результата определяется по значению переполнения при сложении старших байт: 0 = минус, 1 = плюс.

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

-1111      89  89

 1110      11 10

         0 100 99

     -1

 

-111211           89   88  89

 101112           10   11  12

                    0  99 100  01

   -10099

 

-1111   89  89

 1212   12 12

         1   2 01

   101

 

-111160           89 89  40

 121212           12 12 12

                     1 02 01  52

10052

 

-1                     100 100 99

 121212             12   12 12

                     1   13   13 11

121211

 

3)Отрицательное+ Отрицательное. Выполняется обычное сложение байт столбиком с переносом переполнения в следующий байт. Изо всех байт, включая байт переполнения, кроме младшего вычитается 1 (если байт переполнения =0, то в него записывается 99).

Примеры.

-1111               89 89

-1111               89 89

                     1 79 78

-2222

 

  -6666             34 34

  -6666             34 34

                     0 68 68

-13332

 

            Все эти операции можно интерпретировать по-другому. На самом деле, аналогом инверсии в 100-ичной системе является операция 99-t для каждого байта t. Тогда операция перевода положительного числа x в число x будет в 100-ичной системе выглядеть следующим образом: 1)для всех байт делаем инверсию (операцию 99-t); 2)к числу прибавляем 1. Или, что то же самое: 1)из числа вычитаем 1; 2) для всех байт делаем инверсию (операцию 99-t).

3)Для байта степени делаем побитовую инверсию (эквивалентно t=255-t)

 

 

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

 

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

 

Определение 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) -  нижняя оценка времени работы алгоритма m2.

или:

" алгоритма 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: K 2h-1, откуда получаем: h  ³ (log2 K) +1.

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

 

h  ³ (log2 K) +1 = (log2 N!) + 1 =Q(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 ;//M -> 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.

Будем говорить, что множество X состоит из разделимых связных компонент {Ai}, если X=U{Ai}, Ai не пересекаются и " aÎ Ai, bÎ Aj  (ij) найдется cÎ [a,b], такое что сÏ X.

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

Теорема. Пусть W Ì IR   N – множество точек, на которых решением задачи будет `да’. Пусть #W – количество разделимых связных компонент множества W. Тогда, в рамках алгоритмов, описывающихся алгебраическими деревьями степени 1, существует нижняя оценка времени решения задачи, равная Q (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)

Если  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)

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

     }

   i + +; j - -;

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

 

 

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

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

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

 

Теорема. Среднее время работы алго