Теория алгоритмов. Теория алгоритмов реферат

Реферат Теория алгоритмов

скачать

Реферат на тему:

План:

1 Возникновение теории алгоритмов
2 Модели вычислений
3 Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы
4 Современное состояние теории алгоритмов
- 4.1 Анализ трудоёмкости алгоритмов
- 4.2 Классы сложности

Введение

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

1. Возникновение теории алгоритмов

Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

2. Модели вычислений

Машина Тьюринга
Лямбда-исчисление — рассматривается пара — λ-выражение и его аргумент, — а вычислением считается применение, или апплицирование первого члена пары ко второму. Это позволяет отделить функцию и то, к чему она применяется. В более общем случае вычислением считаются цепочки, начинающиеся с исходного λ-выражения, за которым следут конечная последовательность λ-выражений, каждое из которых получается из предыдущего применением β-редукции, то есть правила подстановки.
Комбинаторная логика — трактовка вычисления сходна с λ-исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки Y имеет нормальную форму в комбинаторной логике, а в λ-исчислении — не имеет). Комбинаторная логика была первоначально разработана для изучения природы парадоксов и для построения концептуально ясных оснований математики, причем представление о переменной исключалось вовсе, что помогало прояснить роль и место переменных в математике.
Регистровые машины (англ.)
- RAM-машина (англ.) — абстрактная вычислительная машина, моделирующая компьютер с произвольным доступом к памяти. Именно эта модель вычислений наиболее часто используется при анализе алгоритмов.

3. Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы

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

В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.

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

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.

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

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

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

4.1. Анализ трудоёмкости алгоритмов

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

Трудоёмкость алгоритмов по-разному зависит от входных данных. Для некоторых алгоритмов трудоемкость зависит только от объема данных, для других алгоритмов — от значений данных, в некоторых случаях порядок поступления данных может влиять на трудоемкость. Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.

Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов. Целью асимптотического анализа является сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объемах входных данных. Используемая в асимптотическом анализе оценка функции трудоёмкости, называемая сложностью алгоритма, позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных. В асимптотическом анализе алгоритмов используются обозначения, принятые в математическом асимптотическом анализе. Ниже перечислены основные оценки сложности.

Основной оценкой функции сложности алгоритма f(n) является оценка $\boldsymbol{\Theta}$ . Здесь n — величина объёма данных или длина входа. Мы говорим, что оценка сложности алгоритма

$f(n) = \boldsymbol{\Theta}(g(n))$

если при g > 0 при n > 0 существуют положительные с1, с2, n0, такие, что:

$c_1 g(n)\le \; f(n) \le \; c_2 g(n)$

при n > n0, иначе говоря, можно найти такие с1 и c2, что при достаточно больших n f(n) будет заключена между

$\boldsymbol{c_1\;g(n)}$ и $\boldsymbol{c_2\;g(n)}$ .

В таком случае говорят еще, что функция g(n) является асимптотически точной оценкой функции f(n), так как по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя (см. асимптотическое равенство). Например, для метода сортировки heapsort оценка трудоёмкости составляет

$f(n) = \boldsymbol{\Theta}(n \log n)$ то есть g(n) = nlogn

Из $f(n) = \boldsymbol{\Theta}(g(n))$ следует, что $g(n) = \boldsymbol{\Theta}(f(n))$ .

Важно понимать, что $\boldsymbol{\Theta}(g(n))$ представляет собой не функцию, а множество функций, описывающих рост $\boldsymbol{f(n)}$ с точностью до постоянного множителя.

$\boldsymbol{\Theta}$ дает одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка $\boldsymbol{O}$ представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Мы говорим, что $f(n)=\boldsymbol{O}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; f(n) \le \; c g(n), \forall \; n > n_0$

Иначе говоря, запись $f(n) = \boldsymbol{O}(g(n))$ означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

Оценка $\boldsymbol{\Omega}$ задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. $f(n)=\boldsymbol{\Omega}(g(n))$ если

$\exists \; c > 0, n_0 > 0 : 0 \le \; c g(n) \le \; f(n), \forall \; n > n_0$

Например, запись $f(n)=\boldsymbol{\Omega} (n \log \; n)$ обозначает класс функций, которые растут не медленнее, чем $\boldsymbol{g(n) = n \log \; n}$ , в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы. Равенство $f(n) = \boldsymbol{\Theta}(g(n))$ выполняется тогда и только тогда, когда $f(n)=\boldsymbol{O}(g(n))$ и $f(n)=\boldsymbol{\Omega}(g(n))$ .

Асимптотический анализ алгоритмов имеет не только практическое, но и теоретическое значение. Так, например, доказано, что все алгоритмы сортировки, основанные на попарном сравнении элементов, отсортируют n элементов за время, не меньшее $\boldsymbol{\Omega}(n \log n)$ .

Важную роль в развитии асимптотического анализа алгоритмов сыграли A. Ахо, Дж. Ульман, Дж. Хопкрофт.

4.2. Классы сложности

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

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

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

Литература

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
Колмогоров А. Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
Марков А. А., Нагорный Н. М. Теория алгорифмов, изд. 2. — М.: ФАЗИС, 1996.

wreferat.baza-referat.ru

Теория алгоритмов - учебная работа

Код ссылки для вставки в веб-сайты, социальные сети и блоги :Теория алгоритмов

Тёплое место под солнцем)

Перед Вами представлен документ: Теория алгоритмов.

ПОЛЬЗОВАТЕЛЬСКОЕ СОГЛАШЕНИЕ

Пользовательское соглашение об использовании документа (вид: методичка), именуемого как: Теория алгоритмов, опубликованного по адресу: http://referat7.ru/neo/source/edu-content-13105.html. Файл - методичка на тему Теория алгоритмов является результатом учебной деятельности. Интеллектуальные права на данный (ую) методичка принадлежат его автору. Данный документ представлен исключительно для ознакомительных целей, без вовлечения в коммерческий оборот. Копирование и публикация любой информации с данной страницы допустимы только при условии указания прямой индексируемой гиперссылки. Если Вы являетесь правообладателем информации, размещенной на этой странице и не согласны с её публикацией в открытом доступе - сообщите об этом администратору для решения данной проблемы. Загрузка и использование файла работы на тему "Теория алгоритмов" с веб-ресурса Referat7.ru означает согласие с данными пользовательскими соглашениям.

Кафедра: Автоматика и информационные технологии

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

Екатеринбург

2006

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

Содержание

ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА
Определение
Нормальный алгоритм Маркова
Тезис Маркова
Машина Тьюринга
Основная гипотеза теории алгоритмов (тезис Чёрча)
Универсальная машина Тьюринга
МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ
Оценка алгоритма
Практические и NP-полные алгоритмы
Алгоритмически неразрешимые проблемы
«Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP - полные задачи. Понятие сложности вычислений; эффективные алгоритмы.» ( из стандарта специальности ВМКСС, дисциплина «Математическая логика и теория алгоритмов)

ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМАОпределениеЗадача (массовая задача) - некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены. Задача определяется 1) общим списком параметров, 2) формулировкой тех свойств, которым должен удовлетворять ответ (решение задачи).Индивидуальная задача получается из массовой, если всем параметрам массовой задачи присвоить конкретные (допустимые) значения.Под алгоритмом принято понимать конечную последовательность операций, называемых элементарными, исполнение которой приводит к решению любой задачи из заданного множества задач. В это определение входят такие свойства алгоритма, как дискретность, конечность (конечное число выполняемых операций), массовость (решается не единственная задача, а их класс), результативность (в результате получаем решение задачи). Кроме того, должно выполнятся ещё одно необходимое свойство алгоритма - детерминизм, которое определяется как однозначное понимание каждой операции, или, что то же самое, независимость результата выполнения каждой элементарной операции от того, кто её выполняет.Под это определение подходит широкий круг алгоритмов. Это способен

алгоритм вычисления математической функции, алгоритм технологического процесса, алгоритм проектирования ЭВМ или цеха завода и т.д. Элементарные операции могут

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

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

описание графа с промежуточным взвешиванием рёбер и/или вершин. Результатом проектной операции будет более полное, уточнённое описание объекта. Результатом работы всего алгоритма в графовой задаче способен

выделенный путь или цепь, частичный подграф или веса вершин или ребер. Результатом работы алгоритма проектирования является описание объекта проектирования, достаточное для его изготовления в заданной технологической базе.Рассмотрим несколько способов формального описания алгоритмов.Нормальный алгоритм МарковаАлгоритмическая система, созданная А.А.Марковым, основана на соответствии между словами в абстрактном алфавите A.Алгоритм задают в виде системы подстановок, реализующих отображение слов pi в слова qi.pi qi=1,…,k.Порядок подстановок зафиксирован. Объектом i-й элементарной операции алгоритма является слово в алфавите A, операция состоит в нахождении в этом слове первого слева вхождения слова pi и замене его на qi. Результатом операции будет изменённое слова, если вхождение найдено, или входное слово, если не найдено.Факт замены фиксируется и используется в организации следования операций.Исходное задание представляется некоторым словом в алфавите A. Это слово является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции.Алгоритм удобно представить в виде ориентированного графа, вершинами которого являются элементарные операторы и распознаватели. Распознаватель проверяет условие - имеет ли место вхождение рi во входное слово p. Если ДА, то за ним следует оператор, который заменяет первое слева вхождение слова рi на слово qi. Если НЕТ, то управление передается на вход следующего распознавателя.Дуги, исходящие из операторных вершин, подсоединяются либо к первой вершине - распознавателю, либо к выходной вершине. В первом случае подстановка называется обычной, во втором - заключительной.Кроме того, имеются входная и выходная вершины. Входная вершина связана дугой с первым распознавателем. На вход графа подается некоторое входное слово p.Пример. Граф для трех подстановок (к = 3) (рис.1) имеет три распознавателя (РВ1,РВ2,РВ3) и три операторные вершины (ОП1,ОП2,ОП3).Если подстановки заданы как ba ab, bc ba, bb ac, а входное слово р = bcbaab, то работа алгоритма будет иметь следующий вид.Пpимеp. Задан алфавит А={+, 1} и система подстановок:`1+1' `11' , `1'`1`.Обычная Заключительнаяподстановка подстановкаПусть дано входное слово р = '11+11+1'. Оно перерабатывается алгоритмом в строку:`11+11+1' `1111+1' `11111' `11111` !Алгоритм реализует сложение единиц.Тезис МарковаДля любого алгоритма в произвольном конечном алфавите А можно построить эквивалентный ему нормальный алгоритм.Все известные до сих пор алгоритмы нормализуемы.Машина ТьюрингаОдно из уточнений понятий алгоритма было дано Э. Постом и А. Тьюрингом независимо друг от друга в 1936-1937гг. Основная мысль их заключалась в том, что алгоритмические процессы - это процессы, которые способен свершить подходящим образом устроенная ”машина”. Ими были описаны гипотетические (условные) устройства, которые получили название «Машина Поста» и «Машина Тьюринга»(МТ). Так как в них много общего, то рассмотрим только машину Тьюринга.Машина Тьюринга состоит из следующих частей:1. Информационной ленты, представляющей бесконечную память машины. Это бесконечная лента, разделенная на ячейки. В каждой ячейке можно поместить лишь один символ из возможного их множества S={S1,S2,….,Sm},которое составляет внешний алфавит МТ. В этом алфавите один из символов (пусть это будет S1) соответствует пустому символу.2. Считывающей головки - чувствительного специального элемента, способного обозревать содержимое ячеек. Лента способен перемещаться вдоль головки так, что в каждый момент времени головка обозревает одну ячейку.3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Обозначим множество состояний как {q1,q2,…,qn}. Среди состояний одно соответствует заключительному, при котором МТ останавливается. УУ связано со считывающей головкой.Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, гдеП - переместиться на соседнюю справа ячейку;Л - переместиться соседнюю слева ячейку;Н - продолжать обозревать ту же ячейку.Совокупность символов {q1,q2,…,qn} и {П,Л,Н} образуют внутренний алфавит МТ.Работа машины происходит в дискретном времени. В начальный момент времени в ограниченный участок ленты записано слово в алфавите S, представляющее исходное условие задачи. В остальных ячейках предполагается записанным пустой символ. Управляющее устройство находится в начальном состоянии q1. На каждом шаге работы МТ обозревает на ленте символ Skи в зависимости от него и от состояния qi, переходит в состояние qj, заменяет Sk на символ Sl и передвигает ленту (либо нет) на одну ячейку. Каждая элементарная операция имеет вид qiSk qjSl П(Л,Н). Множество элементарных операций упорядочено и образует абстрактную программу, которая представляет алгоритм.Считывающая головка и управляющее устройство образуют логический блок, который представляет собой (2,3)-полюсник.Структура МТ имеет следующий вид:Q - ячейка хранит символ состояния, а Р - ячейка - символ сдвига. В них происходит задержка данных символов до начала следующего такта.В качестве начальной информации на ленту можно записать любую конечную последовательность символов (входное слово) U внешнего алфавита. В начале работы алгоритма устройство управления находится в начальном состоянии, головка обозревает первый слева непустой символ входного слова U. Если после конечного числа тактов МТ останавливается, переходя в заключительное состояние, а на ленте оказывается информация B, то говорят, что машина применима к последовательности U и перерабатывает ее в последовательность B.Если остановка и сигнал об остановке никогда не поступают, то говорят, что МТ не применима к последовательности U.Рассмотрим функционирование МТ на примере сложения двух чисел, которые будем изображать в виде набора единиц.Внешний алфавит будет состоять из символов: {1, +, }, где - пустой символ.Внутренний алфавит будет состоять из четырех символов {q1, q2, q3, !}, где символ q1 означает начальное состояние, а ! - заключительное состояние.Пусть на ленте записана начальная информация:МТ должна ее переработать в результирующую информацию:Абстрактная программа, реализующий операцию сложения, будет иметь вид:

1q1>q3П1q3>1q3П +q3>+q3П	q3>1q2H +q2 >+q2Л1q2>1q2Л q2 >q1П +q1 >!Н

Начальное состояние УУ=q1, состояние ленты имеет вид:После первого шага состояние YY=q3, состояние ленты как на рис.После пятого шага YY перейдёт в состояние q2. Состояние ленты показано на рис.После десятого шага YY в состоянии q1 (рис. )Последовательность команд, реализующих операцию сложения, удобно задать таблицей, которую называют функциональной схемой алгоритма.

	q1	q2	q3
1	q3П	1q2Л	1q3П
	q1П	q1П	1q2H
+	!Н	+q2Л	+q3П

Основная гипотеза теории алгоритмов (тезис Чёрча)Всякий алгоритм способен

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

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

таких простых функций как сложение и умножение требует много шагов. Машина Тьюринга была придумана не для того, чтобы производить на ней реальные вычисления, а чтобы показать, что сколь угодно сложный алгоритм можно построить из очень простых операций, причем сами операции и переход от одной операции к другой выполняются автоматически.Универсальная машина ТьюрингаУниверсальная машина позволяет решить любую задачу, если наряду с исходными данными в неё записать алгоритм. Как и любая машина Тьюринга, универсальная машина должна иметь конечные внешний и внутренний алфавиты, в то же время она должна иметь возможность принимать в качестве внешнего алфавита любые алфавиты. Это достигается за счёт кодирования внешнего алфавита в алфавите универсальной машины Тьюринга.Требования к кодированию:1. различным буквам должны сопоставляться различные кодовые группы, и одна и та же буква везде заменяется одной и той же кодовой группой;2. Строка текста должна однозначным образом разбиваться на кодовые группы.Сложность универсальной машины Тьюринга определяется произведением числа символов её внешнего алфавита на число состояний усторйства управления. Теорема Триттера определяет, что минимальная универсальная машина Тьюринга имеет 4 символа во внешнем алфавите и её УУ имеет 6 состояний.МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВОценка алгоритмаОценка алгоритма бывает нужной в том случае, когда при решении некоторой задачи есть несколько разных алгоритмов, и стоит задача выбора одного из них для реализации. Даже если задача решается единственным алгоритмом, бывает нужно оценить сложность его реализации и его работы (объём памяти, время решения).Под пространственной эффективностью понимают объём памяти, требуемой для выполнения программы. Временная эффективность программы определяется временем, необходимым для ее выполнения. При этом необходимо учитывать следующие моменты.В первую очередь,время работы программы способен ограничиваться ее назначением. Если эта программа реального времени, например, бронирования авиабилетов, то время обработки задания не должно превышать нескольких минут. Если эта программа автоматического управления каким-либо устройством (например, управлением самолёта), то она должна «успевать» отрабатывать поступающую информацию и своевременно выдавать управляющие воздействия. Далее, -бывает важно знать, как изменяется время работы программы при увеличении размерности задачи. Это позволит оценить объем исходных данных, которые могут

обработаны на компьютере за приемлемое время.Реальное время работы программы на компьютере зависит не только от выбранного алгоритма. В значительной степени оно определяется типом ЭВМ, структурой представления данных, программной реализацией.Самым простым способом оценить алгоритм - сопоставить ему число элементарных операций в описании. При реализации это способен

число команд в программе или объём памяти, которую занимает программа. В этом случае оценка алгоритма A есть некоторое число k: (A) = k.Более интересной способен

оценка пары: алгоритма A и конкретной задачи , которая им решается. Например, оценкой способен

