9

Лекция № 5 Основные понятия и определения. Способы представления алгоритмов. Классификация алгоритмов.

Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритм построены все основные принципы программирования — составление программ для вычислительных машин.

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

Термин "алгоритм" своим происхождением обязан имени узбекского математика Аль-Хорезми, который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Появившееся несколько позже слово "алгорифм" связано с именем древнегреческого математика Евклида, назвавшего так сформулированные им правила нахождения наибольшего общего делителя двух чисел. В современной математике употребляется термин "алгоритм".

Умение решать задачи определенного типа, не обязательно математические всегда означает владение соответствующим алгоритмом.

Пример1: Алгоритм приготовления настойки шиповника или др.

Столовую ложку семян измельчить

1. Залить стаканом кипятка

2. Кипятить на слабом огне 10 мин.

3. Охладить

4. Процедить

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

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

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

• постановка задачи;

• математическое описание задачи;

• выбор и обоснование метода решения;

• алгоритмизация вычислительного процесса;

• составление программы;

• отладка программы;

• решение задачи на ЭВМ и анализ результатов.

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

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

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

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

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

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

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

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

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

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

В ходе синтаксического контроля программы транслятором выявляются конструкции и сочетания символов, недопустимые с точки зрения правил их построения или написания, принятых в данном языке. Сообщения об ошибках ЭВМ выдает программисту, при этом вид и форма выдачи подобных сообщений зависят от вида языка и версии используемого транслятора. Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. Компилятор – это транслятор, осуществляющий перевод исходной программы в эквивалентную ей объектную программу на языке ассемблера. Отличие компилятора от транслятора состоит в том, его входная (результирующая) программа должна быть написана на языке машинных команд или на ассемблере. Результат работы транслятора может быть написан на любом языке. Программа-компилятор переводит весь исходный текст программы в машинный код. Всякий компилятор является транслятором, но не всякий транслятор является компилятором. Если трансляторы и компиляторы во многом похожи, то существуют принципиально отличное от них понятие интерпретатора. Интерпретатор – это программа, которая воспринимает входную программу на исходном языке и выполняет ее. Интерпретатор в отличие от транслятора не выдает результирующую программу или код. После анализа текста исходной программы интерпретатор сразу же переводит программа на машинный язык.

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

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

Разработанная программа длительного использования устанавливается на ЭВМ, как правило, в виде готовой к выполнению машинной программы. К программе прилагается документация, включая инструкцию для пользователя.

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

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

Массовость. Это означает, что алгоритм может применяться к задаче исходные данные, которой могут меняться в известных пределах. В примере 2 мы можем брать любое х.

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

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

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

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

• словесный;

• графический;

• алгоритмические языки программирования.

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

Рассмотрим в качестве примера словесной формы задания алгоритм нахождения действительных корней квадратного уравнения ax²+bx+c=0

1. Задать значения чисел а, в и с.

2. Вычислить значение D по формуле D=:b²-4ac

3. Если , то перейти к п.4, иначе перейти к п.6.

4. Вычислить значения х₁ и х₂ по формулам . Решением задачи считать х₁ и х₂.

1. Решение задачи не существует, так как дискриминант отрицательный.

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

 пояснения на естественном языке бывают, неоднозначны и противоречивы;

 запись алгоритма решения сложных задач громоздка и не наглядна, она плохо формализована и не может непосредственно вводится в ЭВМ.

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

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

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

Изобразим алгоритм нахождения действительных корней квадратного уравнения ax²+bx+c=0 графически, в виде блок схемы.

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

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