дм. ДМ №13 (3). Лекция 12 Раздел Элементы теории алгоритмов
 Скачать 119.07 Kb.
|
|
ДМ Лекция № 12 Раздел 5. Элементы теории алгоритмов 1. Теория алгоритмов Во всех сферах своей деятельности, и в частности, в сфере обработки информации, человек сталкивается с различными способами или методиками решения задач. Они определяют порядок выполнения действий для получения желаемого результата – мы можем трактовать это как первоначальное или интуитивное определение алгоритма. Теория алгоритмов – раздел математики, изучающий общие свойства алгоритмов. Эта теория тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики – понятие исчисления. По существу вся математика связана с теми или иными алгоритмами. Само понятие «алгоритм» сформировалось лишь в 1-й половине 20 века. Алгоритмом называется общий единообразный, точно определенный способ решения любой задачи из данной массовой проблемы. Задача (массовая задача) – некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободные переменные, конкретные значения которых не определены. Задача определяется: Общим списком параметров Формулировкой тех свойств, которым должен удовлетворять ответ (решение задачи). Индивидуальная задача получается из массовой, если всем параметрам массовой задачи присвоить конкретные (допустимые) значения. Под алгоритмом принято понимать конечную последовательность операций, называемых элементарными, исполнение которой приводит к решению любой задачи из заданного множества задач. В это определение входят такие свойства алгоритма, как дискретность, конечность (конечное число выполняемых операций), массовость (решается не единственная задача, а их класс), результативность (в результате получаем решение задачи). Кроме того, должно выполняться еще одно необходимое свойство алгоритма – детерминизм, которое определяется как однозначное понимание каждой операции, или, что то же самое, независимость результата выполнения каждой элементарной операции от того, кто ее выполняет. Под это определение подходит широкий круг алгоритмов. Это может быть алгоритм вычисления математической функции, алгоритм технологического процесса, алгоритм проектирования ЭВМ или цеха завода и т.д. Элементарные операции могут быть достаточно сложными: при вычислении это могут быть, например, нахождение корней уравнения, в проектных или технологических алгоритмах – принятие сложных проектных или технологических решений. Данное выше определение алгоритма не является формализованным и строгим по двум причинам. Во-первых, в нем не формализовано понятие элементарной операции, и, во-вторых, не формализовано представление последовательности операций. Важность разработки общего для всех алгоритмов формального описания заключается в том, что оно дает возможность иметь общие инструментарии для сравнения, оценки, преобразования и др. действий над алгоритмами. Формализация операций алгоритмов связано со следующим: любой алгоритм определен для некоторого объекта действия, каждый объект представляется в виде описания, причем описанием может быть не только тексты на языке, но и рисунки, чертежи и т.д. Значит, можно предположить, что объект описан в виде слова в заданном алфавите. Объект может находиться в различных состояниях, чему соответствуют различные слова. Так, объектом для математических алгоритмов является математическое описание задачи в форме матриц коэффициентов, графа смежности и т.п., для проектных алгоритмов – проектируемый объект в виде технического задания на проектирование или перечень требований и условий к результату. Операция определяется над описанием объекта и ее результатом является новое (измененное) описание (новое слово). Например, если решается графовая задача, то результатом операции может быть описание графа с промежуточным взвешиванием ребер и/или вершин. Результатом проектной операции будет более полное, уточненное описание объекта. Результатом работы всего алгоритма в графовой задаче может быть выделенный путь или цепь, частичный подграф или веса вершин или ребер. Результатом работы алгоритма проектирования является описание объекта проектирования, достаточное для его изготовления в заданной технологической базе. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм говорят, что он «вычисляет функцию f», коль скоро его область применимости совпадает с областью определения f, и он перерабатывает всякий х из своей области применимости в f(x). Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой. Важный пример алгоритмической проблемы – проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию). Функция называется вычислимой, если существует вычисляющий ее алгоритм. 2. Основные черты алгоритмических процессов 1. Конечность описания – любой алгоритм задается как набор инструкций конечных размеров, т.е. программа имеет конечную длину. 2. Дискретность – алгоритм исполняется по шагам, происходящим в дискретном времени. Шаги четко отделены друг от друга. В алгоритмах нельзя использовать аналоговые устройства и непрерывные методы. 3. Направленность – у алгоритма есть входные и выходные данные. В алгоритме четко указывается, когда он останавливается, и что выдается на выходе после остановки. 4. Массовость – алгоритм применим к некоторому достаточно большому классу однотипных задач, т.е. входные данные выбираются из некоторого, как правило, бесконечного множества. 5. Детерминированность (или конечная недетерминированность) – вычисления продвигаются вперед детерминировано, т.е. вычислитель однозначно представляет, какие инструкции необходимо выполнить в текущий момент. Нельзя использовать случайные числа или методы. Конечная недетерминированность означает, что иногда в процессе работы алгоритма возникает несколько вариантов для дальнейшего хода вычислений, но таких вариантов лишь конечное число. Пример 1. На плоскости задан прямоугольник, разбитый на одинаковые клетки со стороной единичной длины. Некоторые клетки заштрихованы – это стены, остальные клетки – это коридоры. Т.е. задан лабиринт, вход которого находится в правой нижней клетке, а выход – в левой верхней (*). В начальный момент времени на входной клетке находится Робот, который умеет отличать стены от коридоров, умеет делать ходы на одну соседнюю незаштрихованную клетку сверху, справа, снизу или слева, умеет принимать простейшие логические решения, и способен распознать символ *. Заранее известно, что в таком лабиринте существует как минимум один путь, ведущий по коридорам из входа в выход. Необходимо запрограммировать Робота так, чтобы он, руководствуясь данной программой несложных операций, смог найти выход из лабиринта. Для этого зарезервируем достаточно большое количество меток, занумерованных натуральными числами. Этими метками Робот будет помечать свои ходы. Искомая программа состоит из 6 пунктов.  Помечаем правую нижнюю клетку меткой 0. Переходим к пункту 1) Проверяем, верно ли, что клетка, на котором стоит Робот, является выходом. Если да, то переходим к п.5. Если нет, переходим к п.2) Проверяем существует ли хотя бы одна непомеченная соседняя (сверху, справа, снизу или слева) клетка. Если существует, то переходим к п.3). Если нет, то переходим к п.4) Выбираем каким-нибудь эффективным способом одну соседнюю непомеченную клетку. Например. можно выбирать первую непомеченную клетку при обходе всех четырех соседних клеток по часовой стрелке, начиная с верхней. Помечаем выбранную клетку наименьшей неиспользованной меткой. Затем передвигаем Робота на эту клетку и переходим к п.1) Возвращаемся на один ход назад, т.е. переставляем Робота обратно на ту клетку, в которой он в последний раз перешел на текущую клетку, переходим к п.2) Работа алгоритма останавливается. Выход найден. Проанализируем свойства алгоритма из примера. Конечность – описание алгоритма состоит из 6 пунктов, каждый из которых записан с помощью конечного числа слов Дискретность – один шаг работы алгоритма – это выполнение одного из пунктов (0)-(5), эти шаги можно занумеровать натуральными числами. В итоге Робот проделывает всегда лишь конечное число шагов для того, чтобы найти выход. Направленность – в нашем примере входные данные – это схема лабиринта, выходные данные – путь по коридорам, ведущий к выходу. Массовость – алгоритм годится для поиска выхода из любого лабиринта прямоугольной формы. Детерминированность – действия Робота детерминированы, но этот алгоритм можно переделать и в недетерминированный, если предоставить Роботу свободу самостоятельного выбора клетки в п.3) . При этом, поскольку этот выбор конечен (соседних клеток всего 4), можно представить дальнейшие действия Робота в виде распределенных (параллельных) вычислений: в момент выбора Робот создает несколько своих клонов, и каждый клон идет по своему пути, руководствуясь теми же пунктами (0)-(5). Если хотя бы один из клонов находит выход, то задача считается решенной. |