Методы представления данных в памяти ЭВМ при программировании по Р-технологии тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ВОПРОСЫ ЭФФЕКТИВНОГО ПРЕДСТАВЛЕНИЯ СТРУКТУР

ДАННЫХ

§ I. Совместное размещение в памяти ЭВМ структур данных

§ 2. Структуры со многими функциями доступа.

§ 3. Организация памяти Р-машины

ГЛАВА П. МЕТОД СОВМЕСТНОГО ПРЕДСТАВЛЕНИЯ СОВОКУПНОСТИ

ХЕШ-ТАБЛИЦ (ТАБЛИЧНАЯ ПАМЯТЬ)

§ I. Исследование основных характеристик - среднего числа проб при удачном и неудачном поисках

§ 2. Сравнение характеристик табличной памяти и изолированно организованных таблиц

§ 3. Особенности табличной памяти

§ 4. Алгоритм динамического расширения хеш-таблиц

ГЛАВА Ш. РАЗВИТИЕ И ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ

ПРЕДСТАВЛЕНИЯ ДАННЫХ.

§ I. Способ построения быстрой стековой таблицы

§ 2. Организация двухуровневой страничной табличной памяти

§ 3. Опыт использования разработанных методов в автоматизированной системе производства программ реального времени

В настоящее время рост производительности труда программистов неразрывно связан с использованием технологии программирования, эффективность которой во многом определяется принятой в ней организацией данных. В этом плане В.М.Глушков отмечал [зо что новая технология программирования в отличие от техники традиционного программирования, уделявшей основное внимание собственно программам, а не данным, должна отводить организации последних очень большое, а часто решающее значение. При этом в круг ее вопросов необходимо включать разработку базовых структур данных ССД) и базовых операторов над ними, что связано с задачей стандартизации как СД, так и их машинного представления в различных типах ЭВМ [l5, 33, 7б].

Одна из главных проблем, которая возникает в процессе разработки СД, их эффективных представлений и способов обработки, заключается в том, чтобы рационально использовать память для хранения данных, обеспечивая при этом высокую скорость доступа к ним. Наряду с успехами, достигнутыми с помощью последовательного и связного представлений, существенный сдвиг в разрешении этой проблемы произошел благодаря открытию хеш-адресации, большой вклад в развитие которой внесли JI.H. Королев [55], А.П.Ершов [44], Р. Моррис [125], Д.Кнут [52] и ряд других авторов. Основным достоинством хеш-адресации является то, что при ее использовании среднее время поиска нужной информации не зависит от общего ее объема. Однако, позволяя значительно ускорить процесс доступа к данным, известные методы хеш-адресации обладают недостатком, обусловленным необходимостью статического задания области, по которой ведется хеширование. В то же время для решения сложных системных и прикладных задач необходимо более гибкое управление памятью, что вызывает потребность в усовершенствовании этих методов.

Названные проблемы определяют важность и актуальность исследований, проводимых в тесной связи с достижениями передовых технологий программирования и направленных на развитие методов организации данных и в первую очередь методов, использующих хеш-адресацию. Поэтому предмет диссертационной работы составляет разработка и анализ новых методов представления СД, в большей своей части основанных на технике хеширования. Прообразом исследуемых СД послужили структуры, явработанной под руководством В.М.Глушкова и И.В.Вельбицкого и получившей широкое распространение в нашей стране.

Задачами работы является усовершенствование известных и создание новых методов представления СД переменной длины в целях обеспечения высокой скорости доступа к их содержимому при одновременном рациональном использовании памяти машины.

Методологическую основу работы составляет обобщение опыта практических разработок автора и их анализа, который проводатся с привлечением математического аппарата теории функций и теории вероятностей и опирается на достижения в области хеш-адресации и Р-технологии программирования. ляющиеся базовыми в Р-технологии программирования

