Введение

Тема 1. Реляционная модель данных

• 1.1. Модели логической организации данных (60мин.)
• 1.2. Реляционная алгебра (89мин.)
• • 1.2.1. Булевы операции (30мин.)
  • 1.2.2. Оператор выбора (30мин.)
  • 1.2.3. Оператор проекции (30мин.)
  • 1.2.4. Оператор соединения (30мин.)
  • 1.2.5. Переименование атрибутов (30мин.)
  • 1.2.6. Реляционная алгебра (30мин.)
• 1.3. Функциональные зависимости (89мин.)
• 1.4. Полнота системы аксиом вывода (30мин.)
• Упражнения (60мин.)
• Тест:  Реляционная модель данных (24мин.)

Тема 2. Информационно-графовая модель данных

• 2.1. Основные понятия (417мин.)
• • 2.1.1. Задача информационного поиска (149мин.)
  • 2.1.2. Информационный граф (268мин.)
• Упражнения (30мин.)
• 2.2. Допустимость информационных графов (89мин.)
• • 2.2.1. Критерий допустимости информационных графов (60мин.)
• Упражнения (60мин.)
• 2.3. Полнота для информационных графов (89мин.)
• • 2.3.1. Критерий полноты базового множества (89мин.)
• Упражнения (30мин.)
• 2.4. Сложность информационных графов (238мин.)
• • 2.4.1. Алгоритм поиска, соответствующий информационному графу (30мин.)
  • 2.4.2. Меры сложности информационных графов (149мин.)
  • 2.4.3. Оптимальные информационные графы (60мин.)
• Упражнения (30мин.)
• 2.5. Простейшие нижние оценки сложности ИГ (89мин.)
• • 2.5.1. Мощностная нижняя оценка (60мин.)
  • 2.5.2. Случай оптимальности перебора (30мин.)
• Упражнения (30мин.)
• Тест:  Информационно-графовая модель данных (50мин.)

Тема 3. Поиск идентичных объектов

• 3.1. Бинарный поиск (60мин.)
• 3.2. Константный в среднем алгоритм поиска (179мин.)
• Упражнения (30мин.)
• 3.4. Константный в худшем случае алгоритм поиска (30мин.)
• 3.5. Теоремы Гасанова-Луговской об оценках памяти константного в худшем случае алгоритма поиска (149мин.)
• 3.6. Алгоритм Клыковой с константным в худшем случае временем поиска и линейной памятью (268мин.)
• Тест:  Поиск идентичных объектов (24мин.)

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

• 4.1. Теорема Гасанова о существовании древовидного оптимального ИГ для задач поиска с коротким ответом (238мин.)
• 4.2. Теорема Гасанова о нижней оценке сложности ИГ для задач поиска c коротким ответом и равновероятными тенями записей (209мин.)
• Упражнения (30мин.)
• Тест:  Задачи поиска с коротким ответом (22мин.)

Тема 5. Включающий поиск

• 5.1. Задачи поиска на частично-упорядоченных множествах данных (60мин.)
• 5.2. Включающий поиск (119мин.)
• Упражнения (30мин.)
• 5.4. Теорема Гасанова о нижней оценке сложности включающего поиска (119мин.)
• 5.5. Верхняя оценка сложности включающего поиска (89мин.)
• 5.6. Асимптотика функции Шеннона сложности включающего поиска (30мин.)
• 5.7. Теорема Гасанова об асимптотике функции Шеннона включающего поиска в классе древовидных ИГ (179мин.)
• Тест:  Включающий поиск (22мин.)

Тема 6. Одномерный интервальный поиск

• 6.1. Случай базового множества характеристических функций (30мин.)
• 6.2. Случай базового множества интервальных функций (209мин.)
• 6.3. Логарифмический поиск (60мин.)
• 6.4. Сверхлогарифмический поиск (149мин.)
• 6.5. Мгновенное решение (89мин.)
• Тест:  Одномерный интервальный поиск (18мин.)

Тема 7. Функциональная сложность двумерной задачи о доминировании

• 7.1. Двумерная задача о доминировании (60мин.)
• 7.2. Вспомогательные структуры (89мин.)
• 7.3. Метод сеток Бентли — Маурера (89мин.)
• Тест:  Функциональная сложность двумерной задачи о доминировании (20мин.)

Литература

Завершение курса

• Тест:  Итоговое тестирование (40мин.)