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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Комбнаторний аналз

Информация:

Тип работы: курсовая работа. Добавлен: 09.09.2012. Сдан: 2012. Страниц: 8. Уникальность по antiplagiat.ru: < 30%

Описание (план):


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Зміст
    Вступ………………………………………………………………………3
    Основна частина:…………………………………………………………5
      Історія виникнення комбінаторних задач…………………………...5
      Способи розв’язання   задач………………………………………….10
        Логічний  спосіб……………………………………………………10
    2.2  За допомогою  формул комбінаторики…………………………..11
      Метод перебору……………………………………………………14
      Розв’язання рівнянь……………………………………………………19
 
     Висновки………………………………………………………………….22
    Література…………………………………………………………………23
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
І. Вступ
     Комбінаторика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів даної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.[ 1]
     Комбінаторика - важливий розділ математики, знання якого  необхідно представникам різноманітних  спеціальностей. З комбінаторними задачами доводиться мати справу фізикам, хімікам, біологам, лінгвістам, спеціалістам по кодам та ін. Комбінаторні методи лежать в основі рішення багатьох задач  теорії ймовірностей та її застосувань.
     Не  так давно (з 1995 року) до шкільної програми з математики включений курс «Елементи комбінаторики, теорії  ймовірностей і статистики». Комбінаторні задачі і раніше зустрічалися на сторінках підручників та інших навчальних посібників із математики, а вчителі використовували їх у практичній роботі на уроках,заняттях гуртків та в позакласних заходах (вікторини, олімпіади, ігротеки тощо), у завданнях ЗНО. Сьогодні, з огляду на актуальність теми, ця науково-дослідницька робота набуває особливого значення. Кожен учень повинен розуміти, що будь-які вміння, у тому числі й уміння розв’язувати комбінаторні задачі, слід формувати виважено й поступово, повільно ускладнюючи пропоновані задачі.
     Об’єктом  дослідження в даній роботі є комбінаторні задачі.
     Предметом дослідження – досить нескладні  задачі, які розв’язуються  за допомогою  декількох певних дій. 

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

II. Основна частина
      Історія виникнення комбінаторних задач
     Комбінаторика - гілка математики, що вивчає комбінації та перестановки предметів, - виникла  в XVII ст. Довгий час здавалося, що комбінаторика  лежить поза основної течії розвитку математики та її застосувань. Хід справ  різко змінився після появи ЕОМ. Зараз комбінаторні методи застосовуються в теорії випадкових процесів, статистиці, математичному програмуванні, обчислювальній математиці, плануванні експериментів і т.д. В математиці комбінаторика використовується при вивченні кінцевих геометрій, комбінаторної геометрії, представлень груп, неасоціативних алгебр і т.д.
     Перша згадка про питання,що близькі до комбінаторних, зустрічається в китайських рукописах, що відносяться до XII - XIII ст. до н.е. (точно датувати ці рукописи неможливо, тому що вони в 213 р. до н.е. імператор Цин Шихуан наказав спалити всі книги, тому до нас дійшли пізніше зроблені копії). В цих книгах писалося, що усе в світі являється поєднанням двох початків - чоловічого та жіночого, які автори позначали символами ------ та --- ---. В рукописи "Же-ким" ("Книга перестановок") показані різні з'єднання цих знаків по два і по три (рис. 1). Вісім малюнків з трьох рядів символів відображали землю, гори, воду, вітер, грозу, вогонь, хмари і небо (деякі малюнки мали інше значення). Сума перших 8 натуральних чисел (тобто число 36) втілювала в уяві давніх китайців весь світ.
------ --- --- ------ --- --- ------ --- --- ------ --- ---
------ ------ --- --- --- --- ------ ------ --- --- --- ---
------ ------ ------ ------ --- --- --- --- --- --- --- ---
(Рис.1) 

------ --- --- ------ --- --- ------ --- --- ------ --- ---
------ ------ --- --- --- --- ------ ------ --- --- --- ---
------ ------ ------ ------ --- --- --- --- --- --- --- ---
k 'ien (небо) tui (хмари) li (вогонь) chon (гроза) sun (вітер) k 'an (вода) kon (гори) k 'un (земля)
7 6 5 4 3 2 1 0
Пд. Пд.Сх. Сх. Пн.Сх. Пд.Зх. Зх. Пн.Зх. Пн.
 
 
        По мірі поглиблення знань знадобилось виразити і інші елементи, що входять до складу світу за допомогою тих самих знаків ------ та --- ---. Були складені 64 фігури, що складалися з п'яти рядів рисочок. Треба вважати, що автор рукопису "Же-ким" помітив подвоєння числа малюнків при додаванні одного ряду символів. Це можна розглядати як перший загальний результат комбінаторики.
     У рукописі "Же-ким" є і більш  складні малюнки. Як стверджує поданий в ній додаток, імператор Ію, котрий жив приблизно 4000 років тому назад, побачив на березі річки священну черепаху, на панцирі якої був зображений малюнок з білих і чорних кружків(мал.2)
       (4   9   2
       3   5   7
       8   1   6)
   
   (Мал.2)
     При додаванні чисел в кожному  рядку, стовпчику та по діагоналі  отримаємо одне і те саме число 15. При тому містичному поясненні, яке  надавали числам давні китайці, відкриті таблиці з такими магічними властивостями  справило невиправні враження. Рис. 2 назвали "ло-шу", і почали вважати його магічним символом і використовувати при закляттях. Тому зараз будь-яку квадратну таблицю чисел з однаковими сумами по кожному рядку, стовпчику та по діагоналі називають магічним квадратом.
     По  цим натякам можна все ж  таки судити, що певні уявлення про  комбінаторику у грецьких вчених були. Філософ Ксенократ, що жив в ІV ст.. до. н.е. підраховував кількість складів. В ІІІ ст.. до н.е. стоїк Хрисипп вважав, що кількість тверджень, отримуваних з 10 аксіом, перевищує мільйон. На думку Геппарха, із стверджуючих аксіом можна скласти 103 049 сполучень, а додавши до них заперечні, 310 952. ми не знаємо який саме зміст надавали ці філософи своїм ствердженням і як вони отримували свої результати - числа, що наводив Геппарх дуже точні, щоб вважати їх результатом грубої оцінки, і в той же час їх не можна пояснити. Напевно, у грецьких вчених були якісь, невідомі нам, правила комбінаторних розрахунків, які, скоріше всього, були невірними.
     Велику  увагу грецькі вчені приділяли  питанням, граничним між комбінаторикою та теорією чисел. Ще в VІ ст. до н.е. в школі філософа-ідеаліста і  математика Піфагора виникло твердження, що світом правлять числа, а речі лише відображення чисел (можливо, ці ідеї виникли  у Піфагора під впливом вавилонської культури). Тому, щоб пізнати світ, пафігорейці почали вивчати властивості натуральних чисел. Їхні досліди про парні і непарні числа, ділення чисел, прості і складені числа поклали основу теорії чисел (в науці буває, що невірні похідні основи дають поштовх до корисних досліджень). Як і китайці, піфагорейці надавали особливе значення числу 36 - воно було для них не тільки сумою перших 4 парних і перших 4 непарних чисел, але й сумою перших трьох кубів: 36 = 13 + 23 + 33. Символом бездоганності піфагорейці вважали бездоганні числа, що дорівнювали сумі своїх дільників, наприклад, 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, а символом дружби - дружні числа, кожне з яких дорівнює сумі дільників іншого числа (наприклад, 220 і 284). Пошук таких чисел потребував комбінаторної майстерності.
     В школі Піфагора була доведена знаменита теорема про сторони прямокутного трикутника. Це викликало інтерес до представлення чисел у вигляді суми двох квадратів, до квадратних чисел 1, 4, 9, 16 і т.д. Квадрати натуральних чисел відображались при цьому геометрично. Але піфагорейці розглядали і інші конфігурації крапок, такі.Кожний трикутник отримується з попереднього збільшенням довжини його сторони на 1. Підраховуючи кількість крапок у кожному трикутнику, отримуємо послідовність трикутних чисел 1, 3, 6, 10... Ці числа можна отримати, послідовно додаваючи натуральні числа: 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4 і т.д. Так само шестикутники призводять до послідовності шестикутних чисел 1, 6, 15 ... отриманій при послідовному додаванні арифметичної прогресії 1 + 5 + 9 + ...
     В 1713 р. була опублікована книга "Мистецтво  припущень" Якоба Бернуллі, в якій вказувались формули для числа  розміщень з n елементів по k, виводились вираження для степеневих сум  та ін. Чудові досягнення в області  комбінаторики належать одному з  найбільших математиків XVIII ст., Леонарду Ейлеру, швейцарцю, що прожив майже  все життя в Росії, де він був  членом Петербурзької академії наук. Основна частина наукової роботи Ейлера присвячена математичному аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і закінчив досліди інших областей. Але у Ейлера вистачало часу думати і про задачі, які, здавалося б, не заслуговували його уваги, - про  те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому самому мості, чи можна поставити 36 офіцерів з 6 різних полків так, щоб у кожній шерензі  і у кожній колоні було по одному офіцеру кожного військового  звання з полку, скількома способами можна розбити число на частини і т.д. Але, дивна справа, робота про мости виявилась так званим зерном, з якого потім виросли топологія і теорія графів, задача про офіцерів виявилась зараз пов'язаною з плануванням експериментів, а методи, що використовувалися при розв'язуванні задачі про розбиття чисел, після довгого та важкого шляху розвитку перетворилась в науку про інтегральні перетворення, що використовується для розв'язання рівнянь математичної фізики.
     Після робіт Паскаля і Ферма, Лейбніца і Ейлера можна було вже говорити про комбінаторику, як про окрему, самостійну гілку математики, тісно пов'язану з іншими областями науки, такими, як теорія ймовірностей., вчення про ряди та ін. В кінці XVIII ст. німецький учений Гінденбург та його учні зробили спробу побудувати загальну теорію комбінаторного аналізу. Проте цікавих задач, які могли б дати необхідний фундамент для такої теорії.
     В ХІХ ст. в ході досліджень по комбінаториці  стали помічатися зв'язки цієї теорії з визначеннями кінцевими геометріями, групами вона не отримала успіху - в той час ще не було накопичено достатньої кількості важливих і, математичної логіки і т.д.[8]
                                                                                                                            
 
 
 
 
 
 
 

      Способи розв’язання задач
      Комбінаторні  задачі – це задачі, де мова йде про  будь-які комбінації об’єктів.[1]
        Логічний  спосіб
     Основний  принцип комбінаторики:Нехай послідовно можна виконати  дій. Першу дію можна  виконати n 1    способами, а другу - n 2 способами.Тоді  всі  дій  послідовно можна виконати .
     Правило додавання. Якщо дві взаємовиключні дії можуть бути виконані відповідно n1 та n2 способами, тоді якусь одну з цих дій можна виконати:
n 1 + n 2 способами.[6]
Приклад : З міста А в місто В можна добратися 4 потягами, 2 літаками, 6
автобусами. Скількома способами можна добратися з міста А у місто В.
Розвязання. Проїзд з А у В на потягу, літаку або автобусом є взаємови-
ключними операціями, тому загальну кількість маршрутів можна одержати як суму способів пересування, тобто N = + = 4+ 2 +6 =12 способів. 

     Правило множення. Нехай дві виконувані одна за одною дії можуть бути здійснені відповідно n1 та n2 способами. Тоді обидві вони можуть бути виконані   n 1 ? n 2 способами.[6]
Приклади:
1.У чемпіонаті країни з футболу беруть участь 16 команд. Скіль-
кома способами  можуть бути розподілені золота, срібна і бронзова медалі?
Розвязання. N = ? = 16 ? 15 ? 14= 3360.
2. Скільки сигналів можна подати з корабля за допомогою чоти-
рьох прапорів різного кольору, розміщуючи їх на щоглі, якщо використовувати різну кількість прапорів?
Розвязання. Сигнали можна подавати чотирма, трьома, двома і одним
прапорами. Відповідно до правила множення, кількість можливих способів подачі сигналу з 4 прапорів складе = 4 ? 3 ? 2 ? 1 =24 для сигналу з 3 прапорів =4 ? ? 2 =24 способів, для сигналу з 2 прапорів маємо
  =4 ? 3 =12
для сигналу з 1 прапора =4 способа. Загальну кількість сигналів можна одержати як суму способів для сигналів з 4, 3, 2 і 1 прапорів, тобто
N = + =24 + 24+ 12+4 = 60 способами.
Обидва правила узагальнюються на випадок будь?якої скінченної кількості дій. 

2.2  За допомогою формул  комбінаторики
      Множина? — одне з основних понять сучасної математики. Строго воно не визначається, але може бути дано інтуїтивне визначення множини як сукупності певних і різних об'єктів довільної природи, яка розглядається як одне ціле. Об'єкти, які складають множину, називаються її елементами. Наприклад, можна говорити про множину усіх книг в певній бібліотеці, множину літер українського алфавіту або про множину всіх коренів певного рівняння тощо.
   Якщо X та множини та будь-який елемент із X є також елементом із Y, то говорять, що:
    X є підмножиною (частиною) Y, позначення — X ? Y;
    надмножина (охоплююча множина) X, позначення — Y ? X.
   У комбінаториці розрізняють три види різних з'єднань (комбінацій) елеме-
нтів фіксованої множини: перестановки, розміщення, сполучення.[3]
     Перестановками з елементів називають різні скінченні впорядковані множини(тобто такі множини,для яких указано порядок розміщення їх елементів),що їх можна дістати з деякої множини, яка містить елементів. Якщо всі елементи даної множини різні, дістаємо перестановки без повторень,  а якщо елементи можуть повторюватися, то перестановки з повтореннями:                                                                                          
Без повторень:                                                                                                      [6]
Приклад :Скільки різних тризначних чисел можна скласти за допомогою
трьох карток з цифрами 1, 2, 3?
Розвязання.
Розвязання. Загальна кількість можливих тризначних чисел дорівнює 

  Легко помітити, що такий же результат можна одержати, застосовуючи правило  множення.
З повтореннями : 

Приклад:Кількість різних шестицифрових чисел, які можна скласти з трьох двійок, двох сімок і однієї п’ятірки: 
 

     Розміщенням  з  елементів по по k називають будь яку впорядковану множину з k елементів, складену з елементів даної множини , яка містить елементів.(Якщо вибрані елементи не повторюються, то одержуємо розміщення  без повторень, а якщо повторюються  ,то розміщення з повтореннями.)
Без повторень: 

Приклад:
Скільки різних двозначних чисел можна скласти за допомогою трьох карток
з цифрами 1, 2, 3?
Розв’язання: Загальна кількість можливих двозначних чисел визначається
відповідно до виразу :
 
З повтореннями: 

Приклад:Кількість різних трицифрових чисел, які можна скласти з цифр 1, 2, 3, 4, 5, 6, якщо цифри в числі можуть повторюватися: 
 

Комбінації( сполучення):
Без повторень :
     Комбінації( сполучення) без повторень з  елементів по називають будь-яку - елементну підмножину –елементної множини. 

При цьому: ; =; 

Приклад: Скількома способами можна вибрати дві цифри з трьох 1, 2, 3?
Розвязання: Загальна кількість можливих способів вибору цифр дорівнює 

З повтореннями:
     Нехай є  елементів(не обов’язково різних) даної множини. Комбінацією(сполученням) з елементів по називають набори цих елементів, до кожного з яких входить елементів і які відрізняються лише складом елементів( хоч би одним елементом)
[9]
Приклад:Якщо в продажу є квіти чотирьох сортів, то різних букетів, що складаються із 7 квіток, можна скласти 

2.3  Метод перебору
Задача 1. Скільки двозначних чисел можна скласти, використовуючи цифри 1, 4 і 7?
Розв’язання . Для того щоб не пропустити і не повторити жодного з чисел, будемо выписувати їх у порядку зростання. Спочатку запишемо числа, які починаються з цифри 1, потім з цифри 4 і, нарешті, з цифри 7. Отримуємо наступний розклад.
11 14 17
41 44 47
71 74 77
Таким чином, з трох даних цифр можна скласти всього 9 різних двозначних чисел.
Однако  існує єдиний підхід к розв’язанню найрізноманітніших комбінаторних задач за допомогою складання спеціальних схем. Зовнішньо така схема нагадує дерево, звідси назва – дерево можливих  варіантів.  При правильній побудові дерева жоден  з варіантів розв’язання не буде втрачений.[7]
Повернемося до задачі про складання двозначних чисел з цифр 1, 4і 7. Для ії розв’язання можно побудувати  спеціальну схему.(9)

