Алгоритмы преобразования ключей

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙ(РАССТАНОВКА)
ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1 ВСТАВКА ЭЛЕМЕНТА В В-ДЕРЕВО
2.2 ОБРАБОТКА ТЕКСТОВЫХ ФАЙЛОВ
ПРИЛОЖЕНИЕ К ВЫПОЛНЕННЫМ ПРОГРАММАМ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ
Даннаякурсовая работа состоит из четырёх основных разделов каждый из которыхпредставляет собой рассмотрения отдельно взятого задания для данной курсовойработы. Для начала следует определить цель каждого задания.
1. Алгоритмыпреобразования ключей (расстановка).
Хеширование — алгоритмическое преобразование ключей в адреса. В СУБД метод индексации, прикотором значение ключа (идентификатора записи) служит аргументом для прямоговычисления либо локализации ассоциированной записи в файле, либо начала ее поиска.
Схешированием сталкиваются едва ли не на каждом шагу: при работе с браузером(список Web-ссылок), текстовым редактором и переводчиком (словарь), языкамискриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словамБрайана Кернигана, это «одно из величайших изобретений информатики». Заглядываяв адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся,что упорядочение по алфавиту является не чем иным, как хешированием.
2. Написатьпроцедуру, реализующую вставку в В-дерево.
Рассмотрим,что же такое В-дерево. Предположим, что нам придется иметь дело с множеством,которое невозможно разместить во внутренней памяти, работа с которой отличаетсябыстрым доступом, целиком из-за его большого объема. Поэтому нам придется хранитьданные во внешней памяти, обладающей относительно большим временем доступа.Значит, наша цель будет заключаться, прежде всего, в попытке уменьшитьколичество запросов на чтение к внешней памяти. Как мы уже видели, оченьэффективным является хранение множества в виде дерева. Поэтому попробуемсоздать такое дерево, которое будет обеспечивать при своем обслуживанииотносительно небольшое количество обращений к внешней памяти.
Дляэтого в каждом узле дерева надо хранить как можно больше элементов (сколько позволяетобъем выделенной внутренней памяти, но не настолько много, чтобы чтение стольбольшого блока требовало много времени) и читать каждый узел за один запрос квнешней памяти. Естественно, наше дерево должно быть упорядочено, ведь, как мывидели ранее, именно упорядоченные деревья позволяют сократить количествопросматриваемых узлов. Также, чтобы гарантировать логарифмическую сложность,желательно поддерживать такое дерево сбалансированным (в том смысле, что длякаждой вершины дерева высота левого поддерева должна быть равна высоте правогоподдерева). Узел такого дерева назовем страницей поиска.
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-му элементу массива «a»или же просто вызывается функция «a» с параметром «i».
Выделяютдва разных вида массивов: одномерные (наиболее общий случай) и многомерные (накаждом слое адресации используется массив фиксированной структуры). Во второмслучае есть и особый подвид: ступенчатые массивы (jagged arrays). Онивстречаются, в частности, в языке C# в том случае, когда на каждом слоеадресации используется массив переменной структуры. Иначе говоря, здесь мыимеем дело с массивом разных массивов. В других языках такая конструкция легкоописывается массивом разнородных указателей (каждый указывает на массив своейструктуры), что фактически определяет массив списков.
Интересно,что Н. Вирт после многих лет использования в своих языках (Паскаль, Модула-2) вкачестве индексирующего типа разных скалярных типов пришел к выводу, чтолаконичное решение, воплощенное в языке Си (а точнее, унаследованное в Си отязыков BCPL и B), носит куда более практичный характер. И в своих новых языкахОберон и Оберон-2 он отказался от идей Паскаля и ограничился заданием размерамассива (количества индексируемых элементов), т. е. определением для индексовдиапазона 0...n—1, где n — это размер массива: A = ARRAY 16 OF E. Связано это сэффективностью реализации и с активным использованием в программированииэлементов модулярной арифметики. В Обероне предопределенная функция MOD («x MODn»), как и в математике, соответствует остатку от целочисленного деления «x» на«n». Как показывает опыт, использование 0 в качестве начального индекса удобнов подавляющем большинстве задач. Механизмы хеширования опираются точно на ту жеоснову.
Вспомнимнекоторые определения из курса элементарной математики. Отображением (f: A —>B) множества A во множество B (функцией на A со значениями в B) называетсяправило, по которому каждому элементу множества A сопоставляется один илинесколько элементов множества B. Отсюда следует, что отображения могут бытьоднозначными и многозначными в зависимости от того, имеет ли каждый прообраз всоответствии один или несколько образов. Однозначное отображение f: A—> Bназывается сюръективным (сюръекцией), если f(A) = B. Это так называемоеотображение «на». Отображение (в общем случае неоднозначное) называетсяинъективным, если образы различных прообразов различны (отображение «в»).Cюръективное и инъективное отображение называется биекцией.
Воттеперь, пользуясь этими понятиями, попробуем разобраться в природе хеширования.Итак, одномерные и многомерные массивы — это яркий пример сюръекции. Поэтому ихможно назвать «сюръективными» массивами. Биекцию в общем случае они не задают,поскольку разным индексам (прообразам) могут соответствовать одни и те жезначения (образы). Примером «биективного» массива может служить, например,соответствующим образом заполненный массив литер: ARRAY 256 OF CHAR.
Вреальных задачах нередко возникают ситуации, когда не столько важно иметьоднозначное соответствие между адресом и значением, сколько гарантию того, чтоодно и то же значение не может быть получено по разным адресам. А это и естьинъекция, реализуемая через хеширование.
Следовательно,в случае хеширования значения хранятся в «инъективных» массивах разнойструктуры.
Именноздесь проходит водораздел между разными схемами и методами хеширования. Именноотсюда и проистекают проблемы поиска оптимального баланса между пространствомхранения и временем доступа.
Традиционнопринято выделять две схемы хеширования:
· хешированиес цепочками (со списками);
· хешированиес открытой адресацией.
Впервом случае выбирается некая хеш-функция h(k) = i, где i трактуется какиндекс в таблице списков t. Поскольку нельзя гарантировать, что не встретитсядвух разных ключей, которым соответствует один и тот же индекс i (конфликт,коллизия), такие «однородные» ключи просто помещаются в список, начинающийся вi-ячейке хеш-таблицы t (см. рисунок).
Очевидно,что процесс заполнения хеш-таблицы будет достаточно простым, но при этом доступк элементам потребует двух операций: вычисления индекса и поиска всоответствующем списке. Операции по занесению и поиску элементов при таком видехеширования будут вестись в незамкнутом (открытом) пространстве памяти.
Большинствозадач решается с использованием методики, называемой хешированием. Ее основусоставляют различные алгоритмы отображения значения ключа в значение адресаразмещения элемента в таблице. Непосредственное преобразование ключа в адреспроизводится с помощью функций расстановки, или хэш-функций. Адреса, получаемыеиз ключевых слов с помощью хэш-функций, называются хэш-адресами. Таблицы, дляработы с которыми используются методы хеширования, называются таблицами свычисляемыми входами, хэш-таблицами, или таблицами с прямым доступом.
Основополагающуюидею хеширования можно пояснить на следующем примере. Предположим, необходимоподсчитать, сколько раз в тексте встречаются слова, первый символ которых —одна из букв английского алфавита (или русского — это не имеет значения, можнов качестве объекта подсчета использовать любой символ из кодовой таблицы). Дляэтого в памяти нужно организовать таблицу, количество элементов в которой будетсоответствовать количеству букв в алфавите. Далее необходимо составитьпрограмму, в которой текст будет анализироваться с помощью цепочечных команд.При этом нас интересуют разделяющие слова пробелы и первые буквы самих слов.Так как символы букв имеют определенное двоичное значение, то на его основевычисляется адрес в таблице, по которому располагается элемент, в минимальномварианте состоящий из одного поля. В этом поле ведется подсчет количества словв тексте, начинающихся с данной буквы. В следующей программе с клавиатурывводится 20 слов (длиной не более 10 символов), производится подсчет английскихслов, начинающихся с определенной строчной буквы, и результат подсчетавыводится на экран. Хэш-функция (функция расстановки) имеет вид:
A=(C-97)*L,
гдеА — адрес в таблице, полученный на основе двоичного значения символа С; L —длина элемента таблицы (для нашей задачи L=l); 97 — десятичное смещение вкодовой таблице строчного символа «а» английского алфавита.
:prg02_07.asm — программа на ассемблере для подсчетаколичества слов, начинающихся с определенной строчной буквы:
Вход: ввод с клавиатуры 20 слов (длиной не более 10символов).
Выход: вывод результата подсчета на экран.
buf_Oahstruc
len_bufdb 11; длина bufjn
lenjin db 0 действительная длина введенного слова (без учетаOdh) bufjn db 11 dup (20h) -.буфер для ввода (с учетом Cdh) ends 1 .data
tabdb 26 dup (0) buf buf_0ah
db Odh.Oah,'$'; для вывода функцией 09h (int 21h)
.code
-.вводим слова с клавиатуры
mov ex,20
lea dx.buf
movah.Oah ml: int 21h: анализируем первую букву введенногослова — вычисляем хэш-функцию: А=С*1-97
mov Ы, buf .bufjn sub Ы. 97 inc [bx] loop ml
: выводим результат подсчета на экран push ds popes
xor al ,al
lea di ,buf
mov ex.type bufjah rep stosb; чистим буфер buf
mov ex.26: синвол в buf.buf_1n
lea dx.buf
mcv Ы,97 m2: push bx
mov buf .bufjn.bi: опять вычисляем хэш-функцию:
А»С*1-97 и преобразуем «количество» в символьныйвид
sub Ы. 97
mov al .[bx]
aam
or ax,03030h; в ах длина в символьном виде
mov buf.len in.al —
mov buf.len_buf.ah; теперь выводим:
mov ah, 09h
int 21h pop bx
inc Ы
loop m2
Такимобразом, относительно сложная с первого взгляда задача очень просто реализуетсяс помощью методов хэширования. При этом обеспечивается высокая скоростьвыполнения операций доступа к элементам таблицы. Это обусловлено тем, чтоадреса, по которым располагаются элементы таблицы, являются результатамивычислений простых арифметических функций от содержимого соответствующихключевых слов.
Перечислимобласти, где методы хэширования оказываются особенно эффективными.
· Разработкакомпиляторов, программ обработки текстов, пользовательских интерфейсов и т. п.В частности, компиляторы значительную часть времени обработки исходного текстапрограммы затрачивают на работу с различными таблицами — операций,идентификаторов, констант и т. д. Правильная организация работы компилятора синформацией в этих таблицах означает значительное увеличение скорости создания объектногомодуля, может быть, даже не на один порядок выше. Кстати, другие системныепрограммы — редакторы связей и загрузчики — также активно работают со своимивнутренними таблицами.
· Системыуправления базами данных. Здесь особенный интерес представляют алгоритмывыполнения операций поиска по многим ключам, которые также основаны на методе хеширования.
· Разработкакриптографических систем.
· Поискпо соответствию. Методы хеширования можно применять в системах распознаванияобразов, когда идентификация элемента в таблице осуществляется на основеанализа ряда признаков, сопровождающих объект поиска, а не полного соответствиязаданному ключу. Если рассматривать эту возможность в контексте задачсистемного программирования, то ее можно использовать для исправления ошибокоператоров при вводе информации в виде ключевых слов. Подробная информация опоиске по соответствию приведена в литературе.
Нона практике не все так гладко и оптимистично. Для эффективной и безотказнойработы метода хеширования необходимо очень тщательно подходить как к изучениюзадачи на этапе ее постановки, так и к возможности использования конкретногоалгоритма хеширования в контексте этой задачи. Так, на стадии изученияпостановки задачи, в которой для доступа к табличным данным планируетсяиспользовать хеширование, требуется проводить тщательные исследования понаправлениям: диапазон допустимых ключей, максимальное количество элементов втаблице, вероятность возникновения коллизий и т. д. При этом нужно знать какобщие проблемы метода хеширования, так и частные проблемы конкретных алгоритмовхеширования. Одну из таких проблем рассмотрим на примере задачи.
Пустьнеобходимо подсчитать количество двухсимвольных английских слов в некоторомтексте. В качестве хэш-функции для вычисления адреса можно предложить функциюподсчета суммы двух символов, умноженной на длину элемента таблицы:A=(Cl+C2)*L-97, где А — адрес в таблице, полученный на основе суммы двоичныхзначений символов С1 и С2; L — длина элемента таблицы; 97 — десятичное смещениев кодовой таблице строчного символа «а» английского алфавита. Проведем простыерасчеты. Сумма двоичных значений двух символов 'а' равна 97+97=194, суммадвоичных значений двух символов 'г' равна 122+122=244. Если организоватьхэш-таблицу, как в предыдущем случае, то получится, что в ней должно быть всего50 элементов, чего явно недостаточно. Более того, для сочетаний типа ab и Ьахэш-сумма соответствует одному числовому значению. В случае когда функция хешированиявычисляет одинаковый адрес для двух и более различных объектов, говорят, чтопроизошла коллизия, или конфликт. Исправить положение можно введением допущенийи ограничений, вплоть до замены используемой хэш-функции. Программист можетлибо применить один из известных алгоритмов хеширования (что, по сути, означаетиспользование определенной хэш-функции), либо изобрести свой алгоритм, наиболееточно отображающий специфику конкретной задачи. При этом необходимо понимать,что разработка хэш-функции происходит в два этапа.
1. Выборспособа перевода ключевых слов в числовую форму.
2. Выборалгоритма преобразования числовых значений в набор хеш-адресов.
3. Выборспособа перевода ключевых слов в числовую форму
Всяинформация, вводимая в компьютер, кодируется в соответствии с одной из системкодирования (таблиц кодировки). В большинстве таких систем символы (цифры,буквы, служебные знаки) представляются однобайтовыми двоичными числами. Впоследних версиях Windows (NT, 2000) используется система кодировки Unicode, вкоторой символы представляются в виде двухбайтовых двоичных величин. Какправило, ключевые поля элементов таблиц — строки символов, Наиболее известныеалгоритмы закрытого хеширования основаны на следующих методах:
· деления;
· умножения;
· извлечениябитов;
· квадрата;
· сегментации;
· переходак новому основанию;
· алгебраическогокодирования;
· вычислениизначения CRC (см. соответствующую главу).
Далеемы рассмотрим только первые четыре метода. Остальные методы — сегментации,перехода к новому основанию, алгебраического кодирования — мы рассматривать небудем. Отметим лишь, что их используют либо в случае значительной длиныключевых слов, либо когда ключ состоит из нескольких слов. Информацию об этихметодах можно получить в литературе.
Рассмотрениеметодов хеширования будет произведено на примере одной задачи. Это позволитлучше понять их особенности, преимущества, недостатки и возможные ограничения.
Необходиморазработать программу — фрагмент компилятора, которая собирает информацию обидентификаторах программы. Предположим, что в программе может встретиться неболее М различных имен. Длину возможных имен ограничим восьмью символами. Вкачестве ключа используются символы идентификатора, какие и сколько — будемуточнять для каждого из методов. Элемент таблицы состоит из 10 байт: 1 байтпризнаков, 1 байт для хранения длины идентификатора и 8 байт для хранениясимволов самого идентификатора.
Метод деления
Этотпростой алгоритм закрытого хеширования основан на использовании остатка делениязначения ключа К на число, равное или близкое к числу элементов таблицы М:
А(К) = К mod M
Врезультате деления образуется целый остаток А(К), который и принимается заиндекс блока в таблице. Чтобы получить конечный адрес в памяти, нужнополученный индекс умножить на размер элемента в таблице. Для уменьшенияколлизий необходимо соблюдать ряд условий:
· ЗначениеМ выбирается равным простому числу.
· ЗначениеМ не должно являться степенью основания, по которому производится переводключей в числовую форму. Так, для алфавита, состоящего из первых пятианглийских букв и пробела {a,b,c,d,e,' '} (см. пример выше), основание системыравно 6. Исходя из этого число элементов таблицы М не должно быть степенью 6Р.
Важноотметить случай, когда число элементов таблицы М является степенью основаниямашинной систем счисления (для микропроцессора Intel — это 2). Тогда операцияделения (достаточно медленная) заменяется на несколько операций.
Метод умножения
Дляэтого метода нет ограничений на длину таблицы, свойственных методу деления.Вычисление хэш-адреса происходит в два этапа:
1.Вычисление нормализованного хэш-адреса в интервале [0..1] по формуле:
хеширование адрес алгоритм обработка текстовый

F(K) = (С*К) mod 1,
гдеС — некоторая константа из интервала [0..1], К — результат преобразования ключав его числовое представление, mod 1 означает, что F(K) является дробной частьюпроизведения С*К.
2.Конечный хэш-адрес А(К) вычисляется по формуле А(К) = [M*F(K)], где М — размерхэш-таблицы, а скобки [] означают целую часть результата умножения.
Удобнорассматривать эти две формулы вместе:
А(К) = М*(С*К) mod 1.
Кнутв качестве значения С рекомендует использовать «золотое сечение» — величину,равную ((л/5)-1)/2«0,6180339887. Значение F(K) можно формировать с помощью каккоманд сопроцессора, так и целочисленных команд. Команды сопроцессора вамхорошо известны и трудностей с реализацией формулы (2.4) не возникает. Интереспредставляет реализация вычисления А(К) с помощью целочисленных команд. Правда,в отличие от реализации сопроцессором здесь все же Удобнее ограничитьсяусловием, когда М является степенью 2. Тогда процесс вычисления сиспользованием целочисленных команд выглядит так:
Выполняемпроизведение С*К. Для этого величину «золотого сечения» С~0,6180339887 нужноинтерпретировать как целочисленное значение,
обходимостремиться к тому, чтобы появление 0 и 1 в выделяемых позициях было как можноболее равновероятным. Здесь трудно дать рекомендации, просто нужно провестианализ как можно большего количества возможных ключей, разделив составляющие ихбайты на тетрады. Для формирования хэш-адреса нужно будет взять биты из техтетрад (или полностью тетрады), значения в которых изменялись равномерно.
Метод квадрата
Влитературе часто упоминается метод квадрата как один из первых методовгенерации последовательностей псевдослучайных чисел. При этом он непременноподвергается критике за плохое качество генерируемых последовательностей. Но,как упомянуто выше, для процесса хеширования это не является недостатком. Болеетого, в ряде случаев это наиболее предпочтительный алгоритм вычисления значенияхэш-функции. Суть метода проста: значение ключа возводится в квадрат, послечего берется необходимое количество средних битов результата. Возможны варианты— при различной длине ключа биты берутся с разных позиций. Для принятия решенияоб использовании метода квадрата для вычисления хэш-функции необходимо провестистатистический анализ возможных значений ключей. Если они часто содержатбольшое количество нулевых битов, то это означает, что распределение значенийбитов в средней части квадрата ключа недостаточно равномерно. В этом случаеиспользование метода квадрата неэффективно.
Наэтом мы закончим знакомство с методами хеширования, так как полное обсуждениеэтого вопроса не является предметом книги. Информацию об остальных методах(сегментации, перехода к новому основанию, алгебраического кодирования) можнополучить из различных источников.
Входе реализации хеширования с помощью методов деления и умножения возможныеколлизии мы лишь обозначали без их обработки. Настало время разобраться с этимвопросом.
Обработка коллизий
Дляобработки коллизий используются две группы методов:
· закрытые— в качестве резервных используются ячейки самой хэш-таблицы;
· открытые— для хранения элементов с одинаковыми хэш-адресами используется отдельнаяобласть памяти.
Видно,что эти группы методов разрешения коллизий соответствуют классификацииалгоритмов хеширования — они тоже делятся на открытые и закрытые. Яркий примероткрытых методов — метод цепочек, который сам по себе является самостоятельнымметодом хеширования. Он несложен, и мы рассмотрим его несколько позже.
Закрытыеметоды разрешения коллизий более сложные. Их основная идея — при возникновенииколлизии попытаться отыскать в хэш-таблице свободную ячейку. Процедуру поискасвободной ячейки называют пробитом, или рехешированием (вторичным хешированием).При возникновении коллизии к первоначальному хэш-адресу А(К) добавляетсянекоторое значение р, и вычисляется выражение (2.5). Если новый хэш-адрес А(К)опять вызывает коллизию, то (2.5) вычисляется при р2, и так далее:
А(К) = (A(K)+Pi)mod М (I = 0… М). (2.5)
push ds popes
lea si .buf.len_in
mov cl .buf .lenjn
inccx: длину тоже нужно захватить
add di .lenjd repmovsb
jmp ml displ:: выводим идентификатор, вызвавший коллизию, на экран
рехэширование
; ищем место для идентификатора, вызвавшего коллизию в таблице,путем линейного рехэширования i nc bx mov ax.bx jmp m5
Квадратичное рехеширование
Процедураквадратичного рехеширования предполагает, что процесс поиска резервных ячеекпроизводится с использованием некоторой квадратичной функции, например такой:
Pi= а,2+Ь,+с. (2.6)

