Введение в сложность вычислений, Крупский В.Н., 2006

Введение в сложность вычислений, Крупский В.Н., 2006.

   Учебное пособие написано по материалам полугодового спецкурса, читавшегося автором на механико-математическом факультете
МГУ им. М. В. Ломоносова для студентов и аспирантов кафедры математической логики и теории алгоритмов, а также специальности
«Защита информации». Излагаются основные идеи и методы теории сложности вычислений.
Для студентов, аспирантов и специалистов, занимающихся анализом эффективности алгоритмов.




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

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



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в сложность вычислений, Крупский В.Н., 2006 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по информатике :: информатика :: компьютеры :: Крупский