85958

Разработка программного приложения в среде программирования Delphi для анализа функций двух переменных

Курсовая

Информатика, кибернетика и программирование

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

Русский

2015-04-01

1.39 MB

10 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НЕФТЕКАМСКИЙ ФИЛИАЛ

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Экономико-математический факультет

Кафедра математического моделирования и информационной безопасности

КУРСОВАЯ работа

по дисциплине «Уравнения свертки»

на тему

«Разработка программного приложения в среде программирования Delphi для анализа функций двух переменных»

Выполнил: студент 3 курса

очной формы обучения

группы М-31

Баймуратов А.В.

Научный руководитель:

ст. пр. Гибаева Р.А.

Нефтекамск 2013


СОДЕРЖАНИЕ

[1]
Введение

[2]
1 СИНТАКСИЧЕКИЙ АНАЛИЗ И СПОСОБЫ ПРЕДСТАВЛЕНИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ

[2.1] 1.1 Формальные языки и грамматики

[2.2] 1.2 Классификация грамматик по Хомскому

[2.3] 1.2 Способы задания грамматик

[2.4] 1.3 Трансляторы компиляторы и интерпретаторы

[2.5] 1.4 Двоичные деревья выражений

[2.6] 2.1 Грамматика языка арифметики

[2.7] 2.2 Вычисления значения выражения, представленного в виде двоичного дерева

[2.8] 2.3 Упрощение арифметического выражения заданного своим двоичным деревом

[2.9] 2.4 Символьное дифференцирование выражения

[2.10] 2.5 Программная реализация

[3]
ЗАКЛЮЧЕНИЕ

[4]
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ


Введение

В настоящее время широко стоит проблема синтаксического анализа текстов. Дисциплина, в которой применяются методы синтаксического анализа, называется теорией компиляторов. Годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма трудоемким процессом.

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

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

В настоящее время существуют различные математические пакеты программ. Все эти пакеты представляют собой сложные вычислительные системы, содержащие в себе сотни математических формул. К наиболее популярным математическим пакетам, которые также называют системами компьютерной алгебры, можно отнести: Matlab, MathCAD, Maple.

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

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

Задачи поиска производных и первообразных функции решается в такой дисциплине как компьютерная алгебра, о которой подробнее можно узнать в книгах Акритаса1, Девенпорта, Сирэ, Турнье2 и Панкратьева3.

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

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

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

Этапы создания синтаксического анализатора включает: анализ требований к будущему программному продукту, составление проекта программы и плана отладки, алгоритмизация, программирование, тестирование и отладка.

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

Поставленная цель определила постановку следующих задач:

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


1 СИНТАКСИЧЕКИЙ АНАЛИЗ И СПОСОБЫ ПРЕДСТАВЛЕНИЯ АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ

1.1 Формальные языки и грамматики

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

Формальное описание грамматики построено на основе системы правил (продукций). Правило представляет собой упорядоченную пару цепочек символов , которую обычно записывают, как  (или ) и читают как « порождает ».

Язык, заданный грамматикой , обозначается как .

Две грамматики  и  называются эквивалентными, если они определяют один и тот же язык: . Две грамматики  и  называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов:

Формально грамматика  определяется как четверка , где:

  •   – множество терминальных символов или алфавит терминальных символов;
  •   – множество нетерминальных символов или алфавит нетерминальных символов;
  •   – множество правил грамматики, вида , где , ;
  •   – целевой (начальный) символ грамматики .

Алфавиты терминальных и нетерминальных символов грамматики не пересекаются: . Целевой символ грамматики – это всегда нетерминальный символ. Множество  называют полным алфавитом грамматики .

Множество терминальных символов  содержит символы, которые входят в алфавит языка, порождаемого грамматикой. Символы из множества  встречаются только в цепочках правых частей правил. Множество нетерминальных символов  содержит символы, которые определяют слова, понятия, конструкции языка. Каждый символ этого множества может встречаться в цепочках как левой, так и правой частей правил грамматики, но он обязан хотя бы один раз быть в левой части хотя бы одного правила4.

1.2 Классификация грамматик по Хомскому

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

Грамматики с фразовой структурой (Тип 0). На структуру этих правил не накладывается никаких ограничений. Для грамматики вида ,  правила имеют вид: , где .

Это самый общий тип грамматик. В него подпадают все без исключения формальные грамматики, но часть из них может быть также отнесена и к другим классификационным типам. Грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре и не имеют практического применения.

Контекстно-зависимые (КЗ) и неукорачивающие грамматики (Тип 1). В этот тип входят два основных класса грамматик:

  •  Контекстно-зависимые грамматики ,  имеют правила вида: , где ;
  •  Неукорачивающие грамматики ,  имеют правила вида: , где .

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

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

Контекстно-свободные (КС) грамматики (Тип 2). КС-грамматики ,  имеют правила вида: , где . Такие грамматики также иногда называют неукорачивающими контекстно-свободными (НКС) грамматиками (в правой части правила должен стоять как минимум один символ). Существует также эквивалентный им класс грамматик – укорачивающие контекстно-свободные (УКС) грамматики , , правила которых имеют вид: , где .

КС-грамматики широко используются при описании синтаксических конструкций языков программирования. Синтаксис большинства известных языков программирования основан на КС-грамматиках.

Во множестве КС-грамматик кроме классов НКС и УКС выделяют еще целое подмножество различных классов грамматик, которые также относятся к типу 2.

Регулярные грамматики (Тип 3). К типу регулярных относятся два эквивалентных класса грамматик: леволинейные и праволинейные.

Леволинейные грамматики ,  могут иметь правила двух видов:  или , где .

В свою очередь, праволинейные грамматики ,  могут иметь правила тоже двух видов:  или , где.

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

1.2 Способы задания грамматик

Схема грамматики содержит правила вывода, определяющие синтаксис языка, другими словами, возможные компоненты и конструкции цепочек порождаемого языка. Для задания правил используются различные формы описания: символическая, форма Наура-Бэкуса, итерационная форма, синтаксические диаграммы и другие.

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, вида: . Тогда эти правила объединяют вместе и записывают в виде: . Одной строке в такой записи соответствует сразу n правил. Такую форму записи правил грамматики называют формой Бэкуса–Наура. Форма Бэкуса–Наура предусматривает, как правило, что нетерминальные символы берутся в угловые скобки: < >.

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

Cоставляющие элементы грамматики :

  •  множество терминальных символов  содержит двенадцать элементов: десять десятичных цифр и два знака;
  •  множество нетерминальных символов  содержит три элемента: символы ,   и ;
  •  множество правил содержит 15 правил, которые записаны в три строки (то есть имеется только три различных правых части правил);
  •  целевым символом грамматики является символ .

Названия нетерминальных символов могут быть не осмысленными. Например, в программе на языке Pascal можно изменить имена идентификаторов, и при этом не изменится смысл программы. Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.

Кроме формы Бэкуса-Наура, существуют и другие способы записи грамматик, а именно запись с использованием метасимволов и графическое представление.

Запись грамматик с использованием метасимволов предполагает, что в строке правила могут присутствовать особые символы – так называемые метасимволы, которые трактуются специальным образом. Обычно в этой роли используются ( ) круглые, [ ] квадратные и { } фигурные скобки, а также «,» запятые и «“ ”» кавычки. Они имеют следующий смысл:

  •  ( ) – в данном месте правила может стоять только одна из всех перечисленных внутри них цепочек;
  •  [ ] – указанная внутри них цепочка может быть в правиле грамматики один раз или ни одного раза;
  •  { } – указанная внутри них цепочка может встречаться любое количество раз (в том числе сколь угодно много или ни одного);
  •  , – разделяет цепочки символов внутри круглых скобок;
  •  “ ” – используются для включения метасимволов в цепочку символов языка.

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

Первое правило означает, что «число есть цепочка символов, которая может начинаться со знака + или -, должна дальше содержать одну цифру, за которой может следовать последовательность цифр любой длины».

Грамматика стала более понятной, кроме того, удалось полностью избежать рекурсии, заменив ее символом итерации { }. Эта форма наиболее употребима для одного из типов грамматик, а именно – для регулярных грамматик.

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

В такой форме записи каждому нетерминальному символу соответствует диаграмма, построенная в виде ориентированного графа. Граф имеет следующие типы вершин:

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

Каждая диаграмма имеет только одну точку входа и одну точку выхода, но сколько угодно вершин других типов. Вершины соединяются направленными дугами, из входной точки дуги могут только выходить, в выходную точку – только входить. Все остальные вершины должны иметь как минимум по одной выходной и одной входной дуге.

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

Описанная ранее грамматика  порождения целых десятичных чисел со знаком изображена на рисунке 1.

Рисунок 1 – Диаграмма, описывающая грамматику

1.3 Трансляторы компиляторы и интерпретаторы

Транслятор – это программа, которая переводит программу на исходном (входном) языке в эквивалентную ей программу на результирующем (выходном) языке7.

С точки зрения преобразования предложений входного языка в эквивалентные им предложения выходного языка транслятор выступает как переводчик.

Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным – не содержит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы транслятора будет сообщение об ошибке.

Компилятор − это программа, которая считывает текст  программы, написанной на одном языке − исходном, и транслирует (переводит) его в эквивалентный текст на другом языке – целевом8.

Результатом работы компилятора будет исполняемый файл.

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

Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семантикой входного языка9.

1.4 Двоичные деревья выражений

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

Кореньэто начальный узел дерева, в который не ведет ни одной дуги.

Дерево представляет собой рекурсивную структуру (определяемую через саму себя). Как и любое рекурсивное определение, определение дерева состоит из двух частей - первая определяет условие окончания рекурсии, а второе - механизм ее использования:

  •  пустая структура является деревом;
  •  дерево − это корень и несколько связанных с ним деревьев (поддеревьев).

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

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

Двоичное дерево можно определить рекурсивно, например, с помощью формы Бэкуса-Наура:

Двоичные деревья упорядочены, то есть различают левое и правое поддеревья. Примером двоичного дерева является генеалогическое дерево. В других случаях двоичные деревья используются тогда, когда на каждом этапе некоторого процесса надо принять одно решение из двух возможных.

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

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

  •  просмотр в ширину (сверху вниз), при котором сначала посещается корень (выводится информация о нем), затем левое поддерево, а затем – правое;
  •  просмотр в симметричном порядке (слева направо), при котором сначала посещается левое поддерево, затем корень, а затем – правое;
  •  просмотр снизу вверх, при котором сначала посещается левое поддерево, затем правое, а затем – корень.

Двоичное дерево, концевыми вершинами (листьями) которого являются операнды, а промежуточными вершинами – операции, называется двоичным деревом выражения. Уровень вершины соответствует приоритету выполнения операции: чем ближе к листьям, тем приоритет выше. Например, на рисунке 2 изображено двоичное дерево арифметического выражения .

Рисунок 2 – Двоичное дерево арифметического выражения

Подробное изложение материала по графам и деревьям можно найти в книгах Новикова10, Касьянова и Евстигнеева11, Алексеева и Таланова12.


2 ОБРАБОТКА АРИФМЕТИЧЕСКИХ выражениЙ

2.1 Грамматика языка арифметики

В программировании вычисление значения математической функции (выражения) является тривиальной задачей. Действительно, достаточно написать программу на языке программирования (Pascal, C++), которая вычисляет значение функции при заданных параметрах. Недостатком такого подхода является необходимость повторного компилирования программы  для вычисления значения другой функции, что для пользователя не имеющего исходных кодов программы будет невыполнимой задачей. Удобнее, если программа будет вычислять значение любой функции заданной пользователем.

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

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

Задача синтаксического анализа – проверить правильность записи выражения и разбить его на лексемы. Лексемой называется неделимая часть выражения, состоящая, в общем случае, из нескольких символов.

Для арифметических выражений лексемами будут:

  •  имена функций и переменных;
  •  константы;
  •  операции (+, -, *, /);
  •  открывающая (закрывающая) скобка.

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

В арифметических выражениях присутствуют два вида операторов: унарные и бинарные. В таблице 1 приведено описание бинарных и унарных операторов.

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

Таблица 1 – Описание арифметических операторов

Тип оператора

Описание

Унарные

