Аннотация:В дипломной работе А.А.Пушкарева исследуется проблема ускорения процесса поиска информации за счет решения вместо требуемой задачи информационного поиска некоторого ее приближения. При этом при решении приближенной задачи в ответе могут появиться лишние элементы данных, т.е. не удовлетворяющие исходной задаче и называемые шумом, и некоторые нужные элементы данных могут в ответ не попасть (потери данных).
В работе два раздела. В первом разделе показывается, что такая операция как расширение отношения поиска, которая обычно приводит к увеличению времени поиска, может в некоторых случаях приводить к ускорению поиска.
Во втором разделе рассматривается задача о метрической по Евклиду близости, приводятся два приближенных алгоритма решения этой задачи, и оцениваются такие характеристики этих алгоритмов, как объем требуемой памяти, средняя величина шума, время поиска в среднем и в худшем случае. В частности, второй алгоритм имеет следующие характеристики: объем памяти линейно зависит от размера базы данных, средний шум пропорционален длине ответа, время поиска в худшем случае (помимо перечисления ответа) равно константе.