Понятие алгоритма

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда аль-Хорезми (783–850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике.

В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем.

Исполнитель — это тот, для кого составляют правила и план, тот, кто будет их выполнять. Это человек, животное, или машина, которые понимают и умеют точно исполнять отдаваемые им команды.

Команда — это указание исполнителю совершить некоторое действие.

Для каждого исполнителя определена система команд — т.е. набор команд, которые он может выполнить. У разных исполнителей разные системы команд.

В рамках науки алгоритм относится к категории неопределяемых понятий, т.е. не обладающих формальным определением в терминах более простых понятий.

Алгоритмы окружают человека во всех сферах деятельности и в повседневной жизни. Как перейти дорогу, как дойти до магазина, как найти на карте города Торговый Центр, как решить математическое уравнение, как получить необходимые сведения по какому-либо вопросу и пр. — все строится по алгоритму.

Таким образом, алгоритм может быть предназначен для его выполнения человеком или автоматическим устройством — формальным исполнителем. Задача исполнителя — точная реализация уже имеющегося алгоритма. Формальный исполнитель не обязан вникать в сущность алгоритма, а возможно, и неспособен его понять.

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

Можно выделить алгоритмы вычислительные и управляющие

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

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

Алгоритм управления — это последовательность команд по управлению объектом, приводящая к заранее поставленной цели.

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

Далее речь идёт о вычислительных алгоритмах

На этапе постановки задачи должно быть четко сформулировано, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимых для получения решения.

Второй этап — формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, отношений. Если решение требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели.

Третий этап — построение алгоритма. Процесс разработки алгоритма для решения задачи называется алгоритмизацией.

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

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

Таким образом, программист должен обладать следующими знаниями и навыками:

• уметь строить алгоритмы;
• знать языки программирования;
• уметь работать в соответствующей системе программирования.

Свойства алгоритма

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

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

Определенность (детерминированность) — предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер. Для этого на каждом шаге алгоритма не должно возникать разночтений и разногласий, т.е. инструкции должны быть четко определены.

Завершаемость (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов, т.е. алгоритмы конечны, они должны завершаться и выдавать результат за заранее известное число шагов.

Результативность — завершение алгоритма определенным результатом, т.е. выполнение алгоритма должно привести к какому-либо результату и не оставлять неопределенности. Результат может в том числе оказаться неудачным — например, алгоритм может сообщить, что решения нет!

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

Классификация алгоритмов

Несмотря на слово «последовательность», алгоритм не всегда описывает действия в жестко заданном порядке. Особенно это актуально сейчас, с распространением асинхронности в программировании. Существует несколько классификаций алгоритмов. Как было сказано ранее алгоритмы делятся на две большие группы: вычислительные алгоритмы и управляющие алгоритмы. Есть особые алгоритмы управления, в которых цикл управления может быть бесконечным.

Вычислительные алгоритмы в зависимости от порядка действий исполнителя подразделяются следующим образом:

• Линейный алгоритм — набор команд (инструкций), выполняемых последовательно во времени друг за другом. Они не переставляются местами, не повторяются, выполняются при любых условиях.
• Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого может осуществляться разделение на несколько параллельных ветвей алгоритма.
• Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. Цикл программы — последовательность команд (тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия: например, повторять этот блок команд, пока в структуре данных не останется пустых ячеек. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов.
  Виды циклических алгоритмов:
  1. Цикл с предусловием (Цикл типа Пока)
  2. Цикл с постусловием (Цикл типа До)
  3. Цикл с параметром
• Рекурсивный алгоритм: Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

Таким образом в алгоритмах есть место для условий, циклов и других нелинейных конструкций.

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

Формы записи алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

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

Пример: написать алгоритм «Одеться по погоде». Если на улице температура ниже −8, то необходимо надеть шубу, иначе — польто.

Словесный способ записи алгоритма

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается на естественном языке в произвольной форме с требуемой детализацией.

Словесно-формульный способ записи алгоритма

Для исполнителя-человека алгоритм может быть представлен предложениями обычного текста с использованием в случае необходимости математической или другой символики. Такой способ записи алгоритма называют словесно-формульным.

Пример 2. Алгоритм поиска вещественных корней квадратного уравнения
ах² + Ьх + с = 0, a ≠ 0 :

1. Задать значения коэффициентов a, b и c.
2. Вычислить дискриминант D = b² − 4ac.
3. Проверить условие существования вещественных корней D ≥ 0.
   Если D ≥ 0 выполнено, то перейти к шагу 5.
   Если не выполнено (т.е. D < 0), то перейти к шагу 4.
4. Дать ответ – «вещественных корней нет». Перейти к шагу 8.
5. Проверить условие существования двух различных корней D > 0.
   Если условие выполнено, то перейти к шагу 7,
   иначе – перейти к шагу 6.
6. Вычислить корень уравнения x = -b/2a.
   Дать ответ – «уравнение имеет один корень x».
   Перейти к шагу 8.
7. Вычислить корни уравнения
   х1 = (-b + √D)/2a,
   х2 = (-b − √D)/2a.
   Дать ответ – «уравнение имеет два корня x1, x2».
8. Закончить вычисления.

Словесный способ не имеет широкого распространения, так как такие описания:

• строго не формализуемы;
• страдают многословностью записей;
• допускают неоднозначность толкования отдельных предписаний.

Графический способ записи алгоритмов

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

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

Внутри блока дается описание соответствующих действий. Блоки, как правило, располагаются сверху вниз. Линии соединения отдельных блоков показывают направление процесса обработки в схеме. Стрелки на соединяющих линиях не ставятся при направлениях сверху вниз и слева направо; противоположные направления показывают стрелкой на линии.

Другие фигуры блок-схем вы найдёте в документации к ГОСТ 19.701-90.

Уметь читать блок-схемы полезный навык, поэтому приведем несколько примеров блок-схем различных алгоритмов >>

Блок-схемы широко используются при написании программ, так как они:

• Гораздо проще для понимания, чем запись в виде команд.
• Упрощают процесс отладки.
• Позволяют составить эффективную программную документацию.
• Облегчают процесс демонстрации и обсуждения программы.

//Пример программы на языке C#
namespace oap
{
class Program
{
static void Main(string[] args)
{
var string mess;
Console.WriteLine("введите
   температуру воздуха t: ");
var t = int.Parse(
         Console.ReadLine());
if (t < -8)
{
 mess = "Одеть шубу";
else
 mess = "Одеть польто";
}
Console.WriteLine(mess);
}}}

Рекомендуемая литература

1. Брукшир Дж. Гленн, Брилов Деннис Компьютерные науки. Базовый курс М: Вильямс, 2019.
2. Леонтьев В.П. Новейшая энциклопедия. Компьютер и Интернет. М.: ОЛМА Медиа Групп.