Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Найдите скорость относительно берега реки лодки, идущей под углом α = 90º к течению. Скорость течения реки v₁ = 1 м/с, скорость лодки относительно вод...полностью>>
'Документ'
Бездетко Павел Андреевич, зав. кафедрой офтальмологии, д. мед. н., проф.; Ильина Евгения Николаевна, ассистент кафедры офтальмологии, канд. мед. наук;...полностью>>
'Документ'
ТО и ремонт строительно-дорожных машин....полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

ТЕОРИЯ АЛГОРИТМОВ.

Вводные положения.

Теория алгоритмов - раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.

Основное понятие этой теории – алгоритм – в интуитивном (наивном) понимании существует в математике довольно давно, а точные математические понятия, которые в том или ином смысле формализуют интуитивное понятие алгоритма, предложены только в середине 30-х годов 20-го века. Необходимость такой формализации была обусловлена как вопросами обоснования математики, так и вопросами доказательства алгоритмической разрешимости и неразрешимости тех или иных задач. Очевидно, что в математике доказываемый объект должен быть точно определен.

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

Замечание:

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

Предмет и содержание читаемого курса.

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

Содержанием курса являются следующие вопросы:

  • языки операндов и алгоритмические языки;

  • рекурсивные функции как математический вариант уточнения понятия вычислимой арифметической функции;

  • машины Тьюринга как математический эквивалент для общего интуитивного представления об алгоритме;

  • нормальный алгоритм Маркова;

  • сложность алгоритма.

Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.

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

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

Примеры:

  1. «Проезд запрещен», «Не курить» - не алгоритмы;

  2. «Придерживайтесь правой стороны», «Место для курения», «Вход» - не алгоритмы;

  3. Сложение (умножение, вычитание, деление) двух чисел (т.е. N2N) столбиком – алгоритм.

Пример:

Упорядочить в порядке возрастания конечное множество М положительных чисел. Описание решения этой задачи в интуитивном смысле может быть:

Шаг 1: В М ищется наименьшее число

Шаг 2: Найденное число приписывается справа к возрастающей последовательности чисел R (в начальный момент R пусто) и вычеркивается из М;

Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1;

Шаг 4: Конец. Результатом считать последовательность R, построенную к данному моменту.

Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=95, 62, (1/3)/2, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

Этот пример показывает, что понятие алгоритма в интуитивном смысле требует уточнения понятия данных (т.е. указать каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать), памяти, дискретности, элементарности, конечности числа шагов, направленности, детерминированности, результативности, массовости.

Пояснения:

  1. Приведенное наивное (интуитивное) определение алгоритма не является точным математическим определением, а лишь объясняет смысл слова «алгоритм», в котором это слово используется в математике.

  2. Характеристиками алгоритма являются:

  • детерминированность (определенность) – однозначность результата процесса при заданных исходных данных;

  • дискретность – расчлененность процесса на отдельные элементарные акты (шаги, действия), возможность выполнения которых человеком или машиной не вызывает сомнений,

  • массовость – исходные данные для алгоритма можно выбирать из некоторого множества данных (потенциально бесконечного), т.е. алгоритм должен обеспечить решение любой задачи из класса однотипных задач.

Основные требования к алгоритмам.

  1. Очевидно, что каждый алгоритм имеет дело с данными: входными, выходными и промежуточными. В этом плане уточнение понятия алгоритм требует и уточнения понятия данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». В теории алгоритмов четкая определенность объектов обусловлена заданием их в формальном языке L=, в котором символы конечного алфавита А рассматриваются как элементарные объекты для построения более сложных объектов конечными средствами S (этот язык часто называется языком операндов в отличие от языка описания самого алгоритма – алгоритмического языка).

  2. В дальнейшем будем различать:

    • описание алгоритма (т.е. инструкции или программы);

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

    • память данных алгоритма;

    • процесс реализации алгоритма, то есть последовательность шагов (действий), которая будет порождена при применении алгоритма к конечным данным.

Пояснения:

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

  2. Предполагается также, что память данных алгоритма однородна и дискретна, то есть состоит из одинаковых ячеек, каждая из которых может содержать только один символ алфавита данных. Вопрос о том, нужна ли одна память или несколько (в частности для входных, выходных и промежуточных данных алгоритма) может решаться по-разному.

  3. Понятие задачи «в общем виде» уточняется при помощи понятия «массовая алгоритмическая проблема». Последняя задается серией отдельных единичных проблем и состоит в требовании найти единый алгоритм их решения (когда такого алгоритма не существует говорят, что рассматриваемая массовая алгоритмическая проблема неразрешима). Так, проблема численного решения уравнений данного типа и проблема автоматического перевода есть массовые алгоритмические проблемы: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае - проблемы перевода отдельных фраз.

  4. Алгоритмический процесс – есть процесс последовательного преобразование конструктивных объектов, происходящий дискретными шагами; каждый шаг состоит в смене одного конструктивного объекта другим. Так, при применении алгоритма вычисления (f: D2 D) столбиком к паре <507, 38> последовательно возникают следующие конструктивные объекты:

_507 _507 _507 _507

38 38 38 38

469

Здесь возможными исходными данными служат пары чисел, возможными результатами – числа (все в десятичной системе счисления), а возможные промежуточные результаты суть трехэтажные записи вида , где q-

запись числа в десятичной системе, z- такая же запись или пустое слово, а p- запись числа в десятичной системе с допущением точек над некоторыми цифрами (точка означает заимствование из старшего разряда).

Основная терминология теории алгоритмов.

Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм U говорят, что он:

  1. «Выявляет функцию f», коль скоро его область применимости совпадает с областью определения f, и U перерабатывает всякий х из своей области применимости в f(x);

  2. «Разрешает множество А относительно множества Х», коль скоро он применим ко всякому х из Х и перерабатывает х из ХА в слово «да», а всякий х из Х\А в слово «нет»;

  3. «Перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.

Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называется разрешимым (рекурсивным) относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым (рекурсивно-перечислимым), если либо оно пусто, либо существует перечисляющий его алгоритм.

Замечания:

  1. Область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

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

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

  4. Процесс выполнения алгоритма называется алгоритмическим процессом.

Основные теоремы теории алгоритмов.

Теорема 1: Функция f вычислима тогда и только тогда, когда перечислим ее график, то есть множество всех пар вида .

Теорема 2: Подмножество А перечислимого множества Х разрешимо относительно Х тогда и только тогда, когда А и Х\А перечислимы.

Теорема 3: Если А и В перечислимы, то АВ и АВ также перечислимы.

Теорема 4: В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5: Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.

Параметры алгоритма.

Как правило, для данного алгоритма можно выделить семь независимых характеризующих его параметров:

  1. совокупность возможных исходных данных;

  2. совокупность возможных результатов;

  3. совокупность возможных промежуточных результатов;

  4. правило начала;

  5. правило непосредственной переработки;

  6. правило окончания;

  7. правило извлечения результата;

Основная гипотеза теории алгоритмов.

Любая практическая задача, приводящая к необходимости создания эффективного вычислительного метода (алгоритма), может быть поставлена в точных математических терминах.

Алгоритмические (формальные математические) модели.

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

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

Так, понятие машины Тьюринга как F S1 следующим образом может быть использовано для уточнения общего представления об алгоритме в данном алфавите, если Тьюринговским алгоритмом в алфавите А называется всякий алгоритм U следующего вида:

    • фиксируется некоторая машина Тьюринга в алфавите А, то есть , здесь Q – множество внутренних состояний машины, а R – правило перехода из одной конфигурации машины к другой);

    • задается  - слово, принимаемое в качестве исходного данного для U (A*);

    • строится исходная конфигурация машины a0q0a0, где q0 – начальное состояние машины q0Q, a0 – пустой символ, a0А;

    • машина, отправляясь из a0q0a0, заканчивает работу в заключительной конфигурации.

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

Замечания:

  1. Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана. По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением правильности тезиса Тьюринга является математическая практика, а также эквивалентные тезисы и, в частности, тезис Черча для рекурсивных функций: «Всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивная».

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

Теорема 1: Всякая частично-рекурсивная функция вычислима на машине Тьюринга.

Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-рекурсивная.

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

  2. Тезисы позволяют выявлять случаи невозможности алгоритмов, однако, не указывают в случае их существования пути построения удобного для практики алгоритма (Напоминание: «Теория алгоритмов не учит строить конкретные алгоритмы»).

Блок-схемы алгоритмов.

Связи между шагами алгоритма можно изобразить в виде графа (блок-схемы) такого, как, например, следующий:

где вершинам соответствуют шаги (блоки), а дугам – переходы между шагами. Его вершины могут быть двух видов – операторы (из этих вершин выходит одно ребро) и предикаты (или логические условия; из этих вершин выходят два ребра). Кроме того, выделяют операторы начала и конца алгоритма.

В подобных схемах шаги могут быть элементарными или могут представлять собой самостоятельные алгоритмы (блоки).

На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации.

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

Отсутствие сходимости алгоритма означает, что в процессе вычисления не появляются условий, ведущих к концу, и процесс идет по бесконечному пути (зацикливается).

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

Очевидно, что блок-схемы являются средством описания детерминизма алгоритма.

Замечания:

  1. На практике блок-схемы часть имеют предикаты (точки разветвления) не только двоичные, но и многозначные, важно лишь, чтобы верным был ровно один из возможных ответов.

  2. Блок схема вида:

где блок А1 вычисляют функцию f1(x), а исходными данными для А2 являются результаты А1, называется композицией алгоритмов А1 и А2 (то есть эта блок-схема задает алгоритм, вычисляющий f2(f1(x)), то есть композицию f1 и f2)

Машина Тьюринга.

Машина Тьюринга Т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.

Содержательное понятие машины.

Машину Тьюринга Т=0, qz, > удобно представлять в виде автоматически функционирующего устройства, способного находиться в конечном числе внутренних состояний Q=q1…qn-2, qz и снабженного бесконечной внешней памятью – лентой. Среди состояний Q имеются два выделенных – начальное q1 и заключительное qz. Лента разделена на ячейки и потенциально бесконечна в обе стороны. В каждой ячейке ленты может быть записана любая из букв внешнего алфавита А=a0, a1…am (a0 – пустая буква, то есть считается, что в пустой ячейке записана a0). Функционирование машины обуславливает программа =qj ai  qk aL dt.

Схема такого устройства как совокупность стуктурно-связанных внутренней и внешней памяти, блока управления и управляемой головки

a0

a2

a5

ai

a9

a3

a5

a0


дает возможность имитировать алгоритмические процессы распознавания и порождения цепочек языка произвольного типа (по Хомскому).

На схеме:

а) Блок управления производит преобразование пары (цепочки из двух символов) qj aiQ*A в тройку qk aL dt Q*A*D. Это означает, что если машина находится в состоянии qj (то есть вычисляет инструкцию qj), а управляемая головка считывает символ ai из обозреваемой ячейки внешней памяти, то блок управления вырабатывает команду qk aL dt, согласно которой:

  1. машина переходит в состояние qk (допускается k=j);

  2. в обозреваемую ячейку ленты вместо символа ai записывается символ aL (допускается i =L);

  3. управляющая головка (лента) перемещается на один шаг или остается на прежнем месте (dЛ – перемещение на один шаг влево, dп – перемещение на один шаг вправо, dн – оставаться на месте; dЛ, dп, dнD).

Итак, если блок управления осуществляет функциональное отображение:

Гf: Q*A Q*A*D,

где qj aiQ*A, qk aL dt Q*A*D, ai, aLА, qj, qkQ, dt D= dЛ, dп, dн, то машину Тьюринга будем называть детерминированной и всюду определенной.

б) Данные (исходные, промежуточные и окончательные) машины есть цепочки символов (слова) в алфавите А, которые записываются на бесконечной ленте внешней памяти (каждый символ слова в отдельной ячейке) (А=Аисх АпромАрез, а0Аисх, а0Арез).

в) Элементарные шаги в рассматриваемой машине следующие:

  1. изменение состояния машины и содержимого ячейки, обозреваемой управляемой головкой;

  2. перемещение управляемой головки на один шаг влево ( вправо);

г) Детерминированность работы машины обуславливается программой ее работы , то есть совокупностью выражений (j, i) (j=0,n; i= 0,n), каждое из которых имеет один из следующих видов:

qj ai  qk aL dн

qj ai  qk aL dЛ

qj ai  qk aL dп,

где 0  k n, 0 L m.

В дальнейшем программу будем записывать в табличном виде:

A \ Q

q0

q1

qj

qz

a0

a1

ai

qk aL dt

am



Похожие документы:

  1. Логика и аргументация

    Документ
    ... нового раздела этой логикитеории алгоритмов, на которую опирается в свою очередь теория математического программирования ... чистой, (теоретической) математике преобладает процесс обобщения понятий, а в приложениях математики – их конкретизация. Хотя ...
  2. Аннотация к рабочей программе дисциплины «Математическая логика и теория алгоритмов» по направлению 230100. 62 Информатика и вычислительная техника

    Документ
    ... . Пользовательские процедуры и приложения по обработке ... Математическая логика и теория алгоритмов"; "Теория вероятностей и математическая статистика"; "Моделирование систем"; "Теория автоматов"; "Теория ... в которой студенты изучают теоретические основы и ...
  3. Конспект лекций по дисциплине: теория систем и системный анализ санкт-Петербург

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

    Эссе
    ... и формула для вычисления. Алгоритм Гаусса решения системы линейных ... разделы возможной тематики дисциплин по выбору и приложения). Материал данных разделов ... общей трудоемкости). 3.1. Элементы математической логики, теории множеств и общей алгебры. ...
  5. Урок информатика

    Урок
    ... математическая логика. вычислительная математика, которая разрабатывает методы решения задач на компьютерах с использованием алгоритмов и программ. теория ... эффективна для малых и простых разделов ... приложений, но их основным отличием является возможность ...

Другие похожие документы..