Тема 2. Методы разработки алгоритмов

Теоретическая часть

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

Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

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

• 
  следование (линейная структура);
• 
  ветвление;
• 
  цикл.

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

Например: вычисление площади прямоугольника со сторонами a и b.

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

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

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

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

^ Блок – схема выполнения алгоритма полного ветвления запись на алгоритмическом языке и языке программирования Pascal

Различают полную и неполную формы ветвлений. Ниже рассмотрен пример поиска максимального из двух введенных чисел. Задача решена двумя способами: с использованием неполной формы ветвления (блок-схема и программа слева) и полной (блок-схема и программа справа).

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

Циклы бывают с параметром (счетчиком), с предусловием, с постусловием.

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

На следующих схемах в цикле с постусловием СЕРИЯ обозначает один или несколько любых операторов; ЛВ — логическое выражение, (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — то НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.

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

Одним из способов обеспечения высокого уровня технологичности разрабатываемого программного обеспечения является структурное программирование. Именно для изображения схем алгоритмов таких программ в свое время был разработан ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие специальный блок. Хотя этот стандарт предусматривает блоки для обозначения циклов, он не запрещает и произвольной передачи управления, т. е. допускает использование команд условной и безусловной передачи управления при реализации алгоритма.

15. Итерационные и рекурсивные алгоритмы. Разработка рекурсивных алгоритмов. Основные понятия, связанные с рекурсивными алгоритмами (глубина, текущий уровень, общее число вызовов).

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

Классическими примерами рекурсивных алгоритмов является вычисление факториала и чисел Фибоначчи. Числом Фибоначчи называется число, определяемое рекуррентной формулой m F

Формула называется рекуррентной, если она выражает зависи- мость некоторого -го члена последовательности через предыдущие члены. n

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

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

При оценке эффективности алгоритмов, содержащих рекурсию, вычисляют следующие характеристики:

1. Глубину рекурсии — максимальное количество вызовов ре- курсивного алгоритма без возвратов.

2. Текущий уровень рекурсии — количество рекурсивных вы- зовов в некоторый момент времени.

3. Общее количество вызовов — число вызовов рекурсивного алгоритма при работе программы.

16.Эффективность и сложность алгоритмов. Понятие степени роста. Свойства функции . Классификация алгоритмов по степени сложности.

Основным фактором при выборе алгоритма для задач, решаемых с помощью перебора большого числа вариантов, является суммарное время нахождение решения. Трудоемкость алгоритма - это число шагов.
Если трудоемкость ограничена полиномом, то алгоритм называется эффективным; если более быстро растущей функцией, то не эффективным.
Зависимость времени работы программы от объема обрабатываемых данных определяется оценкой сложности алгоритма.
Время работы алгоритма обработки массивов данных зависит от размеров этих массивов.
Например, время работы алгоритма выполняющего чтение и запись данных в ОЗУ определяется по формуле an+b, где a - время, необходимое для того, чтобы прочитать или записать один элемент массива; n - количество элементов массива; b - время для выполнения вспомогательных функций.
Поскольку эта формула выражает линейную зависимость от n, сложность соответствующего алгоритма называют линейной. O(n). Таким образом число сравнений здесь выражается полиномом второй степени и сложность здесь будет квадратичная. O(n²).
Если сложность алгоритма вычисляется по уже написанной программе, то вместо числа сравнений вычисляется количество внутренних циклов.

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

Программирование

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

Опр. Программа – последовательность предложений, написанных на некотором произвольном, понятном ЭВМ языке, допускающая однозначность толкования и реализующая данный алгоритм, т.е. программа есть запись алгоритма для решения задачи на ЭВМ.

Отладка

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

Суть отладки состоит в следующем:

1) Подготовка контрольных тестов которые должны содержать набор исходных данных для которых известен конечный результат.

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

Не нашли, что искали? Воспользуйтесь поиском: