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

Основы теории алгоритмов, Поляков В.И., Скорубский В.И., 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 - Яндекс.Диск.




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