Научная новизна результатов заключается в разработке метода совместного представления в памяти ЭВМ совокупности хеш-таблиц, размеры которых заранее не известны. На основе полученных аналитических оценок и экспериментальных данных проведено обоснование преимуществ этого метода по сравнению с традиционным изолированным представлением аналогичных таблиц. Предложен и проанализирован алгоритм организации хеш-таблицы, дотекающий ее динамическое расширение в несколько раз, изложена его модификация для работы с несколькими таблицами. Рассмотрены три схемы отображения хеш-таблиц в двухуровневую страничную память, расширение которой осуществляется динамически.

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

Предложен способ совмещения нескольких видов СД в некотором новом виде, сочетающем в себе функциональные возможности составляющих структур. Такой способ позволяет упростить технологию работы с СД, уменьшить число пересылок данных между различными участками памяти ЭВМ и устранить дублирование информации. Рассмотрено взаимодействие данного способа с методом совместного представления хеш-таблиц применительно к пы обработки информации в Р-технологии.

Все результаты диссертации имеют практическую направленность и могут быть рекомендованы для построения трансляторов, загрузчиков, ИПС, СУЩ и других систем, в которых первостепенными являются вопросы эффективности и технологичности обработки данных. Программные средства, поддерживающие алорганизации памяти Р-машины которой отражены принци горитмы, предложенные в работе, реализованы в инструментальных комплексах РТК [25, 54] на машинах БЭСМ-6 и СМ-4. Использование этих средств сократило в 1.5 - 2 раза сроки разработки автоматизированных систем производства программ СИНТЕРМ-4 и СИНТЕРМ-СМ [2], а в дальнейшем существенно ускорило процесс их функционирования. Годовой экономический эффект от внедрения результатов диссертационной работы в систему СИНТЕРМ-4 составляет 207475 рублей.

Диссертация состоит из трех глав.

В первой главе анализируются основные подходы, используемые для совместного представления в памяти ЭВМ множества СД, размеры которых заранее не известны. Особое внимание уделяется структурам, в основу представления которых положены хеш-механизмы, а также сложным СД, для обработки содержимого которых используются функции доступа, присущие нескольким простым структурам.

После обзорной части излагается предлагаемый в диссертации подход к организации памяти Р-машины, базирующийся на методах совместного представления СД и совмещения их функциональных возможностей. Определяются три вида памяти Р-машины - регистровая, вагонная и табличная. Строится программная модель наиболее мощной из них - табличной памяти (ТП), реализуемой с помощью некоторого нового метода совместного представления в памяти ЭВМ произвольной совокупности хеш-таблиц. При этом размеры таблиц не оговариваются, а работа с ними осуществляется таким образом, что переполнение может возникнуть лишь когда суммарное заполнение всех таблиц превысит размер отведенной для них памяти. В таком случае оптимизируется объем памяти, необходимый для размещения всех таблиц, а технология работы с ними становится простой и удобной. Вводятся базовые операторы над ТП, специфика которых состоит в том, что для работы с содержимым таблиц используется регистровая память. Тем самым все операции, определенные над регистровой памятью, становятся доступными для ТП. Дальнейшее обобщение рассмотренных принципов отражается в построении так называемой РТВ-памяти, сочетающей в себе свойства табличной, вагонной и регистровой памятей.

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

В третьей главе рассматриваются вопросы, которые примыкают к проблеме эффективного использования алгоритмов хеш-адресации и находятся в тесной связи с методами организации памяти, предложенными в предыдущих разделах диссертации. Разработан новый способ построения стековой таблицы символов [35], необходимой для функционирования однопроходного компилятора с языка, имеющего структуру вложенных блоков и процедур. Описывается и анализируется алгоритм работы с такой таблицей. В зависимости от условий обработки данных вводятся и исследуются три схемы отображения хеш-таблиц в двухуровневую страничную память, расширение которой осуществляется динамически. Приводятся количественные характеристики, полученные в ходе длительного использования такой организации таблиц. Анализируется опыт применения программных средств поддержки методов и алгоритмов, изложенных в диссертации, в процессе разработки и эксплуатации автоматизированных систем производства программ СИНТЕРМ.

В заключении формулируются основные результаты диссертационной работы.

