Алгоритмы преобразования ключей
СОДЕРЖАНИЕВВЕДЕНИЕГЛАВА 1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙ (РАССТАНОВКА)ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ2.1 ВСТАВКА ЭЛЕМЕНТА В В-ДЕРЕВО2.2 ОБРАБОТКА ТЕКСТОВЫХ ФАЙЛОВПРИЛОЖЕНИЕ К ВЫПОЛНЕННЫМ ПРОГРАММАМЗАКЛЮЧЕНИЕСПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫВВЕДЕНИЕДанная курсовая работа состоит из четырёх основных разделов каждый из которых представляет собой рассмотрения отдельно взятого задания для данной курсовой работы. Для начала следует определить цель каждого задания.Алгоритмы преобразования ключей (расстановка). Хеширование - алгоритмическое преобразование ключей в адреса. В СУБД метод индексации, при котором значение ключа (идентификатора записи) служит аргументом для прямого вычисления либо локализации ассоциированной записи в файле, либо начала ее поиска.С хешированием сталкиваются едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.Написать процедуру, реализующую вставку в В-дерево. Рассмотрим, что же такое В-дерево. Предположим, что нам придется иметь дело с множеством, которое невозможно разместить во внутренней памяти, работа с которой отличается быстрым доступом, целиком из-за его большого объема. Поэтому нам придется хранить данные во внешней памяти, обладающей относительно большим временем доступа. Значит, наша цель будет заключаться, прежде всего, в попытке уменьшить количество запросов на чтение к внешней памяти. Как мы уже видели, очень эффективным является хранение множества в виде дерева. Поэтому попробуем создать такое дерево, которое будет обеспечивать при своем обслуживании относительно небольшое количество обращений к внешней памяти.Для этого в каждом узле дерева надо хранить как можно больше элементов (сколько позволяет объем выделенной внутренней памяти, но не настолько много, чтобы чтение столь большого блока требовало много времени) и читать каждый узел за один запрос к внешней памяти. Естественно, наше дерево должно быть упорядочено, ведь, как мы видели ранее, именно упорядоченные деревья позволяют сократить количество просматриваемых узлов. Также, чтобы гарантировать логарифмическую сложность, желательно поддерживать такое дерево сбалансированным (в том смысле, что для каждой вершины дерева высота левого поддерева должна быть равна высоте правого поддерева). Узел такого дерева назовем страницей поиска.3. Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество слов, которые содержат определённое количество согласных.4. Выполнить тестирование программы для нормальных, граничных и исключительных условий. Результаты тестирования свести в таблицу.ГЛАВА 1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙХеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (совершенная хеш-функция). Однако на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента.Термин «хеширование» (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г. [1]), хотя сам механизм был известен и ранее. Глагол «hash» в английском языке означает «рубить, крошить», т. е. создавать этакий «винегрет». Для русского языка академиком А.П. Ершовым [2] был предложен достаточно удачный эквивалент — «расстановка», созвучный с родственными понятиями комбинаторики, такими как «подстановка» и «перестановка». Однако пока он не прижился.Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работы Петерсона (1957, [4]) и Морриса (1968, [5]). В первой реализовывался класс методов с открытой адресацией при работе с большими файлами, а во второй давался обширный обзор по хешированию и вводился термин «рассеянная память» (scatter storage).Одна из важных задач, решаемых в программировании,— это обеспечение быстрого (прямого) доступа к данным по некоему коду (индексу, адресу). Неудивительно, что решающий эту задачу массив стал одним из главных строительных блоков, превосходя по использованию списки, которые определяют последовательный доступ к элементам. В математике массиву соответствуют понятия вектор (в одномерном случае) и матрица (в двумерном).Как известно, массив задает отображение (A) множества индексов (I) на множество элементов (E), т. е. A: I —> E. Массив позволяет по индексу быстро найти требуемый элемент. Хеширование решает в точности такую же задачу. Однако здесь уже в роли индекса выступает хеш-адрес, который определяется как значение некоей хеш-функции, применяемой к уникальному ключу. В этом смысле хеш-структуры можно рассматривать как обобщение массива.В программировании зависимость между индексом и значением записывается в виде: A = ARRAY I OF E. В роли индексирующего типа (I) обычно выбирается конкретный диапазон значений из целочисленного типа (хотя в общем случае в их роли могут выступать так называемые скалярные типы, т. е. булев тип, перечисления, множества и др.). Ну а элементы массива в зависимости от языка программирования могут быть любыми, начиная от битов, чисел и указателей (ссылок) и заканчивая составными типами произвольной глубины.То, что массив задает функцию отображения, в языке Ада подчеркивается даже на уровне синтаксиса. Например, при появлении в тексте программы записи вида «a(i)» трудно с ходу сказать, идет ли это обращение к i-му элеме...
Другие файлы:
Алгоритмы криптографической защиты информации
Рассмотрение основных понятий криптографии: конфиденциальности, целостности, аутентификации и цифровой подписи. Описание криптографических средств защ...
Теория и практика вейвлет - преобразования
Излагаются основные вопросы теории вейвлет-преобразования , практические аспекты преобразования, алгоритмы сжатия информации...
Быстрые алгоритмы в цифровой обработке изображений
Изложены основы теории и применения новых эффективных в вычислительном отношении алгоритмов цифровой обработки изображений. Рассмотрены алгоритмы быст...
Современные алгоритмы симметричного шифрования
История появления симметричных алгоритмов шифрования. Роль симметричного ключа в обеспечении степени секретности сообщения. Диффузия и конфузия как сп...
Исследование эхокомпенсатора и улучшение его характеристик в режиме одновременного разговора абонентов
Общие сведения об эхокомпенсации. Алгоритм быстрого преобразования Фурье. Физический смысл дискретного преобразования. Вычислительные алгоритмы, испол...
