Главная » Статьи » Операционные системы » Общее |
Технология разработки программных продуктов
1.1. Основные этапы технологического процесса разработки программ.
На этом этапе раскрывается организационно-экономическая сущность задачи:
При этом определяется:
Основное требование к контрольному примеру - это отражение всего многообразия возможных форм существования исходных данных. Пользователь хорошо знает проблемную сторону задачи, но обычно слабо представляет, как она будет решаться на ЭВМ. Предметная область пользователя часто незнакома программисту, поэтому необходима полная корректная постановка задачи, однозначно понимаемая пользователем и разработчиком. Построение математической модели объекта. На этом этапе производится анализ и исследование задачи. Структура этапа:
Математическая модель - это система математических соотношений (формул, уравнений, неравенств и т.д.), отражающих существенные свойства объекта или явления. Математическая запись постановки задачи отличается высокой точностью отображения ее сущности, лаконичностью записи, однозначностью понимания, но она может быть выполнена не для всех задач. При выборе метода решения предпочтение отдается методу, который:
1.2. Критерии качества программного изделия. Программа является правильной, если она работает в соответствии с техническим заданием (ТЗ - документ, которым завершается постановка задачи). Программа является точной, если выдаваемые ею числовые данные имеют допустимые отклонения от аналогичных результатов, полученных с помощью идеальных математических зависимостей. Программа является совместимой, если она работает должным образом не только автономно, но и как часть программной системы. Программа является надежной, если она при всех входных данных обеспечивает полную повторяемость результатов. Программа является универсальной, если она правильно работает при любых допустимых вариантах исходных данных. В ходе разработки программ предусматриваются специальные средства защиты от ввода неправильных данных, обеспечивающие целостность системы. Программа является защищенной, если она сохраняет работоспособность при возникновении сбоев (режим реального времени, программа большого времени выполнения). Программа является полезной, если задача, которую она решает, представляет практическую ценность. Программа является эффективной, если объем требуемых для ее работы ресурсов ЭВМ не превышает допустимого предела. Программа является проверяемой, если ее качества могут быть продемонстрированы на практике (проверка правильности и универсальности). Существуют формальные математические методы проверки и неформальные (прогоны программы с остановками в контрольных точках, обсуждение результатов заинтересованными пользователями). Программа является адаптируемой, если она допускает быструю модификацию с целью приспособления к изменяющимся условиям функционирования. 1.3. Правила хорошего стиля.
1.4. Выбор алгоритма. Типы алгоритмов.
1.5. Трудоемкость, эффективность и сложность алгоритма. Основным фактором при выборе алгоритма для задач, решаемых с помощью перебора большого числа вариантов, является суммарное время нахождение решения. Методы, используемые для сокращения числа вариантов при переборе или позволяющие выбрать наиболее правдоподобные варианты, называют эвристическими. Трудоемкость алгоритма - это число шагов. Если трудоемкость ограничена полиномом, то алгоритм называется эффективным; если более быстро растущей функцией, то не эффективным. Зависимость времени работы программы от объема обрабатываемых данных определяется оценкой сложности алгоритма. Время работы алгоритма обработки массивов данных зависит от размеров этих массивов. Например, время работы алгоритма выполняющего чтение и запись данных в ОЗУ определяется по формуле an+b, где a - время, необходимое для того, чтобы прочитать или записать один элемент массива; n - количество элементов массива; b - время для выполнения вспомогательных функций. Поскольку эта формула выражает линейную зависимость от n, сложность соответствующего алгоритма называют линейной. O(n). Пример: обменная сортировка списка из n элементов представляет собой следующий процесс: определяется минимальный элемент всего списка и осуществляется его обмен с первым элементом списка; затем определяется наименьший элемент оставшегося списка и производится его обмен со вторым элементом. Таким образом число сравнений здесь выражается полиномом второй степени и сложность здесь будет квадратичная. O(n2). Если сложность алгоритма вычисляется по уже написанной программе, то вместо числа сравнений вычисляется количество внутренних циклов. (n-1)+(n-2)+(n-3)+ … + 3 + 2 + 1= = for i:=1 to n-1 do for j:=i+1 to n do if A[I] >A[j] then begin tmp:=A[j]; A[j]:=A[i]; A[i]:=tmp; end;Внешний цикл выполняется (n-1) раз, внутренний цикл срабатывает в среднем n/2 раз для каждого вхождения во внешний цикл. Общее число обращений к внутреннему циклу будет равно (n-1)*n/2. При больших n за оценку этого выражения принимается n2. for i:=1 to n-1 do for j:=1 to n do begin С[i, j]:=0; for k:=1 to n do С[i, j]:= С[i, j]+A[i, k]*B[k, j]; end;Алгоритм перемножения двух матриц размером n*n имеет число срабатываний внутреннего цикла равное n3. O(n3). Формально сложность алгоритма определяется как порядок функции, выражающей время его работы. Алгоритм двоичного поиска в таблице с упорядоченными элементами оценивается как O(log2n). Логарифмическая зависимость сложности от возрастания n более приемлема чем линейная; линейная предпочтительнее чем полиномиальная или экспоненциальная. Для больших объемов данных нежелательна даже полиномиальная сложность. Пример: составить проект. Имеется последовательность чисел (не больше 30). Положительные четные заменить максимальным числом, отрицательные нечетные заменить средним арифметическим отрицательных чисел. Подсчитать количество замен. Упорядочить элементы последовательности в порядке убывания. 1.6. Итерация и рекурсия. Существуют 2 основные формы повторений: итерация и рекурсия. Итерация в основном используется для тех видов обработки, которые можно определить выражением "выполнить для всех", а рекурсия задается выражением "выполнить тоже, что и в последний раз". Текущее действие выполняется с помощью предыдущего ответа или предыдущих стадий вычисления. В действительности итерация и рекурсия взаимозаменяемы. Пример: function fact (n: integer): longint; begin if n=0 then fact:=1 else fact:=n*fact(n-1); end; begin f:=1; for i:=1 to n do f:=f*i; end.Оба алгоритма имеют линейную сложность, но для рекурсивной процедуры требуются дополнительные расходы памяти и времени, т.к. происходит многократное обращение из подпрограммы к самой себе. Должно создаваться и сохраняться много копий регистров, переменных и точек возврата. Для хранения этой информации используется стековая память, поэтому предпочтительнее итерационная форма. 1.7. Способы описания алгоритмов.
Достоинства:
Графический. Представляет собой изображение структуры алгоритма, при котором все этапы обработки данных представлены в виде блоков - определенных геометрических фигур. Достоинства:
Достоинства:
| |
Просмотров: 1715 | Рейтинг: 0.0/0 |
Всего комментариев: 0 | |