Введение в теорию алгоритмов. Алгоритм. Свойства алгоритмов

Введение в теорию алгоритмов. Алгоритм. Свойства алгоритмов. Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Именно поэтому важно в нем разобраться. Алгоритм — точное предписание, которое задает алгоритмический процесс, начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определенного этим исходным данным результата. Это — не определение в математическом смысле слова, а, скорее, описание интуитивного понятия алгоритма, раскрывающее его сущность. Алгоритмический процесс – процесс последовательного преобразования конструктивных объектов (слов, чисел, пар слов, пар чисел, предложений и др.), происходящий дискретными шагами. Основные свойства алгоритма: дискретность, понятность, определенность, результативность, массовость. Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя хаpактеpизуют: среда; элементарные действия; система команд; отказы; «формальность» действий. В информатике универсальным исполнителем алгоритмов является компьютер. Сpеда (или обстановка) — это "место обитания" исполнителя. А расположение и положение исполнителя задают конкретное состояние среды. Система команд исполнителя – вся совокупность команд, которые данный исполнитель умеет выполнять. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементаpное действие. Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии среды. Исполнитель действует «формально», т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые действия (команды) для получения необходимого результата. Теперь уточним понятие алгоритма, используя понятие исполнителя алгоритма. Алгоpитм — заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов. Как фундаментальное научное понятие алгоритм требует строгого его описания, т.е. «формализации». Известны следующие подходы к формализации понятия алгоритма: • теория конечных и бесконечных автоматов (машины Поста, Тьюринга, нормальные алгоритмы Маркова и др.); • теория вычислимых (рекурсивных) функций; • -исчисление Черча (язык программирования LISP). Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. На практике наиболее распространены следующие формы представления (записи) алгоритмов: • словесная (запись на естественном языке); • графическая (изображения из графических символов); • псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); • программная (тексты на языках программирования). Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных на естественном языке. Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. При графическом способе алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма или блок-схемой. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов, занимает промежуточное место между естественным и формальным языками. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. На практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов и школьный алгоритмический язык. Базовая структура «следование». Образуется последовательностью действий, следующих одно за другим: Школьный алгоритмический язык Язык блок-схем действие 1 действие 2 . . . . . . . . . действие n Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах: если—то; если—то—иначе; выбор; выбор—иначе.     Школьный алгоритмический язык     Язык блок-схем 1. если—то если условие   то действия все 2. если—то—иначе если условие   то действия 1   иначе действия 2 все 3. выбор выбор   при условие 1: действия 1   при условие 2: действия 2   . . . . . . . . . . . .   при условие N: действия N все 4. выбор—иначе выбор   при условие 1: действия 1   при условие 2: действия 2   . . . . . . . . . . . .   при условие N: действия N   иначе действия N+1 все Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице: Школьный алгоритмический язык Язык блок-схем Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. нц пока условие   тело цикла   (последовательность действий) кц Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.      нц для i от i1 до i2   тело цикла   (последовательность действий) кц При построении алгоритма для сложной задачи используют системный подход с использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (программирование снизу-вверх). Как и при разработке структуры сложной системы, при формировании алгоритма используют дедуктивный и индуктивный методы. Существуют множества методов разработки алгоритмов, но необходимо назвать следующие основные: метод частных целей (декомпозиции); метод подъема; метод ветвей и границ; метод отрабатывания назад; методы, основанные на использовании структур данных, динамическое программирование и другие.