UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 12

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваБлизькість (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1057
Скачало245
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Близькість

 

Задача. Найближча пара. На площині задано N точок. Знайти дві з них,

відстань між якими найменша.

 

В одномірному випадку можна впорядкувати координати точок за час O(N *

log N) а потім за лінійний час проглянути точки x1, x2, ..., xN

обчислюючи значення xi+1 - xi, i = 1, ..., N-1.

 

Означення. Точа b є найближчим сусідом точки a множини S (позначається a

??b), якщо

 

dist(a, b) = min dist(a, c), c ??S / a.

 

Відношення найближчий сусід на множині точок

 

Задача. Єдиність елементів. Дано N дійсних чисел. Чи є серед них два

рівних числа?

 

Теорема. Задача єдиність елементів лінійно зводиться до задачі найближча

пара.

 

Доведення. Дано множину дійсних чисел {x1, x2, ..., xN}. Розглядаємо їх

як точки на прямій y = 0 та намагаємося знайти найближчу пару точок.

Якщо відстань між найближчою парою точок не дорівнює нулю, то усі числа

різні.

 

Задача. Найближчі сусіди. На площині задано N точок. Знайти найближчого

сусіда для кожної точки множини.

 

Задача. Евклідове мінімальне остове дерево (ЕМОД). На площині задано N

точок. Побудувати дерево, вершинами якого є всі задані точки і сумарна

довжина всіх ребер якого мінімальна.

 

Теорема. Задача сортування за лінійний час зводиться до задачі ЕМОД.

 

Доведення. Розглянемо кожне число xi множини {x1, x2, ..., xN} як точку

(xi, 0) на площині та будуємо ЕМОД. В побудованому дереві вершини, які

відповідають числам xi та xj, сполучені ребром тоді і тільки тоді, коли

утворюють пару послідовних чисел у впорядкованій множині. Розв’язком

задачі ЕМОД є список з N - 1 пар (i, j), кожна з яких визначає ребро

дерева. Цей список можна впорядкувати за лінійний час.

 

Задача. Триангуляція. На площині задано N точок. Сполучити їх

неперетинаючими відрізками так, щоб кожна область всередині опуклої

оболонки цієї множини точок була трикутником.

 

Теорема. Задача сортування за лінійний час зводиться до задачі

триангуляції.

 

Доведення. Розташуємо N-1 точку з множини {x1, x2, ..., xN} на одній

прямій, а одну точку не на прямій. Триангуляція множини точок може бути

проведена єдиним чином:

 

Список ребер, що породжується алгоритмом триангуляції, можна використати

для отримання впорядкованого списку чисел xi за час O(N)

 

Найближча пара

 

Одномірний випадок. Алгоритм розділяй та пануй.

 

Припустимо, що точка m розбиває множину S на дві підмножини S1 та S2,

при чому p < q для всіх p ??S1 та q ??S2. Рекурсивним чином розв’язуємо

задачу про найближчу пару для множин S1 та S2 і отримаємо дві пари точок

{p1, p2} та {q1, q2}, які представляють найближчі пари для S1 та S2

відповідно. Позначимо через ??найменшу відстань, знайдену на поточний

момент: ??= min( |p2 - p1|, |q2 - q1|). Найближчою парою у множині S

буде або {p1, p2}, або {q1, q2}, або {p3, q3}, де p3 – права точка

множини S1, а q3 – ліва точка множини S2 (це випливає з того, що точки

p3 та q3 повинні знаходитися на відстані, яка не перевищує ? від точки

m).

 

Blpara (S, Begin, End)

 

if Begin = End then return MAXINT;

 

if (Begin - End) = 1 then return S[End] - S[Begin];

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