Методичні вказівки та завдання до виконання контрольних робіт з курсу “Геоінформаційні системи і бази даних” для студентів спеціальності 6.070904 “Землевпорядкування та кадастр” заочної форми навчання

5. Шайтура С.В. Геоинформационные системы и методы их создания. – Калуга: издательство Н. Бочкаревой, 1998. – 252с.

6. Бугаевский Л.М., Цветков В.Я. Геоинформационные системы: Учебное пособие для вузов. – М.:Златоуст, 2000. – 222с.

7. Керівництво користувача системою MAPINFO.

8. Методичні вказівки до виконання лабораторних робіт з курсу „Основи геоінформаційних систем та технологій” для студентів спеціальностей 7.070904 та 8.070904 „Землевпорядкування та кадастр” і 7.070908 „Геоінформаційні системи і технології” стаціонарної та заочної форм навчання. Частини 1 і 2. – Рівне 2004р. (шифри 076-74, 076-75).

9. Мережа INTERNET.

 

Геоінформаційні системи (ГІС) широко використовуються в різноманітних галузях науки, управління і господарства, у тому числі і для вирішення задач управління природними ресурсами. Ефективність використання геоінформаційних технологій досягається поєднанням картографічних можливостей таких систем з відомостями, які розміщені в базах даних, можливостями виконання оперативного аналізу. Різнопланова інформація представляється у вигляді окремих шарів, а їхній спільний аналіз у різних комбінаціях дозволяє одержувати додаткову інформацію у вигляді похідних шарів, з їх картографічним відображенням (у вигляді тематичних карт, сполучених карт різних показників і т.п.).

На ринку програмних продуктів пропонуються різні ГІС, що відрізняються за функціональними можливостями.

Вивчення курсу „Геоінформаційні системи і бази даних” на сьогоднішній день є важливою складовою базової підготовки бакалавра напрямку „Геодезія, картографія та землевпорядкування”. Завданням курсу є вивчення основних положень і знань щодо сучасного розвитку, закономірностей побудови і функціонування інформаційних систем в цілому, і інформаційних систем, пов'язаних з просторовим розміщенням об'єктів, в частковому випадку.

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

Блок аналізу мереж, як правило, входить в більшість програмних засобів ГІС. Однією з найважливіших задач цього класу є задача визначення оптимального маршруту. Відшукання найкоротшого шляху в мережі за алгоритмом Дейкстри дає можливість студенту „зазирнути” в математичний апарат типової геоінформаційної системи і повторити всі ті кроки з розв'язання задачі, які виконувала б ЕОМ.

Засоби тематичного картографування дозволяють користувачу проаналізувати та оцінити просторове розташування того чи іншого суспільного явища. В процесі розробки студентом завдання створюється тематична карта. Ця карта повинна служити підставою для прийняття певних управлінських рішень з охорони та раціонального використання земельних ресурсів.

 

Нехай задана мережа вершин, з'єднаних між собою ребрами. Необхідно знайти найкоротші шляхи від вершини Vi до всіх інших Vk. Введемо позначення Dik – матриця відстаней.

Алгоритм розв'язування задачі складається з одночасного опрацювання трьох масивів даних. Якщо вважати, що кількість вершин дорівнює n, то розмірність масивів теж буде n.

Масив 1: а(n) може містити в кожній з позицій від 1 до n лише два варіанти значення “0”- вершина не розглядалась і “1” – розглядалася.

Масив 2: b(n) – масив відстаней – поточні найкоротші відстані від вершини і до іншої вершини k.

Масив 3: с(n) – масив містить номери вершин, які є передостанніми вершинами маршруту.

Матриця Dik задає довжини ребер. Якщо ж в мережі вершини і та k не з'єднані між собою, то за відстань між цими вершинами приймається значення машинної нескінченності - так зване значення М. При цьому М завжди буде більшим за будь-яке числове значення, але М+1>М.

Алгоритм.

Алгоритм знаходження найкоротших шляхів у мережі вперше був описаний Дейкстрою (1959). Він має вигляд:

1. “Ініціалізація” – заповнюємо нулями масив а; заповнюємо числом і

масив с; масив b заповнюємо і-тим рядком матриці відстаней D.

2. Загальний крок – знаходимо мінімальне значення в масиві b, яке також

є непоміченим в масиві а.

Нехай цей мінімум досягається на індексі масиву j, тобто:

b[j]:=min b[i…n] і a[j]=0.

Далі виконуємо наступні операції:

a[j]:=1.

Якщо b[k]> b[j]+d[jk], то b[k]:= b[j]+d[jk] та с[k]:=j;

в іншому випадку залишаємо b[k] без змін.

Умова b[k]> b[j]+d[jk] означає, що ми знайшли новий коротший шлях від

Vi до Vk через Vj.

Якщо всі елементи масиву а набули значень “1”, то розв'язування задачі

закінчено і найменше значення відстані від точки Vi до Vk треба шукати в

масиві b на k –му місці.

3. Найкоротші маршрути від вершини Vi до всіх інших Vk отримуємо за

такою процедурою:

z:=c[k];

z:=c[z]. Якщо z=0, то закінчуємо розрахунок.

Приклад: Нехай мережа має вигляд, зображений на рис.1. Необхідно

знайти найкоротші шляхи від вершини 2 до інших вершин. Тобто в цьому

випадку і=2.

1 3

5

7

2

12 25

20

35

26

10

16

22

14

24

28

23

18

6

9

4 8

Рис.1. Приклад мережі

9

Для приведеної мережі можна скласти наступну матрицю відстаней D.

V

1

2