Программирование математических объектов

14

ВСТУПЛЕНИЕ

Каждый материальный объект, имеющий форму, является объемным, следовательно, его положение в пространстве можно задать с помощью трёх координат X, Y, Z. Результат любого материального производства, дома, автомобили, станки, можно представить как 3-х мерную модель и отобразить эту модель на дисплее компьютера с помощью соответствующей программы.

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

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

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

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

1. Математические объекты

1.1 Группы

Группа - оперативное множество, в котором действует процедура умножения и которое подчинено следующим условиям:

замкнутости: для каждой пары g1g2=g3, причем g3 должен принадлежать группе G: g1g2 G; g1g2 = g3 G;

наличия тождественного элемента e: среди множества элементов группы G справедливы равенство eg = g; ge = g; e,g G;

наличие обратных элементов: для всякого g из G должен отыскаться единственный ему обратный элемент g, принадлежащий G, при умножении на который получился тождественный элемент e. e = qq; e,g,g G;

ассоциативности: для любых трёх элементов g1, g2, g3 из G справедливо равенство: g1(g2g3) = (g1g2)g3. Условия ассоциативности выполняется для квадратных матриц.

Линейное преобразование A вектора x в вектор c осуществляется с помощью квадратной матрицы y = Ax.

Если есть прямое преобразование, то должно быть и обратное, при условии, что A имеет A. y = Ax;

x = Tx ;y = Tx ; Следовательно Ty = ATx; Умножим с лева на T , получим y = TATx;

Отсюда следует формула прямого преобразования подобия.

14

Формулу обратного преобразования подобия можно получить, умножив на T с права:

14

Если Ax = x; то ненулевой вектор x является собственным вектором. Для нахождения собственных векторов используют формулу

14

*

где E - единичная матрица.

Корни многочлена P() = det(A - E) = 0 подставляют в формулу (*) и получают собственные векторы x.

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

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

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

Вот как эта матрица будет выглядеть:

1.2 Графы

Любое объемное тело, как уже было сказано выше, можно построить с помощью треугольных граней, каждая из которых имеет хотя бы одну общую вершину с соседней гранью. Схематично каждую грань можно изобразить как совокупность вершин, соединенную контурными линиями. Контурные линии - это линии описывающие контур. Контур - это замкнутый путь. Таким образом, грань, содержащая вершины упорядоченно соединённые рёбрами представляет собой ориентированный граф или Орграф.

Граф G как математический объект - это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет собой неупорядоченные (для ориентированного графа - упорядоченные) пары элементов из множества V.

G (V,E) = V; E, n(V) > 0, E V V,

где для неориентированного графа E = E-1 (бинарное отношение E симметрично).

Минимальный граф состоит из одной вершины.

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

Пусть v1 и v2 - вершины, e1 = (v1 , v2 ) - соединяющее их ребро.

Тогда вершина v1 и ребро e1 инцидентны, вершина v2 и ребро e1 также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

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

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

1 Отношение инцидентности задано матрицей смежности:

- столбцы и строки матрицы - вершины графа;

- для смежных вершин элемент матрицы равен1, для остальных - 0;

- для неориентированного графа эта матрица всегда симметрична;

число рёбер равно числу единиц выше или ниже главной диагонали матрицы ( включая элементы на диагонали).

2 Отношение инцидентности задано матрицей инцидентности:

- столбцы матрицы соответствуют вершинам графа, а строки - рёбрам;

- если ребро ei инцидентно вершине vj, то элемент матрицы ij=1, в противном случае - ij = 0.

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

Для ориентированного графа при заполнении матрицы:

ij = -1,если vj - начало ребра;

ij =1,если vj -конец ребра;

ij = (где - любое число, кроме -1,1,0),если ребро - петля в вершине vj;

в остальных случаях ij = 0.

3 Граф задан списком ребер.

Примечание. Здесь ei -ребро, vi, vj - пара вершин, соединяемых этим ребром.

Граф связан, если любая пара его вершин связана ребром.

Граф без кратных ребер называют полным, если каждая пара вершин соединена ребром.

Граф H называют частью графа G, если множество вершин графа H принадлежит множеству вершин графа G и множество рёбер графа H принадлежит множеству рёбер графа G, т.е.:

V(H) V(G); E(H) E(G).

Часть графа H называется суграфом, если она содержит все вершины графа G.

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

Подграф G(U) графа G на множестве вершин U ( U V ) - это часть графа, которой принадлежат все ребра с обоими концами из U.

Звёздный граф для вершины v (v G) состоит из всех рёбер с началом и концом в вершине v. Множество вершин звёздного графа состоит из вершины v и других смежных с ней вершин.

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

Вершина vо, инцидентная ребру e1 и не инцидентная ребру e2, называется началом маршрута в графе G.

Вершина vn, инцидентная ребру en и не инцидентная ребру en-1, называется концом маршрута.

Число ребер маршрута называется его длиной.

Если вершины vо и vn совпадают, то маршрут называется циклическим (или просто циклом).

Отрезок конечного или бесконечного маршрута сам является маршрутом.

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

Другими словами, в цепи ребро может встретиться не более одного раза, а в простой цепи вершина - не более одного раза.

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

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

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

В частном случае расстояние и протяженность между вершинами могут быть одинаковыми.

2. Справка по работе с программой

2.1 Назначение программного продукта

Данный программный продукт предназначен для построения любых объемных фигур с последующей их демонстрацией на экране монитора. Следует отметить, что фигуры могут быть как выпуклыми, так и вогнутыми, но обязательно не должно нарушаться условие целостности. Это значит, что ни одна часть объекта не должна существовать отдельно, а должна быть хоть каким-нибудь своим элементом присоедененной к объекту. То есть два множества: вершин и рёбер, которые получаются, если пройти по контуру, от первой вершины к последней, представляют собой, согласно определению, ориентированный граф и имеют маршрут. Созданный объект можно сохранить на диске, а также загрузить с него, чтобы посмотреть или отредактировать результат работы. Для построения трехмерных объектов можно использовать некоторые доступные примитивы, а именно грань и куб. Каждая грань, в создаваемом объекте, имеет свой цвет, выбираемый программой случайным образом.

Страницы: 1, 2, 3, 4, 5