Абстрактні типи даних
Абстрактні типи даних – типи даних, які розглядаються незалежно від способів їх подання або реалізації засобами мови програмування. Як і типи даних, абстрактні типи даних визначаються безліччю значень і сукупністю операцій, які можуть виконуватися над значеннями даного типу.
Математичний тип даних є компонентом багатоосновної алгебри даних, а абстракція означає, що алгебра даних розглядається з точністю до ізоморфізму. Наприклад, дані, які ми представляємо як "комплексне число", можуть бути визначені за допомогою операцій +, -, x, /, im, re, mod, arg, в той час як самі числа можуть представлятися по-різному за допомогою звичайних типів. Одним з таких уявлень буде пара дійсних чисел, що визначають дійсну та уявну частину, іншим – пара чисел, що визначають модуль та аргумент.
Основну роль абстрактні типи даних грають у методології програмування, що базується на покроковій розробці програм. На етапі побудови специфікації проектованої програми алгебра даних моделює об'єкти предметної області, у термінах яких формулюється завдання. У процесі покрокового уточнення дані конкретизуються шляхом переходу до проміжних уявлень доти, доки знайдено їх реалізацію з допомогою базової алгебри даних використовуваної мови програмування. Багато мов програмування мають підтримку технології покрокової розробки і, зокрема, використання абстрактних типів даних. У цьому основним засобом вважається захист описів абстрактних типів використання внутрішніх властивостей представлення даних. Це досягається тим, що обробка даних, які мають абстрактні типи, можлива лише за допомогою викликів функцій та процедур, які реалізують відповідні операції алгебри. Наприклад, абстрактні типи даних можуть реалізовуватися за допомогою поняття пакета, опис якого поділяється на видиму, невидиму та власну частину. Видима частина містить лише заголовки (специфікації) функцій, однозначно визначаючи типи операцій. Власна частина пакету містить повні описи функцій, підпрограм, із якими вони працюють, визначаючи реалізацію операцій абстрактної алгебри даних.
В теорії абстрактних типів даних досліджуються різні способи визначення незалежно від способів їх реалізації. Відомі три основні підходи:
- алгебраїчний, при якому використовуються методи завдання алгебр та алгебраїчних систем за допомогою утворюючих та визначальних співвідношень, тотожностей та квазітотожностей.
- аксіоматичний, який передбачає використання деякої формальної логічної мови для аксіоматичного визначення властивостей операцій та відносин.
- модельний, при якому елементи алгебри даних будуються явно, як даних структури над іншими, можливо, знову абстрактними алгебрами та типами даних, а операції визначаються, наприклад, рекурсивно або за допомогою функціональних рівнянь.