sin, cos, tg, ctg, sh, ch, th, cth, arcsin, arccos, arctg, arcctg, abs, sgn, sign, sqrt, lg, ln, exp, -, +

Бинарные

+, -, *, /, ^

Далее приведено описание формальной грамматики, которая описывает язык арифметики.

Целевым (начальным) символом  является правило , которое приведено ниже при описании правил вывода.

Множество терминальных символов  содержит десятичные цифры, обозначения арифметических операторов и имена математических функций, необходимые для построения из них арифметических выражений. Очевидно, что каждый элемент множества  определяется единственным образом.

Множество нетерминальных символов содержит символы, которые определяют числа, переменные, функции и другие. Нетерминальные символы определяют некоторые подмножества языка . Например, правило определяет множество слов языка , описывающие положительные целые десятичные числа.

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

Распознаватель – это специальный автомат, позволяющий для некоторой цепочки символов определить, принадлежит ли она заданному языку13.

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

Рассмотрим правила, на основе которых строятся распознаватели цифр (), переменных () и имен функций ():

Очевидно, что распознаватели, построенные по выше приведенным правилам, будут представлять собой процедуры, состоящие из последовательностей условных операторов языка Object Pascal.

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

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

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

Правилам ,  и  соответствуют распознаватели  операций возведения в степень, умножения (деления) и сложения (вычитания).

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

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

2.2 Вычисления значения выражения, представленного в виде двоичного дерева

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

Дерево с одной вершиной. Дерево состоит из одного узла, который хранит либо константу, либо независимый аргумент функции. Такое дерево изображено на рисунке 4.

Рисунок 4 – Дерево, состоящее из одного узла

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

Дерево с бинарной операцией. Рассмотрим двоичное дерево выражения , изображенного на рисунке 5. Дерево представляет собой узел содержащий оператор умножения и два дочерних узла хранящих константы.

Рисунок 5 – Дерево, содержащее бинарную операцию

В данном случае берется константа  и умножается на константу , результат записывается в переменную-аккумулятор.

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

Рисунок 6 – Дерево, содержащее функцию

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

На основе выше изложенного, алгоритм вычисления значения выражения, представленного в виде дерева, можно сформулировать следующим образом:

  •  если корень дерева хранит константу или аргумент функции (дерево состоит из одного элемента), то значение этого корневого элемента и есть значение выражения (если корневой узел хранит аргумент функции, потребуется выполнить подстановку фактического значения аргумента);
  •  если корень дерева хранит вершину, соответствующую знаку бинарной операции, то требуется вычислить значения выражений, соответствующих левому и правому поддеревьям, а затем выполнить заданную бинарную операцию над полученными константами. Например, рассмотрим двоичное дерево выражения , изображенного на рисунке 7:

Рисунок 7 – Процесс вычисления значения выражения по дереву

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

2.3 Упрощение арифметического выражения заданного своим двоичным деревом

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

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

Рисунок 8 – Упрощение выражения заданного своим деревом

Двоичное дерево выражения строится один раз, затем множество раз  выполняется его обход различными процедурами (интерпретатор, оптимизатор). Например, для вычисления  значения функции  в различных точках (внутри цикла). Двоичное дерево выражения, расположенное справа от знака равенства, изображёно на рисунке 8 (слева). В этом дереве содержится выражение , которое не зависит от аргумента  и, следовательно, его можно вычислить до выполнения интерпретации. Таким образом, получается дерево, изображённое на рисунке 8 (справа). Очевидно, чем меньше дерево, тем быстрее происходит вычисление выражения в заданной точке, поэтому второе дерево является более предпочтительным для дальнейшей работы.

Упрощение выражений выполняет рекурсивная процедура по правилам, приведенным в таблице 2.

Таблица 2 – Правила упрощения выражений

До упрощения

После упрощения

0*T

0

T*0

0

1*T

T

T*1

T

0+T

T

T+0

T

T/1

T

T^1

T

0/T

0

T-T

0

T+T

2*T

T/T

1

2.4 Символьное дифференцирование выражения

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

Символьным дифференцированием называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной. Пусть  обозначает арифметическое выражение, содержащее переменную . Производная от  по  записывается в виде  и определяется рекурсивно с помощью некоторых правил преобразования, применяемых к . Символы  и  обозначают выражения, а  – константу. Ниже приведены   правила нахождения производных функций:

Также имеются таблицы, в которых изложено более подробное описание правил нахождения производных различных элементарных функций, о которых, например можно узнать в книгах Ильина, Позняка14 и Письменного15.

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

При выполнении алгоритма дифференцирования выражения заданного своим деревом возможны следующие варианты вершин:

  •  если вершина содержит оператор, то выполняем подстановку правил дифференцирования;
  •  если вершина содержит константу, то выполняем подстановку нуля
  •  если вершина содержит переменную, то выполняем подстановку единицы;
  •  если вершина содержит имя функции, то выполняем подстановку производной функции.

2.5 Программная реализация

Данная программа была разработана в среде программирования Delphi 7. Система программирования Delphi 7 фирмы Enterprise (Borland) предоставляет наиболее широкие возможности для программирования приложений для ОС Windows.

Delphi – это продукт для быстрого создания приложений объединяющий нескольких важнейших технологий:

  •  высокопроизводительный компилятор в машинный код;
  •  объектно-ориентированная модель компонент;
  •  визуальное (а, следовательно, более быстрое) построение приложений из программных прототипов;
  •  масштабируемые средства для построения баз данных.

Подробное изложение возможностей среды программирования Delphi изложены в книге Фленова16.

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

Рисунок 9 –  Процесс ввода данных в приложении

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

Рисунок 10 – Работа приложения


ЗАКЛЮЧЕНИЕ

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

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

  •  построение графика функции;
  •  нахождение аналитического  вида производной функции;
  •  выполнение поиска критических точек графика.

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

Данная программа была реализована на языке программирования Object Pascal среды программирования Delphi 7 и представляет собой исполняемый файл, не требующей установки.

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

Программа состоит из четырех основных модулей:

  •  синтаксический анализатор;
  •  дифференцирование функций;
  •  упрощение выражений;
  •  построение графиков функций.

К числу основных отличительных особенностей созданного программного продукта можно отнести следующее:

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

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


СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

  1.  Акритас, А. Основы компьютерной алгебры с приложениями / А. Акритас. – М.: Мир, 1994. – 544 с.
  2.  Алексеев, В.Е. Графы. Модели вычислений. Структуры данных: учебник / В.Е. Алексеев, В.А. Таланов. – Нижний Новгород: Издательство ННГУ, 2005. – 307 с.
  3.  Ахо, А. Компиляторы: принципы, технологии и инструментарий / А. Ахо, М. Лам, Р. Сети, Д. Ульман. – 2-е изд. М.: Вильямс, 2008. – 1184 c.
  4.  Волкова, И.А. Формальные грамматики и языки. Элементы теории трансляции: Учебное пособие для студентов II курса / И.А. Волкова, А.А. Вылиток, Т.В. Руденко. – 3-е изд. – М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2009. – 115 с.
  5.  Дэвенпорт, Дж. Компьютерная алгебра: Системы и алгоритмы алгебраических вычислений / Дж. Дэвенпорт, И. Сирэ, Э. Турнье. – М.: Мир, 1991. – 352 с.
  6.  Ильин, В.А. Основы математического анализа: Часть I: Учеб. для вузов / В.А. Ильин, Э.Г. Позняк.  – 7-е изд. – М.: ФИЗМАТЛИТ, 2005. – 648 с.
  7.  Карпов, Ю.Г. Теория и технология программирования. Основы построения трансляторов / Ю.Г. Карпов. – СПб.: БХВ-Петербург, 2005. – 272 с.
  8.  Касьянов, В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. – СПб.: БХВ-Петербург, 2003. – 1104 с.
  9.  Молчанов, А.Ю. Системное программное обеспечение: учебник для вузов / А.Ю. Молчанов. – СПб.: Питер, 2006. – 396 с.
  10.  Молчанов, А.Ю. Системное программное обеспечение. Лабораторный практикум / А.Ю. Молчанов. – СПб.: Питер, 2005. – 284 с.
  11.  Новиков, Ф.А. Дискретная математика для программистов: учебник для вузов / Ф.А. Новиков. – 3-е изд. – СПб.: Питер, 2008. – 384 с.
  12.  Панкратьев, Е.В. Элементы компьютерной алгебры / Е.В. Панкратьев. – М.: БИНОМ, 2007. – 243 с.
  13.  Письменный, Д.Т. Конспект лекций по высшей математике: Ч. 1 / Д.Т. Письменный. – 6-е изд. – М.: Айрис-пресс, 2006. – 288 с.
  14.  Свердлов, С.З. Языки программирования и методы трансляции / С.З. Свердлов. – СПб.: Питер, 2007. – 640 c.
  15.  Фленов, М.Е. Библия Delphi / М.Е. Фленов. –  3-е изд. – СПб.: БХВ-Петербург, 2011. – 882 с.

