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

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

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

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

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

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

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

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

Свойства модулей:

— завершённость и функциональная целостность (любой модуль реализует одну функцию, но реализует прекрасно и всецело);

— независимость и автономность от вторых модулей (независимость работы модуля-преемника от работы модуля-предшественника; наряду с этим их сообщение осуществляется лишь на уровне управления/приема и передачи параметров);

— эволюционируемость (развиваемость);

— открытость для разработчиков и пользователей (для использования и модернизации);

— надёжность и корректность;

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

Свойства (преимущества) модульного проектирования методов:

— возможность разработки метода громадного количества (алгоритмического комплекса) разными исполнителями;

— ведения библиотеки и возможность создания чаще всего применяемых методов (подалгоритмов);

— обоснования тестирования и облегчение алгоритмов их правильности ;

— модификации алгоритмов и упрощение проектирования ;

— уменьшение сложности разработки (проектирования) методов (либо комплексов методов);

— наблюдаемость вычислительного процесса при реализации методов.

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

Пример. Для задачи ответа квадратного уравнения ax2 + bx + c = 0 такими необыкновенными случаями, к примеру, будут:

1) a = b = c = 0;

2) a = 0, b, c – хороши от нуля;

3) D = b2 – 4ac 0 и др.

Тестирование метода не имеет возможности дать полной (100%-ой) гарантии правильности метода для всех вероятных комплектов входных данных, в особенности для достаточно сложных методов.

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

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

Сначала отыщем число всех таких сообщений. Число бинарных сообщений длины 1 равняется 2 = 21 (это 0 и 1), длины 2 равняется 4 = 22 (00, 01, 10, 11). Отправляясь от этих частных фактов, способом математической индукции докажем, что число разных сообщений длины n равняется 2n. Данный индуктивный вывод докажет правильность метода.

Пускай это отечественное утверждение правильно для n = k. Тогда для n = k + 1 приобретаем, что добавление каждого бита (0 либо 1) к любому из 2k сообщений длины k приведет к повышению числа сообщений в 2 раза, другими словами их число будет равняется 2 ? 2k = 2k+1, что и обосновывает отечественное индуктивное предположение.

Разработаем сейчас метод вычисления числа x = 2n с применением операции умножения лишь один раз.

Прологарифмируем последнее равенство. Возьмём ln(x) = ln(2n) = n ln(2) .

Применяя равенство exp(ln(x)) = x, возьмём, что exp(ln(x)) = x = exp(n ln(2)).

Остается сейчас, лишь, записать несложный метод вычисления числа x.

Rem Вычисление количества сообщенийclsInput “Введите длину сообщения в битах”; nx=exp(n*log(2))print “Количество сообщений равняется ”; int(x)end

1. структуры и Алгоритмы данных. Введение | Технострим

Похожие статьи:

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Adblock
detector