Элементы компьютерной алгебры

Лабораторная работа №1

Тема: Элементы компьютерной алгебры

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

Задание

1.  На примере программы  символьного дифференцирования, прилагаемого к данной лабораторной работе, рассмотреть структуру данных для представления математических выражений.

2.  Развить данную структуру для представления вещественных чисел, комплексных чисел.

3.  Познакомиться с принципами лексического и синтаксического анализа входных строковых выражений, представляющих математические тексты.

4.  Познакомиться с принципами трансляции из внутреннего представления математических выражений во внешнее – строковое.

5.  Рассмотреть Пролог – программу  для символьного дифференцирования и упрощения алгебраических выражений с точки зрения декларативной семантики (как систему аксиом).

6.  Используя в качестве прототипа программу аналитического дифференцирования, составить программу аналитического интегрирования для выбранного класса функций.

Методические указания

Проблема символьных вычислений традиционно относится к одному из направлений искусственного интеллекта. В настоящее время это направление представляется достаточно развитым. Можно указать ряд монографий, где отражается современное состояние проблемы [1,2]. Существует ряд мощных математических пакетов, в которых имеется возможность символьной обработки математических выражений. К таковым в первую очередь можно отнести такие пакеты как MAPLE V, MATEMATIKA 3, MAXIMA, MATCAD6+.

ПРОЛОГ как язык искусственного интеллекта, является весьма удобным средством обработки цепочек символов, в том числе математических текстов. В нашем случае на примере программы символьного дифференцирования можно почувствовать выразительную силу данного формализма. Обратите внимание на структуры данных, представляющие математические выражения. Их рекурсивный характер предопределяет рекурсивную обработку этих данных. Заслуживают внимание правила дифференцирования, представленные предложениями на ПРОЛОГе. По существу данная программа является хорошим примером декларативного стиля программирования. Используя основные принципы, понятные из данной программы можно, например, сформулировать правила интегрирования и основные приемы интегрирования. Понятно, что эта задача много сложнее, чем дифференцирование. Следует обратить внимание на принципиальную разницу в представлении проблемы дифференцирования и интегрирования. Задача дифференцирования аналитической функции всегда имеет решение, в то время как задача интегрирования не всегда может иметь решения в конечном виде. Если проблема дифференцирования описывается конечным числом правил (аксиом), то проблема интегрирования в целом требует наряду с представлением аксиом интегрирования (интеграл суммы равен сумме интегралов, константа может быть вынесена за знак интеграла и пр.) так же представления приемов интегрирования (интегрирование по частям и пр.). Эти приемы можно рассматривать как базу знаний в области интегрирования функций, которая в принципе может неограниченно  расширяться, но это расширение не гарантирует решения проблемы.

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

Лабораторная работа №2

Тема: Стратегии решения задач

Цель работы: Изучение основных стратегий решения задач. Приобретение  навыков  выбора  адекватных  стратегий в зависимости от типа задач. Выбор инструмента для реализации этих стратегий.

Задание

1.  Сформулировать задачу в закрытой форме. Выбрать комбинацию из следующих подходящих стратегий решения задачи:

-  представление в пространстве состояний;

-  сведения задач к подзадачам;

-  генерация вариантов и проверка;

-  поиск в глубину с возвратом;

-  поиск в ширину;

-  поиск с предпочтением (эвристический поиск),

-  распространение ограничений;

-  сведение задачи к доказательству теоремы.

2.  Разработать адекватную структуру данных, максимально учитывающую специфику  предметной области задачи. Обосновать выбор структуры.