Использование абстракций при разработке алгоритмов

Использование абстракций при разработке алгоритмов

Предмет: Технология разработки программных продуктов.

Тема : Фазы процесса разработки ПО. Абстракции.

Ознакомление с фазами процесса разработки ПО. Абстракции.

Развивать умение слушать других, делать выводы и обобщать полученные знания

Воспитывать чувство значимости предмета в профессиональной деятельности, аккуратности в работе

— Основы алгоритмизации и программирования

Оборудование: доска, мел, письменные принадлежности, проектор, ПК

Тип урока: комбинированный

Метод обучения: Объяснительно иллюстративный

— Проверка готовности кабинета

2. Постановка цели урока

3.Повторение пройденного материала

Выбор архитектуры программного обеспечения

4.Сообщение новых знаний

Технология разработки ПО

Требования к современным технологиям разработки ПО

Этапы проектирования сложных программных средств

Использование абстракций и спецификаций при разработке программ

5. Восприятие и осознание учащимися нового материала

6. Осмысление обобщение и систематизация знаний

7. Подведение итогов урока и постановка домашнего задания

Выучить содержимое темы

Орлов С.А. стр. С.36-40

Ответить на вопросы:

1.2. Технология разработки ПО

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

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

1.3. Требования к современным технологиям разработки ПО

1.4. Этапы проектирования сложных программных средств

В литературе широко используется понятие «жизненный цикл программного обеспечения», включающее в себя все этапы его развития от возникновения потребности в программном изделии до прекращения его использования вследствие морального старения или потери необходимости в программном продукте. По длительности жизненного цикла все программы можно разделить на две группы:

1) программы с малой длительностью эксплуатации – создаются в основном для решения научных и инженерных задач, для получения конкретных результатов вычислений; они содержат от 1 до 10000 команд, разрабатываются одним специалистом или малой группой, не предназначены для тиражирования и передачи; жизненный цикл таких программ не превышает 3-х лет, время эксплуатации практически равно 0;

2) программы с большой длительностью эксплуатации – создаются для регулярной обработки информации и управления; такие программы содержат от 1 до 1000000 команд, обладают свойством независимости от разработчика, возможностью модификации в процессе сопровождения и использования различными программистами, допускают тиражирование, сопровождаются документацией как промышленное изделие, являются отчуждаемыми; жизненный цикл таких программ составляет 10 – 20 лет, из них 70 – 90 % занимает время эксплуатации.

Все последующее изложение ориентировано на ПО второй группы.

Жизненный цикл любой программной системы начинается с определения требований к ней для конкретного набора пользователей и заканчивается эксплуатацией системы этими пользователями в рамках их собственного окружения и состоит из фаз разработки. Общепринятыми являются следующие фазы разработки ПО.

Фаза жизненного цикла

Стадия разработки
по ГОСТ 19.102-77 ЕСПД

Состояние ПО
в конце фазы

Источник

Многоуровневая абстракция

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

Данная статья содержит лишь теорию. Практической будет следующая статья (постараюсь чередовать).

Многоуровневая абстракция

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

Зачем вообще делят на уровни абстракции?

1. Борьба со сложностью. На каждом уровне применяются методы именно данного уровня.
2. Уменьшение связности.
3. Обеспечение взаимозаменяемости классов на всех уровнях кроме верхнего.

Многоуровневая абстракция работы с данными

Идем по убыванию уровня абстракции:
* Класс-сущность реального мира
* Провайдер данных
* Реальные библиотеки работы с данными

Когда возникают проблемы?

1. Обычно в одном проекте несколько многоуровневых абстрактных моделей. Проблемы возникают если несколько абстрактных моделей надо подвергнуть однообразным изменениям. При этом приходится вносить изменения во все промежуточные уровни абстракции включая верхний.
2. При прототипировании накладные расходы на проектирование многоуровневой абстрактной модели могут быть слишком высоки и возможно написание временного кода без уровней абстракции, который придется выкинуть после утверждения прототипа.
3. Абстракция от источников данных может породить (и порой порождает) неоптимальную работу с источниками данных.

Что делать?

Кодогенерация во многих случаях (не всегда) может заменить многоуровневую абстракцию. При этом будут генерироваться конечные классы (из верхнего уровня абстракции), содержащие в себе методы работы с выбранным источником данных.
1. Имея в основе метаданные, мы можем вносить изменения в алгоритмы генерации кода и разом модифицировать всю модель.
2. При наличии метаданных прототип модели можно получить в кратчайший срок.
3. За счет наличия генераторов для каждого источника данных, модель будет сгенерирована с приемлемой оптимальностью работы с выбранным источником данных, учитывая его специфику.

Чем кодогенерация может помочь в сложных моделях

Сложные приложения всегда задают много вопросов. По моим наблюдениям, на бОльшую часть из них можно ответить еще в процессе разработки (например, на сайте нужно кеширование или нет; какая операционная система будет на сервере; использовать буфферизацию вывода или нет. ). Если мы ответим на этим вопросы заранее — мы можем избежать лишней сложности программы, лишних действий, лишних проверок и т.п. Более того, кодогенератор сам может собрать в среде назначения некоторые данные заранее, которые он может использовать для оптимизации работы.

Но это не значит, что меньше результирующего кода = проще система. Кодогенератор сам должен быть достаточно качественный для того, чтобы генерировать качественный код.

Кодогенерация + многоуровневая абстрактная модель

В следующей статье мы разработаем определенный несложный кодогенератор.

Источник

Использование абстракций и спецификаций при разработке программ

3.1. Общие положения

Эффективным способом борьбы со сложностью разрабатываемой программной системы является декомпозиция – разбиение программы на ряд независимых подпрограмм – модулей, которые сообща выполняют требуемую функцию. Требование к подзадачам при декомпозиции задачи:

1) каждая подзадача имеет один и тот же уровень рассмотрения;

2) каждая подзадача может быть решена независимо;

3) полученные решения могут быть объединены вместе.

Эффективным способом декомпозиции является абстракция – игнорирование ряда подробностей для сведения задачи к более простой.

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

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

Можно определить два различных вида абстракции, каждый из которых использует оба способа абстракции:

1) процедурная абстракция (ПА) позволяет расширить заданную некоторым языком виртуальную машину новой операцией;

2) абстракция данных (АД) позволяет добавить к виртуальной машине новые типы данных, состоящие из набора объектов и набора операций, характеризующих поведение этих объектов.

3.2. Процедурная абстракция

3.2.1. Понятие и преимущества процедурной абстракции

Процедура выполняет преобразование входных параметров в выходные.

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

Процедура объединяет в себе абстракцию через параметризацию и абстракцию через спецификацию, т.к. абстрагирует отдельную операцию. В АП мы абстрагируемся от конкретных используемых данных. АП определяется в терминах формальных параметров. Фактические данные связываются с этими параметрами при использовании абстракции. Значения конкретных данных несущественны, важны лишь их количество и тип.

Параметризация позволяет обобщить модуль, в результате чего уменьшается размер программы и, следовательно, объем модификаций.

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

Локальность – возможность реализации абстракции без необходимости анализа реализации какой-либо другой абстракции. Принцип локальности позволяет создавать программу из абстракций, созданных различными программистами, работающими независимо друг от друга.

Модифицируемость – изменения в реализации абстракции не влияют на программу в целом, если спецификации абстракций остаются прежними.

3.2.2. Спецификация процедурной абстракции

Спецификации могут быть формальными и неформальными. Формальные спецификации имеют точно определенное значение. Неформальные спецификации легче читать и понимать, но точное их содержание не всегда может быть установлено. Считается, что языком спецификаций может быть язык более высокого уровня, чем тот, на котором должна быть написана программа. Для спецификации программ будем использовать язык CLU (cluster) – предвестник языка АДА.