объем памяти под программу, исходные и промежуточные данные, необходимые для решения данной задачи , или время для решения данной задачи с помощью алгоритма A. В любом случае это будет число (A()) = k().Свойство массовости алгоритма предполагает, что алгоритм будет использоваться для решения класса A подобных задач, с разными исходными данными. Поэтому более сложной оценкой будет оценка как функция свойства задачи. Cопоставим каждой задаче из класса задач, решаемым алгоритмом, некоторый вектор числовых параметров задачи N = (n1, n2, …, nt). В этом случае оценка (A(A)) = k(N), и это уже будет функция от параметров задачи. Пример. Необходимо ценить алгоритм Прима - алгоритм выделения минимального остова. В первом случае мы рассматриваем число операторов в описании программы, реализующий алгоритм - число сравнений, условных переходов и т.д. Во втором случае анализируется работа алгоритма (программы) выделения остова некоторого заданного графа и определяется необходимый объём памяти. В последнем случае графу припишем параметры - число вершин в графе и число его рёбер, и сопоставим решению задачи функцию от этих параметров.Во многих задачах возможно свести вектор задачи к одному параметру. Так, для графа возможно характеризовать его числом вершин, учитывая, что число ребер в нём коррелированно с числом вершин. Для задач, связанных с булевыми функциями, параметром способен

число аргументов функции. Будем рассматривать только такие задачи. В этом случае оценкой алгоритма будет функция от одного параметра. Временная сложность алгоритма отражает требующиеся для его работы затраты времени Эта функция вставит каждой входной длине n в соответствие максимальное ( по всем индивидуальным задачам длины n) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины. Пример. Пусть функция оценки имеет вид как на рис.1. Необходимо решать задачи с параметром n, лежащим в пределах от 5 до 15. В этом случае необходимо выбрать для реализации алгоритм A1. Если параметр меняется от 20 до 30, лучше использовать алгоритм A2. Если параметр меняется в пределах от 10 до 35, то возможно или выбрать любой из данных алгоритмов, или построить новый алгоритм, который, например, проверяет каждый раз значение параметра и выбирает соответствующий алгоритм.Предположим, что можно рассмотреть все возможные алгоритмы Aiрешения задачи и для каждого параметра n оценить задачу двумя оценками 1() = min ((Ai ())) и 2() = max ((Ai ())), где min и max берётся по всем алгоритмам . В этом случае получим две границы решения данной задачи - нижнюю и верхнюю (рис.2). Этот рисунок определяет тот разброс сложности решений задачи и помогает ответить на вопрос: нужно ли тратить силы на поиск хорошего алгоритма или достаточно взять первый попавшийся. Очень часто возможно оценить исходя из анализа самой задачи вид функции оценки с точностью до некоторого сомножителя - константы. В этом случае эта оценка будет не только оценка алгоритма, но и оценка задачи. Функция f (n)есть O(g(n)), если существует константа с, такая, что f (n)0. По виду этой функции алгоритмы разделяются на следующие группы:с линейной оценкой сложности, если функция =C·n;с квадратичной сложностью, если = C · n2;с полиномиальной сложностью, если = C0 + C1·n +…+ Ck · nk;с факториальной сложностью, если =C·n!;с экспоненциальной сложностью, если = C · a n;с гиперэкспоненциальной сложностью, если = C · a t, где t = a n.Здесь C, a и k = некоторые константы, при этом число C способен

очень большим.Практические и NP-полные алгоритмыПо виду функций алгоритмы (и соответствующие задачи) делятся на два класса. К первому относятся алгоритмы групп 1-3, когда для полиномиальных алгоритмов k? 7. Эти алгоритмы называются практическими. Все

алгоритмы составляют второй класс и называются NP - полными.В табл. 1 приведена зависимость времени работы алгоритмов различной сложности для задач различной размерности, при условии, что время выполнения одной операции во всех алгоритмах одинаковы. Из таблицы видно, что для полинома, степени 5 задачу размерности 6о решить можно за приемлемое время, в то же время для экспоненциальных алгоритмов уже для размерности, больше 30 задача не решается.

Таблица 1.
	Сложность задачи
Сложность алгоритма	10	20	30	40	50	60
N	0.00001с	0,00002с	0,00003с	0,0004с	0,0005с	0,00006с
N^2	0,0001с	0,0004с	0,0009с	0,0016с	0,025с	0,0036с
N^3	0,001с	0,008с	0,027с	0,064с	0,125с	0,216с
N^5	0,1 c	3,2 c	24,3 c	1,7 мин	5,2 мин	13,0мин
2^n	0,001 c	1 c	17,9 мин	12,7 дней	35,7 лет	366 столетий
3^n	0,059c	58 мин	6,5 лет	3855 столетий	2*10^8стол	1,3*10^13 стол

Рост скорости вычислений не уменьшит значение эффективных алгоритмов, что иллюстрирует табл. 2..

Таблица 2
Сложность алгоритма	Максимальный размер задачи, разрешимый за единицу времени
	На современных ЭВМ	Если производ*10	Если производ*1000
N	k	10k	1000k
Nlog n	k	Почти 10k при больших к	Почти 10k при больших к
N^2	k	3,16k	31,6k
N^3	k	2,15k	10k
2^n	k	K+3,3	K+9,97

Если доказано, что задача является NP - полной, то это означает, что её решение для параметров, имеющих практическое значение, связано с огромными затратами времени или памяти, которые не позволят получить решение. В этом случае необходимо переформулировать задачу. Например, задача поиска минимальной формулы для булевой функции является задачей NP - полной, по этой причине при проектировании схем, где эта задача встречается, решают задачу, которую формулируют как поиск функций, близкой к минимальной, для чего пользуются эвристическими алгоритмами, основанными на предположениях здравого смысла. Так, если решается задача размещения объектов в некотором блоке, то разумно начинать размещение с самого большого объекта. В этих алгоритмах не всегда гарантируется получение минимального решения, но если для большинства задач оценка отличается не больше, чем на 10-15% от минимального, то это часто устраивает пользователей. Пpимеp. Оценим сложность алгоритма Прима поиска минимального остова в графе. Пусть граф описан матрицей смежности. Алгоритм. Выберем любую вершину и включим её в остов. Рассмотрим связанные с ней ребра. Найдём вершину, связанную с включённой в остов ребром минимального веса и включим её в остов. Для вершин, включённых в остов, рассмотрим связанные с ними рёбра к вершинам, не включённым в остов. Выберем вершину, связанную ребром минимального веса и включим её в остов. Эту процедуру продолжим до тех пор, пока все вершины не будут включены в остов.Для матричного представления алгоритм примет, следующий вид. Выберем любую вершину и в соответствующей ей строке матрицы найдём ячейку с минимальным весом. Эта процедура потребует n сравнений, где n- порядок матрицы (число вершин в графе). Имя столбца этой ячейки определяет вершину, которую нужно включить в остов. Объединим эти вершины в одну, соответствующую вершинам, включённым в остов. Для этого рассмотрим строки и столбцы этих вершин. Если в i-й ячейке одной из строк не нулевое число, оно запишется в результирующую строку, если ненулевое значение в обеих строках, в результирующую запишем минимальное. Таким образом, для «обработки» одной вершины потребуется число операций, кратных 2 n. Число вершин в рассматриваемом графе сократится на единицу. Повторим то же самое для результирующей строки, пока число вершин не станет равной единицы. Значит, общее число операций оценивается числом, пропорциональным n2, т.е. оценка имеет квадратичную сложность = C · n2.Алгоритмически неразрешимые проблемыЗадачи, для которых доказано, что решающего их алгоритма не существует, называются алгоритмически неразрешимыми.Существует большое количество задач, являющихся алгоритмически неразрешимыми. То есть речь идет об отсутствии единого алгоритма, решающего данную задачу. При этом вовсе не исключается возможность решения задачи в частных случаях, но различными способами для каждого случая.Рассмотрим несколько примеров алгоритмически неразрешимых задач.1 Задача эквивалентности алгоритмовПо двум произвольно заданным алгоритмам определить будут ли они выдавать одинаковые выходные результаты на любых исходных данных.2 Задача останова машины ТьюрингаНе существует алгоритма, позволяющего по описанию произвольного алгоритма и его исходных данных определить, останавливается ли алгоритм на этих данных или работает бесконечно.3 Задача эквивалентности двух слов в ассоциативном исчисленииАссоциативным исчислением называют совокупность всех слов в некотором алфавите вместе с какой-либо конечной системой допустимых подстановок.Подстановка P Q называется ориентированной. Она заключается в замене фрагмента P в слове R фрагментом Q.Подстановка P -- Q называется неориентированной. Она заключается как в замене фрагмента P в слове R фрагментом Q, так и в замене в слове R фрагмента Q фрагментом P.Пример. R = `aabcb' P = `ab' Q = `bcb'При P Q получим: R' = `abcbcb'.При P -- Q получим как R' = `abcbcb', так и R'' = `aaab'.Два слова R1 и R2 называются эквивалентными для заданной системы ориентированных подстановок, если от слова R1 можно, применяя конечное число раз подстановки, перейти к слову R2.Если же подстановки неориентированы, то возможность перехода требуется как от R1 к R2, так и от R2 к R1.Задача эквивалентности слов в ассоциативном исчислении состоит в следующем: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет.Задача слов не является надуманной, так как к ней способен

сведена любая известная задача.Например, рассмотрим задачу поиска пути в лабиринте. Изобразим лабиринт в виде графа, в котором вершинам соответствуют площадки, а ребрам -- соединяющие их коридоры. Каждой площадке или вершине графа сопоставим некоторое слово. Каждому коридору или ребру xixj сопоставим неориентированную подстановку, переводящую слово, соответствующее xi, в слово, соответствующее xj.Например, если вершине x1 соответствует слово `xypt', а смежной вершине x2 -- слово `xyqt', то неориентированная подстановка будет иметь вид:`p' -- `q'.Задача слов решена для некоторых частных случаев. Например, пусть даны алфавит {x, y, z, p, q} и система неориентированных подстановок:xz -- zx, xp -- px, yz -- zy, yp -- py, xyxz -- xyxzq, qzx -- xq, qpy -- yq.Спрашивается, эквивалентны ли в данном ассоциативном исчислении слова: xyxxzp и xzypxp?Ответ: нет, не эквивалентны, так как в первом слове нечетное число букв x, а во втором -- четное; система же подстановок сохраняет четность или нечетность букв x в словах.В общем же случае задача слов алгоритмически неразрешима.4 Задача распознавания выводимостиС задачей эквивалентности двух слов в ассоциативном исчислении тесно связана задача распознавания выводимости, которая является одной из важнейших задач математической логики.Задача распознавания выводимости состоит в следующем:для любых двух слов (формул) S и T в логическом исчислении определить выводима ли формула T из формулы S.Эта задача также алгоритмически неразрешима.Теория алгоритмов Методическое пособие по дисциплине «Математическая логика и теория алгоритмов» / В.П. Битюцкий, Н.В. Папуловская. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006, с.

Далее в список учебных работ по дисциплинеПрограммирование, компьютеры и кибернетика

Referat7.ru бесплатные учебные материалы (с) 2010-2018

referat7.ru

Реферат - Элементы теории алгоритмов

Реферат - Элементы теории алгоритмовскачать (118.5 kb.)Доступные файлы (1):

n1.doc

Агентство по управлению государственными учреждениями Пермского края

ГОУ СПО «Осинский профессионально-педагогический колледж»

Реферат

Элементы теории алгоритмов

Черныш Семен Олегович

Специальность 050709(0312)

Преподавание в начальных классах

Курс 2, группа 25Руководитель:

Бурдыга Валентина Павловна

Оса, 2010

Содержание

Содержание 2

Введение 3

1.Понятие алгоритма 4

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

2.1.Дискретность 6

2.2.Детерминированность 7

2.3.Конечность 7

2.4.Массовость 7

2.5.Результативность 8

3.Виды алгоритмов 9

3.1.Линейный алгоритм 9

3.2.Циклический алгоритм 9

3.3.Разветвляющийся алгоритм 10

3.4.Вспомогательный алгоритм 10

4. Способы описания алгоритмов 12

4.1.Словесный способ 12

4.2.Блок-схемы 12

Заключение 14

Литература 15

Введение

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

Целью реферата является раскрытие базовых знаний об элементах теории алгоритмов.

Для решения поставленной цели необходимо выполнить следующие задачи:

Изучить и проанализировать литературу;
Раскрыть базовые понятия элементов теории алгоритмов;
Рассмотреть свойства и виды алгоритмов;
Сформировать представление о способах записи алгоритмов.

Я выбрал данную тему из-за ее актуальности.

Понятие алгоритма

Знакомство с понятием алгоритма я предлагаю начать с рассмотрения примера.

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

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

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

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

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

Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, видов и сферы применения различных алгоритмов. Научное определение понятия алгоритма дал А. Черч в 1930 году. Позже и другие математики вносили свои уточнения в это определение. В школьном курсе информатики обычно пользуются следующими определениями:

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

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

Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ. Однако любой алгоритм, в отличие от рецепта или способа обязательно обладает свойствами.

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

Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.

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

Достать ключ из кармана.
Вставить ключ в замочную скважину.
Повернуть ключ два раза против часовой стрелки.
Вынуть ключ.

Представьте, что вас пригласили в гости и подробно объяснили, как добраться:

Выйти из дома.
Повернуть направо.
Пройти два квартала до остановки.
Сесть в автобус №5, идущий к центру города.
Проехать три остановки.
Выйти из автобуса.
Найти по указанному адресу дом и квартиру.

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

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

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

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

Детерминированность (от лат. determinate – определенность, точность). Это свойство указывает, что любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Например, если к остановке подходят автобусы разных маршрутов, то в алгоритме должен быть указан конкретный номер маршрута – 5. Кроме того, необходимо указать точное количество остановок, которое надо проехать, - скажем, три.

Конечность

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

Массовость

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

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

Результативность

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

Из числа А вычесть число В.
Если получилось отрицательное значение, то сообщить, что число B больше.
Если получилось положительное значение, то сообщить, что число А больше.

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

Из числа А вычесть число В.
Если получилось отрицательное значение, то сообщить, что число B больше.
Если получилось положительное значение, то сообщить, что число А больше.
Если получилось ноль, то сообщить, что числа равны.

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

Виды алгоритмов

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

Хочется заметить, что в 1969 году Эдсгер В. Дийкстра в статье «Структуры данных и алгоритмы» доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: линейных, ветвящихся, циклических. Рассмотрим эти конструкции.

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

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

Циклический алгоритм

Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий. Каждый год наступает весна, лето, осень и зима. Жизнь растений в течение года проходит одни и те же циклы. Подсчитывая число полных поворотов минутной или часовой стрелки, человек измеряет время.

Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

Разветвляющийся алгоритм

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

Вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Направо пойдешь – коня потеряешь, налево пойдешь – сам пропадешь…»

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

Если пошел дождь, то надо открыть зонт.
Если болит горло, то прогулку следует отменить.
Если прозвенел будильник, то надо вставать и идти в школу и т.д.

Существует специальный раздел математики – формальная логика, которая объясняет, как выстраивать цепочку рассуждений, чтобы прийти к правильному выводу.

Логика учит правильно формулировать условие, под которым понимается предложение, начинающееся со слова «если» и заканчивающееся перед словом «то». Условие может принимать значение «истина», когда оно выполнено, или «ложь», когда оно не выполнено. От значения условия зависит наше дальнейшее действие.

Вспомогательный алгоритм

Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя.

Вспомогательному алгоритму должно быть присвоено имя.

Допустим, вы хотите научиться жонглировать двумя или даже тремя мячами. Если внимательно приглядеться к действиям профессионального артиста и попытаться понять, как это ему удается делать, то оказывается – секрет в том. Что надо научится искусно выполнять несколько определенных движений, которым присвоим соответствующие названия:

Бросок левой – подбросить мяч левой рукой.
Бросок правой – подбросить мяч правой рукой.
Захват левой – поймать мяч правой рукой.
Захват правой – поймать мяч правой рукой.

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

Когда летящий шарик начинает поворачивать к правой руке, выполнитьБросок правой и Захват правой.
Когда летящий шарик начинает поворачивать к правой руке, выполнитьБросок левой и Захват левой.

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

4. Способы описания алгоритмов

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

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

Словесный способ

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

Блок-схемы

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

Таблица 1 Стандартные графические объекты блок-схемы

Вид стандартного графического объекта	Назначение
	Начало алгоритма
	Конец алгоритма
Гуляю	Выполняемое действие записывается внутри прямоугольника
	Условие выполнения действий записывается внутри ромба
	Последовательность выполнения действий: влево и вверх – линия со стрелкой, вниз и вправо – линия без стрелки

На приведенных ниже рисунках 1–5 представлены блок схемы типовых алгоритмических конструкций.

Заключение

Понятие алгоритма является одним из фундаментальных понятий не только математики. Работы по формализации этого понятия привели к появлению нового научного направления – теории алгоритмов. В данном реферате вы познакомились с некоторыми элементами этой науки.

Литература

Аляев Ю. А. Алгоритмизация и языки программиования Pascal, C++, Visual Basic / Ю. А. Аляев. – М., 2002 г.
Макарова Н. В. Информатика 7-9 класс Базовый курс. Теория / Н. В. Макарова. – М., 2003 г.
Семакин И. Г. Информатика Базовый курс 7-9 класс / И. Г. Семакин. – М., 1999 г.
Стариченко Б. Е. Теоретические основы информатики / Б. Е. Стариченко. – М., 2004 г.
Фалина И. Н. Элементы теории алгоритмов / И. Н. Фалина // Информатика. – 2004 г. – №3 (435). – 2-11.

nashaucheba.ru

Теория алгоритмов

Кафедра: Автоматика и информационные технологии ТЕОРИЯ АЛГОРИТМОВ Екатеринбург 2006

Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.

Содержание ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА Определение Нормальный алгоритм Маркова Тезис Маркова Машина Тьюринга Основная гипотеза теории алгоритмов (тезис Чёрча) Универсальная машина Тьюринга МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ Оценка алгоритма Практические и NP-полные алгоритмы Алгоритмически неразрешимые проблемы

«Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча; Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы.» ( из стандарта специальности ВМКСС, дисциплина «Математическая логика и теория алгоритмов)

Определение

Задача (массовая задача) - некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены. Задача определяется 1) общим списком параметров, 2) формулировкой тех свойств, которым должен удовлетворять ответ (решение задачи). Индивидуальная задача получается из массовой, если всем параметрам массовой задачи присвоить конкретные (допустимые) значения. Под алгоритмом принято понимать конечную последовательность операций, называемых элементарными, исполнение которой приводит к решению любой задачи из заданного множества задач. В это определение входят такие свойства алгоритма, как дискретность, конечность (конечное число выполняемых операций), массовость (решается не единственная задача, а их класс), результативность (в результате получаем решение задачи). Кроме того, должно выполнятся ещё одно необходимое свойство алгоритма – детерминизм, которое определяется как однозначное понимание каждой операции, или, что то же самое, независимость результата выполнения каждой элементарной операции от того, кто её выполняет. Под это определение подходит широкий круг алгоритмов. Это может быть алгоритм вычисления математической функции, алгоритм технологического процесса, алгоритм проектирования ЭВМ или цеха завода и т.д. Элементарные операции могут быть достаточно сложными: при вычислении функции это может быть, например, нахождение корней уравнения, в проектных или технологических алгоритмах – принятие сложных проектных или технологических решений. Данное выше определение алгоритма не является формализованным и строгим по двум причинам. Во-первых, в нём не формализовано понятие элементарной операции, и, во-вторых, не формализовано представление последовательности операций. Важность разработки общего для всех алгоритмов формального описания заключается в том, что оно даёт возможность иметь общие инструментарии для сравнения, оценки, преобразования и других действий над алгоритмами. Формализация операций алгоритмов связано со следующим. Любой алгоритм определён для некоторого объекта действия, каждый объект представляется в виде описания, причём описанием может быть не только тексты на языке, но и рисунки, чертежи и т.п. Значит, можно предположить, что объект описан в виде слова в заданном алфавите. Объект может находиться в различных состояниях, чему соответствуют различные слова. Так, объектом для математических алгоритмов являются математическое описание задачи в форме матриц коэффициентов, графа смежности и т.п.т., для проектных алгоритмов – проектируемый объект в виде технического задания на проектирование или перечень требований и условий к результату. Операция определяется над описанием объекта и её результатом является новое (изменённое) описание (новое слово). Например, если решается графовая задача, то результатом операции может быть описание графа с промежуточным взвешиванием рёбер и/или вершин. Результатом проектной операции будет более полное, уточнённое описание объекта. Результатом работы всего алгоритма в графовой задаче может быть выделенный путь или цепь, частичный подграф или веса вершин или ребер. Результатом работы алгоритма проектирования является описание объекта проектирования, достаточное для его изготовления в заданной технологической базе. Рассмотрим несколько способов формального описания алгоритмов.

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

Алгоритмическая система, созданная А.А.Марковым, основана на соответствии между словами в абстрактном алфавите A. Алгоритм задают в виде системы подстановок, реализующих отображение слов pi в слова qi. pi ® qi=1,…,k. Порядок подстановок зафиксирован. Объектом i-й элементарной операции алгоритма является слово в алфавите A, операция состоит в нахождении в этом слове первого слева вхождения слова pi и замене его на qi. Результатом операции будет изменённое слова, если вхождение найдено, или входное слово, если не найдено.Факт замены фиксируется и используется в организации следования операций. Исходное задание представляется некоторым словом в алфавите A. Это слово является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции. Алгоритм удобно представить в виде ориентированного графа, вершинами которого являются элементарные операторы и распознаватели. Распознаватель проверяет условие – имеет ли место вхождение рi во входное слово p. Если ДА, то за ним следует оператор, который заменяет первое слева вхождение слова рi на слово qi. Если НЕТ, то управление передается на вход следующего распознавателя. Дуги, исходящие из операторных вершин, подсоединяются либо к первой вершине – распознавателю, либо к выходной вершине. В первом случае подстановка называется обычной, во втором – заключительной. Кроме того, имеются входная и выходная вершины. Входная вершина связана дугой с первым распознавателем. На вход графа подается некоторое входное слово p. Пример. Граф для трех подстановок (к = 3) (рис.1) имеет три распознавателя (РВ1,РВ2,РВ3) и три операторные вершины (ОП1,ОП2,ОП3). Если подстановки заданы как ba ® ab, bc ® ba, bb ® ac, а входное слово р = bcbaab, то работа алгоритма будет иметь следующий вид. SHAPE \* MERGEFORMAT Подпись: р = bcbaab ® bcabab ® bcaabb ®baaabb ®abaabb ® aababb ® aaabbb ® aaaacb.

Подпись: р = bcbaab ® bcabab ® bcaabb ®baaabb ®abaabb ® aababb ® aaabbb ® aaaacb.

Пpимеp. Задан алфавит А={+, 1} и система подстановок: ‘1+1’ ® ‘11’ , ‘1’®`1`. Обычная Заключительная подстановка подстановка

Пусть дано входное слово р = ’11+11+1’. Оно перерабатывается алгоритмом в строку: ‘11+11+1’ ® ‘1111+1’ ® ‘11111’ ® `11111` ! Алгоритм реализует сложение единиц.

Тезис Маркова

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

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

Одно из уточнений понятий алгоритма было дано Э. Постом и А. Тьюрингом независимо друг от друга в 1936-1937гг. Основная мысль их заключалась в том, что алгоритмические процессы – это процессы, которые может свершить подходящим образом устроенная ”машина”. Ими были описаны гипотетические (условные) устройства, которые получили название «Машина Поста» и «Машина Тьюринга»(МТ). Так как в них много общего, то рассмотрим только машину Тьюринга. Машина Тьюринга состоит из следующих частей: 1. Информационной ленты, представляющей бесконечную память машины. Это бесконечная лента, разделенная на ячейки. В каждой ячейке можно поместить лишь один символ из возможного их множества S={S1,S2,….,Sm},которое составляет внешний алфавит МТ. В этом алфавите один из символов (пусть это будет S1) соответствует пустому символу. 2. Считывающей головки – чувствительного специального элемента, способного обозревать содержимое ячеек. Лента может перемещаться вдоль головки так, что в каждый момент времени головка обозревает одну ячейку. 3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Обозначим множество состояний как {q1,q2,…,qn}. Среди состояний одно соответствует заключительному, при котором МТ останавливается. УУ связано со считывающей головкой. Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, где П – переместиться на соседнюю справа ячейку; Л – переместиться соседнюю слева ячейку; Н – продолжать обозревать ту же ячейку. Совокупность символов {q1,q2,…,qn} и {П,Л,Н} образуют внутренний алфавит МТ. Работа машины происходит в дискретном времени. В начальный момент времени в ограниченный участок ленты записано слово в алфавите S, представляющее исходное условие задачи. В остальных ячейках предполагается записанным пустой символ. Управляющее устройство находится в начальном состоянии q1. На каждом шаге работы МТ обозревает на ленте символ Sk и в зависимости от него и от состояния qi, переходит в состояние qj, заменяет Sk на символ Sl и передвигает ленту (либо нет) на одну ячейку. Каждая элементарная операция имеет вид qiSk ® qjSl П(Л,Н). Множество элементарных операций упорядочено и образует абстрактную программу, которая представляет алгоритм. Считывающая головка и управляющее устройство образуют логический блок, который представляет собой (2,3)-полюсник.

SHAPE \* MERGEFORMAT Структура МТ имеет следующий вид:

Q - ячейка хранит символ состояния, а Р - ячейка – символ сдвига. В них происходит задержка данных символов до начала следующего такта. В качестве начальной информации на ленту можно записать любую конечную последовательность символов (входное слово) U внешнего алфавита. В начале работы алгоритма устройство управления находится в начальном состоянии, головка обозревает первый слева непустой символ входного слова U. Если после конечного числа тактов МТ останавливается, переходя в заключительное состояние, а на ленте оказывается информация B, то говорят, что машина применима к последовательности U и перерабатывает ее в последовательность B. Если остановка и сигнал об остановке никогда не поступают, то говорят, что МТ не применима к последовательности U. Рассмотрим функционирование МТ на примере сложения двух чисел, которые будем изображать в виде набора единиц. Внешний алфавит будет состоять из символов: {1, +, Ù}, где Ù – пустой символ. Внутренний алфавит будет состоять из четырех символов {q1, q2, q3, !}, где символ q1 означает начальное состояние, а ! – заключительное состояние. Пусть на ленте записана начальная информация: МТ должна ее переработать в результирующую информацию: Абстрактная программа, реализующий операцию сложения, будет иметь вид:

1q1

→Ùq3П 1q3→1q3П +q3→+q3П

Ùq3→1q2H +q2 →+q2Л 1q2→1q2Л Ùq2 →Ùq1П +q1 →Ù!Н

Начальное состояние УУ=q1, состояние ленты имеет вид:

После первого шага состояние YY=q3, состояние ленты как на рис.

После пятого шага YY перейдёт в состояние q2. Состояние ленты показано на рис. После десятого шага YY в состоянии q1 (рис. )

			1	2	3	4	5	6	7
				1	+	1	1

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

	q1	q2	q3
1	Ùq3П	1q2Л	1q3П
Ù	Ùq1П	Ùq1П	1q2H
+	Ù!Н	+q2Л	+q3П

Основная гипотеза теории алгоритмов (тезис Чёрча)

Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга. Обоснование гипотезы. Речь не идет о доказательстве гипотезы, так как она содержит не формализованные математические понятия. Уверенность в справедливости гипотезы основана, главным образом, на опыте. Все известные к настоящему времени алгоритмы могут быть заданы посредством тьюринговых функциональных схем. Кроме того, внутри самой теории алгоритмов основная гипотеза не применяется, то есть при доказательстве теорем этой теории ссылок на основную гипотезу не делается.

www.coolreferat.com

Теория алгоритмов. Теория алгоритмов реферат

Реферат Теория алгоритмов

План:

Введение

1. Возникновение теории алгоритмов

2. Модели вычислений

3. Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы

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

4.1. Анализ трудоёмкости алгоритмов

4.2. Классы сложности

Литература

Теория алгоритмов - учебная работа

Реферат - Элементы теории алгоритмов

n1.doc

Содержание

Введение

Понятие алгоритма

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

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

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

Конечность

Массовость

Результативность

Виды алгоритмов

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

Циклический алгоритм

Разветвляющийся алгоритм

Вспомогательный алгоритм

4. Способы описания алгоритмов

Словесный способ

Блок-схемы

Заключение

Литература

Теория алгоритмов

Определение

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

Тезис Маркова

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

Основная гипотеза теории алгоритмов (тезис Чёрча)

Смотрите также