Лекция: Интуитивное понятие алгоритма.
Человек ежедневно встречается с множеством задач, возникающих в различных областях деятельности общества, например:
а) подготовиться к уроку по математике;
б) приготовить раствор для проявления фотопленки;
в) избавиться от лишнего веса.
Для решения задач надо знать, что дано, и что следует получить. Другими словами, задача представляет собой совокупность двух объектов: исходных данных и искомых результатов. Чтобы получить результаты, необходимо знать метод решения задачи, то есть располагать предписанием (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу (получить искомые результаты). Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, называется алгоритмом.
Алгоритм — это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) искомого результата.
Следует иметь в виду, что это — не определение в математическом смысле слова, но довольно подробное описание понятия алгоритма, раскрывающее его сущность. Описание может быть другим. Так, в школьном учебнике по информатике понятие алгоритма дается в следующей форме: «Под алгоритмом понимают понятное и точное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи».
Понятие алгоритма является одним из основных понятий современной математики и является объектом исследования специального раздела математики — теории алгоритмов.
Еще на самых ранних ступенях развития математики в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам. К числу таких правил относились и правила выполнения арифметических операций над числами.
Столетия эти правила были очень сложны и не удивительно поэтому, что производить вычисления с большими числами могли только люди с высшим образованием. Так, чтобы научиться арифметическому делению в средние века требовалось закончить университет. Да еще не всякий университет мог научить этой премудрости. Нужно было непременно ехать в Италию: тамошние математики добились большого искусства в делении. Если напомнить, что в те времена пользовались непозиционной (римской) системой счисления, станет ясно, почему деление миллионных чисел было доступно лишь бородатым мужам, посвятившим этому всю свою жизнь.
С введением позиционной системы счисления все изменилось. В IX веке узбекский математик Мухаммед ибн Муса ал-Хорезми («ал-Хорезми» означает «Хорезмиец») описал правила выполнения четырех арифметических действий в десятичной системе счисления. Новые правила были значительно проще и сейчас ими владеют уже школьники младших классов. Поразительная простота указанных правил стимулировала их повсеместное распространение. Эти правила были изложены Мухаммедом в книге по математике, изданной в 825 году, где, кроме того, приводились многочисленные рецепты решения различных задач.
По латинским переложениям арифметического трактата ал-Хорезми средневековая Европа знакомилась с индийской позиционной системой счисления и с искусством счета в этой системе. При переводе имя автора переделали в Алгоритми. Ссылки на рецепты решений из книги Мухаммеда европейские авторы начинали со слов: «Так говорил Алгоритми ...». С течением времени сами рецепты для решения математических задач стали называть алгоритмами.
Первоначально под алгоритмами понимали только правила выполнения четырех арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Примеры алгоритмов:
· Алгоритмы арифметических действий с числами в двоичной системе счисления
· алгоритм нахождения НОД 2-х целых чисел, 2-х многочленов от переменной х;
· алгоритм извлечения ?n,?n?N ;
· алгоритм дифференцирования многочлена от переменной ;
· алгоритм нахождения определителя квадратной матрицы А над
Команды могут быть не пронумерованы. Все команды могут быть записаны последовательно, в виде сплошного текста. Друг от друга команды разделены либо точкой, либо точкой с запятой. При таком оформлении алгоритма исполнитель выполняет команды в порядке их естественного следования в тексте.
Такая форма записи алгоритма часто используется во всякого рода инструкциях, правилах, рецептах и т.п. Она хороша в случае, когда алгоритм небольшой и когда для описания алгоритма отводится мало места. Недостатком такого оформления является его малая наглядность .
Черты, характерные для интуитивного понятия алгоритма
Дискретность. Это свойство заключается в следующем: в начальный момент задается исходная система величин, а в каждый следующий момент система величин получается из предыдущей системы величин по определенному закону (программе).
Детерминированность. Система величин, получаемых в любой, отличный от начального, момент времени, однозначно определяется системой величин в предшествующие моменты времени.
Элементарность шагов. Закон получения последующей системы величин из предыдущей должен быть простым и локальным.
Эффективность (результативность). Каждый шаг работы алгоритма должен заканчиваться результатом.
Массовость алгоритма. Начальная система величин может выбираться из некоторого бесконечного счетного множества Х.
Конструктивность. Объекты из Х, над которым работает алгоритм, должны быть конструктивными.
4. Виды алгоритмов. Свойства и способы задания алгоритмов.
Выделяют следующие виды алгоритмов: линейный, разветвляющийся, циклический, комбинированный.
Алгоритм, который содержит сразу несколько структур называется КОМБИНИРОВАННЫМ.
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.[источник не указан 518 дней] С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
Результативность — завершение алгоритма определёнными результатами.
Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.