Автор глубоко признателен научному руководителю доктору физико-математических наук И.В. Вельбицкому за постоянное внимание и поддержку диссертационной работы. Автор также приносит свою благодарность кандидату технических наук Л.И. Шолмову за помощь при проведении работ и полезные обсуждения.

Выводы из этого утверждения аналогичны выводам, сделанным после утверждения 2, но только в смысле скорости удачного поиска.

Полученные результаты показывают, что ТП наиболее эффективна в ситуациях, постоянное возникновение которых собственно и вызвало необходимость разработки ТП, а именно: когда таблицы заполняются неравномерно - одни близки к насыщению, а другие пустуют ( в табл. 2.2 приведен пример того, как варьируются величины &'и в зависимости от распределения ключей между таблицами, в то время как С' и О остаются неизменными). Более того, при изолированной организации такая неравномерность чаще всего приводит к переполнению одной из таблиц при наличии свободного места в других, что невозможно в ТП.

ЗАКЛЮЧЕНИЕ

В диссертации получены следующие основные результаты:

1. Разработан метод совместного размещения в памяти ЭВМ совокупности хеш-таблиц, не требующий знания размеров каждой таблицы. Проведены разносторонние исследования, определяющие степень его эффективности в сравнении с традиционным изолированным представлением хеш-таблиц. Метод распространен на двухуровневую страничную память.

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

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

4. Программные средства поддержки методов и алгоритмов, изложенных в диссертационной работе, реализованы в технологических комплексах РТК на машинах БЭСМ-6 и СМ-4 и внедрены в эксплуатацию при разработке семейства автоматизированных систем производства программ для специализированных управляющих машин реального времени. Подтвержденный экономический эффект от внедрения составляет 207475 рублей в год.

Основное содержание диссертации отражено в публикациях [23, 24, 68 - 72].

1. Автоматизированная система производства программ СИНТЕРМ-2 / Айзенберг Я.Е., Вельбицкий И.В., Каюров В.Ю., Кирсанов В.Ф., Конорев Б.М., Рублевская Н.В., Тараненко А.А. - В кн.: Технология программирования. Киев: ИК АН УССР, 1981, с. 57-64.

2. Айзенберг Я.Е., Вельбицкий И.В., Конорев Б.М., Стогний А.А. Автоматизированная система производства программ СИНТЕРМ. -УСиМ, 1980, № 4, с. 16-21.

3. Алгол 68. Методы реализации / Под ред. Г.С.Цейтина. Ленинград: ЛГУ, 1976. - 224 с.

4. Андон Ф.И., Башинский Н.А. Об одном подходе к уменьшению времени поиска информации. Кибернетика, 1978, № I, с. 126131.

5. Андон Ф.И. и др. Основные положения системы управления базами данных ОКА. УСиМ, 1977, № 2, с. 32-35.

6. Архангельский Б.В., Никитин А.И. Системы оптимизации программ. Киев: Техника, 1983. 167 с.

7. Астахов А.Д. Организация эффективного доступа на основе хеширования. Программирование, 1980, № 3, с. 28-33.

8. Бабаян Б.А., Сахин ГО.Х. Система "Эльбрус". Программирование, 1980, № 6, с. 72-86.

9. Баяковский Ю.М., Вьюкова Н.И., Галатенко В.А., Ходулев А.Б. Некоторые особенности реализации языка РОР-2. М., 1975. -18 е.- (Препринт / ИПМ АН СССР; № 92).

10. Берестовая С.Н., Крилюк Н.И., Пашковец Н.Д. ПОСПЛ пакет программ, обрабатывающий списковые структуры. - Кибернетика, 1980, № 2, с. 42-46.

11. Берестовая С.Н., Перевозчикова О.Л., Романов В.М., Ющенко Е.Л. Конструирование систем программирования обработки данных. М.: Статистика, 1979. - £69 с.

12. Беркович С.Я., Кочин Ю.Я., Хребтов Ю.Н. Принципы организации виртуальной памяти ассоциативного типа. Программирование, 1976, № 6, с. 51-60.

