23 (1106260)

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

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

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 231Цифровой поискЦифровой поиск – частный случай поиска заданной подстроки(образца) в длинной строке (тексте).Примеры цифрового поиска: поиск в словаре, в библиотечномкаталоге и т.п., когда делается поиск по образцу в несколькихтекстах (названиях книг, фамилиях авторов, текстах навызванных сайтах и т.п.).Хороший пример – словарь с высечками, т.е. словарь, в которомобеспечен быстрый доступ к некоторым страницам (например,начальным страницам списков слов, начинающихся наочередную букву алфавита).

Иногда используютсямногоуровневые высечки.При цифровом поиске ключи рассматриваются какпоследовательности символов рассматриваемого алфавита(в частности, цифр или букв). Ожидаемое число сравненийпорядка О(logm N), где m - число различных букв, используемыхв словаре, N – мощность словаря. В худшем случае деревосодержит k уровней, где k – длина максимального слова.2Цифровой поискПример. Пусть множество используемых букв (алфавит){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-ичноедерево поиска (на двоичных деревьях для разветвления3берется один бит: m = 1).Цифровой поискПрямоугольниками изображены вершины дерева, в овалах –значения слов (ключей) и связанная с ним информация.Тем самым любая вершина дерева – массив из m элементов.Каждый элемент вершины содержит либо ссылку на другуювершину m-ичного дерева, либо на овал (ключ).4Цифровой поиск#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];} u;};5Цифровой поиск: поиск элемента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->u.r->key[i])return NULL;return u.r->key[i] ? NULL : t->u.r;case node:t = t->u.nodes[ord(key[i])];if (key[i])i++;}}return NULL;}6Цифровой поиск: вставка – вспомогательные функции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->u.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->u.r = r;return t;}7Цифровой поиск: вставка элемента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->u.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->u.r->value = value;return root;}8Цифровой поиск: вставка элемента/* compare the remaining part */int j = i;for (; key[i]; i++)if (key[i] != t->u.r->key[i])break;/* key already exists -- update value */if (!key[i] && !t->u.r->key[i]) {t->u.r->value = value;return root;}/* turn t into a node */struct record *other = t->u.r;t->tag = node;memset (t->u.nodes, 0, sizeof (t->u.nodes));9Цифровой поиск: вставка элемента/* make new nodes for remaining common prefix */for (; j < i; j++) {struct tree *p = make_node ();t->u.nodes[ord(key[j])] = p;t = p;}/* accommodate both other and new record */t->u.nodes[ord(other->key[i])]= make_from_record (other);t->u.nodes[ord(key[i])] = make_word (key, value);return root;}10Цифровой поиск: печать элементов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->u.r->key, t->u.r->value);} else {printf ("node: ");for (int i = 0; i < M + 1; i++)if (t->u.nodes[i])printf ("%c ", chr(i));putchar ('\n');level++;for (int i = 0; i < M + 1; i++)if (t->u.nodes[i])print (t->u.nodes[i], i);level--;}}11Цифровой поискИногда используют комбинации нескольких методов:цифровой поиск вначале, а затем переключение на поиск впоследовательных таблицах.Именно так мы и работаем со словарем с высечками:вначале на высечку, а затем либо последовательныйпоиск, либо дихотомический.Обычно предлагается пользоваться цифровым поиском, покаколичество различных слов не меньше некоторого k, а затемпереключаться на последовательные таблицы.Обобщения: поиск по неполным ключам, поиск по образцу.12Алгоритмы перебора множествПерестановка некоторого набора элементов – это упорядоченнаяпоследовательность из этих элементов.

Например, множество{1, 2, 3} имеет 6 различных перестановок (1, 2, 3), (1, 3, 2),(2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).Для любого множества из n элементов существует ровно n! =1⋅2⋅...⋅n различных перестановок.Задача состоит в том, чтобы написать программу, котораявыводит все перестановки множества {1,2,..., n} влексикографическом порядке (перестановки можнорассматривать как слова в алфавите B = {1, 2, ..., n})13Рекурсивный алгоритм генерации перестановокБудем перебирать перестановки чисел {1, 2, ..., n} в массиве a[n],последовательно заполняя его числами 1, ..., n в различномпорядке.Для перебора всех перестановок будем записывать на первоеместо в массиве a по очереди числа 1, ..., n, и для каждого числарекурсивно вызывать функцию генерации перестановокоставшихся n – 1 чисел.

Массив b отмечает уже выбранныечисла.#include <stdio.h>#include <stdlib.h>void PrintPerm (int *a, int n) {int i;for (i = 0; i < n; i++)printf("%3d", a[i]);printf("\n");}14Рекурсивный алгоритм генерации перестановокvoid GenPerm (int *a, int *b, int i, int n) {if (i == n)PrintPerm (a, n);} else {int j;for (j = 0; j < n; j++)if (b[j] == 0) {b[j] = 1;a[i] = j + 1;GenPerm (a, b, i+1, n);b[j] = 0;}}}15Рекурсивный алгоритм генерации перестановокint main (void) {int *a, *b;int n;scanf("%d", &n);a = malloc (n * sizeof (int));b = calloc (n, sizeof (int));GenPerm (a, b, 0, n); /* первый вызов генератора */free (a);free (b);return 0;}16Нерекурсивный алгоритм генерации перестановокЗадачу посещения (перебора) всех перестановок заданногомножества можно свести к следующей задаче: по даннойперестановке сгенерировать следующую за ней перестановку(например, в лексикографическом порядке). Один из первыхалгоритмов решения этой задачи придумал индийский математикПандит Нарайана еще в XIV веке.Алгоритм Нарайаны по любой данной перестановке из nэлементов а1 а2 ...

аn генерирует следующую(в лексикографическом порядке) перестановку.Если алгоритм Нарайаны применить в цикле к исходнойпоследовательности n элементов а1 а2 ... аn, отсортированныхтак, что а1 ≤ а2 ≤ ... ≤ аn, то он сгенерирует все перестановкиэлементов множества {а1 а2 ... аn}, в лексикографическомпорядке.17Алгоритм НарайаныШаг 1. [Первая перестановка.] Составить перестановку а1 а2 ... аn(а1 < а2 < ...

< аn).Шаг 2. [Найти j, для которого аj < аj+1] Установить j ← n – 1.Если аj >аj+1, уменьшать j на 1 повторно, пока не выполнитсяусловие аj < аj+1. Если окажется, что j = 0, завершить алгоритм.На шаге 2 j является наименьшим индексом, для которогобыли посещены все перестановки, начиная с а1 ... аj.Следовательно, лексикографически следующаяперестановка увеличит значение аj.Шаг 3. [Увеличить аj] Установить l ← n.

Если аj >аl, уменьшать lна 1, пока не выполняется условие аj < аl. Затем поменятьместами аj ↔ аl.Поскольку аj+1 >... >аn, элемент аl является наименьшимэлементом, который больше аj, и который можетследовать за а1 ... аj-1 в перестановке. Перед заменойa j +1 > ... > al −1 > al > a j > al +1 > ...

> an ,выполнялись отношенияа после замены – выполняются a j +1 > ... > al −1 > a j > al > al +1 > ... > anШаг 4. [Обратить аj+1 ... аn] Установить k ← j + 1 и l ← n. Затем,если k < l, поменять местами аk ↔ аl, установить k ← k + 1,18l ← l – 1 и повторять, пока не выполнится условие k >l.Вернуться к шагу 2.Алгоритм Нарайаны#include <stdio.h>#include <stdlib.h>int NextPerm (int *a, int n) {int i, k, t, tmp;/* находим k такое что: а[k] < а[k+1] > .... > а[n-1]*/for (k = n – 2; (а[k] > a[k + 1]) && (k >= 0); k--);/* последняя перестановка */if (k == -1)return 0;/* находим t > k такое, что среди а[k+1],..., а[n–1]a[t] – минимальное число, большее а[k] */for (t = n - 1; (a[k] > a[t]) && (t >= k + 1); t--);tmp = a[k], a[k] = a[t], a[t] = tmp;/* оборачиваем участок массива a[k+1],..., a[n–1] */for (i = k + 1; i <= (n + k)/2; i++) {t = n + k – i;tmp = a[i], a[i] = a[t], a[t] = tmp;}19return i;}Алгоритм Нарайаныint main (void) {int *a, n, i;scanf ("%d", &n);a = malloc (n * sizeof(int));for (i = 0; i < n; i++)a[i] = i + 1;do {PrintPerm (a, n);} while (NextPerm (a, n));return 0;}20.

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

Тип файла PDF

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

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

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