Алгоритм и его формальное исполнение

1. ОПРЕДЕЛЕНИЯ Алгоритм Алгоритм - это конечная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью точных и понятных исполнителю команд. Исполнитель - Исполнитель - человек, живое существо или автоматическое устройство, способное к восприятию и выполнению данных команд. Система команд исполнителя Система команд исполнителя - перечень команд, которые понимает и может исполнить исполнитель.

2. ПРИМЕРЫ ВЫЧИСЛИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ : ПРАВИЛО ВОЗВЕДЕНИЯ ЧИСЛА В СТЕПЕНЬ; ИЗВЛЕЧЕНИЕ КОРНЯ; СЛОЖЕНИЕ, УМНОЖЕНИЕ, ДЕЛЕНИЕ ДРОБЕЙ; РЕШЕНИЕ ЛИНЕЙНЫХ, КВАДРАТНЫХ И ДР. УРАВНЕНИЙ; НАХОЖДЕНИЕ S И V ФИГУР, ВЫЧИСЛЕНИЕ НОД, НОК, НЕВЫЧИСЛИТЕЛЬНЫЕ (БЫТОВЫЕ): РЕЦЕПТ ПРИГОТОВЛЕНИЯ БЛЮД; ПРАВИЛО ПОЛЬЗОВАНИЯ ЛИФТОМ, МЕЖДУГОРОДНИМ ТЕЛЕФОНОМ; ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ ЭЛЕКТРОПРИБОРОВ.

3. СВОЙСТВА АЛГОРИТМОВ Дискретность Дискретность - алгоритм должен быть разбит на шаги (отдельные законченные действия); Определённость Определённость - у исполнителя не должно возникать двусмысленностей в понимании шагов алгоритма (исполнитель не должен принимать самостоятельные решения); Результативность (конечность)Результативность (конечность) - алгоритм должен приводить к конечному результату за конечное число шагов; Понятность и выполнимость Понятность и выполнимость - алгоритм должен быть понятен для исполнителя; Эффективность Эффективность - из возможных алгоритмов выбирается тот алгоритм, который содержит меньше шагов или времени на его выполнение требуется меньше; Детерминированность Детерминированность – команды должны выполняться в строгой последовательности; Массовость Массовость – один и тот же алгоритм может применяться к большому количеству однотипных объектов.

4. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ Выбор средств и методов для записи алгоритма зависит прежде всего от назначения самого алгоритма, а также от того, кто будет исполнять алгоритм. Алгоритмы записываются в виде: словесных правил, блок схем, программ.

5. СЛОВЕСНЫЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМОВ Это, по существу, обычный язык, но с тщательным отбором слов и фраз, не допускающих лишних слов, двусмысленностей и повторений. Дополняется язык обычными математическими обозначениями и некоторыми специальными соглашениями. Алгоритм описывается в виде последовательности шагов. На каждом шаге определяется состав выполняемых действий и направление дальнейших вычислений. При этом, если на текущем шаге не указывается какой шаг должен выполняться следующим, то осуществляется переход к следующему шагу.

Пример 1. Решение: Пример 1. Составьте алгоритм нахождения наибольшего из трех заданных чисел a, b, c. Решение: 1. Сравнить a и b. Если a>b, то в качестве максимума t принять a, иначе (a<=b) в качестве максимума принять b. 2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<=c) принять в качестве максимума с (t=c). 3. Принять t в качестве результата.

НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА ОПИСАНИЯ АЛГОРИТМОВ отсутствие наглядности, недостаточная точность.

ДОСТОИНСТВА СЛОВЕСНОГО СПОСОБА ОПИСАНИЯ АЛГОРИТМОВ С его помощью можно описать любые алгоритмы, в том числе и вычислительные.

СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ЗАПИСИ СЛОВЕСНЫХ АЛГОРИТМОВ. 1) все шаги нумеруют, 2) для задания значения исходных данных используют указания: ВВЕСТИ, 3) для запоминания промежуточного результата используют вспомогательные переменные, 4) для задания значений переменных используется знак присваивания (:=). Слева от него записывают ту переменную, которой присваивается значение выражения, находящегося справа от знака присваивания. Например, x:=x+1, 5) для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.

Пример 2. Составьте алгоритм построения равностороннего треугольника с помощью циркуля и линейки. Решение: Алг Треугольник Начало 1. На произвольной прямой выбрать точку А. 2. Раствором циркуля, равным а, отложить отрезок АВ=в. 3. Из точки А провести окружность радиуса b. 4. Из точки В провести окружность радиуса b. 5. Точку пересечения окружностей обозначить С. 6. Соединить точку С с точками А и В. Конец

6. ГРАФИЧЕСКИЙ СПОСОБ ОПИСАНИЯ АЛГОРИТМА (БЛОК-СХЕМЫ) Это способ представления алгоритма с помощью общепринятых графических фигур (блоков), каждая из которых описывает один или несколько шагов алгоритма. Внутри блока записывается описание команд или условий. Для указания последовательности выполнения блоков используют линии связи (линии соединения). Последовательность блоков и линий образуют блок-схему алгоритма.

2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева направо; 3. Противоположные направления обязательно указывают стрелкой на линии. 4. Для удобства блоки могут помечаться метками (буквами или цифрами). 5. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, принадлежащих вводу/выводу. 6. Внутри блока действия для присваивания переменных значений используется знак присваивания. ПРАВИЛА ИЗОБРАЖЕНИЯ БЛОК-СХЕМ АЛГОРИТМА

Пример нахождения максимума трех чисел.

7. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПРОГРАММ Программа - алгоритм, записанный на языке программирования. Алгоритм, предназначенный для исполнения на компьютере, записывается на языке программирования ( языке, понятном ЭВМ). Наиболее популярные языки: Си Паскаль Delphi Бэйсик

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

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

ЗАДАНИЕ Задача: –Имеются два кувшина: 8 л и 3 л. С помощью этих кувшинов налейте 4 л. воды. Опишите алгоритм решения задачи словесным способом и графическим.