ВУЗ:
Составители:
ВВЕДЕНИЕ
В пособии рассмотрены основные понятия теории алгоритмов и теории формальных
грамматик, языков и автоматов. Пособие ориентировано на студентов младших курсов,
обучающихся по специальности 220400 - "Программное обеспечение вычислительной
техники и автоматизированных систем". В процессе изучения одноименных дисциплин
студенты сталкиваются с тем, что учебный материал разбросан по разным источникам,
написан языком труднопонимаемым для первого знакомства, а для многих понятий
существует множество терминов. Поэтому при работе над пособием автор старался
совместить строгость изложения основных понятий с доходчивостью восприятия.
Теоретический материал по каждому разделу сопровождается методикой решения задач,
примерами, а также приводятся задания для самостоятельной работы. При написании
учебного пособия широко использовались книги и монографии, указанные в списке
литературы, без специальных ссылок на них в тексте пособия.
Пособие содержит введение, пять разделов и заключение. В первом разделе рассмотрены
основные понятия теории алгоритмов и необходимость математического определения
алгоритма. Во втором разделе рассмотрены рекурсивные функции, приводится понятие
простейших функций и приемы построения сложных арифметических функций с помощью
операций суперпозиции, примитивной рекурсии и минимизации. В третьем разделе дано
описание машин Тьюринга, рассмотрены способы их представления, операции над
машинами Тьюринга, рассмотрены алгоритмически неразрешимые проблемы теории
алгоритмов. В четвертом разделе рассмотрены основные понятия формальных грамматик и
языков, приводится классификация грамматик, стратегии грамматического разбора, а также
эквивалентные преобразования КС-грамматик. В пятом разделе рассмотрены различные
типы автоматов (конечные автоматы, автоматы с магазинной памятью, автоматы Мили и
Мура) и их связь с грамматиками и языками.
Автор считает своим долгом выразить признательность Бриковой М., Жаргалову Б.,
Крюкову Е., которые выполнили компьютерный набор первоначального варианта текста
пособия, оказали помощь при подборе заданий для самостоятельной работы.
Все замечания и пожелания по пособию автор просит направлять по адресу: 670013,
г.Улан-Удэ, ул. Ключевская, 40-а, ВСГТУ.
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
1.1. Предварительные сведения
Понятие алгоритма, являющееся одним из основных понятий математики, возникло
задолго до появления вычислительных машин. На протяжении многих веков люди
пользовались интуитивным понятием алгоритма. Арабский математик IX века Мухаммед
ибн Муса Аль-Хорезми впервые выдвинул идею о том, что решение любой поставленной
математической и философской задачи может быть оформлено в виде последовательности
механически выполняемых правил, т.е. может быть алгоритмизировано. Этого же мнения
придерживались Декарт, Лейбниц, Гильберт.
Приведем интуитивное определение алгоритма.
Алгоритм - это строгая и четкая конечная система правил решения некоторого класса
задач, определяющая процесс преобразования исходных данных в искомый результат.
В рамках данного определения понятие алгоритма отождествлялось с понятием метода
вычисления, традиции организации вычислений складывались веками и стали составной
частью общей научной культуры, формулировались и успешно применялись на практике
различные вычислительные алгоритмы. Поэтому понятие метода вычислений считалось
изначально ясным и потребности в изучении самого этого понятия не возникало.
ВВЕДЕНИЕ
В пособии рассмотрены основные понятия теории алгоритмов и теории формальных
грамматик, языков и автоматов. Пособие ориентировано на студентов младших курсов,
обучающихся по специальности 220400 - "Программное обеспечение вычислительной
техники и автоматизированных систем". В процессе изучения одноименных дисциплин
студенты сталкиваются с тем, что учебный материал разбросан по разным источникам,
написан языком труднопонимаемым для первого знакомства, а для многих понятий
существует множество терминов. Поэтому при работе над пособием автор старался
совместить строгость изложения основных понятий с доходчивостью восприятия.
Теоретический материал по каждому разделу сопровождается методикой решения задач,
примерами, а также приводятся задания для самостоятельной работы. При написании
учебного пособия широко использовались книги и монографии, указанные в списке
литературы, без специальных ссылок на них в тексте пособия.
Пособие содержит введение, пять разделов и заключение. В первом разделе рассмотрены
основные понятия теории алгоритмов и необходимость математического определения
алгоритма. Во втором разделе рассмотрены рекурсивные функции, приводится понятие
простейших функций и приемы построения сложных арифметических функций с помощью
операций суперпозиции, примитивной рекурсии и минимизации. В третьем разделе дано
описание машин Тьюринга, рассмотрены способы их представления, операции над
машинами Тьюринга, рассмотрены алгоритмически неразрешимые проблемы теории
алгоритмов. В четвертом разделе рассмотрены основные понятия формальных грамматик и
языков, приводится классификация грамматик, стратегии грамматического разбора, а также
эквивалентные преобразования КС-грамматик. В пятом разделе рассмотрены различные
типы автоматов (конечные автоматы, автоматы с магазинной памятью, автоматы Мили и
Мура) и их связь с грамматиками и языками.
Автор считает своим долгом выразить признательность Бриковой М., Жаргалову Б.,
Крюкову Е., которые выполнили компьютерный набор первоначального варианта текста
пособия, оказали помощь при подборе заданий для самостоятельной работы.
Все замечания и пожелания по пособию автор просит направлять по адресу: 670013,
г.Улан-Удэ, ул. Ключевская, 40-а, ВСГТУ.
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ
1.1. Предварительные сведения
Понятие алгоритма, являющееся одним из основных понятий математики, возникло
задолго до появления вычислительных машин. На протяжении многих веков люди
пользовались интуитивным понятием алгоритма. Арабский математик IX века Мухаммед
ибн Муса Аль-Хорезми впервые выдвинул идею о том, что решение любой поставленной
математической и философской задачи может быть оформлено в виде последовательности
механически выполняемых правил, т.е. может быть алгоритмизировано. Этого же мнения
придерживались Декарт, Лейбниц, Гильберт.
Приведем интуитивное определение алгоритма.
Алгоритм - это строгая и четкая конечная система правил решения некоторого класса
задач, определяющая процесс преобразования исходных данных в искомый результат.
В рамках данного определения понятие алгоритма отождествлялось с понятием метода
вычисления, традиции организации вычислений складывались веками и стали составной
частью общей научной культуры, формулировались и успешно применялись на практике
различные вычислительные алгоритмы. Поэтому понятие метода вычислений считалось
изначально ясным и потребности в изучении самого этого понятия не возникало.