Спецификация процедуры состоит из заголовка и описания функции. Заголовок содержит имя процедуры, количество, порядок и типы входных и выходных параметров. Информация в заголовке чисто синтаксическая. В семантической части описывается смысл выполняемых процедурой действий на естественном языке, возможно расширенном привычными математическими обозначениями. Семантическая часть спецификации состоит из трех предложений: requires (требует), modifies (модифицирует), effects (выполняет). Предложения requires и modifies могут быть опущены. Шаблон спецификации процедурной абстракции:

Pname=proc(входные параметры) returns(выходные параметры)

requires список ограничений

modifies список модифицируемых входных параметров

effects описание работы процедуры

Предложение requires задает ограничения, накладываемые на абстракцию, и необходимо, если процедура является частичной (ее поведение определено для некоторого набора входных данных). Если процедура является общей (ее поведение определено для любых входных данных), то предложение requires может быть опущено.

Предложение modifies задает список имен входных параметров, модифицируемых процедурой. Если входные параметры не указаны, то это предложение может быть опущено.

ha

Предложение effects описывает работу процедуры, определяет выходные значения и модификации над входными параметрами. Предложение effects составляется исходя из предположения, что требования предложения requires удовлетворены. В том случае, когда требования requires не удовлетворены, о поведении процедуры ничего не сообщается.

Примеры спецификаций процедурных абстракций:

Concat=proc(a,b: String) returns(ab: String)

effects По возврату ab есть новая строка, содержащая символы из a (в порядке их расположения в a), за которыми следуют символы из b (в порядке их расположения в b).

RemoveDupls=proc(a:array[real])

modifies a

effects Удаляет из массива a все повторяющиеся элементы, порядок следования оставшихся элементов может измениться.

requires Массив a упорядочен по возрастанию.

effects Если элемент x принадлежит массиву a, то возвращается значение i такое, что a[i]=x; в противном случае возвращается значение i на единицу большее, чем значение верхней границы массива a.

3.2.3. Реализация процедурных абстракций

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

Соглашения при реализации: имена процедур и формальных параметров должны совпадать с их именами в спецификации (это помогает связать спецификацию и реализацию); необходимо использовать комментарии, поясняющие работу реализации, и общепринятые правила форматирования.

Одна и та же процедурная абстракция, как правило, может быть реализована различными способами. Например, процедура поиска заданного значения в массиве (Search) может быть реализована как общая процедура с использованием линейного поиска (не накладываются ограничения на входные данные) либо как частичная процедура с использованием бинарного поиска (входной массив должен быть отсортирован).

Замечания по реализации процедурных абстракций.

1. При реализации ПА могут быть оставлены неопределенными некоторые выполняемые процедурой функции. Такая процедура называется недоопределенной – для некоторых значений входных параметров на выходе вместо единственного правильного результата имеется набор допустимых результатов. Реализация может ограничивать этот набор одним значением, однако он может быть любым из числа допустимых. Например, процедура Search будет недоопределенной, если не будет указано точно, какой индекс должен быть возвращен, если искомое значение встречается в массиве несколько раз.

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

2. Процедура должна обладать хорошо определенным и легко объяснимым назначением, независимым от контекста ее использования.

3. Частичная или общая абстракция? Общие процедуры (не имеют ограничений на входные параметры) являются более безопасными, чем частичные, так как неудовлетворение входных требований в частичной процедуре может привести к неверной работе программы. В свою очередь, частичные процедуры чаще более эффективны в реализации, чем общие. Критерии выбора между частичной и общей абстракцией: 1) эффективность; 2) корректное выполнение с меньшим числом потенциальных ошибок.

Если процедура создается для общего пользования (например, часть библиотеки программ), то в первую очередь необходимо обеспечить условие корректности выполнения.

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

3.2.4. Более обобщенные (параметризованные) процедуры

Процедура Search работает с произвольным массивом вещественных чисел. Она была бы более полезной, если бы смогла работать с массивами данных различного типа. Такого обобщения можно достичь, расширяя абстракцию через параметризацию и используя типы данных в качестве параметров. При этом некоторые значения параметров могут не иметь смысла, например, массив может быть отсортирован только в том случае, если элементы, принадлежащие к типу, упорядочены. Ограничения на параметры типа предполагают набор некоторых заданных операций над ними. Спецификация абстракции должна содержать эти ограничения в наборе requires.

Спецификация параметризованной процедуры в заголовке содержит указание на параметр-тип. Предложение requires помимо прочих ограничений содержит ограничения, накладываемые на параметры-типы.

Например, абстракция Search требует, чтобы ее параметр t имел операции equal (равно) и less (меньше), упорядочивающие t.


requires
t имеет операции: equal, less: proctype(t,t) returns(boolean);
t упорядочивается через less, и массив a упорядочен по возрастанию через less.

effects Если элемент x принадлежит массиву a, то возвращается значение i такое, что a[i]=x; в противном случае – значение i на единицу больше, чем значение верхней границы массива a.

Параметризованная абстракция представляет собой класс взаимосвязанных абстракций, определенных в одной спецификации. Спецификация процедуры получается из спецификации класса путем замены имени параметра-типа его значением и удалением из предложения requires ограничений на тип параметров. Если язык программирования имеет в наличии средства реализации параметризованных абстракций, то класс процедур реализуется в виде одной программы. Если язык реализации не имеет средств для создания параметризованных абстракций, то класс абстракций реализуется в виде нескольких непараметризованных процедур для всех допустимых типов параметров.

3.3. Абстракция данных

3.3.1. Понятие абстракции данных

Процедурные абстракции дают нам возможность добавлять в базовый язык новые операции. Необходимость добавления в базовый язык новых типов данных удовлетворяется абстракцией данных.

Область применения программы определяет набор новых типов данных. Например, при создании компилятора или интерпретатора полезны стеки и символьные таблицы, в аналитических вычислениях – полиномы, в матричной алгебре – векторы и матрицы. Новые типы данных должны включать в себя абстракцию через параметризацию и абстракцию через спецификацию. Смысл АП – использование параметров, АС – включение операций над типом в сам тип: абстракция данных = данные + операции.

3.3.2. Спецификация абстракции данных

Состоит из заголовка, определяющего имя типа и имена его операций, и двух секций – описания и операций:

Dname=data type is список операций

Описание – описание абстракции данных

Операции – спецификации всех операций над типом

end Dname

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

Пример. Спецификация очереди целых чисел.

TQueue=data type is Create, Empty, Insert, Remove, Destroy

Дата добавления: 2015-04-11 ; просмотров: 31 ; Нарушение авторских прав

Источник

Концепция Абстрактного Типа Данных

Доброго времени суток, хабравчане!

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

Введение

Начнем с того, что плавно подойдем к определению АТД. АТД, в первую очередь, представляет собой тип данных, что означет следущее:
наличие определенных доступных операций над элементами этого типа;
а также данные, относительно которых эти операции выполняются (диапазон значений).

Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:

Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.

Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:

АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).

Я считаю, что при разработке АТД сначала нужно определить интерфейс, так как интерфейс не должен зависеть от внутреннего представления данных в АТД. После определения операций, сотставляющих интерфейс, нужно сосредоточиться на данных, которые и будут реализовать заданное поведение АТД. В итоге мы получим некую структуру данных – механизм позволяющий хранить и обрабатывать данные. При этом, прелесть АТД в том, что если нам захочется изменить внутренне представление данных, то нам не придется блуждать по всей программе и менять каждую строку кода, которая зависит от данных, которые мы хотим поменять. АТД инкапсулирует эти данные, что позволяет менять работу объектов этого типа, а не всей программы.

Преимущества АТД

Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):

Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.

Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.

Стоит отметить, что концепция АТД нашла гирокое применение в ООП, т.к именно эта концепция дополняет ООП и позволяет уменшить сложность программ в быстроменяющемся мире требований к ПО.

Данную статью я писал для того, что бы обратить внимание разработчиков на АТД с целью повышения качества работы и разработки программного обеспечения.

Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».

Источник

Adblock
detector