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

ЛЕКЦИЯ 13

ТЕХНОЛОГИИ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ПРОГРАММИРОВВАНИЯ

§ Основы алгоритмизации инженерно- технических задач

w Алгоритмы и их свойства

w Способы описания алгоритмов

w Основные управляющие структуры

§ Инструментальные средства программирования

https://lessons-tva.info/edu/e-inf1/e-inf1-4-2.html

Основы алгоритмизации инженерно- технических задач

Алгоритмы и их свойства

Понятие «алгоритм» является одним из основных в информатике. Это слово происходит от имени узбекского математика аль-Хорезми, что означает «из Хорезма». В IX веке он разработал правила арифметических действий над десятичными числами. Длительное время алгоритмами пользовались только математики, понимая под алгоритмом любое описание процесса решения задачи. Описание процессов решения математических задач предназначалось для человека, поэтому не требовалось большой строгости в описании действий.

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

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

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

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

Дискретность – это разбиение алгоритма на ряд отдельных законченных действий – шагов.

Точность – это четкое указание последовательности шагов.

Понятность – это однозначное понимание и исполнение каждого шага алгоритма его исполнителем.

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

Массовость – применимость алгоритма к решению целого класса однотипных задач.

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

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

Существуют различные способы представления алгоритмов. Рассмотрим некоторые из них.

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

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

В виде блок-схем – схема алгоритма представляет собой графическое изображение алгоритма на формализованном языке, описывающего содержание и логические связи задачи. Под блоком подразумевается любой конечный этап вычислительного процесса, принимаемый в данной схеме как целое. В блок-схеме все части вычислительного процесса представлены фигурами, содержащими пояснения и соединенными между собой линиями. Применяемые графические символы, отражающие основные операции процесса обработки данных, устанавливает ГОСТ 19.003-80 (обозначение символов соответствует международному стандарту ISO 1028-73).

Правила выполнения схем алгоритмов регламентирует ГОСТ 19.002-80 (соответствует международному стандарту ISO 2636-73).

Блок-схема должна иметь начало и конец. Связь между блоками отмечается линиями потока информации, которые показывают последовательность решения задачи. Основное направление потока информации идет сверху вниз и слева направо. Здесь стрелки на линиях можно не указывать. Нумерация блоков производится от начала в порядке их расположения на блок-схеме. Направление линий потока, идущих снизу вверх и справа налево, показывается стрелками. По отношению к блоку линии потока могут быть входящими или выходящими. Количество входящих линий для блока принципиально не ограничено. Выходящая линия может быть только одна. Исключение составляют логические блоки (блоки проверки условия), имеющие не менее двух выходящих линий потока, каждая из которых соответствует одному из возможных исходов проверки логического условия. Над линиями выхода обозначается логическое условие выхода: «Да», если условие выполнено, и «Нет», если условие не выполнено), а также блоки модификации.

Часто используются блоки, представленные в таблице 1.

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

Таблица 1. Блоки, используемые при построении блок-схем

	Начальный блок		Конечный блок
	Блок ввода – вывода. Используется для обозначения операций обмена информацией между устройствами.		Блок вычислений или функциональный блок. В этом блоке осуществляется преобразование информации по заданному действию S.
	Блок проверки условия используется для управления преобразованием информации. В результате анализа выполнения условия Р выбирается одно из двух возможных направлений «да» или «нет», и управление передается блоку, записанному на выбранном направлении.		Блок модификации. Используется для организации цикла с параметром. Сначала управление передается к блоку по стрелке вниз, который повторяется заданное число раз, затем управление передается к блоку, следующему за блоком модификации.
	Соединитель		Межстраничный соединитель

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

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