Понятие алгоритма и его характерные черты

    Понятие алгоритма принадлежит к числу основных понятий математики. Оно прошло большой путь развития. Еще в период зарождения математики в ней стали возникать различные вычислительные процессы чисто механического характера, с помощью которых искомые величины целого класса задач вычислялись последовательно из данных исходных величин по определенным правилам. Со временем такие процессы в математике получили название алгоритмов. Примерами алгоритмов являются:
    1. Правила выполнения арифметических действий над числами.
    2. Правило отыскания наибольшего общего делителя (алгоритм Евклида).
    3. Правило извлечения квадратного корня
    4. Правило отыскания решений квадратного уравнения
    5. Правило отыскания производной многочлена \(n\)-ой степени.
    6. Правило интегрирования рациональной функции.
    В каждом из приведенных примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения \(ax^{2} +bx + c=0\) участвует три параметра \(a\), \(b\) и \(c\); меняя их, получаем различные задачи одного класса.
    В связи со сказанным можно дать следующее интуитивное определения понятия алгоритма.
    Алгоритмом называется общий единообразный, точно определённый способ решения любой задачи из данной массовой проблемы.
    Такое определение нельзя считать строгим. Действительно, в нем встречаются слова, точный смысл которых не установлен. В частности. это касается слова "способ". В связи с этим это не строгое определение алгоритма называют интуитивным.
    Отметим характерные черты понятия алгоритма.
    1. Дискретность алгоритма. Алгоритм – это процесс последовательного построения величин таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определённому закону из системы величин, имевшихся в предыдущий момент.
    2. Детерминированность алгоритма. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.
    3. Элементарность шагов алгоритма. Закон получения последующей системы величин из предшествующей должен быть простым.
    4. Массовость алгоритма. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.
    5. Результативность алгоритма. Последовательный процесс построения величин должен быть конечным и давать результат, то есть решение задачи.
    Алгоритмы, в которых основную роль играют математические действия, называются численными алгоритмами. От численных алгоритмов отделяют логические алгоритмы игр. В качестве примера, дающего логический алгоритм, рассмотрим следующую игру.
    Пример. Имеется 15 предметов. В игре участвуют двое: начинающий и противник. Каждый иrрок по очереди берет один, два или три предмета. Выигрывает то, кто берет последний предмет. Какой стратегии в игре должен придерживаться начинающий, чтобы выиграть?
    Решение. Выигрышная стратегия начинающего может быть описана в форме следующей таблицы:

Номер хода Ход начинающего Ход противника
1
3
\(n\)
2
\(4 - n\)
\(m\)
3
\(4 - m\)
\(p\)
4
\(4 - p\)
0

    Действительно, в итоге такой стратегии начинающий возьмет \(3 + ( 4- n) + ( 4- m) + ( 4-p) = 15 - ( n+m +p)\) предметов, а противник возьмет \(n+m +p\) предметов, то есть в сумме они возьмут 15 предметов, и последний предмет будет взят начинающим.
    Слово "алгоритм" происходит от имени узбекского o математика ХІІІ века Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси. Оно претерпело эволюцию: ал Хорезми - ал Горезми - алгоритм.


2012-11-12 • Просмотров [ 2282 ]