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

СИБИРСКАЯ ГОСУДАРСТВЕННАЯ ГЕОДЕЗИЧЕСКАЯ АКАДЕМИЯ

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО, АЛГОРИТМИЧЕСКОГО И

ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ КОМПЬЮТЕРНОЙ ТЕХНОЛОГИЧЕСКОЙ СИСТЕМЫ ОБРАБОТКИ НАБЛЮДЕНИЙ НАЗЕМНЫХ ГЕОДЕЗИЧЕСКИХ СЕТЕЙ

05.24.01 "Геодезия" Диссертация

на соискание ученой степени доктора технических наук

УДК 528.1,528.33,528.73

На правах рукописи

Нгуен Данг Ви

\

Научный консультант доктор технических наук, £<2^—профессор Панкрушин В.К.

СОДЕРЖАНИЕ

Стр.

Введение.......................................................................................................... 5

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

1.1 Состояние применения ЭВМ для математической обработки измерений в наземных геодезических сетях................................................. 16

1.2 Задачи создания алгоритмического обеспечения компьютерной технологической системы математической обработки измерений в наземных геодезических сетях.................................................................. 24

1.3 Концепция аппаратного и системного программного обеспечения компьютерной технологической системы математической обработки геодезических измерений.................................................................. 32

1.4 Выводы...................................................................................................... 38

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

2.1 Общие положения о поиске элементов геодезических данных в процессе их редактирования, накопления и математической обработки. 41

2.2 Анализ известных алгоритмов поиска элементов данных................. 43

2.3 Разработка структуры хранения бинарных отношений при решении задач математической обработки геодезических измерений............. 51

2.4 Разработка физической модели хранения данных геодезических сетей .................................................................................. 62

2.5 Выводы..................................................................................................... 67

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

3.1 Концепция решения задачи автоматизации процесса распознавания геометрических условий в геодезических сетях................................. 70

3.2 Алгоритм нахождения кратчайшей цепи между двумя вершинами графа......................................................................................................... 73

3.3 Алгоритм нахождения кратчайшей цепи между заданной вершиной

и подмножеством вершин графа........................................................... 82

3.4 Алгоритм нахождения кратчайшей цепи между подмножествами вершин графа........................................................................................... 83

3.5 Базовая система цепей между подмножествами вершин в связном графе и алгоритм ее нахождения........................................................... 85

3.6 Алгоритм нахождения базовой системы цепей между подмножествами вершин в несвязном графе............................................................ 89

3.7 Алгоритм нахождения в графе проходящего через заданное ребро цикла с наименьшей длиной.................................................................. 95

3.8 Алгоритм нахождения циклового базиса графа.................................. 100

3.9. Выводы.................................................................................................... 108

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

4.1 Общие положения разработки способов формирования графов 111 геодезических сетей......................................................................................

4.2 Формирование графов нивелирных сетей............................................ 112

4.3 Формирование графов полигонометрических сетей........................... 113

4.4 Формирование графов сетей треугольников........................................ 115

4.5 Методика локализации грубых ошибок измеренных и исходных данных с применением логических операторов.................................. 131

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

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

4.8 Выводы..................................................................................................... 161

5 Исследование и усовершенствование способов хранения системы линейных уравнений на ЭВМ при решении уравнительных задач............. 164

5.1 Общие принципы.................................................................................... 164

5.2 Анализ способов упаковки разреженной матрицы ............................. 167

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

5.4 Упаковка матрицы системы уравнений поправок.............................. 200

5.5 Упаковка ступенчатой формы ленточной матрицы с окаймляющими столбцами системы нормальных уравнений....................................... 203

5.6 Использование технологии виртуальной памяти и защищенного режима 32-битовых процессоров ПЭВМ для математической обработки геодезических сетей большой размерности................................... 211

5.7 Выводы..................................................................................................... 220

6 Программное обеспечение компьютерной технологической системы математической обработки измерений в наземных геодезических сетях VISAGN......................................................................................................... 223

6.1 Основные характеристики системы VISAGN..................................... 223

6.2 Функционально-технологическое строение системы VISAGN........ 229

