Курсова робота на тему: «Застосування комбінаторики при розв’язуванні перебірних задач»

З М І С Т

ВСТУП    3

Розділ І. Основи комбінаторики    5

1. 1. Принцип добутку і принцип суми. Розміщення з повтореннями    5

1. 2. Розміщення та перестановки без повторень    6

1. 3. Комбінації без повторень    7

1. 4. Перестановки з повтореннями    8

1. 5. Комбінації з повтореннями    9

1. 6. Формули включень і виключень    11

Розділ ІІ. Застосування комбінаторики при розв’язанні задач    16

2.1. Породження і перебір комбінаторних об’єктів    16

2.2. Рекурсія    21

2.4. Складний випадок    28

2.5. Рішення через рекурсію    30

2.6. Правило Варнсдорфа    31

2.7. Перебірне рішення    32

Висновки    35

Список використаної літератури:    36

ВСТУП

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

Саме та обставина, що «математика висновує всі свої правила сама із себе» підкреслює внутрішню притаманність творчості математичним дослідженням. Звідси випливає необхідність творчого методу викладання математики для майбутніх математиків. Досвід переконує, що цей метод є більш ефективним для вивчення математики як науки, для виховання майбутніх творців математики. Але чому ж ми маємо вчити майбутніх «нематематиків» менш ефективним рецептурним методом? Для цього немає жодних аргументів. Зробимо підсумок викладених вище міркувань у формі стислих відповідей на поставлені запитання.

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

Мета дослідження: Огляд та реалізація комбінаторного методу при розв’язувані задач на перебір.

Завдання
дослідження: Огляд основних елементів кобінаторики; розробка алгоритмів застосування комбінаторного тетоду; Реалізація розробки алгоритмів.

Розділ І. Основи комбінаторики

1. 1. Принцип добутку і принцип суми. Розміщення з повтореннями

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то AÈB містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то A´B містить m×n елементів, тобто пар.

Кількість елементів множини A будемо далі позначати |A|.

Ці правила мають також вигляд:

Принцип суми. Якщо об’єкт A можна вибрати m способами, а об’єкт B – n іншими способами, то вибір “або A, або B” можна здійснити m+n способами.

Принцип добутку. Якщо об’єкт A можна вибрати m способами і після кожного такого вибору об’єкт B може бути вибраним n способами, то вибір “A і B” в указаному порядку можна здійснити m×n способами.

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

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

Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

Означення. Розміщення з повтореннями по m елементів n-елементної множини A – це послідовність елементів множини A, що має довжину m.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Якщо |A|=n, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина Am=A´A´´A, містить nm елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2m. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини m.

У багатьох комбінаторних задачах об’єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A1, другий – A2, тощо. Але досить часто множина A2 визначається лише після того, як зафіксовано перший член послідовності, A3 – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A1|=10, |A2|=|A3|=…=|A7|=9, і загальна кількість номерів є 10×96.

1. 2. Розміщення та перестановки без повторень

Означення. Розміщення по m елементів n-елементної множини A, де m£n – це послідовність елементів множини A, що має довжину m і попарно різні члени.

Приклади.

1. При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c), (b,a), (b,c), (c,a), (c,b).

2. Розподіл n
різних кульок по одній на кожний з m
різних ящиків, m£n. Ящики можна пронумерувати від 1 до m, кульки – від 1 до n. Тоді кожному розподілу взаємно однозначно відповідає послідовність довжини m попарно різних номерів від 1 до n.

Неважко підрахувати кількість послідовностей з прикладу 2. На першому місці може стояти будь-який із номерів 1, …, n. На другому – незалежно від того, який саме був на першому, будь-який із n-1, що залишилися. І так далі. За принципом добутку, таких послідовностей

n×(n-1)××(nm+1),

або n!/(nm)!. Цей добуток позначається або (n)m або nm.

Означення. Перестановка
n елементів множини A
без повторень – це розміщення по n елементів, тобто послідовність елементів множини A, що має довжину n і попарно різні члени.

Приклад. При A={a, b, c} усі перестановки –це трійки (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Очевидно, що кількість перестановок n елементів дорівнює кількості розміщень по m при m=n, тобто n!. Отже, nn=n!.

1. 3. Комбінації без повторень

Означення. Комбінація по m елементів n-елементної множини – це її m-елементна підмножина.

Приклади.

1. При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b}, {a,c}, {b,c}.

2. Розподіл n
різних кульок по одній на кожний з m
однакових ящиків, m£n. Оскільки ящики однакові, то розподіл взаємно однозначно визначається підмножиною з m кульок, що розкладаються.

З кожної m-елементної комбінації елементів n-елементної множини можна утворити m! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є =. Ця кількість позначається або .

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Zastos Kombinatoryky Pry Rozv Perebir Zadach (302.0 KiB, Завантажень: 0)

Сторінка: 1 2 3 4 5 6 7 8 9 10
завантаження...
WordPress: 23.24MB | MySQL:26 | 0,424sec