85986 (Знаходження кусково-постійних конфігурацій множин)

Курсова робота

на тему

"Знаходження кусково-постійних конфігурацій множин"

Анотація

У цій роботі були розглянуті основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля. Також була розв’язана задача з цих тем засобами мови програмування С++ та IDE C++ Builder. Це дозволило значно покращити мої знання з профільних дисциплін та підготувати гарного спеціаліста для держави.

Зміст

Вступ

Основна частина

1. Частково впорядкована множина

1.1 Аксіоми частково впорядкованої множини

1.2 Приклади

2. Комбінаторика

2.1 Теорія конфігурацій і теорія перерахування

2.1.1 Правило суми

2.1.2 Правило добутку

2.2 Блок-схеми

Висновок

Список використаних джерел

Додаток (постановка задачі, код програми, приклад)

Вступ

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

В даний час найпоширенішою аксіоматичною теорією множин є ZFC — теорія Цермело-Френкеля з аксіомою вибору. Питання про несуперечність цієї теорії (а тим більше — про існування моделі для неї) залишається нерозв'язаним.

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

1. Частково впорядкована множина

Частково впорядкованою множиною називається пара яка складається з множини разом із рефлексивним,антисиметричним і транзитивним бінарним відношенням (його називають відношення часткового порядку).

Таким чином, за допомогою відношення ми маємо змогу "порівнювати" елементи P. Взагалі, на відміну від натуральних або дійсних чисел із звичайним відношенням порядку, у довільній впорядкованій множині можуть існувати елементи, які неможливо порівняти. Якщо для будь-якої пари елементів a, b впроваджується або то така називается лінійно впорядкованою множиною.

1.1 Аксіоми частково впорядкованої множини

1. (рефлексивність)

2. з і випливає a = b (антисиметричність)

3. з і випливає з (транзитивність)

Для будь-якої частково (відповідно, лінійно) впорядкованої множини довільна підмножина природним чином перетворюється на частково (відповідно, лінійно) впорядковану множину . При цьому у тоді і тільки тоді, коли це справджується у Р.

1.2 Приклади

1. Множина R дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною. Це — надзвичайно важлива властивість дійсних чисел. Виявляється, що існування відношення порядку сумісного з арифметичними операціями і задовільняючого певним додатковим вимогам може буде застосовано для визначення (або характерізації) поля дійсних чисел.

2. Натуральні числа, цілі числа, раціональні числа, ірраціональні числа, додатні дійсні числа тощо всі є підмножинами дійсних чисел, тому утворюють лінійно впорядковані множини зі звичайним відношенням порядку.

3. На множині натуральних чисел N визначимо відношення порядку за подільністю, тобто тоді і тільки тоді, коли a є дільником b. Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо a є дільником b, а b є дільником c, то a є дільником c. Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.

4. Ланцюг з n елементів — це лінійно впорядкована множина з n елементів. У комбінаториці ланцюг, який складається з , позначається [n] або n.

5. Будь-яка множина A перетворюється на частково впорядковану множину, якщо визначити на неї таке відношення порядку: . У цьому разі можна порівняти два елементи A лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

6. Нехай A — це довільна множина, а Ω(A) — це множина, елементами якої є всі підмножини . Визначимо на Ω(A) частковий порядок за вмістком, тобто означає, що де B, C — дві підмножини в A. Тоді Ω(A) перетворюється на частково впорядковану множину з найменшим елементом порожньою множиною та найбільшим елементом A.

2. Комбінаторика

Комбінаторика є однією з найдавніших й, можливо, ключовою галуззю математики. Усякому аналізу передує комбінаторний розгляд, усяка серйозна теорія має комбінаторний аналог.

Комбінаторика має у своєму розпорядженні настільки різноманітні методи, вирішує настільки різноманітні завдання, що важко чітко позначити її границі. Умовно в комбінаторній теорії можна виділити наступні три більші частини:

1. Теорію конфігурацій, що включає блок - схеми, групи підстановок, теорію кодування.

2. Теорію перерахування, що містить твірні функції, теореми обігу й вирахування кінцевих різниць.

3. Теорію порядку, що включає кінцеві впорядковані множини й ґрати, матриці й теореми існування, подібні до теорем Холу й Рамсея.

Треба ще раз підкреслити найвищою мірою умовний характер представленої схеми. Повсюдно можна спостерігати взаємний зв'язок перерахованих розділів комбінаторики. Наприклад, перерахувальна комбінаторика розглядає завдання, що ставляться й до конфігурацій, і до впорядкованих множин.

2.1 Теорія конфігурацій і теорія перерахування

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

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

2.1.1 Правило суми

Якщо елемент A можна вибрати m способами, а елемент B можна вибрати k способами, то вибір елемента A або B можна здійснити m + k способами.

