Методы разработки программного обеспечения

 

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

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

Итак, вначале программист представляет задачу как набор задач (рис.10 – в виде блок-схемы и языка PDL). Затем каждая из задач детализируется, например, в виде нескольких предложений языка PDL. Если она относительно сложная, то можно представить в виде отдельной процедуры.

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

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

Введем понятие простой программы (именно для такой программы может быть доказана теорема о возможности ее преобразования в последовательность основных управляющих структур – следования, повторения и разветвления), для которой

1. Существует единственный вход и единственный выход;

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

Примеры простых программ и непростых приведены на рис.11.

Используя указанное определение, нисходящую разработку можно представить в виде следующего алгоритма:

While

проектирование не окончится

do

заменить некоторый узел простой программой

End-do

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

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

Функция F является рекурсивной, если

1. F(N) = G(N,F(N-1)), где G – известная функция

2. F(1) = некоторому известному числу.

Типичным примером можем являться вычисление факториала. Например, Factorial(450) можно получить умножением 450 на Factorial(449). В результате задача сводится к вычислению Factorial(449). Если это преобразование повторить 448 раз, то получим Factorial(2), который есть 2*Factorial(1). Поскольку Factorial(1) известен и равен 1, то задача решена.

Часто бывает невозможно получить точное решение задачи по соображениям стоимости, сложности или размера. В этом случае возможно построить представление об определенных свойствах задачи, которое называется моделью, а остальные свойства не учитываются. Такой подход называется моделированием. Моделирование широко применяется во многих областях (миниатюрные корабли и самолеты проверяются в иммитированных водоемах и аэротрубах до стадии испытания опытных образцов). Моделирование на вычислительной машине часто применяется для исследования физических процессов, особенно когда известно математическое описание процесса с помощью уравнений. В то же время для разработки программ такой подход используется не так часто. В качестве примера, можно предложить использовать моделирование операционной системы с предполагаемыми затратами 100 человеко-лет перед началом ее разработки.

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

СТРУКТУРЫ ДАННЫХ

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

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

Простейший агрегативный тип – массивы, которые есть упорядоченный набор данных одного типа.

Структуры (в Паскале – записи) – поименованная совокупность данных различных типов.

Во многих языках есть только эти два типа агрегативных данных.

Полезно рассмотреть и другие возможные агрегативные структуры (могут быть организованы с помощью массивов).

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

Очереди – упорядоченный список, в один конец которого элементы добавляются, а из другого изымаются. Иначе – это список FIFO (First In, First Out) – поступивший первым обслуживается первым. Операции – добавить и удалить.

Стеки – упорядоченный список, в один конец которого элементы добавляются, и из него же изымаются. Список LIFO (Last In, First Out). Операции – поместить, извлечь, функция «пусто» = истина, если стек не заполнен.

Множество – совокупность переменных одного типа. Аналогичен списку, за исключением того, что порядок расположения переменных не имеет значения. Операции – добавить, удалить, функция «входит в» = истина, если данная переменная находится в множестве.

Граф – структура, состоящая из узлов и дуг, причем каждая дуга направлена от одного узла к другому.

Дерево – направленный граф, у которого только корневой узел не имеет дуг, входящих в него, в каждый узел входит не более одной дуги, в каждый узел можно попасть из корневого за несколько шагов.

Важное место при работе с агрегативными переменными занимают такие действия как поиск и сортировка данных. Рассмотрим основные методы таких действий.

 

ПОИСК

Поиск – это процесс нахождения нужных значений в некотором наборе данных.

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

1. Линейный поиск.

Наиболее простой в реализации, хотя его выполнение занимает наибольшее время. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Если массив содержит N элементов, то каждый раз, в среднем, будет проверяться N/2 элементов. Легко программируется, подходит для коротких массивов.

2. Двоичный поиск.

Для ведения двоичного поиска ключи должны быть упорядочены по величине или алфавиту. Если такое упорядочивание произведено заранее, то среднее максимальное время поиска в массиве с N элементами будет log₂N.

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

 

СОРТИРОВКА

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

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

- число сортируемых элементов (N);

- до какой степени элементы уже отсортированы.

В качестве основных критериев оценки метода сортировки используют количество необходимых операций сравнения С и объем используемой памяти S. Количество сравнений С(N) для различных методов может быть от N² до N log₂N. Эффективность использования памяти определяется соотношением

где S(N) - объем памяти, занимаемый элементами данных до сортировки, DS(N) - объем дополнительной памяти, требуемой в процессе сортировки.

Задача сортировки состоит в том, чтобы расположить записи в порядке убывания (возрастания) ключей. Тело не влияет на сортировку. Для простоты рассмотрим сортировку одномерного массива.

1. Сортировка методом выборки

Из массива выбирается наименьший элемент и помещается в первый элемент массива, затем выбирается наименьший элемент из оставшихся и помещается во второй элемент массива. В качестве метода поиска наименьшего элемента может быть применен следующий ("Турнир с выбыванием"). На первом шаге сравниваем попарно элементы массива в следующем порядке А(1) с А(2), А(3) с А(4) и т.д. При этом наименьшие элементы массива помещаем на первое место, т.е. на А(1), А(3),…, а наибольшие - на второе. На втором шаге сравниваем первые элементы образовавшихся пар: А(1) с А(3), А(5) с А(7), … и наименьшие помещаем на первое место, т.е. в А(1), А(5),… По окончании процесса обнаружим наименьший элемент на месте первого элемента массива А(1). Далее метод поиска применим к части массива, начиная с А(2) и т.д.

Сортировка таким методом требует порядка N(N+1)/2 сравнений и практически не нуждается в дополнительной памяти.

2. Сортировка включением. Элементы выбираются по очереди и помещаются в нужное место. Один из возможных способов сортировки данным методом ("сортировка простым включением") таков. Начиная с первого элемента сравниваем последовательно пары соседних элементов и продвигаемся вперед до тех пор, пока выполняется условие А(К) <= А(К+1), К = 1,2,3,… Как только А(К) станет больше А(К+1) меняем их местами и начинаем возврат назад, последовательно проводя сравнение и обмен пар соседних элементов до тех пор, пока не будет нарушено условие А(L) > A(L-1), L = K,K-1,… Как только А(L) станет меньше или равно А(L-1), продолжаем процесс сравнения вперед, начиная с А(К+1) (при этом элементы А(1)…А(К+1) будут уже отсортированы). Процесс продвижения вперед, чередующийся с возвратом назад, продолжаем до К = N-1. Пример.

При сортировке простым включением требуется порядка N² сравнений, при этом практически не используется дополнительная память.

3. Сортировка распределением (метод корзин).

Среди методов сортировки распределением широкое распространение получила цифровая сортировка. Любой элемент массива рассматривается как совокупность цифр, а элементы сначала сортируются по значению старшей цифры, затем полученные подмножества (группы) сортируются по значению следующей цифры и т.д. Пусть каждый элемент массива А размером N представляет собой совокупность цифр С₁С₂С₃…С_m, где m - количество цифр максимального элемента (если какой-то элемент содержит меньше цифр, то он слева дополняется нулями). Последовательно просматривая элементы массива А, распределим их по группам: в первую группу объединим все элементы, у которых первая цифра - 0, во вторую - если первая цифра 1, в последнюю 10 - первая цифра 9. К каждой группе применим тот же метод, но относительно цифры С₂. Далее до цифры С_m. Пример.

Алгоритм цифровой сортировки не предполагает сравнение элементов и поэтому нельзя оценить ее эффективность обычным способом. Но если m (число цифр) мало, то ее показатели лучше, чем "N log₂N". Для цифровой сортировки требуется дополнительный массив размером N, и еще массив размером 10, в котором подсчитывается число элементов с выделяемой цифрой 0,1,…9.

4. Сортировка обменами.

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

Метод "Быстрой сортировки". Устанавливаем I = 1, J = N. Сравниваем А(I) и А(J). Если А(I) <= А(J), то уменьшаем J на 1 и продолжаем сравнение. Последовательное уменьшение J и сравнение указанных элементов продолжаем пока не окажется, что А(I) > А(J). Тогда меняем местами эти элементы. После чего увеличиваем индекс I на 1 и снова сравниваем. Последовательное увеличение I и сравнение продолжаем до тех пор, пока не окажется, что А(I) > А(J). В этом случае меняем местами элементы и начинаем уменьшение J.

Чередуя увеличение I и уменьшение J приходим к некоторому элементу, который называется пороговым или главным, и характеризующемуся условием I = J (перед началом сортировки он находился в А(1)). Все элементы массива оказались разделенными главным элементом на две части так, что все элементы слева (сверху) меньше него, а справа (снизу) - больше. К этим двум массивам применяем тот же алгоритм и получаем четыре части и т.д.

Алгоритм "Быстрой сортировки" имеет максимальное число сравнений N², а минимальное N log₂N. Все зависит от выбора главного элемента (желательно, чтобы он делил массив на две равные части). Среднее число сравнений 2N log₂N. Дополнительная память используется для хранения стеков, в которые засылаются границы получаемых частей массивов.

5. Сортировка слиянием.

Два отдельно отсортированных массива затем срединяются в один массив таким образом, чтобы и он стал отсортированным. Пусть имеем два отсортированных массива В и С с числом элементов M и L. Процедура слияния в массив А с числом элементов N = M+L такова. В качестве А(1) выбираем наименьший из В(1) и С(1). Если это В(1), то в качестве А(2) - наименьший из В(2) и С(1) и т.д.

Чтобы применить такой метод к неотсортированному массиву, можно считать каждый его элемент сортированной последовательностью, состоящей из одного элемента. Объединяем каждую пару следующих подряд последовательностей в одну отсортированную последовательность. Затем объединяем по четыре элемента и т.д.

Этот метод требует N log₂N сравнений и один дополнительный массив, содержащий N элементов.

 

СТРАТЕГИИ РАСПРЕДЕЛЕНИЯ ПАМЯТИ.

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

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

1. Первое возможное размещение.

Последовательно просматриваются области памяти, пока не будет найдена область, достаточная для размещения данных. Все свободные области организованы в список (рис.13). Найденная область изымается из списка, на ее место ставится меньшая свободная область - оставшаяся незанятой часть исключенной области. В рамках данного способа легко объединить две соседние области в одну, если они свободны (т.к. список областей упорядочен по адресам). Данный способ довольно прост, однако при его использовании сильно возрастает фрагментарность.

2. Наилучшее размещение.

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

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

 

ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ

Объектно-ориентированные языки создают окружения, радикально отличающиеся от окружения процедурных языков, которое состоит из данных и процедур. ООЯ создает окружение в виде множества независимых объектов, каждый из которых отличается своими свойствами и способами взаимодействия с другими объектами. Задавая структуру обмена сообщениями между объектами, программист получает совокупность операций, которые и составляют программу. Объекты можно использовать для решения задач, не понимая механизма их работы (рассматривать как "черный ящик"). ООЯ скрывает многие детали работы внутри объектов (однако при необходимости можно модифицировать детали внутреннего устройства объектов, создавая тем самым другие объекты).

Внутренность объекта. Каждый объект содержит переменные, в которых находятся данные, его описывающие (в различных ООЯ названия некоторых характеристик могут отличаться, например в языке Object Pascal (Delphi) переменные называются полями). Пусть объект с именем «Окружность А» (рис.14) – это фигура, которая может быть нарисована на экране компьютера. Переменные этого объекта: позиция (позиция на экране центра окружности) и размер (радиус окружности).

Операции над данными объекта запускаются при получении им сообщения, указывающего нужную последовательность действий. Конкретная процедура, которая идентифицируется с сообщением, содержится внутри объекта в виде внутренней программы, которая называется методом. Метод выполняет манипуляции с данными объекта, а также может посылать сообщения другим объектам с целью получения нужного результата, который затем возвращается назад к первому объекту. Объект «Окружность А» имеет три метода. Метод форма говорит объекту как описать его форму, обращаясь к своим переменным, а также посылая сообщения другому объекту «Маркер», который выполняет работу по вычерчиванию. На рис. обозначены методы объекта «Маркер» (сообщение, вызывающее метод Маркер сдвигК посылает координаты центра окружности, т.е. значение переменной Позиция). В объекте «Окружность А» метод форма вызывается своими же методами высветить и  стереть. Методы высветить и стереть посылают сообщения Себе – встроенному имени, позволяющему объекту (в нашем случае «Окружность А») направлять сообщения самому себе. Метод высветить приказывает Себе использовать метод форма для создания окружности, послав предварительно сообщение Маркеру о том, что он должен рисовать черные линии. Метод стереть говорит Себе использовать метод форма для удаления окружности, что делается с применением Маркера, рисующего белым цветом.

Каждый объект в объектно-ориентированном окружении имеет собственные характеристики. Однако объекты имеющие одинаковые свойства и ведущие себя сходным образом объединяются в классы. Класс­ задает общие свойства его составляющих (называются экземплярами), т.е. все они имеют одинаковое число переменных одного и того же типа, реагируют на одни и те же сообщения и реализуют одни и те же методы работы со своими переменными. Экземпляры класса отличаются один от другого конкретными значениями собственных переменных. Рассмотрим пример упрощенного объектно-ориентированного языка, организованного как иерархия суперклассов и подклассов (рис.15). На самом нижнем уровне находится класс «Объект», который задает общие свойства всех объектов, например, их способность отвечать на сообщения. «Дисплейный объект» – это подкласс класса «Объект». Подкласс наследует сообщения и методы суперкласса, кроме того, он может содержать новые сообщения и методы, реализующие его особенности. «Дисплейный объект» представляет собой как бы эскиз объектов, которые отображаются на экране. Он задает методы построения дуг, прямых, и т.д. Класс «Многоугольник» имеет переменные позиция, стороны, угол,…и методы форма, высветить, стереть.

 

 

Может быть послано сообщение классу «Многоугольник» создать объект этого класса «Многоугольник А» - экземпляр, который будет иметь собственные значения переменных и содержать все методы класса «Многоугольник». Следующий класс «Прямоугольник» имеет две переменные, метод форма описывается вновь, поэтому перекрывает этот метод от «Многоугольника», новый метод увеличение, методы высветить и стереть наследуются.

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

Показано, что наиболее удобными для реализации программных систем, разработанных в рамках объектно-ориентированного подхода, являются объектно-ориентированные языки программирования, хотя возможна реализация и на обычных (не объектно-ориентированных) языках (например, на языке C и на языке Fortran). Первый объектно-ориентированный язык программирования Simula 67 был разработан в конце 60-х годов в Норвегии. Авторы этого языка очень точно угадали перспективы развития программирования, но их язык намного опередил свое время. Однако современники (программисты 60-х годов) оказались не готовы воспринять ценности языка Simula 67, и он не выдержал конкуренции с другими языками программирования (прежде всего, с языком Fortran). Прохладному отношению к языку Simula 67 способствовало и то обстоятельство, что он был реализован как интерпретируемый (а не компилируемый) язык, что было совершенно неприемлемым в 60-е годы, так как интерпретация связана со снижением эффективности (скорости выполнения) программ. Но достоинства языка Simula 67 были замечены некоторыми программистами, и в 70-е годы было разработано большое число экспериментальных объектно-ориентированных языков программирования: например, языки CLU, Alphard, Concurrent Pascal и др. Эти языки так и остались экспериментальными, но в результате их исследования были разработаны современные объектно-ориентированные языки программирования: C++, Smalltalk, Eiffel и др. Наиболее распространенным объектно-ориентированным языком программирования безусловно является C++. Свободно распространяемые коммерческие системы программирования C++ существуют практически на любой платформе. Широко известна свободно распространяемая система программирования G++, которая дает возможность всем желающим разобрать достаточно хорошо и подробно прокомментированный исходный текст одного из образцовых компиляторов языка C++. Разработка новых объектно-ориентированных языков программирования продолжается.

Дескриптивные языки (языки логического программирования).