Реферат программирование линейных и разветвляющих алгоритмов

В информатикеабстрактный тип данных (ADT) — это математическая модель для типов данных. Абстрактный тип данных определяется его поведением (семантикой) с точки зрения пользователя, данных. В частности. С точки зрения возможных значений. Возможных операций над данными этого типа и поведения этих операций. Эта математическая модель контрастирует со структурами данных, которые являются конкретными представлениями данных и являются точкой зрения исполнителя. А не пользователя.

Формально АДТ можно определить как это аналогично алгебраической структуре в математике. То, что подразумевается под аксиоматическая (алгебраическая) спецификация

и абстрактная модель; они соответствуют аксиоматической семантике и операционной семантике абстрактной машинысоответственно. Некоторые авторы также включают вычислительную сложность (На практике многие распространенные типы данных не являются ADT. Так как абстракция не идеальна. И пользователи должны знать о таких проблемах. Как арифметическое переполнение, которое связано с представлением. Например, целые числа часто хранятся в виде значений фиксированной ширины (32-битные или 64-битные двоичные числа) и поэтому испытывают переполнение целых чисел при превышении максимального значения.

АДЦ являются теоретическим понятием в информатике. Используемым при проектировании и анализе алгоритмов, структур данных и программных систем . И не соответствуют специфическим особенностям компьютерных языков—основные компьютерные языки непосредственно не поддерживают формально определенные АДЦ. Тем не менее. Различные языковые функции соответствуют определенным аспектам ADTS и легко путаются с собственно ADTS; они включают абстрактные типы, непрозрачные типы данных, протоколыи дизайн по контракту. АДЦ были впервые предложены Барбарой Лисковой и Стивеном Н. Зиллом в 1974 году в рамках разработки

CLU язык.

Например, целые числа являются АДТ, определяемые как значения …, -2, -1, 0, 1, 2, …. И с помощью операций сложения, вычитания. Умножения и деления. Вместе с больше чем. Меньше чем и т. п.. Которые ведут себя в соответствии с привычной математики (с осторожностью для целочисленного деления), независимо от того. Как целые числа представлены в компьютере. [a] В явном виде Обычно целые числа представляются в структуре данных в виде двоичных чисел, чаще всего как дополнение к двум, но может быть двоично-десятичным или в дополнениик единицам . Но пользователь абстрагируется от конкретного выбора представления и может просто использовать данные в качестве типов данных.

АЦП состоит не только из операций. Но и из значений исходных данных и ограничений на операции.

Например. Абстрактный стек, представляющий собой структуру pushвставкой элемента данных в стек; popудалением из него элемента данных; и peekили topобращением к элементу данных поверх стека без удаления. Абстрактная очередь, которая является структурой enqueue, которая вставляет элемент данных в очередь; dequeue, которая удаляет из нее первый элемент данных; и front, который обращается и обслуживает первый элемент данных в очереди. Не было бы никакого способа дифференцировать эти два типа данных. Если бы не было введено математическое ограничение. Которое для стека указывает. Что каждый pop всегда возвращает самый последний выталкиваемый элемент. Который еще не был выталкиваем. Анализируя эффективность алгоритмов. Использующих стеки. Можно также указать. Что все операции занимают одно и то же время независимо от того. Сколько элементов данных было помещено в стек. И что стек использует постоянный объем памяти для каждого элемента.

Абстрактные типы данных — это чисто теоретические сущности. Используемые (среди прочего) для упрощения описания абстрактных алгоритмов. Классификации и оценки структур данных. А также для формального описания систем типов языков программирования. Однако ADT может быть реализован конкретными типами данных или структурамиданных многими способами и на многих языках программирования или описан на языке формальной спецификации. ADT часто реализуются в виде модулей: интерфейс модуля объявляет процедуры. Соответствующие операциям ADT. Иногда с комментариями, описывающими ограничения. Этот стратегия сокрытия информации позволяет изменять реализацию модуля. Не нарушая работу клиентских программ.

Термин абстрактный тип данных также может рассматриваться как обобщенный подход ряда алгебраических структур, таких как решетки. Группы и кольца.[4] Понятие абстрактных типов данных связано с понятием абстракции данных, важной в объектно-ориентированном программировании и проектировании контрактными методологиями разработки программногообеспечения [5].]

Определение абстрактного типа данных

Абстрактный тип данных определяется как математическая модель объектов данных. Составляющих тип данных. А также функций. Работающих с этими объектами. Нет никаких стандартных соглашений для их определения. Можно провести широкое разделение между

Определение императивного стиля

В философии императивных языков программирования абстрактная структура данных понимается как сущность. Которая изменчива—это означает. Что она может быть индифферентными состояниями в разное время. Некоторые операции могут изменить состояние ADT; поэтому важен порядок. В котором операции оцениваются. И одна и та же операция над одними и теми же сущностями может иметь различные эффекты. Если выполняется в разное время—так же. Как инструкции компьютера или команды и процедуры императивного языка. Чтобы подчеркнуть это мнение. Принято говорить. Что операции выполняются или применяются, а не оценивались. Императивный стиль часто используется при описании абстрактных алгоритмов. (Подробнее см. )

Абстрактная переменная

Императивные определения ADT часто зависят от понятия абстрактной переменной, которую можно рассматривать как простейшую нетривиальную ADT. Абстрактная переменная V является изменяемой сущностью. Допускающей две операции:

  • store(V, x) где xзначение неопределенной природы;
  • fetch(V), что дает значение,

с тем ограничением, что

  • fetch(V) всегда возвращает значение x , используемое в самой последней storeоперации (V, x) с той же переменной V.

Как и во многих других языках программирования. Операция store(V, x) часто пишется Vx (или какая-либо аналогичная нотация), и fetch(V) подразумевается всякий раз. Когда переменная V используется в контексте. Где требуется значение. Так, например, VV + 1 обычно понимается как сокращение для store(V,fetch(V) + 1).

В этом определении неявно предполагается. Что хранение значения в переменной U не влияет на состояние отдельной переменной V. Чтобы сделать это предположение явным. Можно было бы добавить ограничение. Которое

  • если U и V-различные переменные. Последовательность { store(U, x); store(V, y) } эквивалентна { store(V, y); store(U, x) }.

В более общем смысле определения ADT часто предполагают. Что любая операция. Изменяющая состояние одного экземпляра ADT. Не влияет на состояние любого другого экземпляра (включая другие экземпляры того же ADT) — если только аксиомы ADT не подразумевают. Что эти два экземпляра связаны (псевдонимы) в этом смысле. Например, при расширении определения абстрактной переменной для включения абстрактных записейоперация . Которая выбирает поле из переменной записи R, должна дать переменную V, которая является алиасом этой части R.

Определение абстрактной переменной V может также ограничивать сохраненные значения x членами определенного набора X, называемого диапазоном или типом V. Как и в языках программирования. Такие ограничения могут упростить описание и анализ алгоритмови улучшить их читабельность.

Обратите внимание . Что это определение ничего не подразумевает о результате вычисления fetch(V), когда V не инициализируется, то есть перед выполнением любой storeоперации над V. Алгоритм. Который делает это. Обычно считается недействительным. Потому что его эффект не определен. (Однако есть несколько важных алгоритмов. Эффективность которых сильно зависит от предположения. Что такое a fetchявляется законным и возвращает некоторое произвольное значение в диапазоне переменной.[требуется цитирование])

Создание экземпляра

Некоторые алгоритмы должны создавать новые экземпляры некоторых ADT (например. Новые переменные или новые стеки). Для описания таких алгоритмов обычно включают в определение ADT createоперацию (). Которая дает экземпляр ADT. Обычно с аксиомами. Эквивалентными

  • результат createфункции () отличается от любого экземпляра. Используемого алгоритмом.

Эта аксиома может быть усилена. Чтобы исключить также частичное сглаживание с другими экземплярами. С другой стороны. Эта аксиома все еще позволяет реализациям createфункции () получить ранее созданный экземпляр. Который стал недоступным для программы.

Пример: абстрактный стек (императив)

В качестве другого примера определение абстрактного стека в императивном стиле может указывать. Что состояние стека S может быть изменено только операциями

  • push(S, x), где x — некоторая величина неопределенного характера;
  • pop(S), что в результате дает значение,

с ограничением, что

  • Для любого значения x и любой абстрактной переменной Vпоследовательность операций { push(S, x); Vpop(S) } эквивалентна Vx.

Поскольку присвоение Vxпо определению не может изменить состояние S, это условие подразумевает. Что Vpop(S) восстанавливает S в состояние . Которое было до push(S, x). Из этого условия и из свойств абстрактных переменных следует, например. Что последовательность

{ push(S, x); push(S, y); Upop(S); push(S, z); Vpop(S); Wpop(S

где x, yи z-любые значения, а U, V, W-попарно различные переменные. Эквивалентно

{ Uy; Vz; Wx

Здесь неявно предполагается. Что операции над экземпляром стека не изменяют состояние любого другого экземпляра ADT. Включая другие стеки. ,

  • Для любых значений x, yи любых различных стеков S и Tпоследовательность { push(S, x); push(T, y) } эквивалентна { push(T, y); push(S, x) }.

Абстрактное определение стека обычно включает также булевозначную функцию empty(Ы) и createоперацию (). Возвращающую экземпляр стека. С аксиомами. Эквивалентными

  • create() ≠ S для любого предыдущего стека S (вновь созданный стек отличается от всех предыдущих стеков);
  • empty(create()) (вновь созданный стек пуст);
  • not empty(push(S, x)) (толкая что-то в стопку. Вы делаете ее непустой).

Стиль одного экземпляра

Иногда ADT определяется так. Как если бы во время выполнения алгоритма существовал только один его экземпляр. И все операции были применены к этому экземпляру. Который явно не обозначен. Например. Абстрактный стек выше можно было бы определить с помощью операций push(x) и pop(), которые работают с единственным существующим стеком. Определения ADT в этом стиле можно легко переписать. Чтобы допустить несколько сосуществующих экземпляров ADT. Добавив явный параметр экземпляра (например, S в предыдущем примере) к каждой операции. Которая использует или изменяет неявный экземпляр.

С другой стороны. Некоторые ADT не могут быть осмысленно определены без принятия нескольких экземпляров. Это тот случай. Когда одна операция принимает в качестве параметров два различных экземпляра ADT. В качестве примера рассмотрим дополнение определения абстрактного стека операцией compare(S, T), которая проверяет. Содержат ли стеки S и T одни и те же элементы в одном и том же порядке.

Определение функционального стиля

Другой способ определения ADT. Более близкий к духу функционального программирования, заключается в рассмотрении каждого состояния структуры как отдельной сущности. В этом представлении любая операция. Модифицирующая ADT. Моделируется как математическая функция, которая принимает старое состояние в качестве аргумента и возвращает новое состояние как часть результата. В отличие от императивных операций. Эти функции не имеют побочных эффектов. Поэтому порядок их вычисления не имеет значения. И одна и та же операция. Примененная к одним и тем же аргументам (включая одни и те же входные состояния). Всегда будет возвращать одни и те же результаты (и выходные состояния).

В частности. В функциональном представлении нет способа (или необходимости) определять fetchstoreопераций с и). Вместо того чтобы хранить значения в переменных. Их передают в функции в качестве аргументов.

Пример: абстрактный стек (функциональный)

Например. Полное функциональное определение абстрактного стека может использовать следующие три операции:

  • push: принимает состояние стека и произвольное значение. Возвращает состояние стека;
  • top: принимает состояние стека. Возвращает значение;
  • pop: принимает состояние стека. Возвращает состояние стека.

В определении функционального стиля нет необходимости в createоперации. Действительно. Нет понятия Состояния стека можно рассматривать как потенциальные состояния одной структуры стека. А состояния двух стеков. Содержащие одинаковые значения в одном и том же порядке. Считаются идентичными состояниями. Это представление фактически отражает поведение некоторых конкретных реализаций. Таких как связанные списки с хэш-минусами.

Вместо create() функциональное определение абстрактного стека может предполагать существование специального состояния стека, пустого стека, обозначаемого специальным символом . Таким как Λ или bottomоперацию (). Которая не принимает аргументов и возвращает это специальное состояние стека. Обратите внимание. Что аксиомы подразумевают. Что

  • push(Λ, x) ≠ Λ.

В функциональном определении стека не требуется emptyпредикат: вместо этого можно проверить. Пуст ли стек, проверив. Равен ли он Λ.

Обратите внимание. Что эти аксиомы не определяют эффект top(s) или pop(s), если только s не является состоянием стека. Возвращаемым a push. Поскольку pushоставляет стек непустым, эти две операции не определены (следовательно, недопустимы) при s = Λ. С другой стороны, аксиомы (и отсутствие побочных эффектов) подразумевают , что push(s, x) = push(t, y) тогда и только тогда. Когда x = y и s = t.

Как и в некоторых других областях математики. Принято также считать. Что состояния стека являются только теми. Существование которых можно доказать из аксиом в конечном числе шагов. В приведенном выше примере абстрактного стека это правило означает. Что каждый стек представляет собой конечную последовательность значений. Которая становится пустым стеком (Λ) после конечного числа pops. Сами по себе вышеприведенные аксиомы не исключают существования бесконечных стеков (которые могут быть popбесконечны. Каждый раз давая другое состояние) или круговых стеков (которые возвращаются в одно и то же состояние после конечного числа popс). В частности. Они не исключают состояния s, такие что pop(s) = s или push(s, x) = s для некоторого x. Однако, поскольку невозможно получить такие состояния стека с заданными операциями. Предполагается. Что они

Следует ли включать сложность

Помимо поведения в терминах аксиом. В определение операции ADT также можно включить их алгоритмическую сложность. Александр Степанов, дизайнер стандартной библиотеки шаблонов C++, включил гарантии сложности в спецификацию STL. Аргументируя это тем, что:

Причина введения понятия абстрактных типов данных заключалась в возможности взаимозаменяемости программных модулей. У вас не может быть взаимозаменяемых модулей. Если эти модули не имеют схожего поведения сложности. Если я заменю один модуль другим модулем с тем же функциональным поведением. Но с другой сложностью. Пользователь этого кода будет неприятно удивлен. Я мог бы сказать ему все. Что мне нравится об абстракции данных. И он все равно не захотел бы использовать код. Утверждения сложности должны быть частью интерфейса.

Александр Степанов[6]

Преимущества абстрактного ввода данных

Инкапсуляция

Абстракция дает обещание. Что любая реализация ADT обладает определенными свойствами и способностями; знание этого-все. Что требуется для использования объекта ADT.

Локализация изменений

Код, использующий объект ADT. Не будет нуждаться в редактировании. Если реализация ADT будет изменена. Поскольку любые изменения в реализации должны по-прежнему соответствовать интерфейсу, а код. Использующий объект ADT. Может ссылаться только на свойства и возможности. Указанные в интерфейсе. Изменения могут быть внесены в реализацию без необходимости каких-либо изменений в коде. Где используется ADT.

Гибкость

Различные реализации ADT. Имеющие все те же свойства и возможности. Эквивалентны и могут использоваться несколько взаимозаменяемо в коде. Использующем ADT. Это дает большую гибкость при использовании объектов ADT в различных ситуациях. Например, различные реализации ADT могут быть более эффективными в различных ситуациях; можно использовать каждую в ситуации. Когда они предпочтительнее. Тем самым повышая общую эффективность.

Типичные операции

Некоторые операции. Которые часто задаются для ADTS (возможно. Под другими именами)

  • compare(s, t), который проверяет. Являются ли состояния двух экземпляров эквивалентными в некотором смысле;
  • hash(s), который вычисляет некоторую стандартную хэш-функцию из состояния экземпляра;
  • print(s) или show(s), которые создают удобочитаемое человеком представление состояния экземпляра.

В императивных определениях ADT часто можно найти также

  • create(), что приводит к новому экземпляру ADT;
  • initialize(s), который подготавливает вновь созданный экземпляр s для дальнейших операций или сбрасывает его в некоторое
  • copy(s, t), что переводит экземпляр s в состояние. Эквивалентное состоянию t;
  • clone(t), который выполняет screate(), copy(s, t) и возвращает s;
  • free(s) или destroy(s), которые восстанавливают память и другие ресурсы. Используемые s.

Эта freeоперация обычно не является релевантной или значимой. Поскольку АЦП-это теоретические объекты. Которые не Однако это может быть необходимо. Когда нужно проанализировать хранилище. Используемое алгоритмом. Использующим ADT. В этом случае нужны дополнительные аксиомы. Которые определяют. Сколько памяти использует каждый экземпляр ADT в зависимости от его состояния и сколько из них возвращается в пул free.

Вот некоторые распространенные АЦП. Которые оказались полезными в самых разнообразных приложениях:

Каждый из этих ADT может быть определен многими способами и вариантами. Не обязательно эквивалентными. Например. Абстрактный стек может иметь или не иметь countоперацию. Которая сообщает. Сколько элементов было выдвинуто и еще не выскочило. Этот выбор имеет значение не только для его клиентов. Но и для реализации.

Абстрактный графический тип данных

Расширение ADT для компьютерной графики было предложено в 1979 году:[7] абстрактный графический тип данных (AGDT). Его представили Надя Маньенат Тельмани Даниэль Тельман. AGDTs предоставляют преимущества ADTS с возможностями построения графических объектов структурированным способом.

Реализация ADT означает предоставление одной процедуры или функции для каждой абстрактной операции. Экземпляры ADT представлены некоторой конкретной структурой данных, которая управляется этими процедурами в соответствии со спецификациями ADT.

Обычно существует множество способов реализации одного и того же ADT с использованием нескольких различных конкретных структур данных. Так, например. Абстрактный стек может быть реализован связанным списком или массивом.

Чтобы клиенты не зависели от реализации. ADT часто упаковывается как непрозрачный тип данных в один или несколько модулей, интерфейс которых содержит только сигнатуру (количество и типы параметров и результатов) операций. Реализация модуля. А именно тела процедур и конкретная используемая структура данных. Может быть скрыта от большинства клиентов модуля. Это позволяет изменить реализацию. Не затрагивая клиентов. Если реализация открыта. Она называется прозрачным типом данных.

При реализации ADT каждый экземпляр (в определениях императивного стиля) или каждое состояние (в определениях функционального стиля) обычно представляются каким-либо дескриптором.]

Современные объектно-ориентированные языки. Такие как C++ и Java, поддерживают некоторую форму абстрактных типов данных. Когда класс используется в качестве типа. Это абстрактный тип. Который ссылается на скрытое представление. В этой модели ADT обычно реализуется как класс, и каждый экземпляр ADT обычно является объектом этого класса. Интерфейс модуля обычно объявляет конструкторы как обычные процедуры. А большинство других операций ADT-как методы из этого класса. Однако такой подход не позволяет легко инкапсулировать несколько репрезентативных вариантов. Найденных в ADT. Это также может подорвать расширяемость объектно-ориентированных программ. В чистой объектно-ориентированной программе. Использующей интерфейсы в качестве типов. Типы относятся к поведению. А не к представлениям.

Пример: реализация абстрактного стека

В качестве примера приведем приведенную выше реализацию абстрактного стека на языке программирования Си.

Императивный интерфейс

Интерфейс императивного стиля может быть:

определение типа структуры stack_Rep stack_Rep; // тип: стопка инстанции представительство (непрозрачный записи) определение типа stack_Rep* stack_T; // тип: дескриптор стека экземпляр (непрозрачный указатель) ьурейее недействительным* stack_Item; // тип значения. Хранящегося в стеке экземпляр (произвольный адрес) stack_T stack_create(недействительным); // создает новый пустой стек инстанции недействительным stack_push(stack_T с, stack_Item х); // добавление элемента в вершину стека stack_Item stack_pop(stack_T ов); // удаляет верхний элемент из стека и возвращает его значение bool stack_empty(stack_T ов); // проверяет. Является ли стек пустым 

Этот интерфейс может быть использован следующим образом:

#включают  // содержит стек интерфейс stack_T с = stack_create(); // создает пустой стек экземпляра типа int х = 17; stack_push(с, &х); // добавляет адрес X в вершину стека пустоту* г = stack_pop(ы); // удаляет адресу X из стека и возвращает его , если (stack_empty(ов)) { } // делает что-то. Если стек пуст 

Этот интерфейс может быть реализован многими способами. Реализация может быть произвольно неэффективной. Поскольку формальное определение ADT. Приведенное выше. Не определяет. Сколько места может использовать стек и сколько времени должна занимать каждая операция. Он также не указывает, продолжает ли существовать состояние стека s после вызова xpop(s).

На практике в формальном определении должно быть указано. Что пространство пропорционально количеству элементов. Выталкиваемых и еще не выскочивших; и что каждая из вышеперечисленных операций должна завершаться за постоянное количество времени. Независимо от этого числа. Чтобы соответствовать этим дополнительным спецификациям. Реализация может использовать связанный список или массив (с динамическим изменением размера) вместе с двумя целыми числами (количество элементов и размер массива).

Функциональный интерфейс

Определения ADT функционального стиля более подходят для функциональных языков программирования. И наоборот. Однако можно обеспечить функциональный интерфейс даже на императивном языке. Таком как C. Например:

определение типа структуры stack_Rep stack_Rep; // тип: стопка государственного представительства (непрозрачный записи) определение типа stack_Rep* stack_T; // тип: дескриптор стека государства (непрозрачный указатель) ьурейее недействительным* stack_Item; // тип: значение из стека состояния (произвольный адрес) stack_T stack_empty(недействительными); // возвращает пустой стек государственной stack_T stack_push(stack_T с, stack_Item х); // добавляет элемент в верхней части стека состояния и возвращает получившуюся стопку государственной stack_T stack_pop(stack_T ов); // удаляет верхний элемент из стека состояния и возвращает получившуюся стопку государственной stack_Item stack_top(stack_T ов); // возвращает верхний элемент стека государства 

Библиотеки ADT

Многие современные языки программирования. Такие как C++ и Java. Поставляются со стандартными библиотеками. Реализующими несколько общих ADT. Таких как перечисленные выше.

Встроенные абстрактные типы данных

Спецификация некоторых языков программирования намеренно расплывчата относительно представления определенных встроенных типов данных. Определяя только операции. Которые могут быть выполнены над ними. Поэтому эти типы можно рассматривать как Примерами могут служить массивы во многих скриптовых языках. Таких как Awk, Luaи Perl, которые можно рассматривать как реализацию абстрактного списка.

  1. ^
  1. ^ Rudolf Lidl (2004). Абстрактная алгебра. Спрингер. ISBN 978-81-8128-149-4., Глава 7, раздел 40.
  2. ^ — Что Такое Объектно-Ориентированное Программирование?. Найм | Upwork. 2015-05-05. 2016-10-28.
  3. ^ Стивенс, Эл (март 1995). . Дневник доктора Добба. Получено 31 января 2015года .
  4. ^ D. Thalmann. N. Magnenat Thalmann (1979). Проектирование и реализация абстрактных графических типов данных. IEEE. doi:10.1109/CMPSAC.1979.762551., Proc. 3-я Международная конференция по компьютерному программному обеспечению и приложениям (COMPSAC’79), IEEE. Чикаго, США. Стр. 519-524
  5. ^ Роберт Седжвик (1998). Алгоритмы в С. Эддисон/Уэсли. ISBN 978-0-201-31452-6., определение 4.4.
  • Лисков, Барбара; Циллес, Стивен (1974). Материалы симпозиума ACM SIGPLAN по языкам очень высокого уровня. — Замечает СИГПЛАН. 9. с. 50-59. CiteSeerX 10.1.1.136.3043. doi:10.1145/800233.807045.
  • Dale, Nell; Walker, Henry M. (1996). Абстрактные типы данных: Спецификации. Реализации и приложения. Джонс и Бартлетт Учатся. ISBN 978-0-66940000-7.

Дальнейшее чтение

Внешние ссылки