Приведенные выше комментарии поясняют интуитивное понятие алгоритма, но само это понятие не становиться от этого более четким и строгим. Тем не менее математики долгое время довольствовались этим понятием. Лишь с выявлением алгоритмически неразрешимых задач. т.е. задач, для решения которых невозможно построить алгоритм, появилось настоятельная потребность в построении формального определения алгоритма, соответствующего известному интуитивному понятию.
Интуитивное понятие алгоритма в силу своей расплывчатости не может быть объектом математического изучения, поэтому для доказательства существования или не существование алгоритма решения задачи было необходимо строгое формальное определение алгоритма.
Построение такого формального определение было начато с формализации объектов (операндов) алгоритма, так как в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания датчиков, фиксирующих параметры производственного процесса, шахматные фигуры и позиции и т.п. Однако, предполагая, что алгоритм имеет дело не с самими реальными объектами, а с их изображениями, можно считать, что операнды алгоритма есть слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритм связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена английским математиком А.Тьюрингом в 1936 году, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга.
Мы будем придерживаться неформального определения алгоритма, формулируемого следующим образом:
Алгоритм - это упорядоченная последовательность указаний, выполнение которой приводит от исходных данных к требуемому результату.
Другими словами алгоритм это план решения задачи, записанный в виде последовательности указаний или групп указаний.
Приведем пример алгоритма Евклида, выполняя который определяется общий наибольший делитель двух положительных целых чисел a и b.
Пример 2. Алгоритм Евклида, нахождения наибольшего общего делителя двух положительных чисел.
1. Проверить a>b. Если да, то перейти к указанию 2, иначе - к указанию 3.
2. Взять за новое значение a разность a-b. Перейти к указанию 1.
3. Проверить b>a . Если да, то перейти к указанию 4, иначе - к указанию 5.
4. Взять за новое значение b разность b-a, перейти к указание 1.
5. За результат взять последнее значение a (b). Перейти к указанию 6.
6. Закончить процесс.
В приведенном выше алгоритме, предполагается, что его может выполнить любой человек или вычислительная машина, который умеет выполнять операции сравнения и вычитания двух чисел. Напомним, что в школе наибольший общий делитель определяется как произведение общих простых делителей чисел. В данном алгоритме о произведении и понятии делителя числа нет даже упоминания и, тем не менее, следуя ему, всегда определяется наибольший общий делитель двух целых положительных чисел. Это факт говорит о том, что получить результат можно разными способами с применением операций, которые, на первый взгляд, не имеют к решаемой проблеме никакого отношения, что позволяет среди всех возможных вариантов решения задачи, искать наиболее эффективный. В дальнейшем рассматриваются алгоритмы для вычислительных машин. Современные компьютеры с мощным программным обеспечением могут выполнять различные операции: от простых арифметических операций, производимых над двумя числами до решения сложных задач из многих сфер деятельности людей. Если на компьютере имеется программа, позволяющая решить требуемую задачу, то алгоритм решения такой задачи сводится к описанию процесса ввода исходных данных, обращения к требуемой программе и получения результатов в нужном виде. В тоже время для очень многих простых задач нет готовых программ их решения. По-видимому, нельзя на все случаи, да и нет такой необходимости, хранить в памяти необходимые программы. Но практически все программные системы, применяемые на компьютерах, имеют реализованные языки программирования, позволяющие с небольшими затратами составить самостоятельно программу решения довольно сложной задачи. Для реализации такой возможности надо уметь составлять алгоритмы и знать правила (синтаксис) записи указаний на алгоритмическом языке. В дальнейшем мы предполагаем, что «машина умеет» выполнять все арифметические операции, операции сравнения, логические операции, а также может вычислять практически все элементарные функции. Кроме этого она может ввести в память необходимые данные, а также напечатать или вывести на дисплей результаты.
Таким образом, алгоритмы должны обладать такими основными свойствами: массовостью (результативностью); понятностью; дискретностью; конечностью; определенностью; эффективностью.
Среди других свойств алгоритмов, следует отметить оптимальность и элегантность. Правда понятие оптимальности в алгоритмах имеет компромиссный характер, так как можно оптимизировать количество необходимых для получения результата операций, или объем требуемой памяти, или скорость выполнения и даже понятность алгоритма. Поэтому, составляя алгоритм, следует определиться, что надо оптимизировать в первую очередь и как этого достичь. Составление алгоритмов является не только трудоемким процессом, но и, в некотором смысле искусством, поэтому так ценятся хорошие элегантные алгоритмы. Составление алгоритма предполагает от составителя следующего:
Ясное понимание хода решения задачи, а лучше нескольких вариантов, получения решения, начиная с ввода (определения) исходных данных.
Знание возможностей исполнителя по выполнению тех указаний, с помощью которых записывается данный алгоритм.
Если алгоритм составляется под написание программы на алгоритмическом языке, то желательно для составителя алгоритма иметь хорошее представление о синтаксисе языка и наборе операторов языка.
Виды и способы записи алгоритмов
Различают три основных вида алгоритмов:
А) линейные; -
Б) разветвляющиеся;
В) циклические.
Алгоритм называется линейным, если его указания выполняются последовательно в том порядке, в котором они записаны.
Алгоритм-- разветвляющийся, если в процессе решения требуется проверять некоторые условия и в зависимости от их выполнения или невыполнения, выполняются те или иные группы указаний.
Алгоритм - циклический, если в нем имеется хотя бы одна группа указаний, которая в процессе выполнения повторяется.
Для реальных задач, как правило, алгоритмы обладают всеми тремя видами, т.е. в них существуют и линейные группы указаний, и разветвляющиеся участки, и циклические группы. Существует несколько способов записи алгоритмов, которые применяются при составлении программ для решения задач на ЭВМ:
операторная схема алгоритма;
блок-схема алгоритма;
программа, запись алгоритма на алгоритмическом языке.
Операторные схемы алгоритмов
Группа указаний, которая имеет свой законченный смысл, называется оператором.
Операторы мы будем обозначать большими буквами с индексами, Ai и т.п. Операторы классифицируется следующим образом.
1) По структурным свойствам:
а) простой; б) составной; в) циклический.
2) По характеру выполняемых действий:
а) арифметический; б) логический; в) оператор перехода (передачи управления); г) оператор ввода информации в машину; д) оператор вывода информации из машины; е) оператор обмена информацией; ж) оператор остановки и др.
Почти каждый алгоритм можно разделить на несколько групп указаний различных по назначению, т.е. операторов. Обозначив, операторы буквами, и указав последовательность выполнения операторов стрелками, мы получим операторную схему алгоритма.
Пример 3. Пусть требуется вычислить величины:
(1)
(2)
Исходными данными для решения задачи является значения переменных x, a. Обозначим оператор ввода исходных данных через B1. Оператор вывода результата (значений y, z) через - B2. Оператор вычисления значения y по формуле (I) - через A1 . Оператор вычисляющий z- по формуле (2), через - A2. Оператор остановки процесса решения через O1 . Переход между операторами обозначим стрелками. Тогда операторную схему алгоритма решения данной задачи можно представить следующим образом:
т.е. вначале следует ввести значения исходных данных - x, a (оператор B1); затем вычислить значение y (оператор A1); вычислив значение y, требуется вычислить значение z (оператор A2); напечатать результат - значения y, z (оператор B2) и остановить процесс - оператор О1.
Если операторы выполняются в том порядке, в котором они записаны, то стрелки можно опустить, т.е. операторную схему можно записать в следующем сокращенном виде: .
Это пример линейного алгоритма. Приведем пример разветвляющегося алгоритма.
Пример 4. Написать операторную схему алгоритма по определению корней квадратного уравнения при . Опишем процесс (план) решения задачи:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
