Алгоритмы и их свойства. Способы записи алгоритмов

Дискретность, детерминированность, результативность, массовость; блок-схемы и псевдокод

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

Алгоритм — это точная, понятная исполнителю конечная последовательность действий (предписаний, команд), направленная на решение поставленной задачи и приводящая от исходных данных к результату за конечное число шагов. Слово «алгоритм» происходит от латинизированного имени среднеазиатского математика аль-Хорезми, описавшего в IX веке правила выполнения арифметических действий над числами в десятичной записи. С алгоритмами человек сталкивается постоянно: рецепт приготовления блюда, инструкция по сборке мебели, правило деления столбиком — всё это алгоритмы, хотя не все они одинаково строгие и формализованные.

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

Свойство дискретности

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

Свойство детерминированности (определённости)

Детерминированность (определённость) означает, что каждый шаг алгоритма сформулирован строго однозначно и не допускает произвольного толкования: при одних и тех же исходных данных исполнитель, выполняя один и тот же алгоритм, всегда получит один и тот же результат, следуя одной и той же последовательности действий (при отсутствии в алгоритме элементов случайности). Расплывчатые формулировки вроде «добавить немного соли по вкусу» недопустимы в формальном алгоритме — команда должна быть понятна исполнителю без каких-либо домыслов и допускать единственное толкование.

Свойство результативности (конечности)

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

Свойство массовости

Массовость означает, что алгоритм разрабатывается не для одного конкретного набора исходных данных, а применим к целому классу однотипных задач с различными допустимыми исходными данными. Например, алгоритм решения квадратного уравнения ax²+bx+c=0 должен работать для любых допустимых коэффициентов a, b, c (при a≠0), а не только для одного заранее выбранного набора чисел. Это свойство делает алгоритмы универсальным и многократно используемым инструментом, а не одноразовым решением частной задачи.

Свойство понятности (для исполнителя)

Иногда как отдельное свойство выделяют понятность: алгоритм должен содержать только те команды, которые входят в систему команд конкретного исполнителя (СКИ) — набор действий, которые исполнитель способен выполнить и правильно понять. Один и тот же алгоритм, записанный для человека, робота-исполнителя или для языка программирования, будет использовать разные допустимые команды, но во всех случаях команды должны входить в возможности исполнителя.

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

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

Блок-схемы

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

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

Псевдокод

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

Пример записи одного и того же алгоритма (нахождение наибольшего из двух чисел) тремя способами — словесно, псевдокодом и на Python:

Словесно: 1) ввести два числа a и b; 2) если a больше b, то наибольшее — a, иначе наибольшее — b; 3) вывести наибольшее число.

Псевдокод: начало; ввод a, b; если a > b то max ← a иначе max ← b; вывод max; конец.

a = int(input())

b = int(input())

if a > b:

max_value = a

else:

max_value = b

print(max_value)

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

Исполнитель алгоритма и система команд исполнителя

Исполнитель — это человек, животное, устройство или программа, способные воспринимать и выполнять команды алгоритма. У каждого исполнителя есть среда (обстановка, в которой он действует) и система команд исполнителя (СКИ) — конечный набор допустимых для него элементарных действий. Алгоритм, составленный для конкретного исполнителя, обязан использовать только команды из его СКИ — команда «раздели пополам угол» бессмысленна для исполнителя, который умеет только двигаться на клетчатом поле вперёд и поворачивать.

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

Задача. Дана инструкция: «Готовь омлет, пока не надоест, добавляя соль по вкусу». Определите, какие свойства алгоритма нарушены.

Решение. Формулировка нарушает сразу три требования. Во-первых, нарушена детерминированность: «по вкусу» — не однозначная команда, разные исполнители поймут её и выполнят по-разному. Во-вторых, нарушена результативность: условие «пока не надоест» не гарантирует завершения процесса за конечное число шагов и не определяет чётко момент и критерий остановки. В-третьих, страдает и понятность для формального исполнителя: команда «готовь омлет» — слишком общая и не разложена на элементарные действия, входящие в систему команд большинства формальных исполнителей.

Чтобы инструкция стала настоящим алгоритмом, её нужно переформулировать однозначно и с чётким условием остановки, например: «разбей 2 яйца в миску, добавь 5 г соли, взбей венчиком 30 секунд, вылей на разогретую сковороду, готовь 3 минуты на среднем огне, переверни, готовь ещё 2 минуты, сними со сковороды».

Типичные ошибки

Частая ошибка на экзамене — путать свойства дискретности и детерминированности: дискретность отвечает за разбиение на отдельные шаги, а детерминированность — за однозначность каждого шага, это разные вещи. Вторая ошибка — не различать результативность (конечность выполнения) и правильность результата: алгоритм может результативно завершиться, выдав неверный ответ (быть результативным, но некорректным), и наоборот, содержать логически верную идею, но не завершаться из-за ошибки в условии цикла. Третья ошибка — при построении блок-схемы путать прямоугольник (действие) и ромб (условие) или забывать подписывать оба выхода из ромба («да» и «нет»).

Краткий словарь терминов

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

Дискретность — разбиение алгоритма на отдельные, чётко разграниченные шаги.

Детерминированность — однозначность и строгая определённость каждого шага алгоритма.

Результативность — завершение алгоритма за конечное число шагов с получением результата.

Массовость — применимость алгоритма к целому классу однотипных задач, а не к одному набору данных.

Блок-схема — графическая запись алгоритма стандартизированными фигурами, соединёнными стрелками.

Псевдокод — запись алгоритма на смеси естественного языка и элементов языка программирования.

Заключение

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