1 Акритас А. Основы компьютерной алгебры с приложениями. – М.: Мир, 1994. – 544 с.

2 Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра: Системы и алгоритмы алгебраических вычислений – М.: Мир, 1991. – 352 с.

3 Панкратьев Е.В. Элементы компьютерной алгебры. – М.: БИНОМ, 2007. – 243 с.

4 Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. – СПб.: Питер, 2006. – С. 14-21.

5 Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. – С. 31-34.

6 Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. – С. 21-27.

7 Там же. – С. 54.

8 Ахо А., Ульман Д. Компиляторы: принципы, технологии и инструментарий. – 2-е изд. – М.: Вильямс, 2008. – С. 29.

9 Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. – С. 67-70.

10 Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. – 3-е изд. – СПб.: Питер, 2008. – 384 с.

11 Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 с.

12 Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: учебник. – Нижний Новгород: Издательство ННГУ, 2005. – 307 с.

13 Молчанов А.Ю. Системное программное обеспечение: учебник для вузов. – С. 26-27.

14 Ильин В.А., Позняк Э.Г. Основы математического анализа: Часть I: Учеб. для вузов. – 7-е изд. – М.: ФИЗМАТЛИТ, 2005. – 648 с.

15 Письменный Д.Т. Конспект лекций по высшей математике: Ч. 1. – 6-е изд. – М.: Айрис-пресс, 2006. – 288 с.

16 Фленов М.Е. Библия Delphi. –  3-е изд. – СПб.: БХВ-Петербург, 2011. – 882 с.

  1.  

 

А также другие работы, которые могут Вас заинтересовать

49710. Разработка программы о доставке сырья на предприятие 623.5 KB
  Московский приборостроительный техникум государственного образовательного учреждения высшего профессионального образования Российский государственный торгово-экономический университет Курсовой проект По дисциплине Математические методы Специальность 230105 Программное обеспечение вычислительной техники и автоматизированных систем Тема: Разработка программы о доставке сырья на предприятие МПТ РГТЭУ. Схемы пользовательского интерфейса...
49714. Общественные отношения по организации и деятельности судебной власти 389 KB
  Общие и хозяйственные суды в Республике Беларусь призваны защищать гарантированные Конституцией и иными актами законодательства личные права и свободы, социально-экономические и политические права граждан
49715. О вреде курения – языком математики. Проценты. Решение задач 134.5 KB
  Решение задач в 6м классе. Проблема: Жить или курить Выбирайте сами Форма проведения: урок проблема Решение проблемного вопроса Курить или быть здоровым при помощи решения задач в ходе обсуждения на внеклассном мероприятии с использованием ИКТ. Решение задач Предмет: математика Учитель: Короткова Наталья Александровна. Решение задач.
49718. Визначення домінуючого типу психологічного впливу в соціальній рекламі проти ВІЛ/СНІДу для шкільної молоді 417 KB
  Психологічні особливості сприймання соціальної реклами проти ВІЛ СНІДу студентською молоддю. Методичне забезпечення18 Стимульний матеріал відеоролики соціальної реклами проти СНІДу. Сучасний світ неможливо уявити без реклами яка на сьогодні пронизує всі сфери життя людини. Отже інформація як ніколи стала інструментом влади а реклама не просто елементом бізнесу маркетингу та лобіювання інтересів певного товаровиробника замовника реклами а і своєрідним культурним простором.