Казимир Малевич (1879-1935)Определение алгоритма. Представление алгоритма: псевдокод, блок-схема. Базовые алгоритмические конструкции. Лекция 1 Алгоритм. - презентация

1

2 Казимир Малевич ( )

3 Определение алгоритма. Представление алгоритма: псевдокод, блок-схема. Базовые алгоритмические конструкции. Лекция 1 Алгоритм – это упорядоченный набор конечного числа строго определенных выполнимых шагов для решения задачи определенного типа. Конечность. Задача. Даны два отрезка разной длины a и b. Построить c - наибольший из отрезков, укладывающихся целое число раз в данных отрезках. Алгоритм(?). Пусть |a| > |b|. Шаг 1. Отложим отрезок b на отрезке а наибольшее количество раз. Шаг 2. Если b точно отложился на a целое число раз, то выполнение алгоритма прекращается, задача решена, искомый отрезок – это b. Шаг 3. Принять в качестве отрезка b остаток отрезка а, куда не помещался отрезок b, а в качестве отрезка a отрезок b и перейти к Шагу 1. Является ли данный набор шагов алгоритмом? Определение алгоритма.

4 Если существует некий отрезок, пусть очень малой длины, укладывающийся целое число раз в отрезках a и b, то можно среди таких отрезков найти и наибольший, используя приведенный выше набор шагов. Но может не существовать такого отрезка, в этом случае говорят, что отрезки несоизмеримы (отношение их длин выражается бесконечной непериодической десятичной дробью). Тогда последовательность приведенных шагов становится бесконечной. Таким образом, в общем случае вышеприведенный набор шагов не является алгоритмом. Для соизмеримых отрезков этот набор является алгоритмом (геометрический аналог алгоритма Евклида). Вопросы: Является ли метод деления столбиком алгоритмом нахождения частного? (бесконечные периодические дроби) Является ли метод деления столбиком алгоритмом нахождения частного с заданной точностью? То же для вавилонского метода оценки квадратного корня x из целого числа y: x:=(x+y/x)/2.

5 Определенность. Задача. Найти длину гипотенузы прямоугольного треугольника, зная длину его катетов. Шаг 1. Возвести в квадрат длину 1-го катета Шаг 2. Возвести в квадрат длину 2-го катета Шаг 3. Сложить полученные числа. Шаг 4. Извлечь квадратный корень из полученного числа. Является ли этот набор шагов алгоритмом? Не определен шаг 4. При извлечении корня получается два числа и только одно из них положительное – арифметический квадратный корень. Необходимо детализировать этот шаг с тем, чтобы результат его выполнения был однозначным.

6 Выполнимость. … Шаг N. Умножить полученное число на сумму x+y+z, где (x,y,z) из N 3 является решением уравнения x 4 +y 4 =z 4 с наименьшим значением x. … Является ли этот набор шагов алгоритмом? Во-первых, шаг N неоднозначен, при одном x может быть несколько решений с разными суммами. Во-вторых, и это главное, шаг N содержит невыполнимые действия. Дело в том, что в соответствие с уже доказанной теоремой Ферма таких решений вообще не существует. [алгоритмически неразрешимые задачи; 10-я проблема Гильберта; вычислимость [А. Тьюринг]]

7 Представление алгоритма. Псевдокод, pidgin Pascal, C и т.п. Блок-схема. [диаграмма активности в UML] Программы на языке высокого уровня. Программа – последовательность нулей и единиц. Виды представлений. Базовые алгоритмические конструкции. Присвоен ие. := Следование. Действие 2 Действие 1

8 Ветвление. Условие Действие1 Действие 2 нет да Условие Действие 2 Если то иначе Конец-если Услови е Действие нет да Цикл-пока. Цикл-пока Конец-цикл

9 нет Условие Действие да Цикл-до (repeat). Выполнять До i=i0, in, ih Действие Счетный цикл Для = Конец-цикл

10 … … Код Действие 1 Действие 2 Код 1Код 2... Выбор. Выбор : … Конец-выбор

11 (список параметров) Последовательность действий (тело процедуры) Возврат Процедура. Описание процедуры: Процедура ( ) …………….. [ := ] Возврат Вызов процедуры: ( )

12 Представить алгоритм Евклида в виде псевдокода и блок-схемы. Шаг1. Разделим m на n и пусть r – остаток. Шаг2. Если r=0, то выполнение алгоритма прекращается; n – искомое значение. Шаг3. Присвоить m:=n, n:=r и вернуться к шагу1. Программа Евклид Ввод m, n r:=m%n Цикл-пока r не равно 0 m:=n n:=r r:=m%n Конец-цикл Вывод n Конец Упражнение Ввод m,n r:=m%n Евклид r = 0 m:=n n:=r r:=m%n Вывод n Конец да нет Задание. Будет ли алгоритм работать, если m