Размер шрифта
  • A
  • A
  • A
Цвета сайта
  • A
  • A
  • A
  • БЕЗ КАРТИНОК
  • С КАРТИНКАМИ



"Объясняем.РФ"

















Теория алгоритмов в колледже в Омске

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

В XVII веке Г. Лейбниц пытался найти общий алгоритм решения любых математических задач. Но только в ХХ веке, когда алгоритм стал объектом математического изучения, выдвинутая Г. Лейбницем идея, приобрела более конкретную форму. Уже в начале ХХ века Э. Борель (1912 г.), Г. Вейль (1921 г) пришли к понятию алгоритма как эффективной вычислительной процедуре, определив ее термином вычислимой функции. Частичная формализация понятия алгоритма началась с попыток решения проблемы разрешения, которую сформулировал Давид Гильберт в 1928 году. Следующие этапы формализации были необходимы для определения эффективных вычислений или «эффективного метода». Среди таких формализаций — рекурсивные функции Геделя — Эрбрана — Клини (1930 – 1935 г.г.), λ-исчисление Алонзо Чёрча (1936 г.). Понятие вычислимой функции было уточнено математиками А. Черчем, К. Геделем (1936 г.). Ими был определен класс частично рекурсивных функций, имеющих строгое математическое определение. Одним из следующих формальных определений алгоритма является определение английского математика А.Тьюринга, который в 1936 году описал схему гипотетической (абстрактной) машины, имитирующей алгоритмические процессы, которые он и назвал алгоритмом в случае их успешной реализации, т.е. алгоритм – это то, что умеет делать такая машина. А если что-то не может быть сделано машиной Тьюринга, то это уже не является алгоритмом. Таким образом, А.Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции.

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

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

В 1954 году советский математик А.А. Марков предложил свою алгоритмическую схему преобразования слов и назвал ее нормальным алгоритмом. Он ввел также понятие нормализации как перехода от разных способов описания алгоритмов к эквивалентным нормальным алгоритмам. Основная гипотеза теории алгоритмов в форме Маркова звучит так:

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

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

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

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

2. Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычисления на выход.

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

4. Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи из данной массовой проблемы.

Хотите узнать больше о "Теории алгоритмов"?

Добро пожаловать в АНПОО «СРШБ (колледж)» для обучения по специальности 09.02.07 Информационные системы и программирование. Доступна очная и заочная формы обучения.