Владимир Липаев - Очерки истории отечественной программной инженерии в 1940-е – 80-е годы

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

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

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

• величина программы, выраженная числом строк, команд или количеством программных модулей в комплексе;

• количество обрабатываемых переменных или объем памяти для размещения базы данных;

• трудоемкость разработки комплекса программ;

• длительность разработки;

• количество специалистов, участвующих в создании комплекса программ.

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

• временная сложность отражала необходимую длительность исполнения комплекса программ или время обработки на ЭВМ совокупности исходных данных до получения требуемых результатов;

• программная сложность характеризовалась длиной текста программы или размером памяти ЭВМ, необходимой для размещения программного комплекса;

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

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

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