Технологический процесс создания программных продуктов

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

Алгоритм  двоичного поиска в таблице с  упорядоченными элементами оценивается  как O(log2n).

Логарифмическая зависимость сложности от возрастания n более приемлема чем линейная; линейная предпочтительнее чем полиномиальная или экспоненциальная.

Для больших  объемов данных нежелательна даже полиномиальная сложность.

 

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 Способы описания алгоритмов

 

1.Словесный.

2.Графический.

3.Псевдокод.

4.Таблицы решений.

Словесный. Действия описываются средствами естественного  языка.

Достоинства:

•общедоступный

•позволяет описывать алгоритм с любой степенью детализации

Недостатки:

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

•низкая наглядность, громоздкое описание

Формульно-словесный: нагляден, лаконичен, но не является строго формальным.

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

Достоинства:

•формализован

•нагляден

•компактен

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

Достоинства:

•простота отражения задачи

•компактность записи

•легкость модификации

•хорошее восприятие логики решения

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Языки программирования

 

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

Алфавит языка программирования - набор символов, включающий буквы, символы и спец. знаки.

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

Семантика языка программирования - это правила, определяющие какие операции и в  какой последовательности должна выполнять  ЭВМ, работая по программе.

 

Общая характеристика языков программирования

 

Первыми языками были машинные языки. Они  задавались системами команд ЭВМ.Языки  высокого уровня способны выразить задачу более лаконично и сжато, позволяя программисту более четко представлять свои задачи и разрабатывать эффективные  методы из решения.Языки машинно-ориентированные  позволяют использовать особенности  машин для повышения эффективности  программ.Такие языки как Си часто  применяют для повышения эффективности  программ.

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

 

 

 

2.1 Способы и методы оптимизации

 

Обычно  большая часть времени расходуется  на выполнение очень небольшой части  программы (примерно 5% ее объема), но наиболее часто используемой, называемой, критической  областью.

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

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

Существует 3 типа программ:

1.  Часто используемые программы (ОС, компиляторы, постпроцессоры). Эффективность - первостепенная задача.

2. Производственные программы. Эффективность существенна.

3.  Программы, написанные не программистами. Эффективность нужна если есть ограничения по памяти или по времени.

Удобочитаемость более существенна чем ее эффективность.

Программу делают более эффективной лишь в  особых случаях:

1.Программа не помещается в памяти.

2.Программа слишком долго выполняется.

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

 

2.2 Структурное программирование

 

Структурное программирование сосредоточено на логике программы и включает 3 главные  составляющие:

1.Проектирование сверху вниз.

2.Модульное программирование.

3.Структурное кодирование.

 

Проектирование  сверху вниз.

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

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

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

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

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

1.Методы нисходящего проектирования.

2.Методы расширения ядра.

3.Методы восходящего проектирования.

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

•последовательности (линейности)

•выбора (ветвления)

•повторения (цикла)

2.3 Вычисление констант

 

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

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

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

Арифметические  операции. Арифметические операции выполняются  с различной скоростью.

В порядке  возрастания времени:

• +, -

• *

• / (деление)

•  возведение в степень

Пример: 3*I = I + I + I

Преобразование  может привести к исключению операции:

X = 2*Y + (A-1)/P + 2*T

X = 2*(Y + T) + (A-1)/P

 

A/50 = A*0,2

 

A = 1.0/X             RX = 1.0/X

A = RX

C = B + D/X         C = B + D*RX

При возведении в степень важно правильно  задавать тип показателя степени. При  возможности использовать целые  типы.

X = Y + A/B*C

Z = W + A/B*C

ABC = A/B*C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3. Отладка

3.1 Виды ошибок

 

Ошибки  анализа.

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

К 1 случаю относятся, например, пренебрежение  возможностью появления отрицательных  значений переменных, малых и больших  величин.

Во 2 случае обычно имеют место крупные и  мелкие логические ошибки, из которых  можно назвать:

1.Отсутствие заданий начальных значений переменных.

2.Неверные условия окончания цикла.

3.Неверную индексацию цикла.

4.Отсутствие задания условий инициирования цикла.

5. Неправильное указание ветви алгоритма для продолжения процесса решения задачи.

Ошибки  общего характера.

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

Такими  ошибками могут быть:

• ошибки из-за недостаточного знания или понимания программистом языка программирования или самой машины

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

Ошибки  физического характера.

Можно назвать  несколько типов ошибок, вызываемых неверными действиями программиста:

 

1.Пропуск некоторых операторов.

2.Отсутствие необходимых данных.

3.Непредусмотренные данные.

4.Неверный формат данных.

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

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

 

Правильность  программ

 

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

Нарушение правильности может проявляться  двумя способами:

•неверная синтаксическая конструкция программы