Хотязначения а, Ь, с можно задавать любыми, велика вероятность быстрогозацикливания значений р(. Поэтому в качестве рекомендации опишем один извариантов реализации процедуры квадратичного рехеширования, позволяющийосуществить перебор всех элементов хэш-таблицы [32]. Для этого значения вформуле (2.6) положим равными: а=1, Ь = с = 0. Размер таблицы желательнозадавать равным простому числу, которое определяется формулой М = 4п+3, где п —целое число. Для вычисления значений р> используют одно из соотношений:
pi = (K+i2)modM. (2.7) Pi = [M+2K-(K+i2)modM]modM. (2.8)
гдеi = 1, 2, ..., (M-l)/2; К — первоначально вычисленный хэш-адрес.
Адреса,формируемые с использованием формулы (2.7), покрывают половину хэш-таблицы, аадреса, формируемые с использованием формулы (2.8), — вторую половину.Практически реализовать данный метод можно следующей процедурой.
1. ЗаданиеI = -М.
2. Вычислениехэш-адреса К одним из методов хэширования.
3. Еслиячейка свободна или ключ элемента в ней совпадает с искомым ключом, тозавершение процесса поиска. Иначе, 1:=1+1.
4. Вычислениеh := (h+|i|)modM.
5. ЕслиI М), таблица полностьюзаполнена.
Программата же, что приведена в методе линейного рехеширования, за исключениемдобавления одной команды для инициализации процесса рехеширования, самогофрагмента рехеширования и небольших изменений сегмента данных. могут являтьсяметоды, основанные на деревьях поиска, и т. п. Наибольший эффект от хеширования— при поиске по заданным идентификаторам или дескрипторам, что характерно длязадач баз данных, обработки документов и т. д. Для задач, в которых поискведется сравнением или вычислением сложных логических функций, лучшеиспользовать традиционные методы сортировки и поиска. Для того, чтобы совершитьплавный переход к рассмотрению следующей структуры данных — спискам, вернемсяеще раз к одной проблеме, связанной с массивами. Упоминалось, что средимассивов можно выделить массивы специального вида, которые называютразреженными. В этих массивах большинство элементов равны нулю. Отводить местодля хранения всех элементов расточительно. Естественно, возникает желаниесэкономить. Что для этого можно предпринять?
Техникаобработки массивов предполагает, что все элементы расположены в соседнихячейках памяти. Для ряда приложений это недопустимое ограничение.
Обобщенноможно сказать, что все перечисленные выше структуры имеют общие свойства:
· постоянствоструктуры данных на всем протяжении ее существования;
· памятьдля хранения отводится сразу всем элементам структуры и все элементы находятсяв смежных ячейках памяти;
· отношениямежду элементами просты настолько, что можно исключить потребность в средстваххранения информации об их отношениях в какой бы то ни было форме.
Исходя изэтих свойств, данные структуры данных и называют статическими. Снять подобныеограничения можно, используя другой тип данных — списки. Для них подобныхограничений не существует.
Преобразование ключей
Наиболеечасто встречается операция поиска записи по идентифицирующему его полю — ключу.Поэтому файл, как правило, индексируется по ключевому полю. Поиск по ключу вобщем виде может рассматриваться как преобразование значения ключевого поля вадрес записи в файле (или номер записи), то есть как функция вида f(key) ->m.
Очевидно,можно сформулировать обратную задачу: если некоторым образом подобрать функциюf(), то ее можно использовать для определения места в файле, куда следуетпоместить запись с ключом key. Основное требование к такой функции: она должнакак можно более равномерно распределять записи с различными значениями ключа пофайлу, то есть иметь «случайный» вид. Кроме того, необходимо каким-тообразом решить проблему «коллизий», то есть попадания несколькихзаписей с различными ключами в один физический адрес (номер записи).
Функция f()называется распределяющей или рассеивающей функцией. Пример одной из такихфункций: берется квадрат значения ключа, из него извлекаются n значащих цифр изсередины, которые и дают значение номера записи в файле:
intPlace1024(key) // Функция рассеивания для файла из
 unsignedkey; // 1024 записей и 16 разрядного
 { // ключа
 unsigned longn,n1;
intm;
n= (unsigned long)key * key;
for (m=0, n1= n; n1 !=0; m++, n1 >>= 1); // Подсчет количества значащих
if(m
m = (m — 10)/ 2; // m — количество битов по краям
return( (n>> m) & 0x3FF);
}
Известны дваспособа решения проблемы коллизий. В первом случае файл содержит областьпереполнения. Если функция f() вычисляет адрес записи в файле, асоответствующее место уже заполнено записью с другим значением ключа, то новаязапись помещается в область переполнения. При этом возможны два варианта:
— записи вобласти переполнения не связаны между собой, и для поиска в ней используетсяпоследовательный просмотр всех записей;
— в областипереполнения организуются списки записей, участвующих в коллизии: то естьзапись в основной области является заголовком списка записей в областипереполнения, куда попадают все записи, вступающие в коллизию.
В другомслучае запись, вступившая в коллизию, помещается в некоторое свободное местофайла, начиная от текущей занятой позиции. Возможные варианты поиска:
— перваясвободная позиция, начиная от текущей;
— проверяютсяпозиции, пропорциональные квадрату шага относительно текущей занятой, то есть m= ( f(key) + i * i ) mod n, где i — номер шага, n — размер таблицы. Такоеразмещение позволяет лучше «рассеивать» записи при коллизии.
/>/>Рассматриваемый метод обозначается терминами расстановкаили хеширование(от hash — смешивать, перемалывать).
Одним изсущественных недостатков метода является необходимость заранее резервироватьфайл для размещения записей с номерами от 0 до m — в диапазоне возможныхзначений функции рассеивания. Кроме того, при заполнении файла увеличиваетсяколичество коллизий и эффективность метода падает. Если же количество записейвозрастает настолько, что файл необходимо расширять, то это связано сизменением функции рассеивания и перераспределением (перезаписью) уже имеющихсязаписей в соответствии с новой функцией.

/>

ГЛАВА 2. ПРАКТИЧЕСКАЯЧАСТЬ
 
2.1. Вставка элемента в в-дерево
Рассмотрим структуру узла B-дерева.
В каждом узле мы будем хранить не болееNumberOfItems записей. Также нам надо будет хранить текущее количество записейв узле. Для удобства возврата назад к корню дерева будем запоминать для каждогоузла указатель на его узел-предок.
Type
PBTreeNode = ^TBTreeNode;
TBTreeNode = record {узел дерева}
Count: Integer;
PreviousNode: PBTreeNode;
Items: array[0..NumberOfItems+1] of record
Value: ItemType;
NextNode: PBTreeNode;
end;
end;
/>
У элемента Items[0] будет использоваться толькополе NextNode. Дополнительный элемент Items[NumberOfItems+1] предназначен дляобработки переполнения, о чем будет рассказано ниже, где будет обсуждатьсяалгоритм добавления элемента в B-дерево.
Поскольку дерево упорядочено, тоItems[1].Value
Само дерево можно задать просто указаниемкорневой вершины. Естественно, что у такой вершины PreviousNode будет равенnil.
Type
TBTree = TBTreeNode;
Прежде чем рассматривать алгоритмы, соберемвоедино все требования к B-дереву:
1. каждыйузел имеет не более NumberOfItems сыновей;
2. каждыйузел, кроме корня, имеет не менее NumberOfItems/2 сыновей;
3. корень,если он не лист, имеет не менее 2-х сыновей;
4. вселистья расположены на одном уровне (дерево сбалансировано);
5. нелистовойузел с k сыновьями содержит не менее k-1 ключ.
Из всего вышесказанного можно сразусформулировать алгоритм поиска элемента в B-дереве.
Поиск элемента в B-дереве
Поиск будем начинать с корневого узла. Еслиискомый элемент присутствует в загруженной странице поиска, то завершаем поискс положительным ответом, иначе загружаем следующую страницу поиска, и так дотех пор, когда либо найдем искомый элемент, либо не окажется «следующейстраницы поиска» (пришли в лист B-дерева).
Посмотрим на примере, как это будет работать.Пусть мы имеем такое дерево (в наших примерах мы будем разбирать небольшиедеревья, хотя в реальности B-деревья применяются при работе с большимимассивами информации):
/>
Будем искать элемент 11. Сначала загрузимкорневой узел. Эта страница поиска содержит элементы 5 и 13. Наш искомыйэлемент больше 5, но меньше 13. Значит, идем по ссылке, идущей от элемента 5.Загружаем следующую страницу поиска (с элементами 8 и 10). Эта страница тоже несодержит искомого элемента. Замечаем, что 11 больше 10 – следовательно,двигаемся по ссылке, идущей от элемента 10. Загружаем соответствующую страницупоиска (с элементами 11 и 12), в которой и находим искомый элемент. Итак, вэтом примере, чтобы найти элемент, нам понадобилось три раза обратиться квнешней памяти для чтения очередной страницы.
Если бы в нашем примере мы искали, допустим,элемент 18, то, просмотрев 3 страницы поиска (последней была бы страница сэлементом 17), мы бы обнаружили, что от элемента 17 нет ссылки на поддерево сэлементами большими 17, и пришли бы к выводу, что элемента 18 в дереве нет.
Теперь точно сформулируем алгоритм поискаэлемента Item в B-дереве, предположив, что дерево хранится в переменной BTree,а функция LookFor возвращает номер первого большего или равного элемента узла(фактически производит поиск в узле).
function BTree.Exist(Item: ItemType):Boolean;
Var
CurrentNode: PBTreeNode;
Position: Integer;
begin
Exist := False;
CurrentNode := @BTree;
Repeat
Position := LookFor(CurrentNode, Item);
if (CurrentNode.Count>=Position)and
(CurrentNode.Items[Position].Value=Item)then
begin
Exist := True;
Exit;
end;
ifCurrentNode.Items[Position-1].NextNode=nil then
Break
else
CurrentNode := CurrentNode.Items[Position-1].NextNode;
until False;
end;
Здесь мы пользуемся тем, что, если ключ лежитмежду Items[i].Value и Items[i+1].Value, то во внутреннюю память надо подкачатьстраницу поиска, на которую указывает Items[i].NextNode.
Заметим, что для ускорения поиска ключа внутристраницы поиска (функция LookFor), можно воспользоваться дихотомическимпоиском, который описан ранее в главе, где разбирались способы хранениямножества элементов в последовательном массиве.
Учитывая то, что время обработки страницы поискаесть величина постоянная, пропорциональная размеру страницы, сложностьалгоритма поиска в B-дереве будет T(h), где h – глубина дерева.
Добавление элемента в B-дерево
Для того чтобы наше дерево можно было считатьэффективной структурой данных для хранения множества значений, необходимо,чтобы каждый узел заполнился хотя бы наполовину. Дерево строится снизу. Этоозначает, что любой новый элемент добавляется в листовой узел. Если при этомпроизойдет переполнение (на этот случай в каждом узле зарезервирован лишний элемент),то есть число элементов в узле превысит NumberOfItems, то надо будет разделитьузел на два узла, и вынести средний элемент на верхний уровень. Можетслучиться, что при этой операции на верхнем уровне тоже получится переполнение,что вызовет еще одно деление. В худшем случае эта волна докатится до корнядерева.
В общем виде алгоритм добавления элемента Item вB-дерево можно описать следующей последовательностью действий:
1. Поисклистового узла Node, в который следует произвести добавление элемента Item.
2. Добавлениеэлемента Item в узел Node.
3. ЕслиNode содержит больше, чем NumberOfItems элементов (произошло переполнение), то
o делимNode на две части, не включая в них средний элемент;
o Item=среднийэлемент Node;
o Node=Node.PreviousNode;
o Переходимк пункту 2.
Заметим, что при обработке переполнения надоотдельно обработать случай, когда Node – корень, так как в этом случаеNode.PreviousNode=nil.
Посмотрим, как это будет работать, на примере.
Возьмем нарисованное ниже дерево и добавим в негоэлемент 13.
/>

Двигаясь от корня, найдем узел, в который следуетдобавить искомый элемент. Таким узлом в нашем случае окажется узел, содержащийэлементы 11 и 12. Добавим. В результате наше дерево примет такой вид:
/>
Понятно, что мы получили переполнение. При егообработке узел, содержащий элементы 11, 12 и 13 разделится на две части: узел сэлементом 11 и узел с элементом 13, – а средний элемент 12 будет вынесен на верхнийуровень. Дерево примет такой вид:
/>
Мы опять получили переполнение, при обработкекоторого узел, содержащий элементы 8, 10 и 12 разделится на два узла: узел сэлементом 8 и узел с элементом 12, – а средний элемент 10 будет вынесен наверхний уровень. И теперь дерево примет такой вид:
/>
Теперь мы получили переполнение в корне дерева.Как мы оговаривали ранее этот случай надо обработать отдельно. Это связано с тем,что здесь мы должны будем создать новый корень, в который во время делениябудет вынесен средний элемент:
/>
Теперь полученное дерево не имеет переполнения.
В этом случае, как и при поиске, время обработкистраницы поиска есть величина постоянная, пропорциональная размеру страницы, азначит, сложность алгоритма добавления в B-дерево будет также T(h), где h –глубина дерева.
Итак, как мы заметили с самого начала, уB-деревьев есть своя сфера применения: хранение настолько больших массивовинформации, что их невозможно целиком разместить в выделяемой оперативнойпамяти, но требуется обеспечить быстрый доступ к ним.
В таких случаях B-деревья являются хорошимсредством программно ускорить доступ к данным.
Ярким примером практического примененияB-деревьев является файловая система NTFS, где B-деревья применяются дляускорения поиска имен в каталогах. Если сравнить скорость поиска в этойфайловой системе и в обычной FAT на примере поиска на жестком диске большогообъема или в каталоге, содержащем очень много файлов, то можно будетконстатировать превосходство NTFS. А ведь поиск файла в каталоге всегдапредшествует запуску программы или открытию документа.
B-деревья обладают прекрасным качеством: во всехтрех операциях над данными (поиск/удаление/добавление) они обеспечиваютсложность порядка T(h), где h – глубина дерева. Это значит, что чем большеузлов в дереве и чем сильнее дерево ветвится, тем меньшую часть узлов надобудет просмотреть, чтобы найти нужный элемент. Попробуем оценить T(h).
Число элементов в узле есть величинавероятностная с постоянным математическим ожиданием MK. Математическоеожидание числа узлов равно:
/>,
где n – число элементов, хранимых в B-дереве. Этодает сложность T(h)=T(log(n)), а это очень хороший результат.
Поскольку узлы могут заполняться не полностью(иметь менее NumberOfItems элементов), то можно говорить о коэффициентеиспользования памяти. Эндрю Яо доказал, что среднее число узлов после случайныхвставок при больших n и NumberOfItems составит N/(m*ln(2))+F(n/m2), так чтопамять будет использоваться в среднем на ln(2)*100%.
В отличие от сбалансированных деревьев B-деревьярастут не вниз, а вверх. Поэтому (и из-за разной структуры узлов) алгоритмывключения/удаления принципиально различны, хотя цель их в обоих случаях одна –поддерживать сбалансированность дерева.
Идея внешнего поиска с использованием техникиB-деревьев была предложена в 1970 году Р.Бэйером и Э.Мак-Крэйтом и независимоот них примерно в то же время М.Кауфманом. Естественно, что за это время былопредложено ряд усовершенствований B-деревьев, связанных с увеличениемкоэффициента использования памяти и уменьшением общего количества расщеплений.
Одно из таких усовершенствований было предложеноР.Бэйером и Э.Мак-Крэйтом и заключалось в следующем. Если узел деревапереполнен, то прежде чем расщеплять этот узел, следует посмотреть, нельзя ли«перелить» часть элементов соседям слева и справа. При использовании такойметодики уменьшается общее количество расщеплений и увеличивается коэффициентиспользования памяти.
program PTree;
{$APPTYPE CONSOLE}
type
TInfo = Byte;
PItem = ^Item;
Item = record
Key: TInfo;
Left, Right: PItem;
end;
TTree = class
private
Root: PItem;
public
constructor Create;
procedure Add(Key: TInfo);
procedure Del(Key: TInfo);
procedure View;
procedure Exist(Key: TInfo);
destructor Destroy; override;
end;
//---------------------------------------------------------
constructor TTree.Create;
begin
Root := nil;
end;
//---------------------------------------------------------
procedure TTree.Add(Key: TInfo);
procedure IniTree(var P: PItem; X: TInfo); //создание корня дерева
begin
New(P);
P^.Key :=X;
P^.Left := nil;
P^.Right := nil;
end;
procedure InLeft (var P: PItem; X: TInfo); //добавление узла слева
var R: PItem;
begin
New(R);
R^.Key := X;
R^.Left := nil;
R^.Right := nil;
P^.Left := R;
end;
procedure InRight (var P: PItem; X: TInfo); //добавить узел справа
var R: PItem;
begin
New(R);
R^.Key := X;
R^.Left := nil;
R^.Right := nil;
P^.Right := R;
end;
procedure Tree_Add (P: PItem; X: TInfo);
var OK: Boolean;
begin
OK := false;
while not OK do begin
if X > P^.Key then //посмотреть направо
if P^.Right nil //правый узел не nil
then P := P^.Right //обход справа
else begin //правый узел — лист и надо добавить к нему элемент
InRight (P, X); //и конец
OK := true;
end
else //посмотреть налево
if P^.Left nil //левый узел не nil
then P := P^.Left //обход слева
else begin //левый узел -лист и надо добавить к нему элемент
InLeft(P, X); //и конец
OK := true
end;
end; //цикла while
end;
begin
if Root = nil
then IniTree(Root, Key)
else Tree_Add(Root, Key);
end;
//-------------------------------------------------------------
procedure TTree.Del(Key: TInfo);
procedure Delete (var P: PItem; X: TInfo);
var Q: PItem;
procedure Del(var R: PItem);
//процедура удаляет узел имеющий двух потомков, заменяя его на самый правый
//узел левого поддерева
begin
if R^.Right nil then //обойти дерево справа
Del(R^.Right)
else begin
//дошли до самого правого узла
//заменить этим узлом удаляемыйQ^.Key := R^.Key;
Q := R;
R := R^.Left;
end;
end; //Del
begin //Delete
if P nil then //искать удаляемый узел
if X
Delete(P^.Left, X)
else
if X > P^.Key then
Delete(P^.Right, X)
 //искать в правом поддереве
else begin
//узел найден, надо его удалить
//сохранить ссылку на удаленный узел
Q := P;
if Q^.Right = nil then
//справа nil
//и ссылку на узел надо заменить ссылкой на этого потомка
P := Q^.Left
else
if Q^.Left = nil then
//слева nil
//и ссылку на узел надо заменить ссылкой на этого потомка
P := P^.Right
else //узел имеет двух потомков
Del(Q^.Left);
Dispose(Q);
end
else
WriteLn('Такого элемента в дереве нет');
end;
begin
Delete(Root, Key);
end;
//-------------------------------------------------------------
procedure TTree.View;
procedure PrintTree(R: PItem; L: Byte);
var i: Byte;
begin
if R nil then begin
PrintTree(R^.Right, L + 3);
for i := 1 to L do
Write(' ');
WriteLn(R^.Key);
PrintTree(R^.Left, L + 3);
end;
end;
begin
PrintTree (Root, 1);
end;
//-------------------------------------------------------------
procedure TTree.Exist(Key: TInfo);
procedure Search(var P: PItem; X: TInfo);
begin
if P = nil then begin
WriteLn('Такого элемента нет');
end else
if X > P^. Key then //ищется в правом поддереве
Search (P^. Right, X)
else
if X
Search (P^. Left, X)
else
WriteLn('Есть такой элемент');
end;
begin
Search(Root, Key);
end;
//-------------------------------------------------------------
destructor TTree.Destroy;
procedure Node_Dispose(P: PItem);
//Удаление узла и всех его потомков в дереве
begin
if P nil then begin
if P^.Left nil then
Node_Dispose (P^.Left);
if P^.Right nil then
Node_Dispose (P^.Right);
Dispose(P);
end;
end;
begin
Node_Dispose(Root);
end;
//-------------------------------------------------------------
procedure InputKey(S: String; var Key: TInfo);
begin
WriteLn(S);
ReadLn(Key);
end;
var
Tree: TTree;
N: Byte;
Key: TInfo;
begin
Tree := TTree.Create;
repeat
WriteLn('1-Добавить элемент в дерево');
WriteLn('2-Вывести узлы дерева');
WriteLn('3-Проверить существование узла');
WriteLn('4-Выход');
ReadLn(n);
with Tree do begin
case N of
1: begin
InputKey('Введите значение добавляемого элемента', Key);
Add(Key);
end;
2: View;
3: begin
InputKey('Введите элемент, существование которого вы хотите проверить', Key);
Exist(Key);
end;
end;
end;
until N=4;
Tree.Destroy;
end.
2.2 ОБРАБОТКА ТЕКСТОВЫХ ФАЙЛОВ
Разработатьблок-схему алгоритма и составить программу обработки текстовых данных,хранящихся в произвольном файле на магнитном диске. Вид обработки данных:подсчитать количество слов, которые содержат определённое количество согласных.Привожу исходный текст программы:Program file;uses crt;labelfin;Const mn=['б','в','д','ж','з','к','л','м','н','п','р','с','т','ф','х','ц','ч','ш','щ'];Var f3:text;i,j,ch,sl:integer;name:string;s:char;wrd :string;dbase:string;BeginclrScr;writeln('vvedite imya faila');readln(name);assign(f3,name);reset(f3);s:=' ';sl:=0;ch:=0;while not eof(f3) dobeginreadln(f3,wrd);i:=1;While i' ' then sl:=sl+1;while (wrd[i]' ') and(i 0then begin{$I-}rewrite(f3);{$I+}if IOResult 0thenbeginwriteln('ERROR!');goto fin;end;end;write(f3,' kol-vo slov --',sl,' kol-vosoglasnih --',ch,'');writeln('chislo slov: ',sl,' chisosoglasnih: ',ch);close(f3);fin:readkey;End.

Приложениек выполненным программам
 
1. Обработкатекстовых файлов
¦ Ввод данных¦
¦ Запись вфайл ¦
¦ Считываниефайла ¦
¦ Обработкаданных ¦
¦ Выводрезультата ¦
+------ Выход------+
Вводданных:Я хочу есть и спать, ещё я бы поиграл в комп.Запись в файлTEXT.pas
Выводрезультата:chislo slov: 11 chiso soglasnih: 17Содержание выходного файла DEN.txt:kol-vo slov --11 kol-vo soglasnih --172. Вставка элемента в В-дерево1-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa331-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa221-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa441-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa111-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod2443322111-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod
ЗАКЛЮЧЕНИЕБыла выполнена курсовая работа по предмету«Структуры и алгоритмы компьютерной обработки данных» на тему «Алгоритмыпреобразования ключей (расстановка)». В данной курсовой работе рассмотренытеоретические вопросы и выполнены практические задания, которые соответствуютвыданному заданию.В данной курсовой работе можно выделить 3основных части, которые соответствуют следующим статусам:1. Теоретическая часть;2. Теоретическая + практическая часть;3. Практическая часть;В курсовой представлена вся необходимаяинформация по данной курсовой, использована как научная литература, так ивозможности всемирной сети Internet. Выполненыпрактические задания, и использованием знаний и умений программировать наалгоритмических языках высокого уровня Turbo Pascal, Borland Delphi.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Hellerman H. DigitalComputer System Principles. McGraw-Hill, 1967.
2. Ершов А.П. Избранныетруды. Новосибирск: ВО «Наука», 1994.
3. Кнут Д. Искусствопрограммирования, т.3. М.: Вильямс, 2000.
4. Peterson W.W.Addressing for Random-Access Storage // IBM Journal of Research andDevelopment. 1957. V.1, N2. Р.130—146.
5. Morris R. ScatterStorage Techniques // Communications of the ACM, 1968. V.11, N1. Р.38—44.
6. Ахо А., Хопкрофт Дж.,Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2000.
7. Чмора А. Современнаяприкладная криптография. М.: Гелиос АРВ, 2001.
8. Кормен Т., ЛейзерсонЧ., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
9. Вирт Н. Алгоритмы +структуры данных = программы. М.: Мир, 1985.
10. Керниган Б., Пайк Р.Практика программирования. СПб.: Невский диалект, 2001.
11. Шень А.Программирование: теоремы и задачи. М.: МЦНМО, 1995.