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

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

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

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

 

ПОШУК:   

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

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

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

 

Застосування у статистиці

 

Означення. Відрізок, що сполучає дві найбільш віддалені точки множини

S, називається діаметром множини S.

 

Задача. Діаметр множини. На площині задано N точок. Знайти дві найбільш

віддалені одна від іншої точки.

 

Найпростіший розв’язок задачі – перебрати всі відстані між точками та

знайти максимальну із них. Такий розв’язок має часову оцінку O(N2).

 

Задача. Роздільність множин. Дано дві множини дійсних невід’ємних чисел

A = {a1, a2, ..., aN} та B = {b1, b2, ..., bN}. Встановити, чи не

містять множини А та В однакових елементів.

 

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

 

Доведення. Відобразимо множини А та В на одиничне коло С, при цьому

елементи множини А відобразимо в перший квадрант, а елементи множини В –

в третій. Відображення відбувається так: ai відображається в точку

перетину кола С з прямою y = aix , що знаходиться в першому квадранті, а

bi відображається аналогічним чином в третій квадрант. Позначимо через S

множину, яка містить 2 * N побудованих точок перетину.

 

Множина S має діаметр 2 тоді і тільки тоді, коли вона містить дві

діаметрально протилежні точки кола С, тобто коли A ? B ? ?.

 

Теорема. Нехай uv – діаметр множини S. Нехай lu та lv – дві прямі,

перпендикулярні відрізку uv, причому lu проходить через точку u, а lv –

через точку v. Тоді точки множини S містяться у смузі, яка визначається

прямими lu та lv.

 

Доведення. Припустимо, що відрізок uv горизонтальний, точка u

розташована зліва, v – справа. Побудуємо коло С з центром в точці u та

радіусом uv. Пряма lv буде дотичною до кола С, оскільки lv

перпендикулярна uv за умовою. Коло С лежить повністю зліва від прямої

lv. Оскільки v – найбільш віддалена точка від u, то всі точки множини S

лежать всередині кола С, а отже зліва від прямої lv. Аналогічно

доводиться, що усі точки множини S лежать справа від прямої lu, що і

доводить теорему.

 

Наслідок. Нехай uv – діаметр множини S. Тоді точки u та v належать

опуклій оболонці.

 

Доведення. Відомо, що точка p належить опуклій оболонці, якщо існує

пряма, що проходить через p, а всі точки множини S лежать по одну

сторону від цієї прямої. Такими прямими будуть lu та lv.

 

Теорема. Діаметр множини дорвнює діаметру його опуклої оболонки.

 

В двовимірному випадку опуклою оболонкою множини точок є опуклий

многокутник.

 

Diam (S) = Diam (CH (S))

 

Задача. Діаметр опуклого многокутника. Дано опуклий многокутник. Знайти

його діаметр.

 

Теорема. Діаметр опуклої фігури дорівнює найбільшій із відстаней між

двома паралельними опорними прямими до цій фігури.

 

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

жодні дві опорні прямі, які проходять через точки p4 та p6, не є

паралельними. Це означає, що відрізок p4p6 не є діаметром.

 

Означення. Пара точок, через які можна провести паралельні опорні

прямі, називається протилежною парою.

 

Дослідимо, як визначити всі протилежні пари, не перебираючі всі можливі

пари точок. Будемо рухатися від точки pi по границі многокутника P проти

-----> Page:

0 [1]

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