Гаврилов А.В. НГТУ, кафедра АППМ 1 Информатика Лекция 4 Алгоритмы

Гаврилов А.В. НГТУ, кафедра АППМ 2 Определения алгоритма «Алгоритм это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) «Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров) «Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков) «Алгоритм строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович) «Алгоритм это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio) «Алгоритм это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич) «Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм».

Гаврилов А.В. НГТУ, кафедра АППМ 3 Определения алгоритма (2) «Алгоритм однозначно, доступно и кратко (условные понятия названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач». «Алгоритм это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые: –дискретны; –детерминированы; –потенциально конечны; –преобразовывают некоторые конструктивные объекты.

Гаврилов А.В. НГТУ, кафедра АППМ 4 Пример алгоритма «Переход дороги» Посмотри налево Если приближается автомобиль жди, когда он проедет Перейди на середину дороги Посмотри направо Если приближается автомобиль, жди, когда он проедет Перейди дорогу

Гаврилов А.В. НГТУ, кафедра АППМ 5

6 Алгоритм нахождения наибольшего общего делителя (НОД) делением (алгоритм Евклида) 1.Большее число делим на меньшее. 2.Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). 3.Если есть остаток, то большее число заменяем на остаток от деления. 4.Переходим к пункту 1.

Гаврилов А.В. НГТУ, кафедра АППМ 7 Пример выполнения Найти НОД для 30 и /18 = 1 (остаток 12) 18/12 = 1 (остаток 6) 12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6

Гаврилов А.В. НГТУ, кафедра АППМ 8 Исходный код на языке Pascal Program Example_11; Var x, y: Integer; Begin Writeln('Введите два числа'); Readln(x,y); {вводим два целых числа} If x>y Then x:=x Mod y Else y:=y Mod x; Until (x=0) Or (y=0); {до тех пор, пока одно из чисел не станет равно нулю} Writeln('НОД=', x+y)); {вывод НОД - без условного оператора, так как одно из чисел обязательно равно нулю} Readln; End.

Гаврилов А.В. НГТУ, кафедра АППМ 9 Исходный код на языке Python a = 50 b = 130 while a!=0 and b!=0: if a > b: a = a % b else: b = b % a print (a+b)

Гаврилов А.В. НГТУ, кафедра АППМ 10 Свойства алгоритма Детерминированность определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. Понятность алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, т.е. которые входят в его систему команд. Завершаемость (конечность) при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0. Массовость (универсальность) алгоритм должен быть применим к разным наборам исходных данных.

Гаврилов А.В. НГТУ, кафедра АППМ 11 Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе. Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

Гаврилов А.В. НГТУ, кафедра АППМ 13 Происхождение слова «алгоритм» Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль- джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово «Алгебра».

Гаврилов А.В. НГТУ, кафедра АППМ 14 Виды представления алгоритма Графический –Блок-схема или схема алгоритма Текстовый –Псевдо-код – текст на языке, похожем на естественный –Код на языке программирования Программа –Код в памяти компьютера на языке команд компьютера

Гаврилов А.В. НГТУ, кафедра АППМ 15 Элементы блок-схемы алгоритма Название символа Обозначение и пример заполнения Пояснение Процесс Вычислительное действие или последовательность действий Решение Проверка условий Модификация Начало цикла Предопределен- ный процесс (подпрограмма) Вычисления по подпрограмме, стандартной подпрограмме Ввод-вывод Ввод-вывод в общем виде Пуск-останов Начало, конец алгоритма, вход и выход в подпрограмму Документ Вывод результатов на печать A=12

Гаврилов А.В. НГТУ, кафедра АППМ 16 Алгоритм вычисления факториала N! F

Гаврилов А.В. НГТУ, кафедра АППМ 17 Пример анализа алгоритма по его блок-схеме 1) А=-2; С=-3 2) А=-1; С=-2 3) А=0, С=-1 4) А=1; С=0 5) А=1, С=0 При каких начальных значениях переменных алгоритм закончит работу Один из вариантов исходных данных