Понятие алгоритма

Каждый человек ежедневно встречается с большим количеством задач от простых до очень сложных. Для многих из них существуют хорошо известные всем правила, указания, инструкции их выполнения. Например, последовательность действий пешехода при переходе проезжей части улицы, включение компьютера и т.д. Чем точнее сформулированы эти правила, тем быстрее человек усилится и будет эффективно применять. Вы, наверное, учитывая свой жизненный опыт заметили, что легче помнить короткие, немногословные указания, а всю инструкцию для некоторых легче запомнить, если указания, последовательность действий пронумерованы или когда инструктор отмечает: ... во-первых ... »,« ... во-вторых ... »и т.д. Как правило, такие инструкции, описания последовательности действий нацелены на достижение вполне определенного результата. Каждый из нас выполняет сотни различных инструкций, указаний, распоряжений, придерживаясь различных правил. В дальнейшем инструкции, описания действий, команды, распоряжения будем называть одним словом - алгоритм.

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

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

Алгоритм - первичное понятие информатики (как точка, прямая, плоскость, расстояние в геометрии; материя, энергия в физике и т.д.). Информатика выделяют следующие классы алгоритмов: вычислительные, информационные и управляющие, Вычислительные алгоритмы, как понятно из названия, - алгоритмы, которые работают с числами, векторами, матрицами. В математике развивается целая отрасль, которая называется «вычислительная математика».

Информационные алгоритмы - набор простых процедур обработки больших объемов информации. Вспомните операции поиска символа или слова в текстовом процессоре, поиск данных, фильтры в электронных таблицах и т.д.

Управляющие алгоритмы обрабатывают данные, поступающие к ним от внешних процессов, и результатом их работы является управляющий сигнал как реакция на быстрое изменение входных данных.

В 30ти годы XX в. возникла теория алгоритмов, которая исследует вопросы построения конкретных алгоритмических моделей, каждая из которых содержит конкретный набор элементарных шагов, способов определения следующего шага. Теория алгоритмов также исследует вопрос существования эффективных алгоритмов решения конкретной или общей задачи. Наиболее ценными являются алгоритмические модели, были бы и универсальные, и простые.

Сложность алгоритма - количественная характеристика, которая определяется временем (временная), за который выполняется алгоритм; объемом памяти компьютера (емкостная), необходимой для хранения текста программы, данных и промежуточных результатов, результатов выполнения программы.

На практике пользователя больше интересуют не сами алгоритмы, а задачи, которые можно решить с их помощью. А поскольку для решения задачи существуют различные алгоритмы, поэтому, естественно, среди всех известных вам выбрать тот, который имеет наименьшую сложность (выбрать самый простой). Что же в этом вопросе нас больше всего интересует?
• Средства создания алгоритмов;
• известные алгоритмы решения типовых задач;
• методы сравнения различных алгоритмов, решающих одну и ту же
задачу.

Примеры алгоритмов
Как вы уже знаете, возникновение понятия алгоритма связано с математикой. И именно в школьном курсе математики вы часто встречались с алгоритмами: на уроках математики еще в начальной школе вы учились поразрядной складывать, вычитать и умножать числа, на уроках геометрии - правила построения середины отрезка, биссектрисы угла, построения треугольника по трем его элементами, в курсе алгебры - алгоритм решения квадратного уравнения, подъем двучлена в степень, построения графика функции и т.п.

Основы алгоритмизации и программирования и правила на уроках физики, химии; учили правила правописания. С алгоритмами мы проводим всю жизнь. Распорядок дня ученика, регламент работы школы, правила поведения в общественных местах, в транспорте, товариществе - примеры алгоритмов.

Вам известна задача о перевозке через реку волка, козы и капусты. Решением этой задачи является алгоритм перевозки.

Мало того, что мы живем в сплошном информатизированном пространстве, мы еще и всю жизнь выполняем алгоритмы.

