02. Введение

В учебные планы по специальностям, связанным так или иначе с программными технологиями, обязательно входят курсы, посвященные разработке различных алгоритмов. Обстоятельный обзор таких алгоритмов содержится в недавно вышедшей в русском переводе книги [1].

Это, несмотря на возникающие собственно математические вопросы, - практические аспекты теории алгоритмов как таковой. Фундаментом же является классическая теория алгоритмов, представленная многочисленными точными моделями алгоритма (машины Тьюринга, рекурсивные функции, канонические системы Поста, нормальные алгорифмы Маркова). Эта теория должна лежать в основе всех дальнейших разработок, и главный результат здесь – анализ алгоритмических массовых проблем и доказательство неразрешимости некоторых из них. Любой программист должен четко знать границы применения алгоритмических методов, понимать суть алгоритмической неразрешимости, знать, какие алгоритмически неразрешимые проблемы возникают в сфере программирования (например, проблема функциональной эквивалентности программ [2, 3]).

В данной статье рассматривается методика изложения ключевых положений теории алгоритмов на примере нормальных алгорифмов Маркова. Эта модель алгоритма заслуживает особого внимания, так как лежит в основе некоторых языков программирования (например, языка РЕФАЛ [4, 5, 6]), предназначенных для обработки символьной информации, для разработки трансляторов в том числе. Изложение ведется на доступном для понимания студентов-нематематиков (программистов, например) уровне с опорой на основополагающие источники, книгу [7] прежде всего. Следует иметь в виду и очень хорошую книгу Б. А. Кушнера [8]. Мы стараемся излагать все доказательства максимально просто и прозрачно, не нанося существенного ущерба строгости изложения. Собственно, в этом и состоит суть предлагаемой методики: достаточно просто и в то же время строго изложить часто весьма непростые результаты и доказательства. Методика ориентирована на студентов-нематематиков, но тем, которым в своей профессиональной деятельности придется математику использовать.

Предваряя дальнейшее изложение основных положений теории алгоритмов, необходимо дать перечень главных разделов этой теории. Эти разделы таковы:

1. Определение основной модели (в данном случае, нормального алгорифма) и формулировка основной гипотезы, состоящей в том, что предлагаемая модель представляет, в известном смысле, любой алгоритм.

2. Понятие эквивалентных алгоритмов.

3. Теоремы сочетания (основные конструкции из алгоритмов, как то: последовательное применение, независимое применение, условный переход и цикл), согласно которым любое сочетание алгоритмов может быть в конечном счете сведено к основной модели.

4. Универсальный алгоритм (по сути, универсальный интерпретатор в классе программ, определяемых основной моделью).

5. Разрешимые и перечислимые множества.

6. Алгоритмически неразрешимые проблемы.

Материал статьи основан на курсе «Логика и теория алгоритмов», который автор уже многие годы читает на программистских специальностях МГТУ им. Н. Э. Баумана. Студенты подготовлены к освоению курса курсом дискретной математики, опирающимся на базовый учебник [9], в котором для понимания теории алгоритмов особенно важны элементы теории формальных языков.

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

< Предыдущая		Следующая >