Оптимальное решение базовых задач хранения и поиска в информационно-графовой модели данных тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

1 Информационный граф (ИГ) как управляющая система, моделирующая алгоритмы хранения и поиска информации

1.1 Задачи хранения и поиска в базах данных.

1.2 Понятие информационного графа.

1.3 Критерий допустимости ИГ.

1.4 Полнота для информационных графов.

1.5 Сложность информационных графов.

1.6 Мощностная нижняя оценка.

1.7 Случай оптимальности перебора

2 Задачи информационного поиска с коротким ответом

2.1 Задачи поиска с коротким ответом.

2.1.1 Существование древовидного оптимального ИГ для задач поиска с коротким ответом.

2.1.2 Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей.

2.1.3 Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом.

2.1.4 Леммы о сведении.

2.2 Поиск идентичных объектов.

2.2.1 Бинарный поиск.

2.2.2 Константный в среднем алгоритм поиска

2.2.3 Константный в худшем случае алгоритм поиска

2.2.4 Оценки памяти константного в худшем случае алгоритма поиска.

2.3 Задачи о близости.

ОГЛАВЛЕНИЕ

2.3.1 Бинарный поиск.

2.3.2 Константный в среднем алгоритм поиска

2.3.3 Константный в худшем случае алгоритм поиск а

3 Задачи поиска на частично-упорядоченных множествах данных

3.1 Задачи поиска на конечных частично-унорядоченных множествах данных.

3.2 Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных

3.2.1 Включающий поиск.

3.2.2 О недревовидности оптимальных ИГ включающего поиска.

3.2.3 О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей

3.2.4 Нижняя оценка сложности включающего поиска

3.2.5 Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ

3.2.6 Оценки сложности одного метода решения задачи включающего поиска.

3.2.7 Оценки B-сложности включающего поиска

3.3 Задачи поиска на линейно-упорядоченных множествах данных.

3.3.1 Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка

3.3.2 Моделирование поиска в системах с несколькими вычислителями.

3.3.3 Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка

3.4 Задачи поиска на декартовых произведениях линейноупорядоченных множеств данных (задача о доминировании)

3.4.1 Последовательные алгоритмы решения задачи о доминировании.

ОГЛАВЛЕНИЕ

3.4.2 Оценки В-сложности задачи о доминировании

3.4.3 Математическая модель фоновых алгоритмов поиска

3.4.4 Фоновый алгоритм решения двумерной задачи о доминировании.

4 Задача поиска на евклидовом параллелепипеде при запросах вида его подпараллелепипедов (интервальный поиск)

4.1 Одномерная задача интервального поиска

4.1.1 Случай базового множества характеристических функций

4.1.2 Случай простого базового множества.

4.1.3 Базовое множество логарифмического поиска

4.1.4 Базовое множество сверхлогарифмического поиска

4.1.5 Мгновенное решение

4.2 Многомерная задача интервального поиска.

4.2.1 Мгновенное решение многомерной задачи интервального поиска

4.2.2 Пример оценки константы специальной ограниченности

4.2.3 Оценки В-сложности задачи интервального поиска

5 Об устойчивости канонического эффекта информационно-графовой модели хранения и поиска данных

5.1 Понятие канонического эффекта.

5.2 Неустойчивость канонического эффекта по отношению к базовому множеству.

5.3 Неустойчивость канонического эффекта по отношению к объему памяти.

5.4 Устойчивость канонического эффекта по отношению к ^-расширению запроса

5.4.1 е-расширение задачи поиска идентичных объектов

ОГЛАВЛЕНИЕ

5.4.2 £-расширение задач о доминировании и интервального поиска

1. Абчук В. А., Суздаль В. Г. Поиск объектов. Советское радио, Москва, 1977.

2. Адельсон-Вельский Г. М., Ландис Е. М. Алгоритм организации информации. ДАН СССР (1962) 146, 263-266.

3. Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. / Под ред. В. Е. Котова и И. Милошко. Наука, Москва, 1982.

4. Альсведе Р., Вегенер И. Задачи поиска. Мир, Москва, 1982.

5. Андреев А. Е. Метод бесповторной редукции синтеза самокорректирующихся схем. ДАН СССР (1985) 283, №2, 265-269.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Мир, Москва, 1979.

7. Белобродский А. В., Решетников В. Н. Об одном способе поиска релевантных векторов. Вопросы оптимизации и управления. Изд-во Моск. ун-та, Москва, 1979, 59-63.

8. Введение в криптографию / Под общ. ред. В. В. Ященко. — М.: МЦНМО, "ЧеРо", 1998. — 272 с.

9. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по курсу дискретной математики. Наука, Москва, 1992.ЛИТЕРАТУРА349

10. Гасанов Э. Э. Некоторые оценки сложности поиска информации. Физическое и математическое моделирование дискретных систем. Межвузовский сборник трудов № 56. Изд-во Моск. энерг. ин-та, Москва, 1985, 43-47.

11. Гасанов Э. Э. Алгоритмы построения информационных деревьев. Препринт Р-5-188 ИЯФ АН УзССР. Ташкент, 1985.

12. Гасанов Э. Э. Оценки средней сложности поиска информации. Препринт Р-5-186 ИЯФ АН УзССР. Ташкент, 1985.

13. Гасанов Э. Э. О сложности информационного поиска. Канд. дисс., Москва, 1985.

14. Гасанов Э. Э. О некоторых оценках сложности поиска информации. Алгебра, логика и теория чисел. Изд-во МГУ, Москва, 1986,37-39.

15. Гасанов Э. Э. Об одной оценке сложности поиска информации. Численные методы в математической физике. Изд-во МГУ, Москва, 1986, 110-111.

16. Гасанов Э. Э. О виде оптимальных информационных сетей для отношений линейного квазипорядка. Препринт Р-5-303 ИЯФ АН УзССР. Ташкент, 1987.

17. Гасанов Э. Э. Оптимальные информационные сети для отношений поиска, являющихся отношениями линейного квазипорядка. Конструкции в алгебре и логике. Изд-во Тверского гос. ун-та, Тверь, 1990, 11-17.

18. Гасанов Э. Э. Об одной математической модели информационного поиска. Дискретная математика (1991) 3, № 2, 69-76.

19. Гасанов Э. Э. Математические модели и сложность информационного поиска. Proceedings of the graduate workshop in mathematics and its applications in social sciences. Ljubljana, 1991, 37-53.ЛИТЕРАТУРА350

20. Гасанов Э. Э. Нижняя оценка сложности информационных сетей для одного класса задач информационного поиска. Дискретная математика (1992) 4, № 3, 118-127.

21. Гасанов Э. Э. О сложности поиска в базах данных. Искусственный интеллект (Межвузовский сборник трудов). Изд-во Саратовского университета, Саратов, 1993, 41-56.

22. Гасанов Э. Э. Некоторые задачи поиска, допускающие мгновенное в среднем решение. Фундаментальная и прикладная математика (1995) 1, № 1, 123-146.

23. Гасанов Э. Э. Об одномерной задаче интервального поиска. Дискретная математика (1995) 7, № 2, 40-60.

24. Гасанов Э. Э. Нижняя оценка сложности включающего поиска. Проблемы теоретической кибернетики: Материалы XI Международной конференции, 10-Ц июня 1996 г. Издательский центр Российского государственного гуманитарного университета, Москва, 1996, 40-41.

25. Гасанов Э. Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8, № 3, 119-134.

26. Гасанов Э. Э. Нижняя оценка сложности информационных сетей для одного отношения частичного порядка. Дискретная математика (1996) 8, № 4, 108-122.

27. Гасанов Э. Э. Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска. Изд. центр РГГУ, Москва, 1997.

28. Гасанов Э. Э., Мхитарова Т. В. Об одной математической модели фоновых алгоритмов поиска и быстрый фоновый алгоритм двумерной задачи о доминировании. Фундаментальная и прикладная математика (1997) 3, № 3, 759-773.ЛИТЕРАТУРА351

29. Гасанов Э. Э. О параллельном решении одномерной задачи о доминировании. Труды II Международной конференции "Дискретные модели в теории управляющих систем", Крас-новидово, (23-28 июня 1997 г.), — М: Диалог-МГУ, 1997. — 16-19.

30. Гасанов Э. Э. Нижняя оценка сложности включающего поиска в классе древовидных схем. Дискретная математика (1998) 10, № 1, 63-72.

31. Гасанов Э. Э., Косолапов А. В. К вопросу о древовидности оптимальных информационных сетей включающего поиска. Интеллектуальные системы (1998) 3, № 1-2, 167-192.

32. Гасанов Э. Э. Информационно-графовая модель хранения и поиска данных. Интеллектуальные системы (1998) 3, № 3-4.

33. Гасанов Э. Э., Кузнецова И. В. Оценки функциональной сложности двумерной задачи интервального поиска. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики", Нижний Новгород, (17-22 мая 1999 г.), — 47.

34. Гасанов Э. Э., Ерохина Е. Р. Моделирование и сложность поиска в многопроцессорных системах. Дискретная математика (1999) 11, № 3.

35. Гасанов Э. Э., Луговская Ю. П. Константный в худшем случае алгоритм поиска идентичных объектов. Дискретная математика (1999) 11, № 4.

36. Гасанов Э. Э. Оценки сложности одного метода решения задачи включающего поиска. Дискретная математика (в печати).

37. Гасанов Э. Э. Решение проблемы оптимального синтеза информационных графов для базовых задач поиска информации. Доклады РАН (в печати).ЛИТЕРАТУРА352

38. Грицык В. В., Златогурский Э. Р., Михайловский В. Н. Распараллеливание алгоритмов обработки информации. На-укова думка, Киев, 1977.

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

40. Евреинов Э. В., Косарев Ю. Г. Однородные универсальные вычислительные системы высокой производительности. Наука, Новосибирск, 1966.

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

42. Ершов А. П. Операторные алгоритмы. III (Об операторных схемах Янова). Проблемы кибернетики. (1968), вып. 20, 181— 200.

43. Ершов А. П. Некоторые субъективные замечания к актуальным проблемам программирования. Перспективы системного и теоретического программрования: Труды Всесоюзного симпозиума, Новосибирск, 20-22 марта, 1978 г. ВЦ СО АН СССР, Новосибирск, 1979, 113-127.

44. Информационные системы общего назначения. Статистика, Москва, 1975.

45. Карцев М. А. Распараллеливание алгоритмов итерационного типа. Вопросы радиоэлектроники. Сер ЭВТ, (1971), вып. 96 36-39.

46. Ким Д. П. Методы поиска и преследования подвижных объектов. Наука, Москва, 1989.

47. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. 3, Мир, Москва, 1978.

48. Колмогоров А. Н., Успенский В. А. К определению алгоритма. УМН (1958) 13, № 4, 3-28.ЛИТЕРАТУРА353

49. Котов В. Е. Сети Петри. Наука, Москва, 1984.

50. Котов В. Е., Нариньяни А. С. Асинхронные вычислительные процессы над памятью. Кибернетика (1966) № 3, 64-71.

51. Котов В. Е., Сабельфельд В. К. Теория схем программ. Наука, Москва, 1991.

52. Кудрявцев В. В., Алешин С. А., Подколзин А. С. Введение в теорию автоматов. Наука, Москва, 1985.

53. Ли Д., Препарата Ф. Вычислительная геометрия. Обзор. Кибернетический сб. (1987) 24, 5-96.

54. Лупанов О. Б. О синтезе некоторых классов управляющих систем. Проблемы кибернетики (1963) 10, 63-97.

55. Мальцев А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

56. Марков А. А. Теория алгоритмов. — Тр. мат. ин-та АН СССР им. В. А. Стеклова, 42. Изд-во АН СССР, Москва, 1954.

57. Мартин Дж. Организация баз данных в вычислительных системах. Мир, Москва, 1980.

58. Минский М., Пейперт С. Персептроны. Мир, Москва, 1971.

59. Миренков Н. Н. Параллельные алгоритмы для решения задач на однородных вычислительных системах. Вычислительные системы. ЙМ СО АН СССР, Новосибирск, (1973), вып. 57, 2-32.

60. Мошков М. Ю. Верхние оценки сложности деревьев решений с квазилинейными проверками Фундаментальные проблемы математики и механики. Математика. Изд-во МГУ, Москва, 1994, 339-341.

61. Мошков М. Ю. Деревья решений. Теория и приложения. Изд-во Нижнегородского ун-та, Нижний Новгород, 1994, 175 с.ЛИТЕРАТУРА354

62. Мошков М. Ю. Нижние оценки временной сложности детерминированных условных тестов. Дискретная математика (1996) 8, № 3, 98-110.

63. Мошков М. Ю. Оценки глубины деревьев решений, вычисляющих булевы функции. Доклады РАН (1996) 350, № 1, 22-24.

64. Мошков М. Ю. Оптимизация деревьев решений. Интеллектуальные системы (1996) 1, № 1-4, 199-204.

65. Мошков М. Ю. О глубине деревьев решений. Доклады РАН (1998) 358, № 1, 26.

66. Наумов А. Н., Вендров А. М., Иванов В. К. и др. Системы управления базами данных и знаний: Справ, изд. Финансы и статистика, Москва, 1991.

67. Ньюмен У. М., Спруэлл Р. Ф. Основы интерактивной машинной графики. Мир, Москва, 1976.

68. Полиа Г., Сеге Г. Задачи и теоремы из анализа. Наука, Москва, 1978.

69. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Мир, Москва, 1989.

70. Решетников В. Н. Алгебраическая теория информационного поиска. Программирование (1979), № 3, 68-74.

71. Решетников В. Н. Моделирование информационного поиска в информационно-поисковых системах. Кибернетика (1979), № 5, 129-132.

72. Решетников В. Н. Моделирование поиска в АИПС с нетривиальными коэффицентами. Вопросы оптимизации и управления. Изд-во Моск. ун-та, Москва, 1980, 45-54.

73. Решетников В. Н. Информационный поиск и ^-структура. Математические вопросы задач оптимизации и управления. Изд-во Моск. ун-та, Москва, 1981, 90-94.ЛИТЕРАТУРА355

74. Решетников В. Н., Сотников А. Н. Алгебраические свойства ^-структуры и псевдорелевантные векторы. Вестн. Моск. унта. Сер. 125. Вычислительная математика и кибернетика. (1981), № 1, 70-73.

75. Селтон Г. Автоматическая обработка, хранение и поиск информации. Советское радио, Москва, 1973.

76. Системы управления базами данных для ЕС ЭВМ: Справочник. / Под общ. ред. В. М. Савинкова. Финансы и статистика, Москва, 1984.

77. Солтон Дж. Динамические библиотечно-ипформационные системы. Мир, Москва, 1979.

78. Страуструп Б. Язык программирования Си++. Радио и связь, Москва, 1991.

79. Теория и методы параллельной обработки информации: Сб. науч. тр. / Под ред. В. Е. Котова. Новосибирск, 1988.

80. Тиори Т., Фрай Дж. Проектирование структур баз данных: В 2-х кн. Мир, Москва, 1985.

81. Фаддеева В. Н., Фаддеев Д. К. Параллельные вычисления в линейной алгебре. Кибернетика, (1977), № 6, 28-40.

82. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. Мир, Москва, 1982.

83. Хеллман О. Введение в теорию оптимального поиска. Наука, Москва, 1985.

84. Черный А. И. Введение в теорию информационного поиска. Наука, Москва, 1975.

85. Шеннон К. Работы по теории информации и кибернетике. Изд-во иностранной литературы, Москва, 1963.ЛИТЕРАТУРА356

86. Элементы параллельного программирования. / В. А. Валь-ковский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков; Под ред. В. Е. Котова. Радио и связь, Москва, 1983.

87. Энциклопедия кибернетики. Киев, 1975, т. 1. Статьи: "Информационно-поисковая система" (с.359), "Информационно-поисковая система документальная" (с.359-400).

88. Яблонский С. В. Введение в дискретную математику. Наука, Москва, 1979.

89. Яненко Н. Н., Коновалов А. Н., Бугров А. Н., Шустов Г. В. Об организации параллельных вычислений и "распараллеливание" прогонки. Численные методы механики сплошной среды. ИТМП СО АН СССР, Новосибирск, (1978), т. 9, 139146.

90. Янов Ю. И. О логических схемах алгоритмов. Проблемы кибернетики. (1958), вып. 1, 75-127.

91. Bayer R., McCreight Е. М. Organization and Maintenance of Large Ordered Indexes. Acta Informatica (1972) 1, № 3, 173-189.

92. Ben-Or M. Lower bounds for algebraic computation trees. Proc. 15th ACM Annu. Symp. Theory Comput. (Apr. 1983) 80-86.

93. Bentley J. L. Multidimensional binary search trees used for associative searching. Commun. Ass. Comput. Mach. (Sept. 1975), 18 509-517.

94. Bentley J. L. Decomposable searching problems, Info. Proc. Lett. (1979), 8 244-251.

95. Bentley J. L., Friedman J. H. Data structures for range searching. Comput. Surveys (1979), 11 397-409.

96. Bentley J. L., Maurer H. A. Efficient worst-case data structures for range searching. Acta Inform. (1980), 13 155-168.ЛИТЕРАТУРА357

97. Bentley J. L., Saxe J. B. Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms (1980), v. 1, 301-358.

98. Bolour A. Optimal retrieval algorithms for small region queries. SIAMJ. Comput. (1981) 10, 721-741.

99. Borodin A. B. Computational complexity — Theory and practice. Currents in Theory of Computings. Englewood Cliffs, NJ: Printice-Hall, 1973, 35-89.

100. Burkhard W. A. Keller R. M. Some Approaches to best match file searching. Commun. Ass. Comput. Mach. (1973) 16, 230-236.

101. Chazelle B. M. Filtering search: a new approach to query-answering. Proc. 24th IEEE Annu. Symp. Found. Comput. Sei. (Nov. 1983), 122-132.

102. CODASYL Systems Committee, Feature Analysis of Generalized Data Base Management Systems, ASM, New York, 1971b.1101 CODASYL Systems Committee, Selection and Acquisition Of Data Base Management Systems, ASM, New York, Mar. 1976.ЛИТЕРАТУРА358

103. COD ASYL — The Stored-Data Definition and Translation Task Group, Stored-Data Description and Data Translation: A Model and Language, Inf. Syst. 2, № 3, 95-148 (1977).

104. Codd E. F. A Relation Model of Data for Large Shared Data Banks, Comm. ACM 13, № 6, ACM, New York, London, Amsterdam, June 1970, 377-387.

105. Codd E. F. Further Normalization of the Data Base Relational Model, Courant Computer Sei. Symposia (vol. 6: "Data-Base System"), ed. by R. Rustin, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1972.

106. Codd E. F. Relational Completeness of Data Base Sublanguages, Courant Computer Sei. Symposia (vol. 6: "Data-Base System"), ed. by R. Rustin, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1972.

107. Codd E. F. A Data Base Sublanguage Founded on the Relational Calculus, Proc. of the 1971 ACM-SIGFIDET Workshop on Data Description, Access, and Control, ACM, New York, London, Amsterdam, 1972.

108. Codd E. F. Access Control for Relational Data Base Systems, BCS Symposium on Relational Data-Base Concepts, Apr. 1973, British Computer Soc., London, 1973.

109. Codd E. F. Recent Investigations in Relational Data-Base Systems, Information Processing'74, North-Holland, Amsterdam, 1974.

110. Codd E. F. Relational Database: A Practical Foundation for Productivity. Commun, of ACM (1982) 25, № 2, 140-155.

111. Data Language/I-System/370 DOS/VS, General Information Manual GH20-1246, IBM, White Plains, New York, 1974.

112. Date C. J., Codd E. F. The Relational and Network Approaches: Comparison of the Application Programming Interfaces, Proc. ofЛИТЕРАТУРА359the 1974 ACM-SIGFIDET Workshop, ACM, New York, London, Amsterdam, 1974.

113. Devroye L. Upper and lower class sequences for minimal uniform spacings. Zeitschrift für Wahrscheinlichkeitstheorie und verwände Gebiete (1982) 61, № 2, 237-254.

114. Dobkin D. P. A nonlinear lower bound on search tree programs for solving knapsack problems. J. Comput. Syst. Sei. (1976) 13, 69-73.

115. Dobkin D. P., Lipton R. J. A lower bound of l/2n2 on linear search programs for the knapsack problem. J. Comput. Sei. (1978) 16,413-417.

116. Dobkin D. P., Lipton R. J. On the complexsity of computations under varying sets of primitives. J. Comput. Syst. Sei. (1979) 18, 86-91.

117. Dumey A. Indexing for Rapid Random Access Memory Systems. Computers and Automation. (1956) 4, № 12, 6-9.

118. Dunlavey M. R. Query performance of many-dimensional best match algorithm. Proc. 19th Allerton Conf. Commun. Control Comput. (1981) 389-396. ■

119. Edelsbrunner H., Overmars M. H., Siedel R. Some methods of computational geometry applied to computer graphics. IIG, Technische Univ. Graz, Austrua, Tech. Rep. Fill. (June 1983).

120. Ferguson D. E. Fibonaccian searching. CA CM (1960) 3, 648.

121. Fortune S., Hopcroft J. A note on Rabin's nearest-neighbor algorithm. Inform Processing Lett. (Jan. 1979) 8, № 1, 20-23.

122. Fredman M. L., Weide B. On the complexity of computing the measure of Uahbi]. Commun. ACM. (1978) 21, № 7, 540-544.

123. Fredman M. L. A lower bound of the complexity of ortogonal range queries. J. ACM. (1981) 28, 696-705.ЛИТЕРАТУРА360

124. Fredman M. L., Baskett F., Shustek J. An algorithm for finding nearest neighbors. IEEE Trans. Comput. (1975) C-24, 1000-1006.

125. Fredman M. L., Bentley J. L., Finkel R. A. An algorithm for finding best match in logarithmic expected time. ACM Trans. Math. Software (1977) 3, № 3, 209-226.

126. Gabow H. N., Bentley J. L., Tarjan R. E. Scaling and related techniques for geometry problems. Proc. 16th ACM Annu. Symp. Theory Comput. (Apr. 1984) 135-143.

127. Gasanov E. E. Some asymptotic evaluations of complexity of information searching. Proceedings of International Conference FCT-87. Kazan, USSR. 1987. Lect. Notes in Comp. Sci. N 278, 137-139.

128. Gasanov E. E. On fast solving of interval search problem. Proceedings of International Congress of Mathematicians. Zurich, Switzerland, 1994, 137.

129. Gasanov E. E. Instantly solvable search problems. Proceedings of International Symposium on Intelligent Data Analysis (IDA-95). Baden-Baden, Germany. HAS Press, 1995, 65-69.

130. Gasanov E. E. On a one-dimensional interval search problem. Discrete Mathematics and Applications (1995) 5, №2, 117-136.

131. Gasanov E. E. Instantly solvable search problems. Discrete Mathematics and Applications (1996) 6, №5, 467-482.

132. Gasanov E. E. A lower bound for the complexity of information networks for one partial order relation. Discrete Mathematics and Applications (1996) 6, №6, 585-598.

133. Gasanov E. E. A lower bound for the complexity of inclusive search in the class of tree circuits. Discrete Mathematics and Applications (1998) 8, №1, 99-108.ЛИТЕРАТУРА361

134. Gasanov E. E., Kuznetsova I. V. On one method to decrease average search time. Abstracts of Ist Turkish World Mathematics Symposium Elazig, Turkey. (29 June 2 July 1999) — p. 135.

135. Gill S. Parallel programming. The Computer J. (1958) 1 № 1, 2-10.

136. Guibas L. J., Stolfi J. On computing all north-east nearest neighbors in Zq-metric. Inform Processing Lett. (Nov. 1983) 17, 219-223.

137. Harper L. H. Optimal numbering and isoperimetric problem on graphs. J. Combin. Theory (1966) 1, № 3, 385-393.

138. Hibbard T. N. Some Combinatorial Properties of Certain Trees with Applications to Searching and Sorting. J. ACM (1962) 9, № 1, 13-28.

139. Hu T. C., Tucker A. C. Optimal Computer Search Trees and Variable-Length Alphabetical Codes. SIAM J. Applied Math. (1971) 21, 514-532.

140. Information Management System Virtual Storage (IMS/VS), General Information Manual GH20-1260, IBM, White Plains, New York, 1974.

141. Information Management System/360, Version 2, Application Programming Reference Manual SH20-0912, IBM, White Plains, New York, 1974.

142. Information Management System/360, Version 2, System Programming Reference Manual SH20-0911, IBM, White Plains, New York, 1974.

143. Katona G. 0. H. A Theorem on finite sets. Theory of Graphs, Proc. Colloq. held at Tihany. Hungary, (1966), 187-207.

144. Katona G. 0. H. The Hamming-sphere has minimum boundary Studia Scient. Math. Rungarica (1975) 10, 131-140.ЛИТЕРАТУРА362

145. Knuth D. E. Optimum Binary Search Trees. Acta Informatica (1971) 1, 14-25.

146. Kruskal F. B. The number of simplices in compex. Mathematical Optimization Techniques (1963), 251-278.

147. Kuck D. J. A survey of parallel machine organization and programming. ACM Computing Surveys, (1977), 9, № 1, 29-59.

148. Lauter U. 4-dimensional binaxy search trees as a means to speed up associative searches in design verification of integrated circuits. Jour, of Design Automation and Fault Tolerant Computing, 2 (3), 241-247 (July 1978).

149. Lee D. T., Wong C. K. Worst case analysis for region and partial region searches in multidimensional binary search trees and balansed quad trees. Acta Informatica (1977) 9 23-29.

150. Lee D. T., Wong C. K. Quintari trees: A file structures for multidimensional database system. ACM Trans. Database Syst. (Sept. 1980) 1, № 1, 339-353.

151. Lee D. T., Wu Y. F. Efficient algorithms for Euclidean 1-line center and problems. Proc. ISOLDE III, Boston, MA, 1984.

152. Loftsgaarden D. 0., Queensberry C. P. A nonparametric density function. Ann. Math. Stat. (1965) 36, 1049-1051.

153. Lueker G. S. A data structure for ortogonal range queries. Processing of the 19th Annual IEEE Symposium on Foundations of Computer Science. (1978), 28-34.

154. Lueker G. S., Willard D. E. A data structure for dynamic range queries. Inform. Processing Lett. (Dec. 1982) 15, № 5, 209-213.

155. Lum V. Y., Yuen P. S. T., Dodd M. Key-to-Address Transformation Techniques: A Fundamental Performance Study on Large Existing Formated Files. Commun. ACM (1971) 14, № 4, 228-239.ЛИТЕРАТУРА363

156. Manber U., Tompa M. Probabilistic, nondeterministic and alternating decision trees. Univ. Washington, Tech. Rep. 82-0301. 1982.

157. Maurer W. D., Lewis T. G. Hash table methods. Commputing Surveys (1975) 7, 5-20.

158. Morris R. Scatter storage techniques. Comm. ACM (1968) 11, № 1, 38-44.

159. Pavlidis T. Algorithms for Graphics and Image Processing. Springer-Verlag, Berlin, 1982.

160. Peterson W. W. Addressing for Random Access Storage. IBM J. Research & Development (1957) 1, 130-146.

161. Petri C. A. Introduction of general net theori. Lecture Notice in Computer Science. Springer-Verlag, Berlin, (1980) 84, 1-26.

162. Post E. L. Finite combinatory processes — formulation 1. J. Symbolic Logic (1936) 1, 103-105.

163. Prepaxata F. P., Shamos M. J. Computational Geometry. Springer-Verlag, New York, 1985.

164. Rabin M. 0. Proving simultaneous positivity o linear forms. J. Comput. Syst. Sci. (1972) 6, 639-650.

165. Reingold E. M. On the optimality of some set algorithms. J. ACM (Oct. 1972) 19, № 4, 649-659.

166. Saxe J. B. On the number of range queries in ¿-space. Discrete Applied Mathematics (1979) 1, 217-225.

167. Saxe J. B., Bentley J. L. Transforming static data structures into dynamic structures. Proc 20th IEEE Annu. Symp. Found. Comput. Sci. (Oct. 1979), 148-168.

168. Schay G.,Jr, Dauer F. W. A probabilistic model of a self-organizing file system. SIAM J. Appl. Math. (1967) 15, 874-888.ЛИТЕРАТУРА364

169. Schay G.,Jr, Spruth W. G. B. Analysis of a File Addressing Method. Comm. ACM (1962) 5, 459-462.

170. Seidel R. A method for lower bounds for certain geometric problems. Dep. Comput. Sci., Cornell Univ., Uthaca, NY, Tech. Rep. 84-592, Feb. 1984.

171. Shamos M. I. Geometric complexity. Proc. 7th ACM Annu. Symp. Theory Comput. (May 1975) 224-233.

172. Shamos M. I. Computational geometry. Ph. D. dissertation, Dep. Comput. Sci., Yale Univ., New Haven, CT, 1978.

173. Shamos M. I., Hoey D. Closest-point problems. Proc. 16th IEEE Annu. Symp. Found. Comput. Sci. (Oct. 1975) 151-162.

174. Shamos M. I., Hoey D. Geometric intersection problems. Proc. 17th IEEE Annu. Symp. Found. Comput. Sci. (Oct. 1976) 208215.

175. Steele J. M., Yao A. C. Lower bounds for algebraic decision trees. J. Algorith. (1982) 3, 1-8.

176. Turing A. M. On Computable Numbers, whis an Application to the Entsheidungsproblem. Proc. London Math. Soc. (1937) 42, Ser 2, 230-235.

177. Ullman J. D. A Note on the Efficiency of Hashing Functions. J ACM (1972) 19, 569-575.186. van Emde Boas P. On the il(nlogn) lower bound for convex hull and maximal vector determination. Inform. Processing Lett. (1980) 10, 132-136.

178. Willard D. E. Predicate-oriented database search algorithms. Ph. D. dissertation, Harvard Univ., Cambridge, MA, 1978.

179. Yao A. C. On the complexity of comparison problems using linear functions. Proc. 16th Annu. Symp. Theory Comput. (1975) 85-89.ЛИТЕРАТУРА 365

180. Yao А. С. A lower bound to finding convex hull. J. ACM. (1981) 28, 780-787.

181. Yao A. C., Rivest R. L. On the polyhedral decision problem. SIAM J. Comput. (1980) 9, 343-347.