Реферат: АЛГОРИТМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
Понятие алгоритма
Решение любого рода задач на ЭВМ основано на применении алгоритмов. Так называют набор предписаний, однозначно определяющий содержание и порядок действий, которые необходимо выполнить над исходными и промежуточными данными для получения конечного результата.
Приведенное определение не является строго математическим; оно лишь объясняет общий смысл данного термина. До появления ЭВМ алгоритмы представляли лишь теоретический интерес. Только в связи с развитием вычислительной техники (и методов вычислительной математики) появилась настоятельная необходимость в уточнении данного понятия; это было нужно для разработки стандартных методов решения обширных классов задач самого различного типа. Постепенно оформилась целая научная дисциплина, изучающая методы создания эффективных алгоритмов — теория алгоритмов.
При разработке любого алгоритма процесс решения задачи формализуется, то есть сводится к применению конечной последовательности достаточно простых правил и действий.
Само слово «алгоритм» произошло от имени известного средневекового математика Мухаммеда ибн Мусы аль-Хорезми (в латинизированной форме — Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил точные правила записи натуральных чисел с помощью арабских цифр и арифметических действий над ними «в столбик», знакомые теперь каждому школьнику. В XII в. эта книга была переведена на латынь и получила широкое распространение в Европе.
В математике для решения типовых задач всегда использовались правила, описывающие определенную последовательность действий. Для решения любой задачи надо знать, что дано, что следует получить, какие действия и в каком порядке выполнить. Например, известны правила сложения дробных чисел, решения квадратных уравнений и т.д. Да и в повседневной жизни часто используются различного рода инструкции и правила, указывающие на последовательность действий, необходимых для получения желаемого результата.
После того как алгоритмразработан, решение задачи можно поручить любому исполнителю (в том числе и тому, кто не понимает, почему
нужно выполнять предписанные алгоритмом действия); точно следуя инструкциям, он добьется желаемого результата. В этом и заключается главная цель алгоритмизации.
Свойства алгоритмов
К основным свойствам алгоритмов относятся:
понятность для исполнителя — он должен понимать, как выполнять предписанные алгоритмом действия при любом варианте исходных данных;
дискретность (прерывность, раздельность); это значит, что алгоритмдолжен представлять процесс решения задачи как последовательное выполнение простых (или определенных ранее) шагов;
определенность — каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвольного толкования. Благодаря этому свойству решение задачи приобретает механический характер, не требуется никаких дополнительных указаний или сведений о ней;
результативность (конечность) заключается в том, что за конечное число шагов алгоритмдолжен либо приводить к решению задачи, либо выдавать сообщение о невозможности получить решение по той или иной причине, либо продолжаться в течение времени, отведенного для его исполнения с выдачей промежуточных результатов;
массовость — алгоритмрешения задачи должен разрабатываться в общем виде, то есть он должен быть применим для целого класса задач, различающихся лишь исходными данными. Эти данныемогут выбираться из определенной области, которая называется областью применимости алгоритма.
Способы записи алгоритмов
Оформить (записать) алгоритмы можно несколькими способами — словесно, формульно-словесно; графически (в виде блок-схемы) или в виде таблицы решений.
Словесный способ записи алгоритмов основан на использовании средств обычного языка, но с жестко ограниченным набором слов и фраз, не допускающим повторений, синонимов, двусмысленностей, лишних слов. К недостаткам такого подхода относится отсутствие строгой формализации и наглядности представления вычислительного процесса. Вместе с тем с помощью данного способа можно описывать алгоритмы с произвольной степенью детализации.
Формульно-словесный способ основан на задании инструкций о выполнении конкретных действий с использованием математических символов и выражений в сочетании со словесными пояснениями.
Графический способ представления алгоритма использует элементы блок-схем. Блок-схемой называется графическое изображение структуры алгоритма, в котором каждый этап процесса переработки данных представляется в виде геометрических фигур (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых при этом операций (рис. 33). Последовательность выполнения пунктов алгоритма, описываемого блок-схемой, устанавливается путем упорядоченного размещения блоков и объединения их линиями потока информации.
Рис. 33. Основные элементы блок-схем
Блок-схемаявляется исключительно наглядным и простым способом записи алгоритма; при этом не накладывается никаких ограничений на степень детализации в его изображении. Выбор ее целиком лежит на программисте. Однако необходимо иметь в виду, что излишне общий характер блок-схемы нежелателен из-за малой информативности, а при большой детализации она теряет наглядность. Поэтому для сложных и больших алгоритмов целесообразно составлять несколько схем разной степени детализации. Блок-схема первого уровня отображает алгоритмв целом, блок-схемы второго уровня раскрывают логику отдельных блоков первого уровня. При необходимости могут быть составлены блок-схемы последующих уровней с еще большей степенью детализации.
Табличный способ предполагает представление алгоритма в виде таблицы решений и обычно носит вспомогательный характер.
Базовые алгоритмические конструкции
Вычислительные процессы, используемые для решения различного рода задач на ЭВМ, в общем виде могут быть разделены на три большие группы: линейные, разветвляющиеся и циклические.
Линейным называют вычислительный процесс, в котором этапы вычислений выполняются в линейной последовательности и каждый этап выполняется только один раз (рис. 34). На схеме блоки размещаются сверху вниз в порядке их выполнения. Для таких процессов характерно, что направление вычислений не зависит от исходных данных или промежуточных результатов.
Разветвляющийся вычислительный процесс реализуется по одному из нескольких заранее предусмотренных направлений в зависимости от выполнения некоторого условия (рис. 35, я). Каждое направление вычислений называется ветвью. В любом конкретном случае процесс реализуется только по одной ветви, а выполнение остальных исключается.
Циклический вычислительный процесс включает участки, на которых вычисления выполняются многократно по одним и тем же математическим формулам, но при разных значениях исходных данных. Такой многократно повторяющийся участок вычислений называется циклом (рис. 35, б).
Для организации цикла необходимо предусмотреть:
задание начального значения параметра цикла — переменной, которая будет изменяться при его повторении;
изменение значения этой переменной перед каждым новым повторением цикла;
проверку условия окончания цикла по значению его параметра и порядок перехода к началу цикла, если он не окончен.
Рис. 34. Линейный вычислительный процесс
Рис. 35. Разветвляющийся (а) и циклический (б) вычислительные процессы