Ця  схема дійсно схожа на дерево, правда, "вверх ногами" і без стовбура. Знак “*” зображає корень дерева, вітки дерева – різноманітні варіанти розв’язання. Щоб отримати двозначне число, необхідно спочатку вибрати першу його цифру, а для неї є три варианта: 1, 4 або 7. Тому з точки * проведено три відрізка і на кінцівках поставлені цифри 1, 4 і 7.
Тепер потрібно вибрати другу цифру, а для цього також існує три варіанти: 1, 4 або 7. Тому від кожної першої цифри проведено по три відрізки, на кінцях яких знову записано 1, 4 або 7. Отже, отримано всьго 9 різних двозначних чисел. Інших двозначних чисел из цих трьох цифр скласти неможливо.
У наслідку, ми побачимо, як побудова дерева допомагає розв’язати найрізноманітніші комбінаторні задачі.
Додаткова під задача: Скільки двозначних чисел можна скласти, використовуючи цифри 1, 4 і 7, якщо цифри десятків і одиниць не повторюються? (15)
Задача 2. Скільки тризначних чисел можна скласти, використовуючи цифри 3 і 5?(8)

Задача 3. Туристична фірма планує відвідування туристами в Італии трьох міст: Венеції, Риму и Флоренції. Скільки існує варіантів такого маршрута?
Перебор спрощується, якщо ввести зручні умовні позначення. Наприклад, якщо у задачі йде мова про розміщення в ряд деяких червоних та зелених шарів, то не треба малювати ці шари чи писати повністю їх кольори. Можна обмежитися тільки першими літерами кольору цих шарів - Ч і 3. Таку зміну предметів їх умовними позначеннями називають кодуванням.
Позначимо міста їх першими літерами. Тоді код кожного маршруту буде складатися з трьох букв: В, Р і Ф, кожна з яких повинна бути використана тільки один раз, наприклад, ВФР або ФРВ.(6)
 
 

Розв’язання задач[5]
1. Андрій зайшов у магазин, щоб купити майки. В магазині виявилися майки чотирьох кольорів: білі, голубі, зелені, чорні.
а) Скільки варіантів покупки є у Андрія, якщо він хоче купити дві майки?(7)
Підказка: позначте кольора майок Б, Г, З, Ч. Запишіть всі можливі варіанти покупки, виконуючи їх перебір в алфавітному порядку.
б) Скільки вариантів покупки є у Андрія, якщо він хоче купувати дві майки різного кольору?(6)
2. У турнірі з настольного тенісу приймали участь 5 чоловік.
а) Скільки було зіграно партій, якщо кожен учасник зіграв з іншими по одній партії?(25)
Дайте відповідь на питання, використовуючи спосіб кодування, позначивши учасників турниру цифрами 1, 2, ....
3. У шостому класі вивчається 8 предметів. Скільки різних варіантів  розкладу можна скласти на понеділок, якщо у цей день повинно бути 5 уроків і всі різні?
Підказка: на першому уроці можна провести будь-який з 8 предметів, на другом уроці – будь-який з залишившихся 7 предметів, на третьому уроці
4. У магазині є чотири  типи диваних подушок: круглі, овальні, прямокутні и трикутні Скільки варіантів покупки є у покупця, який хоче купити дві подушки?
Розв’яжить  задачу, закінчивши побудову дерева можливих варіантів.
5. Випищіть усі трьохзначні числа, використовуючи при записі кожного числа цифри 1, 2, 3, і кожну з них лише один раз.(6)
6. Фірма володіє чотирма магазинами. Касир магазина № 1 повинен об’їхати інші магазини, щоб зібрати виручку, і повернутись назад. Який з можливих маршрутів найкоротший?(1)

7. У класі три чоловіка добре співають, два інші грають на гітарі, а ще один вміє показувати фокуси. Скількома способами можна скласти концертну бригаду з співака, гітариста і фокусника?
8. Є 3 види конвертів і 4 види марок. Скільки існує варіантів вибору конверта з маркою?
9. В буфеті є чотири сорти пиріжків. Скількома способами учень може собі купити два пиріжки? два різні пиріжки?
10. Скільки існує шестизначних чисел, у яких:
а) третя цифра – 3;(123)
б) остання цифра – парна;
в) на парних місцях стоять непарні цифри;
г) на непарних місцях стоять парні цифри? 

Задачі для самостійного розв'язання
1. Скількома способами можна розташувати на полиці в ряд три різні книги?
2. Скількома способами можна розсадити за круглим столом п'ять гостей
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.