LOGO Понятие алгоритма и его основные черты

Понятие «алгоритм» относится к числу наиболее фундаментальных понятий математики

Алгоритм - точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа Интуитивное понятие алгоритма

1) Алгоритм приготовления манной каши 2) Алгоритм сложения двух произвольных натуральных чисел, записанных в десятичной системе счисления Интуитивное понятие алгоритма Приведите примеры алгоритмов (математических и нематематических) 3) Пойди туда, не знаю куда, принеси то, что не знаю

Происхождение слова алгоритм Историческая справка Происхождение слова алгоритм связано с алгоритмами позиционной арифметики Правила с числами, записанными в десятичной системе счисления, были впервые найдены в средневековой Индии

Происхождение слова алгоритм Историческая справка Европейцы познакомились с ними по книге арабского ученого IX века Мухаммеда ибн Муса аль-Хорезми, что буквально означает «Мухаммед сын Мусы, уроженец Хорезма» В те времена Аральское море называлось «озером Хорезм», а сам город Хорезм располагался южнее этого моря в бассейне реки Амударьи Имя ученого аль-Хорезми латинизировалось и стало звучать «алхоризм», «алгорифм», «алгоритм»

Понятия, связанные с понятием алгоритма - Каждый такт работы алгоритма завершается переходом в новое состояние, среди которых некоторые опознаются как заключительные состояния - Каждый алгоритм имеет исполнителя (устройство или человек, выполняющий алгоритм) - Алгоритм задает вычислительный (алгоритмический) процесс, состоящий из отдельных, элементарных шагов – тактов алгоритма - Алгоритм перерабатывает исходный набор данных Р (входной объект) в результат работы Q (объект на выходе)

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

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

3) В некотором состоянии процесс вычислений обрывается без выдачи результата – произошла безрезультатная остановка (например, ошибка – деление на ноль) Варианты протекания алгоритмического процесса

Алгоритм применим к исходному набору данных Р, если на некотором шаге возникает заключительное состояние и выдается результат Q Обозначение: Q = (P) Т.е. алгоритм – процедура вычисления некоторой функции Q = (P)

Алгоритм - это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: - конечность, - определённость, - ввод, - вывод, - эффективность Дональд Эрвин Кнут ( ), американский ученый, иностранный член Российской академии наук, создатель настольной издательской системы ТЕХ

Основные черты алгоритма 1) Дискретность алгоритма Алгоритмический процесс – последовательность элементарных шагов (тактов) Каждый шаг – смена одного набора данных - другими

Основные черты алгоритма 2) Детерминированность алгоритма Для каждой пары (,Р), т.е. данного алгоритма и исходного набора данных Р однозначно определяется результат работы Q, последовательность элементарных шагов и т.д. Т.е. при повторном выполнении с объектом P на входе снова получится объект Q. Это позволяет сообщать алгоритм одним лицом другому, например, компьютеру

Основные черты алгоритма 3) Массовость алгоритма Каждый алгоритм решает какую-нибудь массовую проблему – класс однотипных задач Частные случаи получаются при варьировании исходных данных

Для каждого алгоритма существует некоторая фиксированная, потенциально бесконечная совокупность Х – возможных начальных данных Из этой совокупности выбирается объект Р, поступающий на вход алгоритма

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

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

Абстракция потенциальной осуществимости Т.е. считается, что можно оперировать со сколь угодно большими конечными объектами, например, со сколь угодно длинными словами

Абстракция потенциальной осуществимости Пример Число (единица со ста нулями в десятичной записи счисления) американский математик Эдвард Каснер в 1938 году назвал «гугол», чтобы проиллюстрировать разницу между невообразимо большим числом и бесконечностью

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

Абстракция потенциальной осуществимости Пример Мы не сможем на практике осуществить работу со словом из букв. Но принцип абстракции потенциальной осуществимости разрешает оперировать с такими большими объектами Замечание: Название компании Google является искажённым написанием слова «гугол» («googol»)

Литература 1.Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, с. 2.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с. 3.ВикипедиЯ. Свободная энциклопедия.

Великие силы - только для великих целей