Правило суми можна перефразувати теоретико-множинною мовою. Позначимо через | A | число елементів множини A, через - об'єднання множин A і B, через - декартовий добуток множин A і B. Тоді для непересічних множин A і B виконується рівність:

.

Узагальненням правила суми є правило добутку.

2.1.2 Правило добутку

Якщо елемент A можна вибрати m способами, а після кожного вибору елемента A елемент B можна вибрати k способами, тоді, упорядковану пару елементів (A, B) можна вибрати m*k способами.

Правило добутку можна поширити на вибір послідовності (x1, x2, ..., x_n) довільної кінцевої довжини n.

Теоретико-множинною мовою правило добутку формулюється так:

.

2.2 Блок-схеми

Комбінаторні конфігурації найбільш загального виду були досліджені в 30- е роки XX сторіччя й були названі блок-схемами (block desіgn). Блок-схеми складаються з наборів елементів, називаних блоками. Вибір елементів і пара елементів у блоки підкоряються певним правилам.

Урівноваженою неповною блок-схемою називається таке розміщення v різних елементів по b блоках, що кожний блок містить точно k різних елементів, кожний елемент з'являється точно в k різних блоках і кожна пара різних елементів a_i , a_j з'являється точно в блоках.

Множина всіх сполучень із v елементів по k, узятих як блоки, утворить повну блок-схему. Частина цих сполучень, у яких кожна пара a_i , a_j з'являється одне й те саме число раз, є неповною, але врівноваженою блок-схемою. Між п'ятьома параметрами блок-схеми виконуються наступні два співвідношення:

Частинним випадком блок-схем є так звані скінченні площини. Виберемо скінченну множину P. Елементи з P назвемо точками. Деякі підмножини з P назвемо прямими. Нехай відношення інцидентності між точками й прямими задовольняє наступним геометричним аксіомам.

1. На кожній прямій лежить n точок B.

2. Через кожну точку проходять n прямих.

3. Будь-які дві прямі перетинаються в одній точці.

4. Через будь-які дві точки проходить єдина пряма.

5. Існують 4 точки неколлінеарні по трьох.

Тоді кінцева множина P точок і множина L прямих утворить кінцеву проективну площину.

Для знаходження кусково-постійних конфігурацій множин треба спочатку на множині усіх множин ввести Р(D) лінійні бінарні відношення та =. Матимемо частково впорядковану множину . Потім знаходимо ті групи множин, які у заданій конфігурації розташовані поряд і які рівні – це й будуть "куски" постійності у конфігурації множин, а сама така конфігурація називається кусково-постійною.

Висновок

У процесі роботи над цим твором я навчився програмувати засобами IDE C++ Builder з допомогою вбудованого GUI, функцій та класів. Для розв’язання задачі знадобились знання з комбінаторики та теорії множин, які я освіжив також при опрацюванні теоретичної частини курсового проекту. Було досягнуто значних успіхів у поглибленні розуміння підґрунтя математики та кібернетики, був зроблений крок до підготовки ще одного гідного випускника нашого славного вишу.

Список використаних джерел

1. http://www.embarcadero.com/ru/products/cbuilder\

2. Александров П. С. Введение в теорию множеств и общую топологию. — М.: "НАУКА", 1977. — 368 с.

3. Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: "Вильямс", 2006. — С. 960. — ISBN 0-13-086998-8

4. Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.

5. Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer’s Guide. — М.: "Вильямс", 2004. — С. 976. — ISBN 0-672-32480-6

6. Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer’s Guide. — М.: "Диалектика", 2001. — С. 884. — ISBN 0-672-31972-1

7. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.

8. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: "ФИЗМАТЛИТ", 2004. — 572 с. — ISBN 5-9221-0266-4

9. Р. Стенли Перечислительная комбинаторика = Enumerative Combinatorics. — М.: "Мир", 1990. — С. 440. — ISBN 5-03-001348-2

10. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.

11. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2

Додаток (постановка задачі, код програми, приклад)

Постановка задачі

Нехай маємо "n"кульок і три ящики А1,А2,А3. Встановити число способів Рn можна розмістити кульки так щоб у перших двох ящиках була однакова к-сть кульок

Код програми

//---------------------------------------------------------------------------

//Нехай маємо "n"кульок і три ящики А1,А2,А3.Встановити число способів

//Рn можна розмістити кульки так щоб у перших двох ящиках була однакова к-сть кульок

#include

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

#include "stdio.h"

int n=1, Pn=0;

int f(int n)

{

int r=1;

for(int i=1;i<=n;++i)

{

r=r*i;

}

return r;

}

int A(int n, int k)

{

return f(n)/f(n-k);

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{

int n=Edit1->Text.ToInt(), Pn=A(n,2);

for(int i=0;i<=n/2;++i)

{

Pn+=A(n,i)*A(n-i,i);

}

AnsiString as = "Відповідь: "+IntToStr(Pn);

ShowMessage(as);

}

//---------------------------------------------------------------------------

Приклад