Свойства алгоритма
Из всего сказанного можно сделать вывод, что алгоритм является инструкцией, последовательностью некоторых указаний, но не каждая инструкция или последовательность действий является алгоритмом.

Основные свойства алгоритма:
Дискретность - Любой алгоритм изображается в виде последовательности отдельных действий.
Выполнение команд алгоритма должно быть последовательным с точной фиксацией завершения выполнения одной команды и начала выполнения следующей (как выполнение музыкальной упражнения, где указано продолжительность и высоту каждого звука - ноты).

Конечность - выполнение алгоритма завершается после завершения конечного количества шагов.
Вычисление доли от деления носит алгоритмический характер, но сам процесс деления не всегда конечным, аналогично - вычисление значения квадратного корня из простого числа и т.д. Следовательно, это свойство не выполняется для алгоритма деления натуральных чисел, но свойственная для алгоритма деления рациональных чисел.

Определенность - каждый шаг алгоритма должен быть четко и однозначно сформулирован и не допускать произвольного, двусмысленной трактовки исполнителем.

Алгоритм рассчитан на механическое исполнение. Если поручить двум разным исполнителям выполнить один и тот же алгоритм, то они должны получить не только один и тот же результат, а получить его за одинаковое количество шагов.

Понятность - формулировка действий алгоритма должно быть ориентировано на конкретного исполнителя.

Исполнитель должен понимать и осознанно выполнять команды алгоритма. Если же исполнитель является некомпетентным человеком в вопросах, решаемых по алгоритму, то необходимо выбрать доступную для формулирования форму, которой является словесный образ. Если же выполнение алгоритма будет предложено компьютеру, то сам алгоритм ритм необходимо записать соответствующей машинной или понятной для машины языке.

Массовость - в алгоритме должна предусматриваться возможность его применения для различных аргументов (значений исходных данных величин).
Этим самым мы обеспечиваем использования алгоритма для решения однотипных задач (не только на яблоки и груши, но и для других овощей).
Результативность - алгоритм должен обеспечивать обязательное получение результата после конечного количества шагов.
Понятно, что алгоритм, который не дает результатов, для конкретной задачи является излишним.

Эффективность - каждый шаг алгоритма должен быть выполнен точно по кончен промежуток времени.

Каждая команда, действие, должна быть достаточно простой, чтобы исполнитель мог выполнить ее точно за конечное промежуток времени и в пределах команды.

Исполнитель алгоритма
Точное определение исполнителя очень сложный и для нас не является необходимостью. Важно понять основные характеристики исполнителя: среда, элементарные действия, система команд, отказ. Среда - место нахождения исполнителя. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка команд - системы команд исполнителя. Для каждой команды должны быть заданы условия применения, т.е. в каких состояниях среды может быть выполнена команда.

Исполнителя можно представлять в виде некоторого устройства, управляемого побуждает к выполнению той или иной команды. После вызова команды исполнитель осуществляет соответствующую элементарное действие (в данном случае нас интересует результат действия, а не механизм выполнения команды). Отказы исполнителя возникают в случае вызова команды в недопустимом для этой команды состоянии среды (деление на 0, вычисление логарифма отрицательного числа и т.д.). Ситуации, при которых возникают отказы, разные для разных команд. Во время выполнения некоторых команд отказа никогда не возникают.

В некоторых случаях исполнителем алгоритма является человек, но человек - не единственный исполнитель алгоритма. Роботы манипуляторы, станки с числовым программным управлением (ЧПУ), автоматы (механические часы), живая клетка, дрессированные животные в цирке <5 исполнителями алгоритмов, даже таких, которые человеку не под силу.

Что же такое (кто такой) исполнитель - упрощенно, формально, абстрактно - это устройство управления, соединенный с набором инструментов. Устройство управления понимает алгоритмы и организует их выполнение, управляя соответствующими инструментами. Инструменты выполняют элементарные действия, реализуя команды управляющего устройства. Если человек - исполнитель, то мозг - управляющий устройство, конечности и другие органы - инструменты. У роботов-автоматов, станков с ЧПУ, компьютеров устройством управления является процессор, а набор инструментов зависит от задач, для которых предназначен исполнитель.

Под формальным выполнением алгоритма понимается такое его выполнения, когда сам исполнитель не знает ни постановки задачи, ни содержания полученных результатов, но, четко выполняя все действия, записанные в алгоритме, достигает необходимого результата.
Чаще алгоритм выполняется формально. Формальными исполнителями являются пользователи различных бытовых приборов, большинство учащихся при выполнении задач по физике, химии, математики по известным формулам, написание диктантов с использованием языковых правил.
Компьютер тоже является формальным исполнителем алгоритмов при исполнении им программ.

Аргументы и результаты алгоритма
Для работы большинства программ необходимо задавать начальные значения величин, которые обрабатываются этим программам. Эти значения передаются в алгоритм с помощью аргументов.
Аргументы - это величины, значения которых нужно задать для выполнения алгоритма.
Правда, встречаются алгоритмы, которые не требуют никаких начальных значений для своего исполнения, однако нет ни одного алгоритма, который не дает никакого результата - какой же смысл в таком алгоритме?

Результаты - это величины, значения которых получают в результате выполнения алгоритма.
При составлении многих алгоритмов возникает необходимость запоминать результаты промежуточных вычислений, в процессе дальнейшего выполнения алгоритма будут использоваться для выполнения алгоритма в целом. Значения промежуточных результатов называют промежуточными величинами.

Промежуточные величины - величины, которые дополнительно вводятся 1 в процессе разработки алгоритма.
Так во время решения общего квадратного уравнении ах2 + bх + с = 0 по формуле корней вы предварительно вычисляете значение дискриминанта В = Ь2 4ас. Здесь аргументами является коэффициент уравнения а, Ь и Су значение дискриминанта £> - промежуточная величина, а значения корней уравнения - результатами выполнения алгоритма решения квадратного уравнения по формуле корней.

Вы уже представляете, что такое алгоритм? А как он выглядит с точки зрения пользователя? Чаще всего обычный пользователь не знает, каким образом этот алгоритм (компьютерная программа) записан, на каком языке программирования, с помощью каких команд достигается результат, какие методы были применены для его реализации. Пользователь видит только внешнюю сторону (реализован сценарий): какие исходные данные нужно задать и в каком виде получается результат. Каждый из вас наверняка сталкивался с домашней кухонной мясорубкой. Часто ли вы задумывались над тем, что происходит в ней во время перемалывания мяса на фарш? А вспомните увиденного по телевизору или в цирке фокус иллюзиониста, который в цилиндр или в черный ящик ставит одни предметы, а вынимает другие. Такой «черной ящиком» для пользователя является алгоритм, которым он пользуется.

Выполним несколько задач.
1. Вспомните алгоритм деления отрезка пополам. Что являются аргументами этого алгоритма? Конечно, концы отрезка, а результатом являются отрезка, которая является его серединой. Есть ли здесь промежуточные величины? Да, это засечки в разных полуплоскость, границей которых является прямая, содержащая отрезок; прямая, которая проходит через точки. Проанализируйте, выполняются все свойства для этого алгоритма.

2. Сформулируйте задачу о перевез волка, козы и капусты. Запишите алгоритм с графической иллюстрацией (схематическими рисунками) решения этой задачи. Является ли этот алгоритм массовым? дискретным? конечным?

3. В начальной школе, после того как вы изучили таблицу умножения, учитель показывал фокус отгадывания задуманного числа, при этом вы задумывали число и выполняли, пусть, следующее:
1) умножить задуманное число на 5;
2) к произведению прибавить 8;
3) полученное сумму умножить на 2;
4) сообщить результат.