ЗАДАНИЕ 10. ПОЛУЧЕНИЕ ОБРАТНОЙ ПОЛЬСКОЙ ЗАПИСИ

Цель работы: изучить алгоритмы формирования и просмотра динамической структуры данных – «обратная польская запись» или «ПОЛИЗ». Научиться программировать различные действия  с данным видом динамических структур данных. 

Краткие теоретические сведения

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

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

Краткие теоретические сведения

Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X→Y вершина X называется предком (родителем), а Y - потомком (сыном).

Дерево имеет единственный узел, у которого нет предков. Такой узел называют корнем. Любой другой узел имеет ровно одного предка. Узел, не имеющий потомков, называется листом.

Внутренний узел – это узел, не являющийся ни листом ни корнем. Порядок узла –– максимальный порядок его узлов. Глубина узла равна числу его предков плюс один. Глубина дерева – это наибольшая глубина его узлов. количество его узлов-потомков. Степень дерева

Графически такую структуру можно изобразить следующим образом

ЗАДАНИЕ 8. Программирование с отображением графической информации

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

Краткие теоретические сведения

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

       Построение графика (диаграммы) производится после вычисления таблицы значений функции y=f(x). Полученная таблица с помощью метода AddXY передается в специальный двумерный массив Charti.Series[k] компонента TСhart (k – номер графика (0,1,2,...)). Компонент TChart осуществляет всю работу по отображению графиков: строит и размечает оси, рисует координатную сетку, подписывает название осей и самого графика, отображает переданную таблицу в виде всевозможных графиков или диаграмм.

ЗАДАНИЕ 7. СОРТИРОВКА ДАННЫХ И ПОИСК

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

Краткие теоретические сведения

Сортировка (упорядочение) - это процесс перегруппировки (перераспределения) заданного множества объектов в некотором определенном порядке. Основная цель сортировки - облегчить поиск заданных элементов в таком упорядоченном множестве.

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

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

Обычно сортировку подразделяют на два класса: внутреннюю, когда все объекты хранятся в оперативной памяти, и внешнюю, когда они там все не помещаются. Мы рассмотрим только внутреннюю сортировку.

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

а) сортировка выбором;

б) сортировка обменами;

в) сортировка включениями (вставками).

Рассмотрим основные алгоритмы сортировки на примере целочисленного массива.

ЗАДАНИЕ 6. АЛГОРИТМЫ ЧИСЛЕННОГО ИНТЕГРИРОВАНИЯ

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

Краткие теоретические сведения

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

Постановка задачи:

Найти определенный интеграл, где f(x) – некоторая заданная на отрезке [a,b] непрерывная функция.

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

.                                                                        (6.1)

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

ЗАДАНИЕ 5. АППРОКСИМАЦИЯ ФУНКЦИЙ

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

Краткие теоретические сведения

Нахождение функции y=φ(x), близкой (т.е. аппроксимирующей)  к некоторой исходной функции y=f(x)является одной из основных задач теории аппроксимации функций.

       Интерполяция является одним из способов аппроксимации функций. Суть ее состоит в следующем. В области значений x, представляющей некоторый интервал [a, b], где функции f и φ должны быть близки, выбирают упорядоченную систему точек (узлов). (обозначим их как вектор ), число которых равно количеству искомых параметров . Далее, параметры вектора подбирают такими, чтобы функция совпадала с f(x) в этих узлах, (5.1)

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

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

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

Пусть f(x) – функция, непрерывная на отрезке [a,b].

Выберем на этом отрезке  узлы интерполяции:

.

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

.                                                                        (5.2)

Ставится задача: найти  алгебраический многочлен Pn-1(x) такой, что

ЗАДАНИЕ 4. ЧИСЛЕННОЕ РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

Краткие теоретические сведения

       Математической моделью многих физических процессов является функциональная зависимость y=f(x). Поэтому задачи исследования различных свойств функции f(x) часто возникают в инженерных расчетах. Одной из таких задач является нахождение значений x, при которых функция f(x) обращается в ноль:

                       f(x*)=0.                                                                (4.1)

т.е. решение уравнения заключается в поиске его корней на указанном участке [a, b], которые превращают его в нуль.

Обычно для нахождения корней уравнения применяются численные методы.

Решение уравнения (1.1) при этом осуществляется в два этапа:

1. Приближенное определение местоположения – этап отделения корней (нахождение грубых корней).

2. Вычисление выбранного корня с заданной точностью ε. Это, как правило, итерационные методы.

       Первая задача чаще всего решается графическим методом: на заданном отрезке [a, b] вычисляется таблица значений функции с некоторым шагом h, строится ее график и определяют интервалы - в дальнейшем [a, b] длиной h, на которых находятся корни по следующему условию:

- если функция (x) непрерывна на отрезке и то на отрезке существует хотя бы один корень уравнения ).

На втором этапе вычисление значения корня с заданной точностью осуществляется одним из итерационных методов. При этом, в соответствии с общей методологией m-шагового итерационного метода, на интервале (α,β), где находится интересующий нас корень x*, выбирается m начальных значений x0, x1, …, xm-1 , после чего последовательно находятся члены (xm, xm+1, ..., xn-, xn) рекуррентной последовательности порядка m по правилу до тех пор, пока не выполнится неравенство . Последнее xn выбирается в качестве приближенного значения корня (x* ≈ xn).