25 (1108024)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 251Пирамидальная сортировка (heapsort)Можно использовать дерево поиска для сортировкиНапример, последовательный поиск минимального элемента,удаление его и вставка в отсортированный массивНедостатки:Сложность такого алгоритма есть O (nh), где h – высотадереваТребуется дополнительная память для дереваТребуется построить само дерево (с минимальной высотой)Можно ли построить похожий алгоритм без требований кдополнительной памяти?2Пирамидальная сортировка: пирамида (двоичная куча)Рассматриваем массив a как двоичное дерево:Элемент a[i] является узлом дереваЭлемент a[i/2] является родителем узла a[i]Элементы a[2*i] и a[2*i+1] являются детьми узла a[i]Для всех элементов пирамиды выполняется соотношение(основное свойство кучи):a[i] >= a[2*i] и a[i] >= a[2*i+1]илиa[i/2] <= a[i]Сравнение может быть как в большую, так и в меньшую сторонуЗамечание.

Определение предполагает нумерацию элементовмассива от 1 до nДля нумерации от 0 до n-1:a[i] >= a[2*i+1] и a[i] >= a[2*i+2]3Пирамидальная сортировка: пирамида (двоичная куча)Для всех элементов пирамиды выполняется соотношение:a[i] >= a[2*i] и a[i] >= a[2*i+1]илиa[i/2] <= a[i]Сравнение может быть как в большую, так и в меньшую сторону4Пирамидальная сортировка: просеивание элементаКак добавить элемент в уже существующуюпирамиду?Алгоритм:Поместим новый элемент в корень пирамидыЕсли этот элемент меньше одного из сыновей:Элемент меньше наибольшего сынаОбменяем элемент с наибольшим сыном(это позволит сохранить свойство пирамидыдля другого сына)Повторим процедуру для обмененного сына5Пирамидальная сортировка: просеивание элементаstatic void sift (int *a, int l, int r) {int i, j, x;i = l; j = 2*l; x = a[l];/* j указывает на наибольшего сына */if (j < r && a[j] < a[j + 1])j++;/* i указывает на отца */while (j <= r && x < a[j]) {/* обмен с наибольшим сыном: a[i] == x */a[i] = a[j]; a[j] = x;/* продвижение индексов к следующему сыну */i = j; j = 2*j;/* выбор наибольшего сына */if (j < r && a[j] < a[j + 1])j++;}}6Пирамидальная сортировка: просеивание элемента/* l, r - от 0 до n-1 */static void sift (int *a, int l, int r) {int i, j, x;/* Теперь l, r, i, j от 1 до n, а индексы массивауменьшаются на 1 при доступе */l++, r++;i = l; j = 2*l; x = a[l-1];/* j указывает на наибольшего сына */if (j < r && a[j-1] < a[j])j++;/* i указывает на отца */while (j <= r && x < a[j-1]) {/* обмен с наибольшим сыном: a[i-1] == x */a[i-1] = a[j-1]; a[j-1] = x;/* продвижение индексов к следующему сыну */i = j; j = 2*j;/* выбор наибольшего сына */if (j < r && a[j-1] < a[j])j++;}}7Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева8Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева9Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева10Пирамидальная сортировка: алгоритм(1)(2)Построим пирамиду по сортируемому массивуЭлементы массива от n/2 до n являются листьямидерева, а следовательно, правильными пирамидами изодного элементаДля остальных элементов в порядке уменьшения индексапросеиваем их через правую часть массиваОтсортируем массив по пирамидеПервый элемент массива максимален (корень пирамиды)Поменяем первый элемент с последним(таким образом, последний элемент отсортирован)Теперь для первого элемента свойство кучи нарушено:повторим просеивание первого элемента в пирамидеот первого до предпоследнегоСнова поменяем первый и предпоследний элемент и т.п.11Пирамидальная сортировка: программаvoid heapsort (int *a, int n) {int i, x;/* Построим пирамиду по сортируемому массиву *//* Элементы нумеруются с 0 -> идем от n/2-1 */for (i = n/2 - 1; i >= 0; i--)sift (a, i, n - 1);for (i = n – 1; i > 0; i--) {/* Текущий максимальный элемент в конец */x = a[0]; a[0] = a[i]; a[i] = x;/* Восстановим пирамиду в оставшемся массиве */sift (a, 0, i – 1);}}12Пирамидальная сортировка: пример13Пирамидальная сортировка: пример14Пирамидальная сортировка: пример15Пирамидальная сортировка: пример16Пирамидальная сортировка: пример17Пирамидальная сортировка: сложность алгоритма(1)Построим пирамиду по сортируемому массиву(2)Элементы массива от n/2 до n являются листьямидерева, а следовательно, правильными пирамидами из 1 элементаДля остальных элементов в порядке уменьшения индексапросеиваем их через правую часть массиваОтсортируем массив по пирамидеПервый элемент массива максимален (корень пирамиды)Поменяем первый элемент с последним(таким образом, последний элемент отсортирован)Теперь для первого элемента свойство кучи нарушено:повторим просеивание первого элемента в пирамидеот первого до предпоследнегоСнова поменяем первый и предпоследний элемент и т.п.Сложность этапа построения пирамиды есть O(n)Сложность этапа сортировки есть O(n log n)Сложноcть в худшем случае также O(n log n)Среднее количество обменов – n/2* log n18Цифровой поискЦифровой поиск – частный случай поиска заданной подстроки(образца) в длинной строке (тексте).Примеры цифрового поиска: поиск в словаре, в библиотечномкаталоге и т.п., когда делается поиск по образцу в несколькихтекстах (названиях книг, фамилиях авторов, текстах навызванных сайтах и т.п.).Хороший пример – словарь с высечками, т.е.

словарь, в которомобеспечен быстрый доступ к некоторым страницам (например,начальным страницам списков слов, начинающихся наочередную букву алфавита). Иногда используютсямногоуровневые высечки.При цифровом поиске ключи рассматриваются какпоследовательности символов рассматриваемого алфавита(в частности, цифр или букв). Ожидаемое число сравненийпорядка О(logm N), где m - число различных букв, используемыхв словаре, N – мощность словаря. В худшем случае деревосодержит k уровней, где k – длина максимального слова.19Цифровой поискПример.

Пусть множество используемых букв (алфавит){A, B, C, D}. Мы добавим к алфавиту еще одну букву (пробел).По определению слова АА, АА , ААсовпадают.Пусть {A, AA, ABB, AC, ADBD, BCA, BCD, CBA} – словарь(множество ключей).Построим m-ичное дерево, где m = 5 = | , A, B, C, D |.Следующая небольшая хитрость позволит иногда сократитьпоиск: если в словаре есть слово а1а2а3...аk и первые i его букв(i < k) задают уникальное значение: комбинация а1...аiвстречается в словаре только один раз, то не нужно строитьдерево для j > i, так как слово можно идентифицировать попервым i буквам.Очень важное обобщение цифрового поиска: таким же образомможно обрабатывать любые ключи, не привязываясь к байту (8битам), который обычно используется для кодирования символовалфавита.

Мы можем отсекать от ключа первые m бит,использовать 2m-ичное разветвление, т.е. строить 2m-ичноедерево поиска (на двоичных деревьях для разветвления20берется один бит: m = 1).Цифровой поискПрямоугольниками изображены вершины дерева, в овалах –значения слов (ключей) и связанная с ним информация.Тем самым любая вершина дерева – массив из m элементов.Каждый элемент вершины содержит либо ссылку на другуювершину m-ичного дерева, либо на овал (ключ).21Цифровой поискИногда используют комбинации нескольких методов:цифровой поиск вначале, а затем переключение на поиск впоследовательных таблицах.Именно так мы и работаем со словарем с высечками:вначале на высечку, а затем либо последовательныйпоиск, либо дихотомический.Обычно предлагается пользоваться цифровым поиском, покаколичество различных слов не меньше некоторого k, а затемпереключаться на последовательные таблицы.Обобщения: поиск по неполным ключам, поиск по образцу.22Цифровой поиск#include <stdio.h>#include <stdlib.h>#include <string.h>#define M 5typedef enum {word, node} tag_t;struct record {char *key;int value;};struct tree {tag_t tag;union {struct record *r;struct tree *nodes[M+1];}; /* анонимное объединение */};23Цифровой поиск: поиск элементаstatic inline int ord (char c) {return c ? c - 'A' + 1 : 0;}struct record *find (struct tree *t, char *key) {int i = 0;while (t) {switch (t->tag) {case word:for (; key[i]; i++)if (key[i] != t->r->key[i])return NULL;return t->r->key[i] ? NULL : t->r;case node:t = t->nodes[ord(key[i])];if (key[i])i++;}}return NULL;}24Цифровой поиск: вставка – вспомогательные функцииstruct record *make_record (char *key, int value) {struct record *r = malloc (sizeof (struct record));r->key = strdup (key);r->value = value;return r;}struct tree *make_word (char *key, int value) {struct tree *t = malloc (sizeof (struct tree));t->tag = word;t->r = make_record (key, value);return t;}struct tree *make_node (void) {struct tree *t = calloc (1, sizeof (struct tree));t->tag = node;return t;}struct tree *make_from_record (struct record *r) {struct tree *t = malloc (sizeof (struct tree));t->tag = word;t->r = r;return t;}25Цифровой поиск: вставка элементаstruct tree *insert (struct tree *t, char *key, int value) {if (!t)return make_word (key, value);int i = 0;struct tree *root = t;/* skip all nodes */while (t->tag == node) {struct tree **p = &t->nodes[ord(key[i++])];if (!*p) {*p = make_word (key, value);return root;}t = *p;}/* all word skipped -- key exists, update value */if (i && !key[i - 1]) {t->r->value = value;return root;}26Цифровой поиск: вставка элемента/* compare the remaining part */int j = i;for (; key[i]; i++)if (key[i] != t->r->key[i])break;/* key already exists -- update value */if (!key[i] && !t->r->key[i]) {t->r->value = value;return root;}/* turn t into a node */struct record *other = t->r;t->tag = node;memset (t->nodes, 0, sizeof (t->nodes));27Цифровой поиск: вставка элемента/* make new nodes for remaining common prefix */for (; j < i; j++) {struct tree *p = make_node ();t->nodes[ord(key[j])] = p;t = p;}/* accommodate both other and new record */t->nodes[ord(other->key[i])]= make_from_record (other);t->nodes[ord(key[i])] = make_word (key, value);return root;}28Цифровой поиск: печать элементовvoid print (struct tree *t, char c) {static int level = 0;if (!t) {printf ("empty\n");return;}for (int i = 0; i < level; i++)putchar (' ');if (level)printf ("%c: ", chr (c));if (t->tag == word) {printf ("word: %s %d\n", t->r->key, t->r->value);} else {printf ("node: ");for (int i = 0; i < M + 1; i++)if (t->nodes[i])printf ("%c ", chr(i));putchar ('\n');level++;for (int i = 0; i < M + 1; i++)if (t->nodes[i])print (t->nodes[i], i);level--;}}29.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций