При разработке программ и алгоритмов важным этапом является этап подбора математической абстракции для описания данных, используемых в формулировке задачи. Например, в случае поиска оптимальной стратегии для игры чет-нечет таким объектом была игра, в случае задачи об Ариадне и Тезее - лабиринт, в задаче о ходе коня - шахматная доска, в примере из лекции 16 - учреждение. Будем называть предстваление этих объектов-данных ввиде математических абстракций Абстрактными Структурами Данных (АСД). В случае игры в качестве АСД мы использовали дерево; в случае лабиринта - граф; в случае шахматной доски - матрицу.
Выбрав подходящую по своим математическим свойствам структуру АСД, мы приходим к другой проблеме - как представить выбранную АСД в терминах тех структур данных, с которыми умеет работать исполнитель алгоритмов, которые есть в испоьзуемом языке программирования. Назовем эти струтктуры данных Структурами Данных Хранения (СДХ). Например, в случае задачи об Ариадне и Тезее мы представили граф, представляющий лабиринт, в виде матрицы смежности, которую мы представили в виде соотвествующей СДХ - массива, для шахматной доски мы применили ту же структуру данных для хранения данных задачи, для учреждения - мы использовали запись.
Критерием выбора для АСД подходящей СДХ является эффективность операций над СДХ, являющихся аналогами соотвествующих операций над АСД. Под эффективностью мы понимаем сложность алгоритмов над СДХ.
Итак, мы приходим к следующей проблеме: задано АСД, набор СДХ; требуется построить отображение АСД -> СДХ так, чтобы сложность алгоритмов операций над СДХ, соотвествующих надлежащим оперциям над АСД, была бы минимальной.
2. Основные понятия и определения
Структура G на множестве M - это пара (R,M) где R это отношение порядка на множестве M.
Возможно вы искали - Реферат: Ссылочный тип данных. Динамические объекты.
Определение.
Отношение порядка на множестве M это подмножество множества M*M обладающее следующими свойствами:
1.a<=a - рефлективность;
2.если a<=b и b<=c, то a<=c - транзитивность;
3.если a<=b и b<=a, то a=b - антисимметричность.
Похожий материал - Реферат: Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод
Если отношение не обладает свойством антисимметричности, то оно называется предпорядком.
Определение.
Отношение порядка назывется линейным, если оно определено для любых a и b из M.
Определение.
Множество называется частично упорядоченным если на нем зафиксирован некоторый порядок.
Очень интересно - Реферат: Познание природы и логика
Примеры.
1. Множество натуральных чисел с отношением <=.
2. Множество слов в алфавите с отношением лексико-графического упорядочения.
3. Множество людей с отношением родства.
4. Множество людей с отношением начальник-подчиненный.
Вам будет интересно - Реферат: Математика в средние века
Для выбора и обозачения элементов на M используют индексацию I: I - это отображение M -> [ 1.. |M| ].
3. Абстрактные структуры данных.
Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф, дерево, стек, очередь, таблица.
3.1. Строка
Строка - конечное множество символов с отношением линейного прядка, определяющем следование символов в строке.
Примеры: текст, программа, формула.
Свойства строк:
Похожий материал - Реферат: О некоторых тенденциях развития математики
1.Переменная длина;
2.Обращеие к элементам строки в отношении порядка, а не индексации;
3.Строка может иметь дополнительную структуру, называемую синтаксис, но это дополнительная структура.
Типичные операции: