Читать онлайн «Теория алгоритмов, формальных языков, грамматик и автоматов. Учебное пособие»

Министерство образования Российской Федерации Восточно-Сибирский государственный технологический университет Бильгаева Н. Ц. Теория алгоритмов, формальных языков, грамматик и автоматов Учебное пособие для студентов специальности 220400 -"Программное обеспечение вычислительной техники и автоматизированных систем" Издательство ВСГТУ Улан-Удэ 2000 УДК 681. 5. 01:512  Бильгаева Н. Ц. Теория алгоритмов, формальных языков, грамматик и автоматов: Учебное пособие. Улан-Удэ: Изд-во ВСГТУ, 2000. - с. В учебном пособии рассмотрены основные понятия теории алгоритмов, формальных языков, грамматик и автоматов; рассмотрены формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы. Рецензенты: Найханова Л. В. - к. т. н. , доцент, заведующий кафедрой систем информатики ВСГТУ. Дармаев Т. Г. – к. ф. -м. н. , заведующий лабораторией геоинформационных технологий БИП СО РАН. Печатается по решению редакционно-издательского совета Восточно-Сибирского государственного технологического университета  Восточно-Сибирский государственный технологический университет, 2000 г. ВВЕДЕНИЕ В пособии рассмотрены основные понятия теории алгоритмов и теории формальных грамматик, языков и автоматов. Пособие ориентировано на студентов младших курсов, обучающихся по специальности 220400 - "Программное обеспечение вычислительной техники и автоматизированных систем". В процессе изучения одноименных дисциплин студенты сталкиваются с тем, что учебный материал разбросан по разным источникам, написан языком труднопонимаемым для первого знакомства, а для многих понятий существует множество терминов. Поэтому при работе над пособием автор старался совместить строгость изложения основных понятий с доходчивостью восприятия. Теоретический материал по каждому разделу сопровождается методикой решения задач, примерами, а также приводятся задания для самостоятельной работы. При написании учебного пособия широко использовались книги и монографии, указанные в списке литературы, без специальных ссылок на них в тексте пособия. Пособие содержит введение, пять разделов и заключение. В первом разделе рассмотрены основные понятия теории алгоритмов и необходимость математического определения алгоритма. Во втором разделе рассмотрены рекурсивные функции, приводится понятие простейших функций и приемы построения сложных арифметических функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. В третьем разделе дано описание машин Тьюринга, рассмотрены способы их представления, операции над машинами Тьюринга, рассмотрены алгоритмически неразрешимые проблемы теории алгоритмов.