6.3 Тестирование, апробация, реализация и направления развития системы VISAGN......................................................................................... 238

6.4 Выводы..................................................................................................... 246

Заключение..................................................................................................... 248

Список использованных источников......................................................... 253

Приложение А Акты внедрения системы VISAGN в производство..... 273

ВВЕДЕНИЕ

Актуальность

История развития математической обработки геодезических измерений связана с именами таких великих ученых, как Ф. Гаусс, Ф. Гельмерт, J1. Крю-гер, Лежандр и с именами видных ученых геодезистов таких, как В.Д. Большаков, П.А. Гайдаев, В.И. Ганынин, В.Г. Зданович, A.A. Изотов, Ф.Н. Кра-совский, А.И. Мазмишвили, В.В. Попов, И.Ю. Пранис-Праневич, K.JI. Про-воров, H.A. Урмаев, A.C. Чеботарев и других. Сегодня эта отрасль науки получает дальнейшее развитие в работах таких видных ученых геодезистов, как И.Т. Антипов, В.А. Беляев, В.А. Бывшев, В.А. Вагин, А.А Визгин, М.Д. Герасименко, В.В. Голубев, A.B. Гордеев, Н.Д. Дроздов, Г.Н. Ефимов, И.Г. Жур-кин, В.А. Капустин, Ю.Б. Кемниц, С.Ф. Коробков, В.А. Коугия, Н.В. Лебедев, Ю.И. Маркузе, С.И. Матвеев, М.М. Машимов, Ю.М. Нейман, В.И. Мицкевич, И.В. Рабинович, А.З. Сазонов, М.С. Урмаев, З.С. Хаимов, З.М. Юр-шанский, W. Baarda, В. Benciolini, F. Crossila, G. Mamzoni, G. Forlani, J.A. George, L. Grundig, B. Heck, К. Kostadinov, Ngo Phuc Hung, Dang Hung Vo, Phan Van Hien, W. Stark, William F. Teskey и многих других.

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

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

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

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

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

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

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

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

Для достижения поставленной цели решались следующие задачи.

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

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

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

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

3) Разработка экспертной системы оценки качества и локализации грубых ошибок геодезических данных на основе:

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

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

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

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

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

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

5) Разработка программного обеспечения для создания компьютерной технологии математической обработки измерений в наземных геодезических сетях на базе ПЭВМ типа IBM PC.

Объект исследований

Объектом исследований является компьютерная информационная технология обработки измерений в наземных геодезических сетях на базе современных ПЭВМ.

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

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

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

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

Инструментальной компьютерно-технической базой для выполнения работы служили ЭВМ ЕС 1022, IBM PC разных поколений, различные языки программирования, основными из которых являются FORTRAN-4, FORTRAN-77, FORTRAN-90, C/C++, ASSEMBLER и их компиляторы.

Исследования проведены в соответствии с направлениями НИР в следующих научно-исследовательских, учебных и производственных организациях: Институт сельского проектирования и землеустройства Вьетнама; Межотраслевая научно-исследовательская лаборатория автоматизации технологии геодезических работ НИЧ Ташкентского Политехнического института; МОСГОРГЕОТРЕСТ; лаборатория инженерной геодинамики Новосибирской государственной академии строительства; Сибирская государственная геодезическая академия. Материалами экспериментальных исследований служили результаты работ, выполненных на производственных геодезических объектах Института сельского проектирования и землеустройства Вьетнама, научно-исследовательского центра ГУГКа Вьетнама, CAB ВНИИПИ Промтехнология, УзГИИТИ, СредазГидропроекта, Геодезического Маркшейдерского предприятия «АЗИМУТ РУМБ» УС Ташметрост-роя, МОСГОРГЕОТРЕСТ, МосНИиПИИ Землеустройства.

Достоверность результатов исследований и разработок подтверждена экспериментально.

Научная новизна диссертационной работы

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

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

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

- концепция решения задачи автоматизации процесса распознавания геометрических условий в геодезических сетях;

- система эффективных алгоритмов для распознавания геометриче-

и 1

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

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

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

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

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

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