Читать онлайн «Основы теории алгоритмов»

В. И. Поляков, В. И. Скорубский Основы теории алгоритмов Учебное пособие по дисциплине «Математическая логика и теория алгоритмов» Санкт-Петербург 2012  Министерство образования и науки Российской Федерации САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ В. И. Поляков, В. И. Скорубский Основы теории алгоритмов Учебное пособие по дисциплине «Математическая логика и теория алгоритмов» Санкт-Петербург 2012 1  Поляков В. И. , Скорубский В. И. Основы теории алгоритмов. – СПб: СПб НИУ ИТМО, 2012. – 51 с. Пособие содержит обзор моделей алгоритма: - алгоритмы распознавания регулярных языков конечными автоматами; - свойства читающих, записывающих конечных автоматов и автоматов с выходом; - преобразования блок-схем в конечные автоматы и регулярные выражения; - машины Тьюринга и Поста; - ассоциативные вычисления; - рекурсивные функции. Приводятся задания для преобразования регулярных выражений в конечные автоматы и блок-схемы. Пособие предназначено для студентов, обучающихся по направлениям 230100 «Информатика и вычислительная техника» и 231000 «Программная инженерия». В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена программа его развития на 2009–2018 годы. В 2011 году Университет получил наименование «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики».  Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2012  В. И. Поляков, В. И. Скорубский, 2012 2  Содержание Введение __________________________________________________4 1. Регулярные языки ________________________________________ 6 2. Конечные автоматы _______________________________________9 2. 1. Читающие конечные автоматы __________________________9 2. 1. 1. Конечные автоматы - модель алгоритма распознавания строк регулярного языка. ________________________________9 2. 1. 2. Преобразование регулярных выражений в конечные автоматы _____________________________________________11 2. 1. 3. Преобразование конечного автомата в регулярное выражение ____________________________________________15 2. 2. Распознавание нерегулярных языков ____________________17 2. 2. 1. Распознавание нерегулярных языков рекурсивным запуском конечного автомата________________________________18 2. 3. Конечные автоматы c выходом ________________________18 2. 4. Событийная интерпретация конечного автомата c выходом_ 19 2. 5.