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

Основы теории алгоритмов, Поляков В.И., Скорубский В.И., 2012

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

  • Книги и учебники →
  • Книги по информатике и компьютерам

СкачатьЕще скачатьСмотреть Купить бумажную книгуКупить электронную книгуНайти похожие материалы на других сайтахКак открыть файлКак скачатьПравообладателям (Abuse, DMСA)Основы теории алгоритмов, Поляков В.И., Скорубский В.И., 2012.   Пособие содержит обзор моделей алгоритма:- алгоритмы распознавания регулярных языков конечными автоматами;- свойства читающих, записывающих конечных автоматов и автоматов с выходом;- преобразования блок-схем в конечные автоматы и регулярные выражения:- машины Тьюринга и Поста;- ассоциативные вычисления:- рекурсивные функции.Приводятся задания для преобразования регулярных выражений в конечные автоматы и блок-схемы.Пособие предназначено для студентов. обучающихся по направлениям 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия».

КЛАССЫ СЛОЖНОСТИ.

В рамках классической теории алгоритмические задачи различаются по классам сложности (Р-сложные, NP-сложные, экспоненциально сложные и др.).Классы сложности — множества вычислительных задач, примерно одинаковых по сложности вычисления.

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

Классом сложности X называется множество предикатов Р(х), вычислимых на машинах Тьюринга и использующих для вычисления 0(f(n)) ресурса, где п — длина слова х.В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы).

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

.

Введение.1. Регулярные языки.2. Конечные автоматы.2.1. Читающие конечные автоматы.2.1.1. Конечные автоматы — модель алгоритма распознавания строк регулярного языка. 2.1.2. Преобразование регулярных выражений в конечные автоматы.2.1.3. Преобразование конечного автомата в регулярное выражение.2.2.

Распознавание нерегулярных языков.2.2.1. Распознавание нерегулярных языков рекурсивным запуском конечного автомата.2.3. Конечные автоматы с выходом.2.4. Событийная интерпретация конечного автомата с выходом.2.5. Записывающие конечные автоматы.3. Применение конечных автоматов в программировании.4. Машина Тьюринга.5. Машина Поста.

6. Ассоциативные исчисления.7. Рекурсивные функции.8. Классы сложности.Заключение.Именной указатель.Литература.Приложение 1.Приложение 2.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Основы теории алгоритмов, Поляков В.И., Скорубский В.И., 2012 — fileskachat.

com, быстрое и бесплатное скачивание.

Скачать pdf

Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу

Скачать — pdf — Яндекс.Диск.

15.02.2020 06:51 UTC

учебник по информатике :: информатика :: компьютеры :: Поляков :: Скорубский :: алгоритмы

Следующие учебники и книги:

  • Аудит безопасности информационных систем, Скабцов Н., 2018
  • Теория и практика машинного обучения, Воронина В.В., Михеев А.В., Ярушкина Н.Г., Святов К.В., 2017
  • Совершенный алгоритм, Основы, Рафгарден Т., 2019
  • Генетические алгоритмы, Панченко Т.В., 2007

Предыдущие статьи:

  • Нейронные сети и нейроконтроллеры, Бураков М.В., 2013
  • Искусственный интеллект, Современный подход, Рассел С., Норвиг П., 2006
  • Интеллектуальные системы, Кадырова Г.Р., 2017
  • Базы данных, Интеллектуальная обработка информации, Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В., 2000

Следующая статья >>

 

Источник: https://nashol.me/20200215118424/osnovi-teorii-algoritmov-polyakov-v-i-skorubskii-v-i-2012.html

1 В.И. Поляков, В.И. Скорубский Основы теории алгоритмов Учебное пособие по дисциплине «Математическая логика и теория алгоритмов» Санкт-Петербург 2012 Министерство

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

Книги по всем темамPages:     || 2 | 3 | 4 | 5 | В.И. Поляков, В.И.

Скорубский Основы теории алгоритмов Учебное пособие по дисциплине «Математическая логика и теория алгоритмов» Санкт-Петербург 2012 Министерство образования и науки Российской Федерации САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ В.И. Поляков, В.И.

