К содержанию курса теории алгоритмов

К СОДЕРЖАНИЮ КУРСА ТЕОРИИ АЛГОРИТМОВ

Кафедра Информатики и прикладного програмирования

Национальный Университет Узбекистана им. М. Улугбека,

г. Ташкент, Узбекистан

Введение. В работе приводится перечень основных вопросов, которые могут рассматриваться в рамках теории алгоритмов (ТА). Это связано с попыткой ответить на вопрос о том, что же следует включить в электронные учебники и типовые (рабочие) программы обучения по данному курсу [2], так как весь список рассматриваемых в ТА задач поистине огромен, и при этом они могут рассматриваться в рамках других теорий, пересекающихся с ТА. Например, помимо теории вычислимых (рекурсивных) функций, теории множеств, теории сложности вычислений, ТА тесно связана и с математической логикой, поскольку на понятие алгоритма опирается одно из понятий математической логики ─ понятие исчисления. Понятие исчисления является близким к понятию алгоритма, и столь же фундаментальным. В [3] её рекомендуют рассматривать совместно с ТА. Теория алгоритмов тесно связана также с кибернетикой, с основаниями математики. ТА образует теоретический фундамент для ряда вопросов вычислительной математики, а также используется для обоснования теории информации. И всё же, ТА рассматривают как самостоятельную дисциплину, а понятие алгоритма как принадлежащая к числу фундаментальных (оно не может быть выражено через другие).

Выделяются две основные задачи, рассматриваемые в курсе ТА. Первое, это задача нахождения алгоритмов (вопросы существования или несуществования эффективных алгоритмов). Разрешимость считалась основным вопросом в деле формализации математики. В рамках теории были получены, например, разрешающие алгоритмы для ряда теорий, например, элементарной геометрии, атомной булевой алгебры и других. Оказались неразрешимы (т. е. не существует единого алгоритма для решения всех задач) теории элементарной арифметики, аксиоматических систем теории множеств и прочих. Вторая задача связана с открытием противоречий в теориях, таких, например, как теория множеств, логика и т. д., т. е. связана с необходимостью обоснования математики (заметим, что и логическая наука развилась как средство решения обоснования математики). Например, к настоящему времени доказана непротиворечивость элементарной геометрии, анализа, аксиоматической системы теории множеств Цермело-Френкеля и других. Начальной точкой отсчета современной теории алгоритмов можно считать теорему о неполноте символических логик, доказанную Геделем. Было показано, что некоторые математические проблемы не могут быть решены алгоритмами из определенного класса. Как следует из теоремы Геделя о неполноте, всякая достаточно богатая теория необходимо содержит такие предложения. Некоторые важные теории оказались полными: исчисление высказываний и исчисление предикатов, элементарная геометрия, теория векторных пространств и т. д. Но в других теориях получены предложения, которые нельзя ни доказать, ни опровергнуть. Теория алгоритмов проясняет фундаментальные понятия доказуемости, сложности, случайности, рассматривает вопросы об установлении корректности (правильности) алгоритмов (как бы ни был получен алгоритм, он должен быть обоснован).

Точного определения алгоритма не существует, многочисленные существующие формулировки алгоритма понимают чаще как пояснения, а не как определения. Понятие признаётся существующим независимо от формализаций, в виде представительных (формальных) вычислительных моделей. Эти конструкции были предложены для уточнения, или адекватной формализации, общего интуитивного понятия алгоритма (вернее, понятия вычислимой функции), так как тем исходным материалом, на основании которого построено широкое научное понятие алгоритма, является интуитивное понятие [1]. Уточнением понятия алгоритма являются, помимо приведённых, также обще-рекурсивные функции, m - рекурсивные функции, l - определимые функции, графические схемы и другие. Эти понятия алгоритма являются адекватными выражениями интуитивного представления. Невозможно доказать адекватность, так как не существует точного определения алгоритма в интуитивном смысле. Чёрч высказал предположение, отождествляющее интуитивное понятие алгоритма с одним из эквивалентных между собой точных определений. Чаще обосновывают понятие алгоритма исходя их понятия автоматически работающей машины. Все алгоритмы в точном смысле являются алгоритмами в интуитивном смысле. А все известные алгоритмы могут быть промоделированы алгоритмами в точном смысле. В качестве универсальной непротиворечивой теории может рассматриваться арифметика целых чисел. Известно, что любая вычислимая функция может быть интерпретирована на языке арифметики первого порядка. Таким образом, общий метод проверки на непротиворечивость - выразить анализирумую аксиому (формулу) на языке этой теории и показать истинность её в соответственной модели.

Роль адекватных формализаций понятия алгоритма могут играть и так называемые языки программирования. Эти языки могут быть использованы для задания точно очерченного представительного класса алгоритмов [3]. Здесь важно то, что каждый алгоритм может быть записан на языке. Языки программирования основываются на уточнениях понятия алгоритма, что позволили проводить (логическое) исследование семантики языков, при спецификации, синтезе и конструировании, верификации, доказуемости правильности программ. Отметим и тесную связь понятия программы с математическим понятием алгоритма, так как написание программы, по сути, это продолжение разработки алгоритма.

Уточнение понятия алгоритма позволило формализовать понятие существования решения массовых алгоритмических проблем. Формальные задания алгоритмов (исчислений) могут быть объектом алгоритмических (исчислительных) преобразований. Возникает понятие способ программирования и программы как объекта вычисления и порождения. Соответственно, создается способ программирования как способ погружения формального задания алгоритма в ансамбль входов и выходов.

Под исчислением понимается конечный список разрешительных (порождающих) правил, или правил вывода. Понятие исчисления включает язык и аксиомы исчисления, правила вывода. Исчисление – это формальный аппарат оперирования со знаками определённого вида, позволяющий дать исчерпывающе точное описание некоторого класса задач. Если алгоритм задаёт алгоритмический (вычислительный) процесс, то каждое исчисление задаёт исчислительный (порождающий) процесс. Исчисление формализует понятие доказательства, давая ему строгое математическое определение. Представительными порождающими моделями являются канонические системы, нормальные системы Поста, грамматики [3].

В соответствии с [3] теорию алгоритмов (и исчислений) удобно разделить на две части - общую теорию, связанную со строением алгоритмов и исчислений самих по себе, и прикладную теорию, имеющую дело с проблемами (связанными с понятием алгоритма и исчисления) возникающими в различных областях математики. В общей теории выделяется дескриптивная сторона, занимающаяся вопросами о наличии или отсутствии алгоритмов и исчислений, о способах задания этих алгоритмов и исчислений, и метрическую сторону, занимающуюся оцениванием сложности процессов вычисления и порождения. Одного только существования алгоритма, решающего ту или иную массовую проблему, далеко недостаточно для практики. После уточнения понятия сложности вычисления стали исследовать вопросы такого рода, как внутренняя сложность вычислимой функции, её криптографическая стойкость, приобретающие особую актуальность с развитием сетей связи, вычислительной техники и автоматизированных систем управления. Традиционные теории алгоритмов изучают вопросы существования (несуществования) алгоритмов путем сведения вопросов к исследованию какого-либо одного узкого класса алгоритмов. В противоположность им для содержательных теорий именно алгоритмы как таковые во всем их разнообразии являются её предметом. В [4] выделяют следующие разделы ТА: классическая теория алгоритмов, теория асимптотического анализа алгоритмов, теория практического анализа вычислительных алгоритмов. Большой список математических приложений ТА приведён в [3]. Об основных задачах и направлениях развития, характерных для современной теории алгоритмов, об их теоретическом и практическом аспектах можно посмотреть в [4].

Что не следует относить к ТА? Теоремы, предполагающие построение тех или иных алгоритмов, и встречающихся в различных областях математики, но не требующие для своего понимания общего понятия алгоритма, не следует рассматривать в курсе ТА. Построение конкретного алгоритма лучше относить к соответствующей области математики или вычислительной практики, к которой принадлежит решаемая этим алгоритмом задача, и методы которой используются при построении алгоритма. Не рекомендуют рассматривать в рамках ТА и оценки сложности конкретных алгоритмов, если они не были получены для представительной вычислительной модели [3].

Коротко перечислим некоторые основные разделы теории: классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, описание сложностных классов задач, введение новых моделей вычислений). Теория асимптотического анализа алгоритмов (понятие сложности и трудоемкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, анализ трудоемкости, получение теоретических нижних оценок сложности задач). Теория практического анализа вычислительных алгоритмов, введение в сложностные классы задач с точки зрения недетерминированных алгоритмов, наиболее распространенные методы разработки эффективных алгоритмов. Обобщая исследования в различных разделах теории алгоритмов, можно выделить следующие основные задачи и направления развития, характерные для современной теории алгоритмов. Это формализация понятия ‘алгоритм’ и исследование формальных алгоритмических систем (моделей вычислений). Точнее, это введение общих понятий алгоритма и исчисления как самостоятельных, конструктивные объекты, представительные вычислительные и порождающие модели, вычислимые функции, породимые, разрешимые, перечислимые множества, рекурсивные функции. Из задач [3] − доказательство алгоритмической неразрешимости задач; формальное доказательство правильности и эквивалентности алгоритмов; классификации задач, определение и исследование сложностных классов; получение методов разработки эффективных алгоритмов; исследование и анализ рекурсивных алгоритмов; получение явных функций трудоемкости алгоритмов и другие [3,4]. Этот список не охватывает некоторых разделов теории.

Полученные в теории алгоритмов результаты находят сегодня достаточно широкое практическое применение, в рамках которого можно выделить два следующих аспекта. Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос - является ли эта задача в принципе алгоритмически разрешимой. В случае алгоритмической разрешимости задачи следующим важным теоретическим вопросом является вопрос о принадлежности этой задачи к классу NP -полных задач. При утвердительном ответе можно говорить о существенных временных затратах для получения точного решения этой задачи для больших размерностей исходных данных, иными словами — об отсутствии быстрого точного алгоритма ее решения. Практический аспект: методы и методики теории алгоритмов, в основном разделов асимптотического и практического анализа [4]. Из приложений ТА в [3] приведены математические приложения теории алгоритмов, оставляя в стороне ее приложения, скажем, к биологии, к психологии, к теории управления. Имеются, впрочем, приложения, не подпадающие под указанную рубрикацию. В работе [2] предложен электронный учебник по теории алгоритмов, но там большая часть текста посвящена технологии создания.

В этой работе приведено только самое общее(!), рассматриваемое в рамках ТА. Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели к практически значимым исследованиям алгоритмов и вычислительных задач. В них предугаданы основные концепции, заложенные в аппаратуру и языки программирования. В данный период оформились такие разделы в теории алгоритмов, как классическая теория, теория асимптотического анализа алгоритмов, теория практического анализа вычислительных алгоритмов. Полученные в теории алгоритмов результаты находят сегодня достаточно широкое практическое применение.

Литература.

1. Носов, теории алгоритмов, анализа их сложности./ Курс лекций// М. – 1992. -139с.

2. Ходиев, Ш. И., Тиллаев создания электронных учебников/ , // Труды межд. конф. “Вычислит. и информ. технологии в науке, технике и образовании”, II том Павлодар: ТОО НПФ “ЭКО”. –2006. - с. 290-295.

3. Успенский, В. А., Семенов, алгоритмов: основные открытия и приложения /, // Наука.–1987. - 288с.

4. Макконелл, современных алгоритмов/ // М.: Техносфера, 2-е дополненное издание. –2004. -368с.