Теория баз данных

Description

Курс лекций. - М.: МГУ им. М. В. Ломоносова, Кафедра математической теории интеллектуальных систем Информационно-графовая модель данных. Критерий допустимости информационных графов (ИГ). Критерий полноты базового множества. Сложность информационных графов. Теорема о существовании оптимальных ИГ. Мощностная нижняя оценка. Случай оптимальности перебора. Задача поиска идентичных объектов. Константный в среднем алгоритм поиска идентичных объектов. Оценки памяти константного в худшем случае алгоритма поиска идентичных объектов. Задачи поиска с коротким ответом. Древовидность оптимальных информационных графов для задач поиска с коротким ответом. Нижняя оценка сложности задач поиска с коротким ответом в случае равновероятных теней записей. Одномерная задача интервального поиска. Линейный по памяти непереборный алгоритм решения двумерной задачи интервального поиска. Задача включающего поиска. Нижняя оценка сложности включающего поиска. Асимптотика функции Шеннона сложности включающего поиска. Нижняя оценка сложности включающего поиска в классе древовидных схем. Асимптотика функции Шеннона сложности включающего поиска в классе древовидных схем.