Скорубский Основы теории алгоритмов Учебное пособие по дисциплине «Математическая логика и теория алгоритмов» Санкт-Петербург 2012 1 Поляков В.И., Скорубский В.И. Основы теории алгоритмов. – СПб: СПб НИУ ИТМО, 2012. – 51 с.

Пособие содержит обзор моделей алгоритма:

— алгоритмы распознавания регулярных языков конечными автоматами;

— свойства читающих, записывающих конечных автоматов и автоматов с выходом;

— преобразования блок-схем в конечные автоматы и регулярные выражения;

— машины Тьюринга и Поста;

— ассоциативные вычисления;

— рекурсивные функции.

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

Пособие предназначено для студентов, обучающихся по направлениям 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия».

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет».

Министерством образования и науки Российской Федерации была утверждена программа его развития на 2009–2018 годы. В 2011 году Университет получил наименование «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики».

© Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2012 © В.И. Поляков, В.И.Скорубский, 2012 2 Введение 4 1. Регулярные языки 6 2. Конечные автоматы _9 2.1. Читающие конечные автоматы 2.1. 1. Конечные автоматы — модель алгоритма распознавания строк регулярного языка. 2.1.2.

Преобразование регулярных выражений в конечные автоматы _2.1.3. Преобразование конечного автомата в регулярное выражение 2.2. Распознавание нерегулярных языков 2.2.1. Распознавание нерегулярных языков рекурсивным запуском конечного автомата2.3. Конечные автоматы c выходом 2.4. Событийная интерпретация конечного автомата c выходом_ 2.5.

Записывающие конечные автоматы _3. Применение конечных автоматов в программировании 4. Машина Тьюринга _5. Машина Поста 6. Ассоциативные исчисления _7. Рекурсивные функции 8. Классы сложности _Заключение _Именной указатель_Литература _Приложение 1 _Приложение 2 _ВВЕДЕНИЕ Современное формальное определение алгоритма было дано в 30 — 50-х гг. XX века в работах А.

Тьюринга1, Э. Поста2, А. Чёрча3, Н. Винера4, А.

А. Маркова5.

Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 г. он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился.

Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»).

Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга альХорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»).

По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.

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

Это интуитивное определение сопровождается описанием интуитивных свойств (признаков) алгоритмов: эффективность, определенность, конечность [1].

Эффективность – возможность исполнения предписаний за конечное время.

Например, алгоритм – процедура, состоящая из “конечного числа команд, каждая из которых выполняется механически за фиксированное время и с фиксированными затратами” [2].

Функция алгоритмически эффективно вычислима, если существует механическая процедура, следуя которой для конкретных значений ее аргументов можно найти значение этой функции [3].

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

Конечность – выполнение алгоритма при конкретных исходных данных за конечное число шагов.

Для демонстрации алгоритмов в теории используются алгоритмические преобразования слов и предложений формального языка [1, 3].

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

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

Алгоритмические вычисления применяются во всех областях науки и техники – монография Д. Кнута [1] рассматривает разнообразные проблемноориентированные алгоритмические решения.

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

Объектно-ориентированное обобщение алгоритмических языков позволяет активизировать алгоритмическое мышление и организовать масштабное программирование, опираясь на огромные ресурсы производительности и объемы памяти ЭВМ, постоянно наращиваемые стандартные библиотеки.

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

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

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

— конечные автоматы;

— машина Тьюринга;

— машина Поста;

— ассоциативное исчисление или нормальные алгоритмы Маркова;

— рекурсивные функции.

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

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

1. РЕГУЛЯРНЫЕ ЯЗЫКИ Для того, чтобы представить формальное описание алгоритма необходимо формальное описание решаемой задачи. В большинстве случаев описание задачи неформальное (вербальное) и переход к алгоритму неформальный и требует верификации и тестирования и многократных итераций для приближения к решению.

Верификация (от лат. verus – «истинный» и facere – «делать») – проверка, способ подтверждения каких-либо теоретических положений, алгоритмов, программ и процедур путем их сопоставления с опытными (эталонными или эмпирическими) данными, алгоритмами и программами [4].

Тестирование применяется для определения соответствия предмета испытания заданным спецификациям [4].

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

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

Расширения регулярных языков находят применение при описании лексики формальных алгоритмических языков, при описании алгоритмов, редактирования поиска по шаблону, в современном программировании (языки Perl, Java, Phyton, C#, PHP), в компиляторах и системах управления обработкой данных, как интерактивный язык в операционных системах.

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

Алфавит языка обозначается как конечное множество символов.

Например: ={a,b,c,d}, ={0,1}.

Символ и цепочка символов образуют слово – a, b, 0, abbcd, 0111000.

Пустое слово (е) не содержит символов.

Множество слов S={a, ab, aaa, bc} в алфавите называют языком L().

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

Рассмотрим следующие операции формирования новых множеств из существующих множеств слов:

1) Символы алфавита могут соединяться конкатенацией (сцепление, соединение) в цепочки символов-слов, которые соединяются в новые слова.

Конкатенация двух слов x|y обозначает, что к слову x справа приписано слово y или x|y=xy, причем xyyx.

Произведение S1|S2=S1S2 множеств слов S1 и S2 — это множество всех различимых слов, построенных конкатенацией соответствующих слов из S1 и S2.

Если S1={a, aa, ba}, S2={e, bb, ab}, то S1S2={a, aa, ba, abb, aabb, baab, …}.

Для конкатенации выполняется ассоциативность, но коммутативность и идемпотентность не выполняются:

S1S2 S2S1;

SS S.

2) объединение (S1 S2) или (S1+ S2) множеств S1={a, aa, ba}, S2={e, bb, ab}, S1 S2={a, aa, ba, e, bb, ab}.

Для операции объединения выполняются следующие законы:

Коммутативность объединения S1S2=S2S1.

Идемпотентность объединения S S=S.

Ассоциативность объединения S1 (S2 S3) =( S1 S2 ) S3.

Дистрибутивность конкатенации (умножения) и объединения S1(S2 S3) = S1S2 S1S3.

3) Итерация множества {S}* состоит из пустого слова и всех слов вида S0=е, S1=S, S2=SS, S3=SSS.

Формулы, содержащие эти операции с множествами слов, называют регулярными выражениями.

Ассоциативность итерации S1 * (S2 * S3) =( S1 * S2 )* S3.

Дистрибутивность объединения с итерацией S1 *(S2 S3) = S1*S2 S1*S3.

Если a, b – любые регулярные выражения, то (ab)* = (a* b*)* = (a*b*)* =(a*b)*a*;

a*=a*a*=(a*)*=(a a2.. ak )*;

(a *b)*=(a b)*b.

Таким образом, формулы могут содержать скобки и могут быть преобразованы с использованием этих законов.

Регулярные выражения допускают формальные алгебраические преобразования, Языки, определяемые регулярными выражениями, называются регулярными языками, а множество слов — регулярными множествами.

Пример 1.1.

Регулярные выражения регулярного языка в алфавите ={0,1} (0 10*;

(1(0)*))= (0 1*)*;

1)* = (0* (01)*011 — все cлова из 0 и 1, заканчивающиеся на 011;

(ab)(a+b)*=(ab)(a* b*)* — cлова, начинающиеся c a или b;

(0011)*((0110)(0011)*(0110)(0011)*)* — все слова, содержащие четное число 0 и 1.

Пример 1.2.

Регулярное выражение, определяющее правильное арифметическое выражение [5].

Входной алфавит ={i, +, -}, где i – идентификатор;

(+, -) – знаки арифметических операций.

Примеры правильных арифметических выражений i, — i, i + i, i — i, — i — i, i + i — i, … Обозначим знаки арифметических действий буквами p = (+), m=(-).

Тогда соответствующие правильные (регулярные) арифметические выражения имеют вид i, mi, ipi, imi, mimi, ipimi, … и регулярное выражение, определяющее регулярный язык, L(M)=(mi + i)( ( p + m )i )*.

Утверждение. Для каждого регулярного множества (языка L()) можно построить, по крайней мере, одно регулярное выражение, но для каждого регулярного выражения существует только одно регулярное множество.

2. КОНЕЧНЫЕ АВТОМАТЫ 2.1. Читающие конечные автоматы 2.1. 1. Конечные автоматы — модель алгоритма распознавания предложений регулярного языка Алгоритм распознавания предложений регулярного языка называют конечным автоматом (КА) [5].

Определение. Конечный автомат определяется символами M=(Q,,, q0, F), где Q={q0, q1, …, qn} – конечное множество состояний;

={a, b, c,…} – входной алфавит (конечное множество);

: Q* {Pj } – функция переходов, Pj — подмножество Q.

Конечное множество значений для этого функционального отношения может быть определено перечислением в таблице переходов:

Q Pj qi a qj q0 — начальное состояние;

F — множество заключительных состояний.

Конечный автомат называется недетерминированным (НДКА), если Pj содержит более одного состояния.

КА называется детерминированным (ДКА), если Pj содержит не более одного состояния.

КА полностью определенный, если Pj в детерминированном автомате не пустое. Если есть пустые элементы множества Pj, то автомат частично определен.

Работа КА или выполнение алгоритма распознавания слов регулярного языка могут быть представлены последовательностью шагов, которые определяются текущим состояние Q, входным символом и следующим состоянием Pj.

Используется конструктивное описание принципа работы КА как машины M, имеющей следующую организацию:

a b c d лента (память с возможностью чтения) читающая головка, управляемая КА КА Рис 2.1. Машина, исполняющая Конечный автомат КА читает входной символ в текущем состоянии qi Q, переходит в следующее состояние qj Q и сдвигает читающую головку к следующему символу.

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

Конфигурация КА k=(q, ), где q-текущее состояние КА, — непрочитанная цепочка символов слова на ленте, включая символ под читающей головкой.

k = (q, ) текущая конфигурация;

k0 = (q 0, 0) начальная конфигурация;

kf = (q, е), где q F, — заключительная конфигурация и (е) – символ, обозначающий конец строки.

Шаг алгоритма — переход из одной конфигурации КА в другую Ki Kj или (qi, i ) (qj, j).

Функция переходов, заданная в табличной форме, может быть представлена графом переходов G=(Q, R), где Q — вершины графа, R — бинарное отношение между парой вершин, которое представлено множеством дуг (qi, qj).

(qi, qj) Q*Q, если существует символ a и (qi, a) = qj.

На дугах графа (qi, qj) отмечаются соответствующие символы алфавита.

Пример 2.1.

0, p q r Рис.2.2. Детерминированный читающий КА Для ДКА, приведенного на рис. 2.2 состояния Q={p, q, r}, входной алфавит ={0,1}, начальное состояние p, конечное — r.

Таблица переходов ДКА Q 0 p q p q r p r r r Исполнение алгоритма это последовательность шагов, в которых изменяется конфигурация КА:

(p, 01001) (q, 1001) (p, 001) (q, 01) (r, 1) (r, е);

(p, 01001)- начальная конфигурация;

(r, е) – конечная конфигурация.

В результате применения слова 01001 в начальном состоянии p автомат переходит в следующее состояние q и следующее значение цепочки символов на входе 1001.

Автомат М допускает слово 0, если существует (q0, 0) *(qf, е), где *( ), обозначает транзитивное замыкание и существует путь, соединяющий q0 и qf для входного слова 0.

Язык L(M), определяемый (распознаваемый, допускаемый) автоматом М включает множество всех слов, допускаемых М.

2.1.2. Преобразование регулярных выражений в конечный автомат Утверждение. Язык L является регулярным тогда и только тогда, когда он определяется КА. Для любого регулярного языка, представленного регулярным выражением, можно построить КА — распознаватель слов, допустимых языком.

Метод Ямады преобразования L(M) M позволяет формально выполнить преобразование [5, 6]:

Pages:     || 2 | 3 | 4 | 5 | Книги по всем темам

Источник: http://knigi.dissers.ru/books/1/9779-1.php

Biz-books
Добавить комментарий