Различные аспекты понятия алгоритм. Фундаментальный аспект

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

Фундаментальный аспект понятия алгоритм.

Некоторые этапы построения математики:

1. Дедуктивный (аксиоматический) подход Пифагора (580-500 г.г. до н.э.).

2. Арифметический подход, середина XIX века. Нуль, отрицательные числа и дроби, можно представлять парами натуральных чисел: 0->{1,1}; -5->{1,6}; 2/3->{2,3}, и т.д.

3. Подход теории множеств, конец XIX - начало XX века.

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

 

Логические теории алгоритмов. Тезис Черча.

Примеры выявленных неразрешимых проблем, то есть задач, для которых не существует способа их решения.

Задача о квадратуре круга: требуется найти метод (алгоритм) построения с помощью циркуля и линейки квадрата равновеликого данному кругу.

Задача о трисекции угла: требуется найти способ деления с помощью циркуля и линейки произвольного угла на три равные части.

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

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

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

Тезис Черча

Каков бы ни был алгоритм, перерабатывающий наборы целых неотрицательных чисел в целые неотрицательные числа, существует эквивалентная рекурсивная функция.

Таким образом проблема существования или не существания алгоритма сводится к решению вопроса о существовании или не существовании соответствующей рекурсивной функции.

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

 

Машина Поста.

Машина Поста представляет собой идеальное, воображаемое устройство, состоящее из неограниченной в обе стороны ленты и каретки, способной перемещаться вдоль ленты. Лента разбита на клетки. Любая клетка может быть отмеченной или нет. За один шаг каретка может переместиться на одну клетку вправо или на одну клетку влево. Каретка может определить отмечена текущая клетка или нет, а также поставить в текущую клетку отметку или же стереть её.

 

Машина Поста задается:

1.начальным распределением отмеченных клеток;

2.начальным положение каретки;

3.программой, определяющей последовательность действий каретки.

Командой машины Поста называется указание исполнителю (каретке) выполнить единственное действие из набора возможных действий.

Структура команды машины Поста:

<порядковый номер команды>. <операция> <номер следующей команды>

Невыполнимые команды:

Ø стереть отметку, если текущая клетка не отмечена;

Ø поставить отметку, если текущая клетка уже отмечена.

Выполнение программы может:

Ø не завершится никогда (безостановочная работа);

Ø завершится безрезультатно на невыполнимой команде;

Ø завершится результативно на команде Стоп.

 

Требование к программе машины Поста

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

2. Используемые в командах номера должны обозначать присутствующие в программе команды.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: