Название "алгоритм" произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi, написавшего популярную в эпоху средневековья книгу о правилах выполнения арифметических действий, т.е. об алгоритмах вычисления произведения, частного и т.д.
PRIVATE<TBODY>Исполнитель алгоритма — это некоторый абстрактный (воображаемый) или реальный объект, способный выполнить действия, предписываемые алгоритмом. В информатике универсальным исполнителем алгоритмов является компьютер.
Основные свойства алгоритма. Слова “инструкция” или “предписание” близки по смыслу слову “алгоритм”, однако они не тождественны ему. Дело в том, что не всякая инструкция может быть названа алгоритмом, поскольку он должен обладать рядом обязательных свойств, которыми произвольное предписание обладать не обязано. Перечислим эти свойства.
1) Конечность – любой алгоритм должен заканчиваться после выполнения конечного (т.е. не бесконечного) числа шагов.
Если алгоритм содержит цикл, т.е. повторяющуюся группу команд, то в алгоритме должно присутствовать некое условие, при выполнении которого следует прерывание цикла.
Например, еще древние греки знали метод приближенного извлечения квадратного корня из произвольного числа а > 0. Пусть х(0) – некоторое начальное приближение к . Для вычисления каждого следующего приближения построим рекуррентную формулу:
, k = 0, 1, … (2.1)
называемую алгоритмом Герона.
Вычислим с его помощью , взяв х(0) = 1.5. Последовательно получим х(1) = 1.4166667; х(2) = 1.4142157; х(3) = 1.4142136; х(4) = 1.4142136. Теоретически эти вычисления можно продолжать бесконечно, получая все более точный результат, поэтому формула (2.1), строго говоря, алгоритмом не является.
Для того, чтобы ее с полным правом можно было назвать алгоритмом, надо указать условие окончания вычислений. Например, можно таким условием считать совпадение определенного количества N цифр в двух последовательных значениях х(k) и х(k+1). Доказано, что в этом случае при использовании формулы (2.1) у всех последующих приближений первые N цифр будут такими же, как у х(k+1). В приведенном примере у х(3) и х(4) совпали первые N = 8 цифр. Следовательно, ответ получен с точностью 10–7, и если она нас устроит, то вычисления можно заканчивать.
2) Определенность – каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола.
Благодаря этому свойству выполнение алгоритма носит чисто механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Например, не является алгоритмом такая инструкция: слегка подогрейте в маленькой кастрюле немного коньяку, добавьте специи по вкусу. Здесь слова “слегка”, “немного” и т.д. носят неопределенный характер, который каждый исполнитель может трактовать по-своему.
3) Эффективность – все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за разумное время с помощью карандаша и бумаги. Например, нельзя считать простой операцией решение алгебраического уравнения 12-й степени. Поэтому, если в инструкции присутствует такая команда: найти решение уравнения х12 + 5х11 + 15х10 + 22х5 + 15258 = 0, то такая инструкция эффективной не является, а, следовательно, ее нельзя считать алгоритмом.
4) Результативность – любой алгоритм должен после своей работы выдавать какой-нибудь результат.
Возможна ситуация, что поставленная задача вообще не имеет решения. В этом случае алгоритм должен заканчиваться выдачей сообщения: “нет решения”.
5) Массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
2.2. Формы записи алгоритма
На практике наиболее распространены следующие формы представления алгоритмов:
- словесная – запись на естественном (“человеческом”) языке;
- графическая – изображение команд в виде графических символов;
- программная – текст на языке программирования.
Словесный способ записи алгоритмов. Это PRIVATE<TBODY>описание последовательных этапов (шагов) обработки данных. Алгоритм задается в произвольном изложении на естественном языке. </TBODY>
Пример 2.1. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Предлагается следующий алгоритм – алгоритм Евклида.
1. Задать два числа.
2. Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма.
3. Заменить большее из чисел разностью большего и меньшего из чисел.
4. Повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75:
1. m = 125, n = 75.
2. m > n, значит
3. новое m = 125 – 75 = 50, n = 75. Возврат к 2.
2. n > m, значит
3. новое n = 75 – 50 = 25, m = 50. Возврат к 2.
2. m > n, значит
3. новое m = 50 – 25 = 25, n = 25. Возврат к 2.
2. m = n. Значит ОТВЕТ = 25.
Словесный способ не имеет широкого распространения по следующим причинам:
- описания не формализованы (нет строгих правил);
- страдают многословностью записей;
- допускают неоднозначность толкования отдельных предписаний.
Графический способ записи алгоритмов. Графический способ представления алгоритмов является более наглядным по сравнению со словесным.
PRIVATE<TBODY>При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.</TBODY> Такое представление называется блок-схемой алгоритма.
| Таблица 2.1. | ||
| PRIVATE<TBODY>Название символа | Обозначение и пример заполнения | Пояснение |
| Процесс |
| Вычислительное действие или последовательность действий |
| Решение |
| Проверка условий |
| Модификация |
| Начало цикла |
| Ввод-вывод |
| Ввод-вывод в общем виде |
| Пуск-останов |
| Начало или конец алгоритма |
В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.
В таблице 2.1. приведены наиболее часто употребляемые символы.
Блок "процесс" применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения указанных данных. Для улучшения наглядности схемы несколько отдельных действий по обработке можно объединять в один блок. Представление отдельных операций достаточно свободно.
Блок "решение" используется для обозначения изменения порядка действий в зависимости от некоторого условия. В каждом блоке "решение" должны быть указаны вопрос, условие или сравнение, которые он определяет.
Блок "модификация" используется для организации циклических конструкций. Слово модификация означает видоизменение, преобразование. Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения. На рис. 2.1. приведена блок-схема алгоритма решения задачи примера 2.1.
| Да |
| Нет |
| Нет |
| Да |
| Ввести m, n |
| Начало |
| m=n? |
| Вывести n |
| Конец |
| m>n? |
| m = m – n |
| n = n – m |
| Рис. 2.1. Блок-схема алгоритма Евклида |
Языки программирования. Это искусственные языки для записи компьютерных программ. В отличие от естественных языков, страдающих неоднозначностью, конструкция языков программирования такова, что составленные на них тексты обязательно обладают свойством определенности и эффективности – важными свойствами алгоритмов.
Запишем программу алгоритма решения задачи примера 2.1 на языке PASCAL.
var m, n : integer;
begin readln(m, n);
repeat if m = n then
begin writeln(n:5); halt; end;
if m > n then m := m - n else n := n - m;
until False;
end.
Приведем перевод ключевых слов для понимания алгоритма.
var – переменные; integer [интедже]– целый;
readln [риидлн]– ввод данных с клавиатуры;
writeln [райтелн]– вывод данных на экран;
begin – начало текста программы или ее блока;
end – конец текста программы или ее блока; until [антил]– пока;
halt – конец вычислений; then [зен]– тогда;
if – если (проверка условия); else [элз]– иначе;
repeat [репиит]– повторять; false [фолс] – ложно.
Если подставить вместо английских слов их русский перевод, то получим описание алгоритма, близкое к описанию на естественном языке.
2.3. Базовые алгоритмические структуры
PRIVATE<TBODY>Логическая структура любого алгоритма может быть представлена комбинацией трех базовых (основных) структур: следование, ветвление, цикл.
1. Базовая структура “следование”. Образуется из последовательности действий, следующих строго одно за другим.
Например, требуется вычислить величину y по формуле y = ax2 + bx при произвольных a, b, x. Блок-схема соответствующего алгоритма имеет вид, приведенный на рис 2.2. В данном случае алгоритм состоит из простой последовательности действий (блоков). Значит, </TBODY>он соответствует структуре “следование”.
| Ввести a, b, х |
| Начало |
| Вывести y |
| y = ax2 + bx |
| Конец |
| ||||
2. Базовая структура “ветвление” обеспечивает в зависимости от результата проверки выполнения некоторого условия (да или нет) выбор одного из альтернативных путей работы алгоритма.
Структура “ветвление” существует в двух основных вариантах:
если – то:
если – то – иначе.
В алгоритме примера 2.1 присутствуют оба варианта этой структуры. После блока “m = n ?” в случае положительного ответа выполняется действие “Вывести n”, а в случае отрицательного – работа алгоритма продолжается далее. Таким образом, реализована структура “если – то”. После блока “m > n ?” в случае положительного ответа выполняется действие “m = m – n”, а в случае отрицательного (т.е. иначе) – действие “n = n – m”,. Таким образом реализована структура “если – то – иначе”.</TBODY>
3. Базовая структура “цикл”. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Пример 2.2. Рассмотрим следующую задачу. Двум бойцам, посланным в разведку, надо перебраться через широкую реку. У берега в маленькой лодке удят рыбу два мальчика. Как бойцам с помощью этих детей перебраться на другой берег, если лодка выдерживает либо одного взрослого, либо двоих детей?
Пусть, для определенности, бойцам надо перебраться с правого берега на левый. Предлагается следующий алгоритм решения задачи.
1. Оба мальчика переправляются на левый берег.
2. Один мальчик возвращается на правый берег, второй – остается на левом.
3. Первый боец переправляется на левый берег, а первый мальчик остается на правом.
4. Второй мальчик переправляется на правый берег.
5. Оба мальчика переправляются на левый берег.
6. Один мальчик возвращается на правый берег, второй – остается на левом.
7. Второй боец переправляется на левый берег.
8. Второй мальчик переправляется на правый берег.
Заметим, что шаги 1 – 4 почти совпадают с шагами 5 – 8, разница только в номере переправляемого бойца. Очевидно, что с помощью подобного алгоритма можно переправить любое количество N бойцов, а не только двоих. Для этого надо выполнить следующий алгоритм.
1. Повторять шаги со 2 по 6, увеличивая каждый раз на 1 значение k от 1 до N.
2. Оба мальчика переправляются на левый берег.
3. Один мальчик возвращается на правый берег, второй – остается на левом.
4. k-й боец переправляется на левый берег, а первый мальчик остается на правом.
5. Второй мальчик переправляется на правый берег.
6. Если k = N, то стоп.
Это будет циклический алгоритм, тело которого составляют шаги 2 – 6. Другой вариант циклической структуры дан в примере 2.1. В нем телом цикла являются шаги 2 – 4.
2.4. Последовательность подготовки и решения задачи на ЭВМ
Подготовка и решение инженерной задачи на ЭВМ (электронной вычислительной машине) включает в себя ряд последовательно выполняемых этапов.
1) постановка задачи;
2) составление математического описания задачи;
3) разработка алгоритма решения;
4) составление текста программы;
5) ввод программы в ЭВМ, ее трансляция и отладка;
6) ввод исходных данных и выполнение программы (счет);
7) анализ результатов.
Постановка задачи должна включать в себя
- цель решения;
- словесную формулировку самой задачи в терминах той области знаний, для которой она решается;
- перечень исходных данных, необходимых для решения задачи;
- перечень искомых величин и форму их представления;
- сведения о требуемой точности счета.
Во многих случаях в постановку задачи включают ее экономическое обоснование.
Математическое описание (математическая модель) задачи представляет собой формализованную запись содержания поставленной задачи в виде совокупности математических соотношений, которые связывают между собой исходные данные и результаты счета. Математическая модель технической или научной задачи формулируется, как правило, с использованием понятий таких математических дисциплин, как дифференциальное и интегральное исчисление, линейная алгебра и т.д.
Вспомним пример 1.1. Митя и Алеша вместе собрали 40 грибов. Митя собрал на 10 грибов больше, чем Алеша. Сколько грибов собрал каждый мальчик?
В постановке задачи сформулирована цель – узнать количество грибов, собранное каждым мальчиком. Записав условия задачи в формализованном виде, мы получим математическую модель. Обозначим х и у – количество грибов, собранное Митей и Алешей, соответственно. Составим систему уравнений
,
которая и является математической моделью процесса собирания грибов. Чтобы решить задачу, надо составить алгоритм, например, на основе правила Крамера.
Трансляция программы – перевод текста программы с алгоритмического языка (например, PASCAL) на язык машинных команд. Для этого используется специальная программа – транслятор, которая просматривает текст программы и осуществляет автоматический перевод.
Отладка программы – анализ работы программы и исправление ошибок. Существует два вида ошибок: синтаксические и семантические (см. далее определения синтаксиса и семантики языка программирования). Синтаксические ошибки обусловлены неправильным синтаксисом текста программы, т.е. если текст написан с нарушением правил выбранного языка программирования. Поскольку в транслятор заложены синтаксические правила языка, то при трансляции синтаксические ошибки обнаруживаются самим компьютером и выдаются соответствующие сообщения.
Семантические ошибки (смысловые) возникают при неправильно составленном алгоритме. В этом случае программа, даже составленная по всем правилам, выдает неправильный результат. Такие ошибки не могут быть исправлены автоматически, а требует активного вмешательства программиста. Наиболее универсальный способ обнаружения семантических ошибок – тестирование. Тестирование программы – пробное решение примеров с заранее известными ответами. Если ответ, полученный программой не совпадает с известным, это означает, что программа содержит ошибки. Правильно составленный тест позволяет достаточно точно определить ошибочный участок текста программы (локализовать ошибку), найти ее и исправить. Составление хороших тестов – весьма сложное занятие, требующее большого мастерства и опыта.
Пример 2.3. Пусть необходимо составить программу решения системы уравнений, полученной в примере 1.1. Воспользуемся для этого правилом Крамера. Представим данную систему в общем виде
Тогда, согласно правилу Крамера, решение будет иметь следующий вид:
; , где D = А11×А22 – А21×А12, Dx = b1×A22 – b2×A12,
Dy = A11×b2 – A21×b1.
Соответствующая программа будет иметь вид:
var x,y,A11,A12,A21,A22,b1,b2,Dx,Dy,D : real;
begin readln(A11,A12,b1);
readln(A21,A22,b2);
D:=A11*A22-A21*A12;
Dx:=b1*A22-b2*A12; Dy:=A11*b2-A21*b1;
x:=Dx/D; y:=Dy/D;
writeln(x:10:2,y:10:2);
readln;
end.
Как было сказано, в программе возможны синтаксические и семантические ошибки. Синтаксические ошибки обнаруживаются транслятором, а семантические – тестированием программы. Наиболее вероятные семантические ошибки в любой программе – неправильно записанные формулы. Для проверки правильности формул данной программы решим какую-нибудь простую, легко решаемую систему, например, систему с единичной матрицей, т.е. при A11 = 1, A12 = 0, A21 = 1, A22 = 0. Тогда для любых b1 и b2 при правильных формулах получим x = b1, y = b2. В противном случае формулы содержат ошибки. Если, например, мы при b1 = 10, b2 = 6 получили х = 6, у = 10, то это означает, что мы перепутали формулы для Dx и Dy и в программу надо внести соответствующее изменение.
2.5. Конструктивные элементы языка PASCAL
PRIVATE<TBODY>Алгоритмический язык (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.
Алфавит – это фиксированный для данного языка набор основных символов, т.е. “букв алфавита”, из которых должен состоять любой текст на этом языке, никакие другие символы в тексте не допускаются.
Алфавит языка PASCAL содержит следующие символы:
1. 26 латинских букв a,…z , строчные и прописные.
2. Арабские цифры 0, … , 9.
3. Знаки арифметических операций + – * /.
4. Знаки отношения = < >
5. Знаки пунктуации . , ; : ‘ (апостроф), знак пробела.
6. Скобки ( ) [ ] { }.
7. Специальные парные символы <> <= >= .. := .
Синтаксис – это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная команда языка. Точнее говоря, синтаксис языка представляет собой набор правил, устанавливающих, какие комбинации символов являются осмысленными предложениями на этом языке.
Каждое понятие алгоритмического языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных. Основными понятиями в алгоритмических языках являются следующие.
1. Данные – величины, обрабатываемые программой.
2. Операции – действия, выполняемые программой над данными.
3. Имена (идентификаторы) – употребляются для обозначения объектов программы (данных), над которыми в программе выполняются действия. В языке PASCAL имена образуются по следующим правилам.
1) Имя – последовательность букв и цифр, начинающаяся с буквы.
2) Длина имени может быть любой, но распознаются только первые 8 символов.
Например, имена mamapapadub и mamapapaded будут считаться одинаковыми.
3) PASCAL не различает строчные и прописные (большие и маленькие) буквы.
Эту особенность можно использовать для придания именам большей выразительности. Например, имя NumberDay читается легче, чем numberday.
Пример 2.4. Неправильные имена:
1x (начинается с цифры); x 2 (содержит пробел);
Num-Students (содержит дефис);
var (является служебным словом).
4. Ключевые слова (служебные слова) – зарезервированные слова, имеющие строго определенный смысл, который не может быть изменен. Некоторые ключевые слова языка PASCAL приведены в примере 2.1 после программы. Более полный перечень дан в Приложении 1.
5. Выражения (формулы) – сочетания основных символов алфавита, предназначенные для выполнения необходимых вычислений, состоят из констант, переменных, указателей функций (например, sin(x)), объединенных знаками операций.
Выражения записываются в виде линейных последовательностей символов (без подстрочных и надстрочных символов, “многоэтажных” дробей и т.д.), что позволяет вводить их в компьютер, последовательно нажимая на соответствующие клавиши клавиатуры.
6. Операторы (команды) – содержательное понятие языка, каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. В состав операторов входят:
- ключевые слова;
- данные;
- выражения и т.д.
7. Комментарий – заключается в фигурные скобки. Текст комментария может содержать любые символы (но не должен начинаться с символа $).
Например: {Это комментарий}
Семантика определяет смысловое значение предложений языка. Являясь системой правил истолкования отдельных языковых конструкций, семантика устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке.
2.6. Обзор языков программирования
Язык программирования – набор правил, определяющих систему записей, составляющих программу, синтаксис и семантику используемых грамматических конструкций.
Алгоритм, записанный по правилам языка программирования, является исходной программой на этом языке.
Компьютеры непосредственно выполняют программы на машинном языке программирования данной ЭВМ. При этом программа представляет собой набор отдельных команд компьютера. Эти команды являются достаточно "простыми", например, сложение, умножение, сравнение и пересылка отдельных данных. Каждая команда содержит в себе сведения о том, какая операция должна быть выполнена (код операции), с какими операндами (адреса данных или непосредственно сами данные) выполняются вычисления и куда (адрес) должен быть помещен результат.
Машинные языки были первыми языками программирования. Программирование на них затруднительно ввиду того, что, во-первых, эти языки различны для каждого типа ЭВМ, во-вторых, являются трудоемкими для большинства пользователей по причине необходимости знания особенностей каждой ЭВМ и большого количества реализуемых ею операций (команд). Данные языки обычно используются для разработки системных программ. Однако чаще применяются специальные экономичные языки – Ассемблеры, близкие к соответствующим машинным языкам. Их называют языками низкого уровня.
Языки программирования высокого уровня значительно ближе и понятнее человеку, нежели компьютеру. Особенности устройства конкретных вычислительных машин в них не учитываются, поэтому создаваемые программы легко переносятся на другие ЭВМ, для которых создан транслятор этого языка.
Первые языки высокого уровня относились к так называемому процедурному стилю программирования. В программах, соответствующих этому стилю основное внимание уделяется описанию тех действий (процедур), которые необходимо произвести с исходными данными для получения результата.
Pаsса1 (Паскаль) является одним из наиболее популярных среди прикладных программистов процедурным языком программирования, особенно для ПЭВМ. Этот язык удобен для организации диалога, обеспечивает создание надежных программ, позволяет осуществлять манипулирование с нечисловыми данными, дает возможность пользователям вводить и использовать необходимые для них типы данных произвольного характера.
В языке Pascal реализован ряд концепций, рассматриваемых как основа "дисциплинированного" программирования и заимствованных впоследствии разработчиками многих языков. Одним из существенных признаков языка Pascal является последовательная и достаточно полная реализация концепции структурного программирования.
Смысл структурного программирования состоит в акцентировании отдельных блоков программы, её четкое разделение на части, выполняющие некоторые законченные операции: ветви условного оператора, тело цикла, вычисление некоторой совокупности выражений и т.д. При записи текста программы используется так называемая лесенка, что позволяет физически выделить отдельные блоки программы. Подобный прием позволяет проследить строение программы и лучше понять смысл выполняемых действий.
Кроме того, в языке реализована концепция определения новых типов данных на основе уже имеющихся.
Pascal характеризуется высоким уровнем, широкими возможностями, стройностью, простотой и краткостью, строгостью, способствующей написанию эффективных и надежных программ, высоким коэффициентом реализации на ЭВМ.
В настоящее время широко используются такие версии этого языка для ПЭВМ, как Воrland Раsсаl, Тurbо Раsсаl со специальной библиотекой объектно-ориентированного программирования Тurbo Vsion.
Язык АДА, созданный на основе языка ПАСКАЛЬ предназначен для программирования задач, решаемых в реальном масштабе времени, т.е. задачи решаются в том же темпе, что и описываемый или управляемый процесс.
В настоящее время на смену процедурному программированию приходят следующие новые стили программирования:
· функциональное;
• логическое;
• объектно-ориентированное.
Сущность функционального (аппликативного) программирования определена А. П. Ершовым как "... способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции, а единственным правилом композиции – оператор суперпозиции функции (функция от функции). Никаких ячеек памяти, ни операторов присваивания, ни циклов, ни, тем более, блок-схем, ни передачи управления".
Роль основной конструкции в функциональных языках играет выражение. К нему относятся скалярные константы, структурированные объекты, функции, тела функций и вызовы функций.
Аппликативный язык программирования включает следующие элементы:
• классы констант, которыми могут манипулировать функции;
• набор базовых функций, которые программист может использовать без предварительного объявления и описания;
• правила построения новых функций из базовых;
• правила формирования выражений на основе вызовов функций.
Аппликативные языки – языки программирования очень высокого уровня. Первым таким языком был LISP(ЛИСП) (LISt Processing – обработка списков), созданный в 1959 году. Цель его создания состояла в организации удобства обработки символьной информации. Существенная черта этого языка – унификация программ и структур данных: все выражения записываются в виде списков. Язык ЛИСП предназначается для обработки строк и рекурсивных данных, выполнения арифметических и логических операций. Он широко применяется в создании программ для интеллектуальных систем обработки информации.
Логическое, или реляционное программирование‚ открыло появление языка РROLOG (Пролог) (PROgramming in LOGic — программирование в терминах логики). Этот язык был создан французским ученым А. Кольмероэ в 1973 году. В настоящее время известны и другие языки, однако наиболее развитым и распространенным языком логического программирования является именно Пролог. Языки логического программирования широко используются в системах искусственного интеллекта.
Центральным понятием в логическом программировании является отношение – некоторое соответствие между парой каких-либо объектов (в арифметике и языке Pascal используются отношения между числами: =, … Продолжение »