Структури даних

Структуры данных.

1. Постановка задачи.

Під час розробки програм, тож алгоритмів важливим етапом є етап добору математичної абстракції для описи даних, які у формулюванні завдання. Наприклад, у разі пошуку оптимальної стратегії для гри чіт-непара таким об'єктом була гра, у разі завдання про Аріадні і Тезеї - лабіринт, в завданню про перебіг коня — шахівниця, в прикладі з лекції 16 — установа. Будемо називати предстваление цих объектов-данных ввиде математичних абстракцій Абстрактними Структурами Даних (АСД). Що стосується гри акторів-професіоналів у ролі АСД ми використовували дерево; у разі лабіринту — граф; у разі шахівниці - матрицу.

Вибравши підходящу за своїми математичним властивостями структуру АСД, ми дійшли інші проблеми — як уявити обрану АСД в термінах тих структур даних, із якими вміє працювати виконавець алгоритмів, що є у испоьзуемом мові програмування. Назвемо ці струтктуры даних Структурами Даних Зберігання (СДХ). Наприклад, у разі завдання про Аріадні і Тезеї ми представили граф, що становить лабіринт, як матриці суміжності, що її подали вигляді соотвествующей СДХ — масиву, для шахівниці ми застосували таку ж структуру даних для зберігання даних завдання, закладу — ми використовували запись.

Критерієм вибору АСД підходящої СДХ є ефективність операцій над СДХ, є аналогами соотвествующих операцій над АСД. Під ефективністю ми розуміємо складність алгоритмів над СДХ.

Отже, ми дійшли наступній проблемі: поставлено АСД, набір СДХ; потрібно побудувати відображення АСД -> СДХ те щоб складність алгоритмів операцій над СДХ, соотвествующих належним оперциям над АСД, було б минимальной.

2. Основні поняття і определения

Структура G на безлічі M — це пара (R, M) де R цей показник порядку на безлічі M.

Определение.

Отношение порядку на безлічі M це підмножина безлічі M*M що має такими свойствами:

1.a.