Презентація на тему:
ІСТОРІЯ РОЗВИТКУ КОМБІНАТОРИКИ

ІСТОРІЯ РОЗВИТКУ КОМБІНАТОРИКИ

Комбінаторика - важливий розділ математики. Справи давнини. Перша згадка про питання, близькі до комбінаторних. Комбінаторика в Давній Греції. Комбінаторика та астрологія. Комбінаторика в країнах Сходу. Комбінаторика та азартні ігри. Комбінаторика в ієрогліфах та клинописі. Комбінаторика в шифрах та анаграмах. Комбінаторика в біології. Хімічний пасьянс. Комбінаторика епохи комп'ютерів. Основоположники комбінаторики. ЗМІСТ

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

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

Перша згадка про питання, близькі до комбінаторних, зустрічається в китайських рукописах, що відносяться до XII - XIII ст. до н.е. (точно датувати ці рукописи неможливо, тому що вони в 213 р. до н.е. імператор Цин Шихуан наказав спалити всі книги, тому до нас дійшли пізніше зроблені копії). В цих книгах писалося, що усе в світі являється поєднанням двох початків - чоловічого та жіночого Перша згадка Серед предметів, покладених в піраміду, де 35 століть тому назад був похований єгипетський фараон Тутанхамон, знайшли розкреслену дощечку з трьома горизонталями і 10 вертикалями та фігурки для давньої гри "сенет", про правила якої ми, можливо, ніколи не дізнаємось. Пізніше з'явились нарди, шашки й шахмати, а також їх різноманітні варіанти (китайські та японські шахмати, японські облавні шашки "го" і т.д.). в кожній з цих ігор доводилося розглядати різноманітні комбінації фігур, що мали здатність пересовуватись, та вигравав той, хто їх краще вивчив, знав переможні комбінації та вмів уникати програшів.

Говорити з повною впевненістю про рівень знань древніх греків в області комбінаторики дуже важко, оскільки до нас дійшли далеко не все з їх наукових досягнень. В 391 р. н.е. натовп монахів зруйнував центр язичної науки - олександрійський Музеум - і спалив більшу частину зберігаємої там бібліотеки, що налічувала багато тисяч томів. Можна все ж таки судити, що певні уявлення про комбінаторику у грецьких вчених були. Філософ Ксенократ, що жив в ІV ст.. до. н.е. підраховував кількість складів. В ІІІ ст.. до н.е. стоїк Хрисипп вважав, що кількість тверджень, отримуваних з 10 аксіом, перевищує мільйон. На думку Геппарха, із стверджуючих аксіом можна скласти 103 049 сполучень. Конкретні комбінаторні задачі, що торкалися перерахунку невеликих груп предметів, греки розв'язували без помилок. Аристотель описав без пропусків всі види правильних тричленних силогізмів, а його учень Аристоксен з Тарента перерахував різноманітні комбінації довгих і коротких складів у віршових розмірах. Математик Папп (ІV ст. н.е.) роздивлявся число пар і трійок, які можна отримати з трьох елементів, не забороняючи їх повторення Комбінаторика в Давній Греції

Велику увагу грецькі вчені приділяли питанням, граничним між комбінаторикою та теорією чисел. Ще в VІ ст. до н.е. в школі філософа-ідеаліста і математика Піфагора виникло твердження, що світом правлять числа, а речі лише відображення чисел . Як і китайці, піфагорійці надавали особливе значення числу 36 - воно було для них не тільки сумою перших 4 парних і перших 4 непарних чисел, але й сумою перших трьох кубів. Символом бездоганності для піфагорейці вважали бездоганні числа, що дорівнювали сумі своїх дільників, наприклад, 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 а символом дружби - дружні числа, кожне з яких дорівнює сумі дільників іншого числа (наприклад, 220 і 284). Пошук таких чисел потребував комбінаторної майстерності. Перехід від площини до простору дав можливість будувати ще більш складні числа. Наприклад з трикутників можна скласти піраміди. Підраховуючи кількість крапок в таких пірамідах, прийшли до пірамідальних чисел 1, 4, 10, 20, ..., що були сумами ряду 1 + 3 + 6 + 10 + ..., складеного з натуральних чисел. Проте подальше узагальнення потребувало введення багатомірних просторів, що лежало за рамками можливостей давньогрецької математики.

Комбінаторика та астрологія З ІІ ст. до н.е. починається спочатку поступовий, а потім все більш швидкий занепад науки. Одночасно з кабалістами і містиками комбінаторикою в ці темні століття занепаду науки займались астрологи. Їх цікавило питання про рух планет і їх "вплив" на долі людей. Особливе значення надавали вони порядку планет - зустрічі планет одному знаку Зодіаку. Астролог Бен Езра у 1140 році розрахував кількість суміщень семи планет по дві, по три і т. д. Він знав, що число суміщень планет по дві дорівнює числу їх суміщень по п'ять, а число суміщень по три дорівнює дорівнює числу суміщень по чотири. В остаточному вигляді формулу для числа суміщень отримав математик Леві бен Гершон (початок XIV ст.), Проте його робота, написана на малодосяжному для багатьох вчених древньоєврейській мові, залишилась майже непоміченою

