Понятие алгоритма, его свойства, логические теории алгоритмов



страница1/57
Дата29.05.2018
Размер7.41 Mb.
#26058
ТипЗакон
  1   2   3   4   5   6   7   8   9   ...   57
  1. Понятие алгоритма, его свойства, логические теории алгоритмов.


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

Свойства алгоритма.

* Дискретность.

* Понятность

* Детерминированность

* Массовость

* Результативность
Дискретность - это свойство алгоритма, когда алгоритм разбивается на конечное число элементарных действий (шагов).

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

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

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

Результативность – свойство, при котором любой алгоритм в процессе выполнения должен приводить к определённому результату. Отрицательный результат также является результатом.
Алгоритм может быть записан различными способами: на естественном языке в виде описания; в виде графических блок-схем; на специальном алгоритмическом языке. В школе на уроках информатики для записи алгоритмов используется, так называемый, "школьный алгоритмический язык". Этот язык по существу является "мёртвым" языком,. так как на нём не работают компьютеры, и мы не будем им пользоваться. Запись алгоритмов на родном языке доступна и удобна. Примеров таких записей множество, хотя бы книга кулинарных рецептов есть не что иное, как сборник алгоритмов, написанных на родном языке.

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


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

Все имеющиеся алгоритмы можно разделить на три вида:

* линейные алгоритмы;

* алгоритмы ветвления;

* циклические алгоритмы.


В примере алгоритма “Телефонный разговор” имеются все три вида алгоритмов, хотя пример носит не математический характер. Если задача решается с помощью математического аппарата, то в зависимости от степени сложности задачи, чаще всего используется также три вида алгоритмов: линейные, ветвление и циклы. Для решения любых задач достаточно этих трех видов алгоритмов.


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

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


Появилась в 30-х годах 20 века.

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

Рис. 7.1. Схема машина Тьюринга.
Лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево. Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A = {, a1…a n} – этот алфавит называется внешним. В нем выделяется специальный символ – , называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции – по этой причине команда сдвига ленты влево обозначается R («Right»), сдвига вправо – L («Left»), отсутствие сдвига – S («Stop»).

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, z} , причем, состояние z соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1)
/***********************Другой источник******************************/
По сути своей, алгоритм есть механический процесс обработки информации. Впервые Алан Тьюринг определил понятие алгоритма исходя из понятия автоматически работающей машины; более того, он предложил формальную модель такого устройства, которое интуитивно моделирует действия человека, решающего задачу руководствуясь некоторым алгоритмом. Это устройство было названо мишиной Тьюринга. Как окаэывается, машина Тьюринга являетсявесьма простым расширением модели конечного автомата. При выполнении алгоритма в интуитивном смысле мы можем пользоваться потенциально неограниченной памятью, запоминая в процессе выполнения алгоритма по мере необходимости нужную информацию, например, на листочке бумаги. В то же время, основным ограничением конечного автомата является конечность числа его состояний, а значит, его памяти. Можно предположить, что именно поэтому конечный автомат не может быть использован как модель устройства, выполняющего произвольные алгоритмы.

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




Рассмотрим, чем отличается машина Тьюринга от простой модели конечного автомата. Конечный автомат можно представить себе как устройство с конечным числом внутренних состояний, работающее с двумя лентами: входной и выходной (рис.5.1). Конечный автомат работает по тактам. На каждом такте он читает с помощью некоторой входной головки символ из обозреваемой ячейки входной ленты, изменяет свое состояние и печатает некоторый символ выходного алфавита в обозреваемую ячейку выходной ленты, после чего две его головки чтения и записи перемещаются на одну позицию вправо. Описание функционирования конечного автомата можно считать его программой: в ней просто перечислено конечное число четверок (команд) , где s – текущее состояние, a - очередной входной сигнал, р - следующее состояние и у - очередной выходной сигнал.

Программа КА - это просто перечисление аргументов и соответствующих результатов частично-определенной функции переходов и выходов автомата .:S.X>S.Y. В своем вычислительном устройстве Тьюринг просто смоделировал доведенный до самых элементарных операций процесс выполнения произвольного алгоритма человеком. Человек имеет конечную память, и в этом смысле его можно представить системой с конечным числом состояний. Исходная информация к алгоритму обычно представляется в виде цепочки символов. Можно себе представить, что эта информация представлена в виде слова (конечной последовательности символов) конечного словаря. Выполняя алгоритм, человек-вычислитель использует дополнительную память (которая может быть потенциально бесконечной, например, листы бумаги) для записи информации, причем эта запись производится им последовательно, символ за символом. При вычислениях человек может возвращаться к ранее записанной информации, стирать некоторую информацию и т.д. Таким образом, элементарными операциями при выполнении алгоритма можно считать запись и стирание символа, а также перенесение внимания с одного участка записи на другой. Предложенная Тьюрингом формальная модель отличается от конечного автомата только в этих двух аспектах: она имеет одну бесконечную рабочую ленту, с которой читает и куда пишет символы, и одну головку чтения-записи, которая может двигаться по рабочей ленте в любую сторону (рис.5.1). Такая свобода движения головки чтения-записи по сути означает возможность создавать и впоследствии анализировать промежуточную информацию. Как оказывается, такое простое расширение возможностей радикально увеличивает вычислительную мощность машин Тьюринга по сравнению с обычными конечными автоматами.

Машина Тьюринга работает по тактам. На каждом такте она читает символ из обозреваемой ячейки рабочей ленты, изменяет свое состояние в зависимости от своего внутреннего состояния и прочитанного символа и печатает символ в обозреваемую ячейку рабочей ленты, после чего ее головка чтения-записи может переместиться на одну позицию влево, вправо или остается на месте. Описание функционирования МТ можно считать ее программой, которая представлена конечным набором пятерок (команд) < s,a,p,y,D >, где s, a, р и у имеют тот же смысл, что и в конечном автомате, а D -направление перемещения головки по рабочей ленте, которое может быть одним из трех значений: L -влево, R - вправо и Н - оставаться на месте. Иными словами, программа МТ- это просто конечный список пятерок, представляющих собой аргументы и соответствующие им результаты частично-определенной функции переходов и выходов .:S.X>S.X.Г.

Машина Тьюринга имеет один конечный рабочий алфавит X, в котором входные и выходные символы не различаются: выходной символ, напечатанный на ленте, машина может прочитать в последующих тактах. Для удобства обычно считают, что X содержит пустой символ ., находящийся во всех ячейках рабочей ленты слева и справа от конечной цепочки “значащих” символов в начале работы.

Рассмотрим, как работает машина Тьюринга. Конфигурацией машины Тьюринга называется ее текущее состояние, текущее состояние рабочей ленты и место расположения головки. При работе МТ в каждом такте происходит смена конфигураций. Пусть МТ находится в состоянии s и в обозреваемой ячейке ленты находится символ a. Если в программе МТ нет команды для пары , то МТ останавливается. Если в программе МТ несколько команд для данной пары , то это - недетерминированная машина Тьюринга, в ней выполняется одна из нескольких возможных команд с левой частью . Очевидно, что в любой момент работы на ленте МТ находится только конечная цепочка “значащих” символов. После останова машины Тьюринга эта цепочка является результатом переработки входной цепочки. Таким образом, МТ является автоматом-преобразователем символьных цепочек.

Машина Тьюринга также может быть распознавателем множеств цепочек. В такой МТ выделяются специальные заключительные состояния стоп или “!”, и если МТ, работающая как распознаватель, останавливается в одном из этих состояний при пустой входной ленте, то она распознает входную цепочку. Если в заключительном состоянии останавливается машина-преобразователь Тьюринга, то информация на рабочей ленте является результатом переработки входной информации.




  1. Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   57




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница