Проспект учебного пособия

Ю.Г.Карпов

Теория автоматов и алгоритмов

учебное пособие

АННОТАЦИЯ.

Учебное пособие обеспечивает один из важнейших компонентов федерального государственного образовательного стандарта бакалавров по направлению Информатика и вычислительная техника. Теория автоматов и алгоритмов является основной составной частью дисциплины Теоретическая информатика, входящей в естественнонаучный цикл дисциплин под номером ЕН2. Курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем, а также для осознания целей и ограничений при создании вычислительных структур, алгоритмов и программ для обработки информации.

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

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

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

В частности, в результате освоения данного курса студент на основе ясного понимания соответствующих теоретических разделов должен УМЕТЬ:

• реализовать простейший вид преобразования информации - конечное функциональное отображение - в произвольном базисе логических функций;

• выделять в доказательных рассуждениях естественного языка логическую структуру, факты, посылки и следствия; строить схемы формальных доказательств и проверять их правильность;

• интерпретировать программы на языке логического программирования Пролог;

• разрабатывать дискретные системы управления на базе модели конечного автомата, доводя их до программной и аппаратной реализации;

• использовать алгебру регулярных выражений и синтаксические диаграммы для задания формальных языков, строить трансляторы автоматных языков;

• распознавать алгоритмически неразрешимые проблемы и оценивать сложность алгоритмов;

• проводить верификацию простых программ обработки данных и осуществлять генерацию тестов для них.

СОДЕРЖАНИЕ