Комбінаторика в країнах Сходу В VIII ст. н.е. почався розквіт арабської науки. Араби переклали багато творів грецьких учених, вивчили їх, а потім просунулись вперед по областях, мало звертавших увагу греків, - в науці про рішення рівнянь (саме слово "алгебра" - арабського походження), теорії та практиці обчислень та ін. Вирішуючи питання про знаходження коренів з будь-якого степеня, арабські алгебраїсти вивели формулу для степені суми двох чисел, яка відома під невірною історичною назвою "біном Ньютона". Напевно цю формулу знав поет і математик Омар Хайям (ХІ - ХІІ ст. н.е.). у будь-якому випадку вже і ХІІІ ст. таку формулу друкує в своїх творах Насир ад-Дин ат-Туси, а в XV ст. вона була ретельно досліджена Гияседдином ал-Каші. Судячи по деяких європейських джерелах, східним до арабських оригіналів, для пошуків коефіцієнтів цієї формули брали число 10001 и зводили його до 2-го, 3-го, ......, 9-го степеня. Виходила таблиця в якій жирним шрифтом були виділені коефіцієнти бінома Ньютона.

Цікавились суміщеннями і в Індії. Ще в ІІ ст. до н.е. індійці знали числа Сkn і той факт, що сума C0n + C1n + … + Cnn дорівнювала 2n. А в ХІІ ст. індійський математик Бхаскара написав книгу "Лілаваті", в якій серед інших питань математики вивчає і проблеми комбінаторики. Він пише про застосування перестановок до підрахунку варіацій у віршоскладанні, різних розміщень в архітектурі та ін. Він також дає правила для пошуку числа перестановок та суміщень декількох предметів, при чому розглядає і випадок, коли в цих перестановках є елементи, що повторюються.   Одночасно з арабами вирахуванням біноміальних коефіцієнтів займались китайські математики. Вони склали до ХІІІ ст. н.е. таблицю таких чисел до n=8, наведену в книзі алгебраїста Чжу Ши-дзе "Ямшове дзеркало". Існують здогади, що І Сінь в VIII ст. н.е. вирахував кількість різних розміщень фігур у грі, що нагадувала шахи. 

Треба було лише визначити, скільки потрібно зробити кидків, щоб гра була йому така ж вигідна, як і перша. Шевальє вирішив, що треба кидати 24 рази. Адже при чотирьох кидках однієї кості шестірка випадала більш ніж у половині випадків, а так як друга кость дає шість варіантів випадання, то й треба помножити 4 на 6.Роздуми здавалися незаперечними, але досвід не підтвердив надій де Маре - тепер він став частіше програвати, ніж вигравати. В повному нерозумінні він звернувся до двох великих математиків Франції XVII ст. - Блезу Паскалю та П'єру Ферма. Розбираючись в цій та інших задачах, поставлених перед ними де Маре, вони сформулювали і довели перші теореми комбінаторики та теорії ймовірностей. Значний поштовх до розвитку комбінаторики дали азартні ігри, які існували ще в глибоку давнину, але отримали особливе розповсюдження після хрестових походів. Найбільшу популярність отримала гра в кості - два чи три кубики з нанесеними на них очками кидали на стіл, і вигравав той, хто отримував більшу кількість очок. Одним з найазартніших гравців в кості у XVII ст. був шевальє де Маре, котрий без перестану знаходив нові види змагань. Наприклад, він запропонував, що буде кидати чотири кості і буде брати виграш лише у випадку, коли хоча б одна з них відкриється на шести. Проте скоро його партнери відмовились від такої гри - шевальє частіше вигравав, ніж програвав. Тоді де Маре придумав інший варіант - він кидав декілька раз пару костей і забирав виграш в тому випадку, якщо хоча б раз випадали дві шестірки.   Комбінаторика та азартні ігри

Ще тісніше пов'язана з комбінаторикою розшифровка клинописів. Історикам вдалося зясувати, що ці надписи було зроблено в епоху Ахеменідів, що правили в Ірані два з половиною тисячоліття тому назад. Були зроблені і припущення про мову надписів. А потім комбінаторний аналіз тексту виявив часте повторення певної групи знаків з семи знаків. Комбінаторика дозволила прочитати і крито-мікенське лінійне письмо. Перші надійні основи розшифровки цієї писемності заклала Аліса Д. Кобер, яка захистила у 1932 р. докторську дисертацію по математиці у Колумбійському університеті. Навички в розгадці складних шифрів допомогли ученим, коли археологи почали відкопувати камені та черепи з таємними знаками - письменністю, що замовкла декілька тисячоліть тому. Одним з найкращих успіхів у розшифровці було читання французьким філологом Жаном Франсуа Шампольним ієрогліфів, якими писали єгиптяни ще до того, як виникла наука у древніх греків. Це було торжеством комбінаторного методу у читанні забутих писемностей, заснованого на спостереженні за текстом, на співставленні повторюванні комбінацій слів та граматичних форм в поєднанні з уявою.   Комбінаторика в ієрогліфах та клинописі

Не тільки азартні ігри спонукали математиків до комбінаторних роздумів. Ще в кінці XVI ст. розшифровкою переписів між ворогами французького короля Генріха ІІІ та іспанцями займався один із творців сучасної алгебри Франсуа Вієт. А в Англії XVII ст. монархічні заколотники дивувались швидкості, з якою Кромвель проникав у їх замисли. Монархісти вважали шифри, якими вони користувались при переписі, нерозшифрованими, і вважали, що ключі до них були видані кимсь з учасників заколоту. І лише після падіння республіки та царювання Карла ІІ вони дізналися, що всі їх шифри розгадував один з найкращих англійських математиків того часу, професор Оксфордського університету Уолліс, котрий володів винятковими комбінаторними можливостями. Він назвав себе засновником нової науки "криптографії". Комбінаторика в шифрах та анаграмах Тексти з переставленими літерами називаються анаграми. Проте не завжди анаграми дозволяли зберегти все у таємниці. Коли Гюйгенс відкрив перший супутник Сатурна та визначив його порядок обертання навколо планети, він виклав своє відкриття в анаграмі і відправив її своїм колегам. Проте вже згадуваний вище Уолліс, отримав цю анаграму, розгадав її, після чого склав свою анаграму та відправив її Гюйгенсу. Коли вчені обмінювалися розгадками анаграми, то вийшло так, немов Уолліс ще до Гюйгенса зробив те ж саме відкриття. Потім Уолліс зізнався, що пожартував із Гейгенсом, щоб довести безкорисність анаграм у справі таємності. Проте, хоча Гейгенс і сам був великим любителем і знавцем комбінаторики, він не оцінив жарту і розізлився.

Складність будови біологічних систем, їх строга ієрархічність, взаємо поєднання окремих процесів в цілому організмі роблять біологію підходящим полем для прикладання комбінаторних методів. Радянський біолог А. А. Любищєв припускав навіть, що схожість рослин та морозних візерунків на вікнах не випадково - в обох випадках проявляються певні закони комбінування частин в одне ціле. Однією з найбільш складних загадок в біології ХХ ст. була будова "ниток життя" - молекул білка і нуклеїнових кислот. Поєднуючи комбінаторні розгляди з вивченням рентгенівських знімків, вченим вдалося розгадати будову багатьох білків, в тому числі гемоглобіну, інсуліну та ін. Комбінаторика в біології Коли біологи почали вивчати передачу генетичної інформації у бактерій, то помітили, що в процесі цієї передачі хромосоми переходять від однієї бактерії до другої не цілком. Виникла потреба визначити порядок розміщення генів у хромосомі. Французькі вчені Жакоб та Вальмон порівняли карти хромосом тапомітили їх комбінаторну схожість. Найбільшим досягненням комбінаторного підходу до проявів життя можна вважати розшифровку будови дезоксирибонуклеїнової кислоти (ДНК), зроблену в Кембриджі Ф. Криком та Дж. Уотсоном у 1953 р..  

  Небагато знайдеться днів в історії науки, які можна порівняти по своєму значенню з 17 лютим 1869 р. у цей день з хаосу хімічних елементів, кожен з яких мав свої властивості, виникла таблиця - був відкритий періодичний закон. Це відкриття було зроблено Дмитром Івановичем Мендєлєєвим, професором Петербурзького університету. Готуючи курс лекцій по загальній хімії, він задумався над порядком, в якому потрібно було розповідати про елементи. Розкладуючи свій хімічний пасьянс, великий вчений після напружених роздумів, знайшов правильне розміщення елементів. Кажуть, що кінцевий вигляд таблиці постав перед ним у сні, коли, стомлений неперервними роздумами над нею, він приліг відпочити.   Хімічний пасьянс Не тільки у відкритті періодичної системи елементів виявилась корисною комбінаторика. Як відомо серед обмежених об'єднань зустрічаються і ізомери, тобто об'єднання, котрі мають один і той самий склад, але різну будову. Комбінаторика дала можливість перерахувати усі ізомери даного складу.

В цю епоху дискретної математики змінилась і роль давньої області дискретної математики - комбінаторики. З області, що цікавила більшу частину авторів задач та знаходила основні застосування в кодуванні і розшифровці давні х писемностей, вона перетворилася на область, що знаходилась на магістральному шляху розвитку науки. За допомогою ЕВМ стало можливим робити перебори, що раніше потребували сотень і тисяч років. Тепер такі абстрактні образи математики, як математична логіка, загальна алгебра, формальні граматики, стали прикладними - для складання алгоритмічних мов, на яких пишуть програми для машин.  Комбінаторика епохи комп'ютерів

Основоположники комбінаторики Яков Бернулли Жозеф Луи Лагранж П'єр Фермá Леонард Эйлер Коши Огюстен

Є.П.Нелін.Алгебра: Підручник для загальноосвітніх навчальних закладів. – Харків ,2011.-447 с. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c. Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8 Р. Стенли Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2 Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975. Використані джерела: