Сложность поиска в случайных базах данных

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