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

по курсу

 

 

 

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

 

 

 

 

 

 

 

 

 

 

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

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

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

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

2018г.


 

 

Лекция 1. 1

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

Целые. 1

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

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

Лекция 2. 1

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

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

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

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

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

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

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

Лекция 3. 1

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

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

QuickSort. 1

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

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

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

Лекция 4. 1

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

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

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

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

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

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

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

Лекция 5. 1

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

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

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

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

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

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

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

Переменные. 1

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

Вектор. 1

Стек. 1

Лекция 6. 1

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

Стек. 1

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

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

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

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

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

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

Очередь. 1

Дек. 1

Списки. 1

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

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

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

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

Лекция 7. 1

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

Графы.. 1

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

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

Лекция 8. 1

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

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

Лекция 9. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 10. 1

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

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

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

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

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

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

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

Лекция 11. 1

B-деревья. 1

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

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

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

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

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

Лекция 12. 1

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

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

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

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

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

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

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

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

Лекция 14. 1

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

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

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

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

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

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

Лекция 15. 1

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

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

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

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

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


Лекция 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 – количество бит в двоичном представлении числа.

 

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

 

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

 

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

 

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-битные вещественные числа, вообще говоря, могут интерпретироваться процессором по-разному). В этом формате  старший бит мантиссы обычно не изымается из машинного представления вещественного числа, что несколько уменьшает возможную точность представления вещественного число, в  обмен на более простые алгоритмы работы с такими числами.

 

BCD - Binary Coded Decimal.

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

 

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

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

Стоит отметить, что для типа NUMBER в Oracle при задании переменной задаются точность (общее количество цифр) и масштаб (количество чисел после запятой), что является признаком числа с фиксированной точкой. Тем не менее, само число хранится, как число с плавающей точкой.

Данный формат обладает несомненным преимуществом – возможностью точного представления в ЭВМ дробных десятичных чисел. Другим преимуществом данного формата является возможность хранения (передачи) чисел в таком формате в текстовой строке, в которой конец строки помечается символом с нулевым кодом (во внутреннем представлении чисел в формате 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: K2h-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-ой порядковой статистики и при том, что в качестве псевдомедианы каждый раз будет выбираться первый элемент в подмассиве.

 

Теорема. Среднее время работы алгоритма 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) для случая |ai|<O(N)

Очень часто встречаются задачи, когда требуется искать порядковую статистику большого множества целых чисел, значения которых ограничены некоторой небольшой константой. Классическим примером таких задач является поиск порядковой статистики для некоторого подмножества пикселов серого изображения (=значения пикселов от 0 до 255). Данная задача может быть решена по аналогии с алгоритмом сортировки подсчетом.

Итак, пусть есть массив целых чисел {Ai} (i=0,…,N-1), 0£ Ai<M. Требуется вычислить порядковую статистику с номером q. Для работы алгоритма требуется дополнительный массив целых чисел B длины M. Алгоритм аналогичен сортировке подсчетом:

 


 QFindStatD (A,N, q, B,M)

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

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

Для всех i от 0 до M-1 с шагом 1 выполнить: ЕСЛИ q<B[i] то ВЕРНУТЬ i  ИНАЧЕ q-=B[i]

 

 

 


Теорема. O(N+M) является верхней оценкой времени работы алгоритма  QFindStatD  для случая 0£ Ai<M, где N – количество элементов в обрабатываемом массиве. Для случая M=O(N) верхней оценкой времени работы алгоритма является O(N).

 

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

Обычно под серым изображением имеется в виду массив целых чисел Ai,j размером Nx×Ny со значениями 0£ Ai£255. Требуется для всех I,J найти порядковую статистику с номером q для множества пикселов с индексами I-M £ i £ I+M, J-M £ j £ J+M.

Если воспользоваться предыдущим алгоритмом поиска порядковой статистики, то мы получим верхнюю оценку времени работы алгоритма = O(Nx×Ny×M2), что будет ощутимо медленно работать в случае изображения среднего размера (1000×1000) и средних значений M (например, M больше 100). Оказывается, данную задачу можно решить существенно более быстро. При этом окажется, что среднее время подсчета медианы будет по порядку меньше количества элементов последовательности, по которой считается медиана (!).

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

Для I=0 медиана будет считаться с помощью алгоритма QFindStatD.

Далее в цикле по I при расчете медианы для окрестности пиксела I,J отметим, что в рассматриваемое множество пикселов будут добавляться точки с i=I+M  (кроме M последних столбцов) и удаляться точки с i=I-M (кроме M первых столбцов).

Тогда, если мы будем хранить в процессе вычислений массив B из алгоритма QFindStatD, то для каждого I,J его модификация потребует всего лишь O(M) операций. Здесь, конечно, следует отметить, что в оценку времени работы алгоритма войдет количество градаций яркости изображения (у нас = 256), но для больших M (у нас больше 100) это замечание несущественно.

Таким образом, мы получили алгоритм решения данной задачи с верхней оценку времени работы = O(Nx×Ny×M), т.е. среднее время вычисления порядковой статистики в данном случае для каждой области равно квадратному корню от количества точек в рассматриваемой области.

 

 

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

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

Итак, для поиска k-ой статистики массива A, состоящего из N элементов, следующий алгоритм надо вызывать в виде QFindStat5(A,1,N,k)

QFindStat5(A,I,M,k)

 


Если M -I+1 £ 5 то найти k-ую статистику с номером x любым методом; return x

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

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

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

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

     => массив разбит на куски [I,L] и [L+1, M]

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

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

 

 


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

Доказательство. В массиве медиан пятерок [(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);

 

 

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

 

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

int **st6=NULL;

 

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

 

int ** StackCreate6(int n )

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

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

  st[1] = st[0]+n;

}

 

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

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

 

void StackDelete6(int  ***st ) { free(*st);*st=NULL;}

а ее вызов будет выглядеть так:  StackDelete6 (&st6);

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

Добавлять элемент в стек и извлекать элемент из стека можно следующими функциями:

 

int StackPush6(int **s, int v )

 {

  if(s[0]>=s[1])return -1;//стек заполнен

  *(s[0]++)=v;

 return 0;

}

int StackPop6(int **s, int *v )

 {

  if(s[0]<=(int*)(s+2))return -1;//стек пуст

  *v=*(--s[0]);

 return 0;

}

 

Очередь.

 Очередью называется структура данных, организованная по принципу 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 ребер;

Имеем следующие времен