В настоящее время создание алгоритмов — написание программ для электронных вычислительных машин — стало видом человеческой деятельности. Важнейший конструктивный компонент программирования, не зависящий от особенностей синтаксиса языков программирования и специфики функционирования конкретных вычислительных машин, — разработка алгоритма.
Подходы к созданию алгоритмов и требования к ним существенно изменялись в ходе эволюции компьютеров. Первоначально, в эпоху ЭВМ 1 — го и 2-го поколений, когда они были еще мало распространены, машинное время было дорого, а возможности ЭВМ очень скромны (с точки зрения сегодняшних достижений), основным требованием к алгоритму была его узко понимаемая эффективность:
1) минимальные требования в отношении оперативной памяти компьютера — . программа должна была использовать наименьшее возможное число ячеек оперативной памяти компьютера;
2) минимальное время исполнения (минимальное число операций). При этом программы составлялись из команд, непосредственно или почти непосредственно исполнявшихся компьютером (точнее говоря, процессором):
Обработка информации и алгоритмы | Информатика 10-11 класс #9 | Инфоурок
• простейших арифметических операций;
• операций сравнения чисел;
• операторов безусловного и условных переходов (изменяющих порядок вычисления команд в программе);
• операторов вызова подпрограмм (вспомогательных алгоритмов).
Такой подход в программировании (создании алгоритмов), ориентированный на непосредственно выполняемые компьютером операции, можно назвать операциональным.
Рассмотрим подробнее операции, которые выполняются компьютером и которые являются шагами программы при операциональном подходе.
Операция присваивания состоит в том, что некоторое значение фигурирующей в программе величины помещается в ячейку памяти компьютера. Эта ячейка может либо принадлежать оперативной памяти, либо находиться в арифметико-логическом устройстве, выполняющем основные операции (это устройство — часть процессора).
После операции присваивания указанное значение сохраняется в ячейке памяти, куда оно было помещено, пока не будет заменено другим в результате другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается именем (идентификатором) соответствующей переменной. Примеры идентификаторов: а, х, у1, у2.
Важно помнить, что переменные и, соответственно, их значения могут быть разных типов — числовые (целые или действительные), литерные или логические. Значения различных типов представляются (кодируются) в компьютере по-разному, поэтому они должны соответствовать типам переменных, которым они присваиваются. При разработке алгоритма следует всегда помнить и ‘тщательно различать типы переменных.
Набор простейших арифметических операций «сложения» (+), «вычитания» (-), «умножения» (*) и «деления» (/) (причем во многих случаях следует тщательно отличать деление, выполняемое над целыми числами — в этом случае операция деления распадается на деление нацело и вычисление остатка от деления) позволяет записывать арифметические выражения с использованием числовых констант и идентификаторов переменных. Для определения порядка операций в выражениях чаще всего используют стандартное математическое соглашение о старшинстве операции, согласно которому старшими и выполняемыми в 1-ю очередь являются умножение и деление, а младшими — сложение и вычитание. Для изменения «естественного» порядка выполняемых операций служат скобки. Сравните, например, порядок операций в выражениях:
Алгоритмы и структуры данных простыми словами. Зачем учить алгоритмы? #codonaft
(а + 2) * х и а + 2 * х.
Что же касается порядка выполнения операций одного старшинства, то они, как правило, выполняются в порядке записи в выражении.
Операция сравнения числовых значений фактически сводится к определению знака разности этих значений. Этот знак отображается с помощью специальной ячейки памяти (флага знака результата) вычислительного устройства компьютера и может использоваться при выполнении условных переходов между командами (шагами) алгоритма.
Чтобы понять, что такое условные и безусловные переходы при выполнении алгоритма, надо исходить из того, что шаги или команды алгоритма обладают метками или адресами, и, помимо естественного порядка выполнения команд соответственно их записи, возможен и другой порядок, при котором последовательность выполнения команд определяется переходами на команды с определенными метками или адресами. Безусловным называется переход, для которого изменение порядка выполнения команд раз и навсегда определено и не зависит ни от каких условий. Условным называется переход, для которого порядок выполнения команд определяется по некоторому условию, чаще всего условию сравнения величин числовых типов.
Операция вызова подпрограммы (вспомогательного алгоритма) — это такой переход в последовательности команд алгоритма, при котором на определенном этапе выполнения алгоритма происходит вначале переход на другую программу (подпрограмму по отношению к той, откуда совершен переход), а затем, после ее завершения, возврат в точку вызова подпрограммы и продолжение выполнения команд, начиная со следующей после команды вызова подпрограммы, в-их естественном порядке. Очевидно, что операция вызова подпрограммы представляет собой переход, при котором запоминается адрес команды, следующей за командой вызова подпрограммы, что позволяет вернуться к исходному алгоритму (головной программе) после выполнения вспомогательного алгоритма (подпрограммы).
Отметим, что универсальность существующих компьютеров достигается за счет определенного набора команд, типа только что описанного, и автоматического механизма их выполнения, а проблема решения задачи с помощью компьютера состоит лишь в преобразовании решаемой задачи в последовательность этих команд. В качестве примера рассмотрим операциональное представление алгоритма вычисления квадратного корня из положительного числа а с помощью рекуррентной формулы:
Можно показать, что .
Будем обозначать через x0 нулевое приближение (за него в данном случае можно принять любое положительное число), через заданную точность вычислений и через c0 какое-нибудь число, удовлетворяющее условию 0 c0 x 2;
7) присвоить переменной у значение y -а;
8) присвоить переменной у значение у/c0;
9) присвоить переменной значение у/2;
10) сравнить и ; если > , то перейти к команде 3, иначе перейти к следующей команде;
11) вывести числа х, а и ;
В этом алгоритме все команды, кроме 10, предполагают переход к следующим за ними по записи командам, и лишь команда 10, являющаяся командой условного перехода, меняет порядок исполнения команд — после нее в нарушение порядка может выполняться команда 3, т.е. она определяет циклическую конструкцию в алгоритме.
Поясним эту программу. Команда 2 помещает значение начального приближения x0 в ячейку памяти, в которой хранятся значения переменной х (на каждом этапе вычислений в этой ячейке хранится значение х, равное значению одного из членов рекуррентной последовательности xn ).
Команды 3-5 вычисляют по числу х число (х + а/х) /2. Результат помещается в ячейку памяти, в которой хранится значение переменной х, при этом старое значение «стирается» новым. Команды 6-9 вычисляют величину
с помощью которой оценивается сверху разность х — . Важное значение имеет команда 10. По ней не производятся вычисления, а сравниваются между собой вычисленное значение 5 и заданная точность . Если > , то управляющее устройство вернет вычислительный процесс к команде 3 и заставит повторить процесс.
В противном случае, когда требуемая точность достигнута, печатается полученный результат и работа прекращается.
Методы разработки и анализа алгоритмов
Аннотация: Рассматриваются основные понятия о методах проектирования (нисходящем, восходящем, модульном, структурном) и разработки алгоритмов (программ), тестирование и верификация алгоритма, трассировка алгоритма.
Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача ( алгоритм ) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь , вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования «снизу вверх».
Структурные принципы алгоритмизации ( структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление , повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм , представленный как следования и вложения базовых алгоритмических структур . У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз («как читается, так и исполняется»). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур .
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер. Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм , используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма .
Свойства модулей:
- функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);
- автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
- эволюционируемость (развиваемость);
- открытость для пользователей и разработчиков (для модернизации и использования);
- корректность и надежность;
- ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
- возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
- возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);
- облегчение тестирования алгоритмов и обоснования их правильности ;
- упрощение проектирования и модификации алгоритмов ;
- уменьшение сложности разработки ( проектирования ) алгоритмов (или комплексов алгоритмов);
- наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Пример. Для задачи решения квадратного уравнения ax 2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b 2 – 4ac < 0 и др.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Пример. Составим алгоритм нахождения числа всех различных двоичных сообщений (двоичных последовательностей) длины n битов, используя при этом не более одной операции умножения, и докажем правильность этого алгоритма. Вначале найдем число всех таких сообщений. Число двоичных сообщений длины 1 равно 2 = 2 1 (это «0» и «1»), длины 2 равно 4 = 2 2 («00», «01», «10», «11»). Отправляясь от этих частных фактов, методом математической индукции докажем, что число различных сообщений длины n равно 2 n . Этот индуктивный вывод докажет правильность алгоритма.
Пусть это наше утверждение верно для n = k . Тогда для n = k + 1 получаем, что добавление каждого бита (0 или 1) к любому из 2 k сообщений длины k приведет к увеличению числа сообщений в 2 раза, то есть их число будет равно 2 x 2 k = 2 k+1 , что и доказывает наше индуктивное предположение.
Составим теперь алгоритм вычисления числа x = 2 n с использованием операции умножения только один раз.
Прологарифмируем последнее равенство . Получим ln(x) = ln(2 n ) = n ln(2) .
Используя равенство exp(ln(x)) = x , получим, что exp(ln(x)) = x = exp(n ln(2)) .
Остается теперь записать простейший алгоритм вычисления числа x .
Program Power; Uses Crt; Var x: real; n: integer; Begin ClrScr; WriteLn(‘Введите длину в битах n =’); < приглашение к вводу входного параметра >ReadLn(n); < ввод входного параметра >x:=exp(n*ln(2)); < вычисление степени >WriteLn(‘количество сообщений равно: ‘, int(x+0.5)); < вывод х с округлением >End.
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
Источник: intuit.ru
Методы разработки и анализа алгоритмов
9. Лекция: Методы разработки и анализа алгоритмов Рассматриваются основные понятия о методах проектирования (нисходящем, восходящем, модульном, структурном) и разработки алгоритмов (программ), тестирование и верификация алгоритма, трассировка алгоритма. Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур).
Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод , наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования «снизу вверх».
Структурные принципы алгоритмизации (структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление, повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно. Структурированный алгоритм – это алгоритм, представленный как следования и вложения базовых алгоритмических структур.
У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз («как читается, так и исполняется»). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур. Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер.
Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм, используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма.
Свойства модулей: • функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью); • автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления); • эволюционируемость (развиваемость); • открытость для пользователей и разработчиков (для модернизации и использования); • корректность и надежность; • ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок. Свойства (преимущества) модульного проектирования алгоритмов: • возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями; • возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов); • облегчение тестирования алгоритмов и обоснования их правильности ; • упрощение проектирования и модификации алгоритмов ; • уменьшение сложности разработки (проектирования) алгоритмов (или комплексов алгоритмов); • наблюдаемость вычислительного процесса при реализации алгоритмов. Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев. Пример. Для задачи решения квадратного уравнения ax2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b2 – 4ac
В закладки
Разместил пособие
hailastexhaups75
Эксперт по предмету «Информатика»
Поделись лекцией и получи скидку 30% на платформе Автор24
Заполни поля и прикрепи лекцию. Мы вышлем промокод со скидкой тебе на почту
Твоя лекция отправлена! Жди скидку на почте. Есть еще материалы? Загрузи прямо сейчас
Загрузить еще лекции
Поделись лекцией и получи промокод на скидку 30% на платформе Автор24
Заполни поля и прикрепи лекцию. Мы вышлем промокод со скидкой тебе на почту
Твоя лекция отправлена! Жди скидку на почте. Есть еще материалы? Загрузи прямо сейчас
Источник: spravochnick.ru