13. Брябрин В.М. Универсальная семантическая память в системе ЛОРД. В кн.: Обработка символьной информации. М.: ВЦ

14. АН СССР, 1975, вып. 2, с. 5-21.

15. Бублик В.В., Гороховский С.С., Летичевский А.А., Щеголева Н.Н. Реализация базовых структур данных. В кн.: Авто-» матизация проектирования ЭВМ и их компонентов. Киев: ИК АН УССР, 1977, с. 29-45.

16. Бублик В.В., Дорошенко А.Е., Кривой С.Л., Лябах В.Ф. Интерактивная обработка структур данных. Кибернетика, 1978, № 5, с. 13-18.

17. Вельбицкий И.В. Безбумажная технология программирования в диалоговой среде. УСиМ, 1982, № 6, с. 29-37.

18. Вельбицкий И.В. Метаязык для формального задания семантики языков программирования. В кн.: Тр. Всесоюз. симпоз. по методам реализации новых алгоритм, языков (Новосибирск, 1975). Новосибирск: ВЦ СО АН СССР, 1975, ч. I, с. I6I-I82.

19. Вельбицкий И.В. Метаязык Р-грамматик. Кибернетика, 1973, № 3, с. 47-63.

20. Вельбицкий И.В. Метод обработки дискретной информации на базе одного способа формального задания синтаксиса и семантики языка: Дис. . докт. физ.-мат. наук. Киев, 1977. - 399 с.

21. Вельбицкий И.В., Ковалев А.Д. Метасистема СТЭЛЗ. Принципы эволюционного развития языков программирования. УСиМ, 1980, № I, с. 56-60.

22. Вельбицкий И.В., Медведева В.Н., Михайлова Г.А. Мульти-стековое запоминающее устройство. В кн.: Автоматизация программирования. Киев: ИК АН УССР, 1969, с. 97-101.

23. Вельбицкий И.В., Нетесин И.Е. Организация функциональной памяти вычислительной машины. Кибернетика, 1983, № 5, с. 34-40.

24. Вельбицкий И.В., Нетесин И.Е., Шолмов Л.И. Табличная память. Программирование, 1982, № I, с. 27-37.

25. Вельбицкий И.В., Ходаковский В.Н., Шолмов Л.И. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-6. М.: Статистика, 1980, - 258 с.

26. Гиренко Ф.И., Громов С.П., Личман Г.А. Опыт применения Р-технологии при разработке программных систем. В кн.: Опыт использования Р-технологии для решения прикладных задач. Киев: ИК АН УССР, 1980, с. 26-28.

27. Гла,пун В.П. Организация памяти для поиска и записи по ключу. Кибернетика, 1965, № 4, с. 83-92.

28. Глушков В.М. О простых алгоритмах анализа и синтеза магазинных автоматов. Кибернетика, 1968, № 5, с. 1-9.

29. Глушков В.М. Теория автоматов и вопросы проектирования структур цифровых машин. Кибернетика, 1965, № I, с. 3—II.

30. Глушков В.М. фундаментальные исследования и технология программирования. Программирование, 1980, № 2, с. 3-13.

31. Глушков В.М., Бакаев А.А., Крамаренко Р.П. Система управления базами данных "Пальма". УСиМ, 1980, № 5, с. 94-97.

32. Глушков В.М., Вельбицкий И.В. Технология программирования и проблемы ее автоматизации. УСиМ, 1976, № 6, с. 75 -93.

33. Глушков В.М., Капитонова Ю.В., Летичевский А.А. О применении метода формализованных технических заданий к проектированию программ обработки структур данных. Программирование, 1978, № 6, с. 31-43.

34. Говорун и др. Мониторная система "Дубна" для ЭВМ БЭСМ-6. В кн.: Тр. 2 Всесоюз. конф. по программированию (Новосибирск, 1970). Новосибирск: ВЦ СО АН СССР, 1970, вып. Ж, с. 5-24.

35. Грис Д. Конструирование компиляторов для цифровых вычислительных машин / Пер. с англ. под ред. Ю.М.Банковского и В.С.Штаркмана. М.: Мир, 1975. - 544 с.

36. Ррисуолд Р., Поудд Дж., Полонски И. Язык программирования СН0Б0Л-4 / Пер. с англ. под ред. Ю.М.Банковского. М.: Мир, 1980. - 268 с.

37. Гурин В.Н., Обиднов Б.И. Конструктивная табличная память. -УСиМ, 1980, № I, с. 85-89.

38. Гусев В.В., Каминский Л.Г. Простой механизм динамического распределения одноуровневой памяти. Кибернетика, 1971, № 6, с. 146-147.

39. Дейкстра Э. Дисциплина программирования / Пер. с англ. под ред. Э.З.Любимского. М.: Мир, 1978. - 275 с.

40. Дейт К. Введение в системы баз данных. М.: Наука, 1980. -463 с.

41. Дрибас В.П. Реляционные модели баз данных. Минск: БГУ, 1982. 192с.

42. Дудкина Л.В., Сумарокова Т.В. Система управления базой данных БАНК. В кн.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1976, вып. 8, с. 3452.

43. Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977. 286 с.

44. Ершов А.П. О программировании.арифметических операторов. -Докл. АН СССР, 1958, 118, № 3, с. 427-430.

45. Шоголев Е.А. Программирование в метасинтаксических обозначениях. УСиМ, 1980, № I, с. 61-65.

46. Зайцев Н.Г. Реляционная однородно структурированная свободная (несвязная) база данных. УСиМ, 1982, № 6, с. 7478.

47. Камынин С.С., Любимский Э.З. Алгоритмический машинно-ориентированный язык АЛМО. В кн.: Алгоритмы и алгоритмические языки. М.: ВЦ АН СССР, 1967, вып. I, с. 5-58.

48. Капитонова Ю.В. Об изоморфизме абстрактных автоматов. 4.1.П. Кибернетика, 1965, № 3, с. 25-28; № 5, с. 10-13.

49. Карась В.А. Реализация в графическом РТРАНЕ алгоритма совмещения переменных ОЗУ специализированной машины. -В кн.: Р-технология программирования: Тез. докл. I Все-союз. конф. (Киев, 1983). Киев: ИК АН УССР, 1983, ч. I, с. III-II3.

50. Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы. М.: Мир, 1976. - T.I. 735 с.

51. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы. М.: Мир, 1977. - Т.2. 724 с.

52. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. М.: Мир, 1978. - Т.З. 844 с.

53. Козлов П.И. Реализация структурного расширения ФОРТРАНА с помощью Р-технологии. В кн;: Опыт использования Р-технологии для решения прикладных задач. Киев: ИК АН УССР, 1980, с. 22-23.

54. Косяк А.С., Романовский А.Б., Тараненко А.А., Штелик Е.В. Технологический комплекс программиста РТК СМ. В кн.: Р-технология программирования: Тез. докл. I Всесоюз. конф. (Киев, 1983). Киев:: ИК АН УССР, 1983, ч. I, с. 28-31.

55. Королев Л.Н. Кодирование и свертывание кодов. Докл. АН СССР, 1957, 113, № 4, с. 746-747.

56. Кохонен Т. Ассоциативные запоминающие устройства / Пер. с англ. под ред. В.И.Зуева. М.: Мир, 1982. - 383 с.

57. Курочкин В.М., Подшивалов Д.Б. Система БЭСМ-АЛГОЛ. В кн.: Тр. 2 Всесоюз. конф. по программированию (Новосибирск, 1970). Новосибирск: ВЦ СО АН СССР, 1970, вып. Б, с. 25-29.

58. Лаврищева Е.М., Ющенко Е.Л. Метод анализа на базе СМ-язы-ка. Кибернетика, 1972, № 2, с. 41-44.

59. Лавров С.С. Об экономии памяти в замкнутых операторных схемах. ЖВМ и МФ, 1961, I, № 4, с. 687-701.

60. Летичевский А.А. Представление контексно-свободных языков в автоматах с памятью типа push-down. Кибернетика, 1965, № 2, с. 80-84.

61. Липаев В.В., Колин К.К., Серебровский Л.А. Математическое обеспечение управляющих ЦВМ. М.: Советское радио, 1972. -528 с.

62. Литвинов В.А., Кокорин А.А. Прогрессивная организация записей переполнения в файлах с рандомизированной структурой.-Программирование, 1978, № 5, с. 69-73.

63. Лорин Г. Сортировка и системы сортировки / Пер с англ. Р.Л.Смелянского. М.: Наука, 1983. - 384 с.

64. Малышев О.В. Моделирование абстрактных видов памяти Р-метаязыка. В кн.: Технология программирования. Киев: ИК АН УССР, 1977, с. 15-21.

65. Мазный Г.Л. Программирование на БЭСМ-6 в системе "Дубна". -М.: Наука, 1978. 272 с.

66. Мартин Дж. Организация баз данных в вычислительных системах/ Пер. с англ. под ред. А.А.Стогния и А.Л.Щерса. М.: Мир, 1980. - 662 с.

67. Мельников И.А., Саар Х.Я. Организация данных в Интегрированной системе программирования. Программирование, 1975, № 6, с. 28-37.

68. Нетесин И.Е. Быстрая стековая таблица. В кн.: Р-техноло-гия программирования и средства ее инструментальной поддержки. Киев: ИК АН УССР, 1982, с. 39-41.

69. Нетесин И.Е. Один способ организации хеш-таблиц. В кн.: Р-технология программирования: Тез. докл. I Всесоюз. конф. (Киев, 1983). Киев: ИК АН УССР, 1983, ч. I, с. 28-31.

70. Нетесин И.Е. Оптимальная организация табличной памяти в диалоговом технологическом комплексе РТК СМ ЭВМ. В кн.: Тез. докл. Всесоюз. конф. "Диалог Человек-ЭВМ" (Ленинград, 1982). Ленинград: ЛИАП, 1982, ч. I, с. 107-109.

71. Нетесин И.Е. Оптимизация табличной памяти РВМ. В кн.: Состояние разработки Р-технологии и программных средств ее поддержки на машинах ЕС ЭВМ, СМ ЭВМ и БЭСМ-6. Киев: ИК АН УССР, 1980, с. 61-63.

72. Нетесин И.Е. MIXER механизм табличной памяти в РТК БЭСМ-6. - В кн.: Технология программирования: Тез. докл. I Всесоюз. конф. (Киев, 1979). Киев: ИК АН УССР, 1979, секция И, с. 51.

73. Оснач Б.Г. Применение Р-технологии для реализации диалоговой системы автоматизированного ввода графической информации. В кн.: Опыт использования Р-технологии для решения прикладных задач. Киев: ИК АН УССР, 1980, с. 15-16.

74. Пакет прикладных программ "Система управления динамической страничной памятью прямого доступа". (ЭРМ-процессор). руководство системного программиста. ВЕРА. DPM.03.03 / Товстолес А.Н., Шейнкман Г.А., Белов В.В. и др. Рига: Лат. НИИЛП, 1982. - 77 с.

75. Перевозчикова 0.JI., Ющенко Е.Л. Тенденции развития систем обработки данных. Программирование, 1977, №5, с. 70-90.

76. Погребной В.К. Об автоматизации распределения памяти на графовых моделях алгоритмов. УСиМ, 1980, № 5, с. 37-42.

77. Поздняков Л. А. Об одном подходе к построению функций расстановки при работе с перемешанными таблицами. М., 1978. - 34 с. - (Препринт / ИПМ АН СССР; № 33).

78. Поздняков Л.А. Сравнение двух схем использования параллельного доступа к памяти при работе с перемешанными таблицами. М., 1977. - 63 с. - (Препринт / ИПМ АН СССР; №96).

79. Рвачев В.Л., Мацевитый A.M. Общая память в Алголе-ГДР. -Программирование, 1980, №6, с. 59-63.

80. Редько В.Н. Некоторые вопросы теории языков. Кибернетика, 1965, № 4, с. 12-21.

81. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика / Пер. с англ. под ред. В.Б.Алексеева. М.: Мир, 1980. - 476 с.

82. Родионов С.Т., Козлов П.И., Попов П.Г. Конфигурация РТК БЭСМ-б для построения информационно-поисковых систем.

83. В кн.: Операционные системы и технология программирования. Киев: Ж АН УССР, 1979, с. 43-47.

84. Г^ухлин А.П. Распределение памяти для объектов изменяющихся размеров. В кн.: Тез. докл. Всесоюз. конф, по методам трансляции (Новосибирск, 1981). Новосибирск: СО АН1. СССР, 1981, с. 187-189.

85. Суханов В. И. Трансляция языка для решения задач -гдискретной оптимизации средствами РГК БЭСМ-6. В кн.: Опыт использования Р-технологии для решения прикладных задач. Киев: ИК АН УССР, 1980, с. 62-63.

86. Сухомлин В.А. Алгоритмическая система для описания процессов трансляции. I.- Программирование, 1975, № 2, с. 7783.

87. Тамм Б.Г., Тыугу Э.Х. О создании проблемно-ориентированного программного обеспечения. Кибернетика, 1975, № 4, с. 78-85.

88. Тараненко А.А., Каюров В.Ю., Кирсанов В.Ф., Ковалев А.Л., Косяк А.С. Организация процесса проектирования в безбумажной Р-технологии программирования. УСкМ, 1983, № 6, с. 38-43.

89. Трифонов Ю.В. Оптимизационные методы в технологии организации файлов прямого доступа. Программирование, 1980,2, с. 77-82.

90. Феллер В. Введение в теорию вероятностей и ее приложения / Пер. с англ. под ред. Е.Б.Дынкина. М.: Мир, 1967. - T.I. 498 с.

91. Филиппов В.И. руководство по СУЦЦ КОМПАС. М.: ВЦ АН СССР 1981. - 46 с.

92. Флорес И. Структуры и управление данными. М.: Финансы и статистика, 1982. - 319 с.

93. Холл П. Вычислительные структуры / Пер. с англ. под ред. Э.З.Любимского. М.: Мир, 1978. - 214 с.

94. Хопгуд Ф. Методы компиляции / Пер. с англ. под ред. Э.З.Любимского и В.В.Мартынюка. М.: Мир, 1972. - 160 с.

95. Цейтлин Г.Е., Ющенко Е.Л. Стандартизация памяти в технологии структурного программирования. Программирование, 1979, № 6, с. 3-10.

96. Чесноков Е.В. Табличный метод доступа в РТК ОС ЕС. В кн.: Р-технология программирования и средства ее инструментальной поддержки. Киев: ИК АН УССР, 1982, с. 50-52.

97. Шолмов Л.И., Макаров В.В. Использование инструментальных средств РТК БЭСМ-6 для генерации АСПП СИНТЕШ. В кн.: Технология программирования: Теэ. докл. I Всесоюз. конф. (Киев, 1979). Киев: ИК АН УССР, 1979, секция П, с. 64-65.

98. Шолмов Л.И., Ходаковский В.Н., Макаров В.В. и др. Графическое представление алгоритмов в безбумажной Р-технологии программирования. УСиМ, 1982, № 6, с. 43-47.

99. Шоу А. Логическое проектирование операционных систем / Пер. с англ. под ред. Г.Н.Соловьева. М.: Мир, 1981. -360 с.

100. Шура-Бура М.Р., Мартынюк В.В. Об эффективной организации динамического использования памяти. ЖВМ и М9>, 1964, 4, №5,с.963-967.

101. Ющенко Е.Л., Цейтин Г.Е. Об алгебре многорегистровых операторов. Кибернетика, 1971, № 2, с. 66-71.

102. Arable 0., Knuth D. Ordered hash tables. Comput. J., 1974, 17, P. 135 -1^2.

103. Batson A. The organization of symbol tables. Comm. ACM, 1965, 8, 2, p. 111 - 112.

104. Bays C. A note on when to chain overflow items within a direct-access tables. Comm. ACM, 1973, 16, N 1, p. k7.

105. Bays C. Some techniques for structuring chained hash tables. Comput. J., 1973, 16, n 2, p. 126 -131.

106. Bays C. The reallocation of hash-coded tables. Comm. ACM, 1973, 16, N 1, p. 11 -14.

107. Bell J.R., Kaman C,H, The linear quotient hash code. -Comm. ACM., 1970, 13, N 11, p. 675 677107- Bently J.L,, Yao A,C, An almost optimal algorithm forunbounded searching. Inf. Proc. Lett., 1976, 5, N 3, p. 82 - 87.

108. Berztiss А.T, A note on storage of strings. Comm. ACM, 1965, 8, N 8, p. 512 - 513.

109. Blaggen M.W. ,, Astrahan M.M, and other. System R: An architecture overview. IBM Syst. J., 1981, 12, N 1, p. 41 -62.

110. Bloom B,H, Space/Time trade-offs in hash coding with allowable errors. Comm. ACM, 1970, 13, N 7, P. ^22 -426.

111. Brent R,P. Reducing the retrieval time of scatter storage techiques. Comm. ACM, 1973, 16, N 2, p. 105 - 109.

112. Carter J,L, , Wegman M,N, Universal classes of hash functions. J. Comput. & Syst. Science, 1979, 18, N 2, p. 1^3-15^.

113. Coffman E.G., Eve Jr., Eve J.,File structures using hashing functions. Comm. ACM, 1970, 13, N 7, p. 427-^32.

114. Cohen J. Garbage collction of linked data structures. ACM Comput. Surveys, 1981, 13, N 3, P. 3^1-367.

115. Elcock E,V. Note on the addressing of lists by their sourse-language names. Comput. J., 1965, 8, N 2, p. 242-2^3.

116. Erickson R.E., Lass H. Optimal sizing of records used to store message of various length. Management Science, 1980,26, N 8, p. 796-809.

117. Gonnet R, Open-addressing hashing with unequal-probability keys. J. Comput. & Syst. Science, 1980, 21, N 3, p. 354367.

118. Haddon B.K., Waite W.M, A compaction procedure for variable length storage elements. Comput. J., 1967, 10, N 2, p. 162-165.

119. Hopgood F.R.A. A solution to the table overflow problem for hash tables. Comput. Bull., 1968, 11, p. 287.

120. Knott G.D. Hashing functions. Comput. J., 1975, 18, N 3, p. 265-278.

121. Larson P.A. Dynamic Hashing. BIT, 1978, 18, N 2, p. 184191 .

122. Lipton R.J., Rosenberg A.L., Yao A.C. External hashing schemes for collections of data structures. J. ACM, 1980,27, N 1, p. 81-95.

123. Liskov B.H., Zilles S.N. Programming with abstract data types. SIGPLAN Not., 1974, 9, N 4, p. 50-79.12^. Maurer W.D. , Lewis T.G. Hash tables methods. Comput. Surveys, 1975, 7, N 1, p. 5-9.

124. Morris R, Scatter storage techniques, Comm. ACM, 1968, 11, N 1, p. 38-kh.

125. Peterson ¥,¥. Addressing for random-access storage. IBM J. of Research and Develop,, 1957, 1, P. 130-1^6.

126. Quittner P, Efficient combination of index tables and hashing. Soft. Pract. & Exper., 1983, 13, N 6, p. ^7178.

127. Rosenberg A.L, On storing ragged arrays by hashing. Math. Syst. Theory., 1976, 10, p. 193-210.

128. Rosenberg A.L,, Stockmeyer L.Y, Hashing schemes for extendible arrays. J. ACM, 1977, 24, N 2, p. 199-221.

129. Stonebraker M,, Wong E. and other. The design and implementation of INGRES. ACM Trans, on Database Syst., 1976, 1, N 3, p. 189-222.