Костюк - Основы программирования

132

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

Пример 7.10. Алгоритм вычисляет определитель квадратной матрицы методом Гаусса с частичным выбором ведущего элемента. Массив A размерностью n×n со­ держит коэффициенты матрицы. Результат – X.

i:=1; r:=n; p:=1; while i<=r do

begin {Выбор ведущего элемента A[v,i] (7.17)} if abs(A[v,i])<eps then r:=i-1

else begin {Перестановка строк (7.18)} (7.16) {Вычитание строк матрицы (7.19)}

i:=i+1 end

end;

{ Вычисление определителя (7.20)}

Запишем отдельные этапы алгоритма (7.16). Выбор ведущего элемента – в алго­ ритме (7.17), перестановка строк – в алгоритме (7.18), вычитание строк матрицы – в алгоритме (7.19), вычисление определителя – в алгоритме (7.20).

133

if r<n then X:=0 else begin

X:=p*A[1,1]; (7.20) for i:=2 to n do X:=X*A[i,i]

end;

Нетрудно видеть, что общее количество исполнений внутреннего цикла на этапе вычитания уравнений (самом трудоемком этапе) приближенно равно n3/3, как в алго­ ритме (7.8). Перед выполнением алгоритма (7.16) необходимо также задать eps.

Конец примера.

Вычисление обратной матрицы. Согласно определению, обратная матрица

рица. Все матрицы имеют размер n×n. Равенство (7.6) можно представить в виде:

где Dj – j–й столбец обратной матрицы, I j – j–й столбец единичной матрицы.

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

Пример 7.11. Алгоритм вычисляет обратную матрицу методом Гаусса с частич­ ным выбором ведущего элемента. Массив A размерностью n×n содержит ко­ эффициенты матрицы. Массив D размерностью n×n первоначально содержит эле­ менты единичной матрицы. Результат (обратная матрица) – в массиве D.

i:=1; r:=n; while i<=r do

begin {Выбор ведущего элемента A[v,i] (7.17)} if abs(A[v,i])<eps then r:=i-1;

else begin {Перестановка строк (7.22)} (7.21) {Деление i–й строки на A[i,i] (7.23)}

{Вычитание уравнений (7.24)} i:=i+1

end

135

9) возведение квадратной матрицы в положительную целочисленную степень. Взять за основу алгоритмы (7.1) – (7.7).

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

3.Оформить в виде процедуры алгоритм решения системы n линейных уравнений с n неизвестными методом Гаусса с частичным выбором ведущего элемента. Взять за осно­ ву алгоритмы (7.8) – (7.10).

4.Взяв за основу алгоритмы (7.11) – (7.15), написать программу, вычисляющую общее ре­

шение системы n линейных уравнений с m неизвестными методом Гаусса.

5.Оформить в виде процедуры алгоритм вычисления определителя квадратной матрицы ме­ тодом Гаусса с частичным выбором ведущего элемента. Взять за основу алгоритмы (7.16) – (7.20).

6.Оформить в виде процедуры алгоритм обращения квадратной матрицы методом Гаусса с частичным выбором ведущего элемента. Взять за основу алгоритмы (7.21) – (7.24).

7.Написать программу, которая вводит из файла прямоугольную матрицу и вычисляет ее

ранг методом Гаусса с выбором ведущего элемента. Взять за основу алгоритмы (7.8) – (7.10).

Глава 8 Технология программирования

8.1 Программы, комплексы программ и программные продукты

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

Обычная программа, как правило, реализует некоторый алгоритм с одним вхо­ дом и выходом. Программная система или комплекс программ состоит из сово­ купности функционально связанных программ, предназначенных для решения цело­ го класса задач. Их создание требует гораздо большего труда, чем написание анало­ гичной по объему простой программы; согласно исследованиям, объем работы при этом возрастает в 3–4 раза.

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

Научная дисциплина технология программирования начала создаваться в 60–е годы, когда в практическом программировании стали разрабатываться программные продукты большого объема, вследствие чего появилась потребность в планировании труда программистов для сокращения сроков разработки и улучшения качества со­ здаваемых программных продуктов. В дальнейшем рекомендации этой научной дис­ циплины вошли в различные промышленные и государственные стандарты. Далее,

137

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

Весь процесс разработки системы можно разделить на следующие последова­ тельно выполняемые этапы:

1)этап технического задания (ТЗ);

2)проектирование архитектуры системы;

3)проектирование и разработка системы;

4)этап опытной эксплуатации.

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

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

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

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

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

138

процесс называется сопровождением программного продукта. Жизненный цикл системы продолжается, пока разработчик (или тот, кому переданы эти обязанности) осуществляет сопровождение системы. Очередной вариант системы, полученный в процессе ее сопровождения, называют версией или релизом. Версии обычно нуме­ руют двумя числами, записываемыми через точку, причем начинают нумерацию с версии 1.0. После небольшой модификации системы, когда в основном исправляют лишь обнаруженные ошибки, в номере версии увеличивают на единицу второе чис­ ло. Если же система была подвергнута существенной доработке, то увеличивают на единицу первое число, а второе число делают нулем. Так, после версии 1.5 может идти версия 2.0, затем 2.1, 2.2 и т.д.

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

8.2 Программная документация

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

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

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

139

компьютера (компьютерной сети) и операционной системы, где может функциониро­ вать система. Должен быть приведен список файлов системы, описаны действия пользователя для развертывания системы на компьютере. Как правило, файлы с про­ граммами поставляются для пользователей в готовом (откомпилированном) виде. Для сложных систем разработчики обычно создают специальную программу по уста­ новке (по-английски “set up”), которая автоматически создает необходимые разделы на диске, копирует файлы, запрашивает пользователя о параметрах установки (если они предусмотрены в системе).

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

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

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

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

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

140

Вописании программы должно быть также написано, как генерировать (трансли­ ровать, собирать готовые к выполнению компоненты системы). Должны быть описа­ ны методы тестирования и приведены сами тесты.

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

Эксплуатационная документация может поставляться пользователям не только в бумажном, но и в электронном виде. Документация сопровождения обычно создает­ ся в электронном виде, но так, чтобы при необходимости ее можно было распечатать. При этом исходный текст должен поставляться в виде файла, непосредственно вос­ принимаемого компилятором, а файлы тестов должны быть такими, чтобы их «пони­ мала» система. Необходимо, чтобы без всякого изменения этих файлов можно было бы повторить как генерацию системы, так и ее тестирование.

Иногда система предназначена не для широкого круга пользователей, а для про­ граммистов, которые используют систему для создания своих программ как набор конструкционных элементов. Такая система создается в виде, например, библиотеки классов на некотором объектно-ориентированном языке. В эксплуатационной доку­ ментации подобной системы должна быть сделана поправка на высокий уровень пользователей. Им бывает важно знать, какие алгоритмы реализованы в системе, где они опубликованы. Кроме того, иногда вся система или ее часть поставляется в виде исходных текстов, а не сгенерированных модулей.

8.3Проектирование и программирование программ и комплексов программ

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

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