Головна

Історія виникнення і розвитку комбінаторики

  1. A) Федеральна служба по нагляду у сфері охорони здоров'я і соціального розвитку (Росздравнадзор)
  2. II. Закономірність загального руху і розвитку
  3. III. Цілі, завдання та результати розвитку фінансового ринку на період до 2020 року
  4. III.2.5. ОСОБЛИВОСТІ РОЗВИТКУ ОСОБИСТОСТІ І емоційно-Вольова СФЕРИ
  5. А) загального зв'язку, б) детермінізму, в) розвитку.
  6. Аварії та вибухи апаратів, що працюють під тиском, та причини їх виникнення
  7. Авторські теорії формування і розвитку особистості

Орієнтація на загальний розвиток особистості в процесі освіти включає елементи історії математики. Використання історико-математичного матеріалу на заняттях сприяє підвищенню їх загальної ефективності. Математика постає перед студентами несформованої наукою, а в процесі створення, в динаміці. Історія науки дозволяє учням побачити її рушійні сили, спостерігати в дії взаємозв'язок і взаємозумовленість наукового пізнання і практичної діяльності людини. «Кращий метод для передбачення майбутнього розвитку математичних наук полягає у вивченні історії та нинішнього стану цих наук» відзначав А. Пуанкаре [3].

З цієї точки зору, доцільно починати вивчення комбінаторики з історії виникнення і розвитку даної науки.

Перш, ніж та чи інша область знання сформується в особливу науку, вона проходить тривалий період накопичення емпіричного матеріалу, період розвитку в надрах іншої, більш загальної науки, і потім виділяється в самостійну науку. Не є винятком і наука про загальні закони комбінування і освіти різних конфігурацій об'єктів, що отримала назву «комбінаторика». Ще в доісторичну епоху люди зіткнулися з проблемою вибору тих чи інших об'єктів, розташування їх у певному порядку, знаходження серед різних розташувань підходящих. Наприклад, під час полювання необхідно було вибрати найкраще розташування мисливців, під час битви - розташування воїнів. Їм вдавалося знайти своє застосування і в години дозвілля. «Не можна точно сказати, коли поряд зі змаганнями в бігу, метанні диска, стрибках з'явилися гри, які вимагали вміння розраховувати, складати плани і спростовувати плани противника. Про таких іграх англійський поет У. Вордсворт писав:

 «Не потрібно нам володіти клінком.Не шукаємо слави громкой.Тот перемагає, хто знакомС мистецтвом мислити тонким» [4]

Серед речей єгипетського фараона Тутанхамона, який був похований 35 століть назад, в піраміді, були знайдені розграфлені дошки, з 3 горизонталями і 10 вертикалями, і фігурки для стародавньої гри «сенет». Її правила не дійшли до наших днів.

Надалі в таких іграх, як нарди, шахи і різних їх варіантах (китайські та японські шахи, японські шашки «го» і т.д.), необхідно було розглядати різні поєднання пересуваються фігур. І, як правило, вигравав той, хто краще розв'язував задачі з найбільш вдалому розташуванню фігур.

Питання, пов'язані з комбінаторики, зустрічаються в китайських рукописах, що відносяться до XIII XII ст. до н.е. [5] Китайці вважали, що «все в світі є поєднанням двох начал - чоловічого і жіночого, які позначалися символами - і -.». У рукописі «Ж Кім» ( «Книга перестановок») показані різні сполуки цих знаків по два і по три.

 - - -  - - -  --- -  --- -  - ---  - ---  ---  ---
 k'ienнебо  tuiпар  liогонь  chonгром  sundtnth  k'andjlf  konгора  k'unземля
 південь  Південний Схід  Схід  Північний схід  Південно-Захід  Захід  Північно-Захід  північ

«Вісім малюнків з трьох рядів символів зображували землю, гори, воду, вітер, грозу, вогонь, хмари і небо (деякі малюнки мали і інші значення)». Тому не дивно, що сума перших 8 натуральних чисел втілювала в уявленнях давніх китайців весь світ. Пізніше були складені 64 фігури, що містили п'ять рядів рисок. Мабуть, автор рукопису «Ж Кім» зауважив подвоєння числа малюнків при додаванні одного ряду символів. Це можна розглядати як перший загальний результат комбінаторики [6].

З рукописи «Ж Кім» ми можемо також дізнатися, що імператор Ію, який жив приблизно 4000 років тому, «знайшов на березі річки священну черепаху, на її панцирі був зображений малюнок з чорних і білих гуртків».

Мал. 1

Якщо замінити кожну фігурку відповідним числом, виникне така таблиця:

 рис.2

Якщо скласти числа в кожному рядку, стовпці і діагоналі, то вийде одна і та ж сума 15. У давнину китайці давали містичне тлумачення числам. Коли китайці відкрили таблицю з такими чудовими властивостями, то вона справила на них незабутнє враження. Даний малюнок назвали «ло-шу», стали вживати його при заклинаннях і вважати магічним символом. «Магічним квадратом» тепер називають будь-яку квадратну таблицю з однаковими сумами по кожному рядку, стовпці і діагоналі.

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

У XVIII столітті відбувається розквіт арабської науки. Арабами були переведені багато роботи грецьких і римських учених. Арабські алгебраїсти, при добуванні коренів, вивели формулу для ступеня суми двох чисел, яка в історії математики відома нам під назвою «біном Ньютона». Історики вважають, що цю формулу знав поет і математик Омар Хайям (XI-XII ст.) Її в XIII столітті наводить у своїх працях Насир ад-ДИНАТ-Тусі, а в XV столітті вона була досліджена Джемшид ібн Масуд аль-Каші.

Як повідомляють нам деякі європейські джерела, висхідні до арабських оригіналів, «коефіцієнти цієї формули вираховували наступним чином: брали число 10001 і зводили його в другу, третю, четверту, ..., дев'яту ступеня» [7]. Складалася таблиця, що має такий вигляд:

 1000900360084012601260084003600090001 100080028005600700056002800080001 10007002100350035002100070001 1000600150020001500060001 100050010001000050001 10004000600040001 1000300030001 100020001 10001

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

В обчисленні біноміальних коефіцієнтів не відставали від арабів і китайські математики. Уже до XIII століття в книзі алгебраиста Чжу Ши-дза "яшмових дзеркало» наводиться таблиця таких чисел, аж до n = 8. Відомо також, що «в VIII столітті астроном І. Синь обчислив кількість різних розташувань фігур в грі, яка нагадувала шахи».

Інтерес до сполученням проявлявся і в Індії. У VII столітті індійський математик Бхаскара в книзі «Лілаваті», вивчаючи проблеми комбінаторики, писав про застосування перестановок до підрахунку варіацій розміру в віршуванні, різних розташувань в архітектурі і т. П. У його роботі ми можемо знайти правила для відшукання числа перестановок і поєднань декількох предметів. При цьому їм також розглядається і випадок, коли в перестановках є повторювані елементи.

В результаті розвитку торгівлі зі Сходом на початку XII століття арабська наука проникає в Західну Європу. У той час арабське навчальний заклад закінчив Леонардо - син пізанського купця, який торгував в Алжирі. «Він написав книгу« Liber Abaci », яка вийшла 1202 році. Леонардо отримав прізвисько Фібоначчі, він привів в систему всю арифметику арабів », деякі відомості з геометрії Евкліда і додав до них результати своїх досліджень. У роботі Фібоначчі викладаються нові комбінаторні задачі, наприклад, «про відшукання найменшого кількості гир, за допомогою яких можна отримати будь-який цілий вага від 1 до 40 фунтів» [8]. Леонардо приділяв увагу і відшукання цілих рішень рівнянь. Розгляд аналогічних завдань в подальшому призвело до появи кількості натуральних рішень систем рівнянь і нерівностей, які мають право на розгляд як на одну з глав комбінаторики. Леонардо виявив нову послідовність, поряд з відомими ще з часів грецьких математиків, арифметичної і геометричної прогресій, кожен член яких виходив за певними правилами з попередніх, члени нової послідовності були пов'язані один з одним співвідношенням  . Це було першою формулою, де кожен наступний член послідовності висловлювався через два попередніх. Подібні формули отримали назву рекурентних (від лат. recurrere - Повертатися). Метод рекурентних формул виявився згодом корисний для вирішення комбінаторних завдань.

Інститути, які ще в глибоку давнину азартні ігри, які отримали особливе поширення після хрестових походів, сприяли розвитку комбінаторики.

Найбільшого поширення набула гра в кості - два або три кубика з нанесеними на них окулярами кидали на стіл, і ставку брав той, у кого випала велика сума очок. Незважаючи на грізні заборони церкви, азартні ігри все ж розвивалися. У будь-якому місті можна було спостерігати картину, яка описана в «Божественної комедії» Данте:

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

У кістки грали ще етруски жителі Мохенджо-Даро, це відомо з археологічних розкопок. Однак, ці стародавні гри не піддавалися математичному дослідженню досить довго.

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

Наприклад, при киданні двох кісток сума 6 виходить з поєднань (1, 5), (2, 4), (3, 3), а сума 7 - з поєднань (1, 0), (2, 5), (3, 4). Так як три поєднання були різні в обох випадках, то напрошувався помилковий висновок про те, що суми очок 6, 7 і 8 (також отримується з трьох поєднань кісток) повинні випадати однаково часто. Але згідно з досвідом 7 очок випадає частіше. Поєднання (3, 3) при киданні двох кісток може бути отримано єдиним способом, а поєднання (3, 4) - двома способами. Саме завдяки цьому, сума 7 випадає найбільш часто. Таким чином, виявилося, що треба враховувати не тільки поєднання очок, але і їх порядок.

Цими питаннями займалися такі відомі італійські математики XVI століття, як Д. Кардано, Н. Тарталья і ін. Найбільш повно досліджував це питання в XVII столітті Галілео Галілей, але його рукопис залишалася неопублікованою до 1718 р

У 1713 р була опублікована книга «Мистецтво припущень» Якоба Бернуллі, в якій вказувалися формули для числа розміщень з  елементів по  , Виводилися вираження для статечних сум і т. Д.

Роботи Б. Паскаля [9] і П. Ферма [10] ознаменували народження двох нових гілок математичної науки - комбінаторики і теорії ймовірностей. Раніше комбінаторні проблеми лише порушувалися в загальних працях по астрології, логіці і математиці або здебільшого ставилися до області математичних розваг. У 1666 році В. Лейбніц [11] публікує «Дисертацію про комбинаторном мистецтві», в якій вперше з'являється термін «комбінаторний». Цей математичний працю Лейбніца мав стати лише початком великої роботи, про яку він часто згадував у своїх листах і друкованих працях. В. Лейбніц планував для комбінаторики численні програми: до ігор, статистикою, до кодування і декодування, до теорії спостережень. Він вважав, що комбінаторика повинна займатися «однаковим і різним, схожим і несхожим, абсолютним і відносним розташуванням, в той час як звичайна математика займається великим і малим, одиницею і багатьом, цілим і частиною». Іншими словами, під комбінаторикою В. Лейбніц розумів приблизно те, що ми тепер називаємо дискретної математикою. До області комбінаторики В. Лейбніц відносив і «універсальну характеристику» - математику суджень, тобто прообраз нинішньої математичної логіки. Проекти В. Лейбніца здавалися нездійсненними математикам його часу, але зараз, після створення швидкодіючих обчислювальних пристроїв, багато його плани стали втілюватися у життя, а дискретна математика виросла в своєму значенні і почала змагатися з математичним аналізом.

Чудові досягнення в області комбінаторики належать одному з найвидатніших математиків XVIII століття Леонарда Ейлера [12], швейцарцю, який прожив майже все життя в Росії, де він був членом Петербурзької академії наук.

Основна частина наукової роботи Л. Ейлера присвячена математичного аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і підвів підсумки досліджень в інших областях. Але у Л. Ейлера вистачало часу поміркувати і над завданнями, які, здавалося б, не заслуговували його уваги, - про те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому ж мосту? - Чи можна поставити 36 офіцерів з 6 різних полків так, щоб в кожній шерензі і кожній колоні було по одному офіцеру кожного військового звання з кожного полку? - Скількома способами можна розбити дане число на складові і т.д. Робота про мости з'явилася зерном, з якого згодом виросли топологія і теорія графів, завдання про офіцерів виявилася зараз пов'язаної з плануванням експериментів, а методи, використані при вирішенні задачі про розбивку чисел, після тривалого і складного шляху розвитку перетворилися в науку про інтегральних перетвореннях, яка застосовується для вирішення рівнянь математичної фізики.

Після робіт Б. Паскаля і П. Ферма, Г. Лейбніца і Л. Ейлера можна було вже говорити про комбінаторики як про самостійне розділі математики, тісно пов'язаному з іншими областями науки, такими, як теорія ймовірностей, вчення про рядах і т.д. Таким чином, комбінаторика як самостійна гілка математики виникла в XVII столітті.

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

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

 



Поняття комбінаторної задачі | кінцеві безлічі

Приклади розв'язання деяких комбінаторних задач ... 97 | Операції над множинами | Декартово твір множин А і В | Завдання для самостійного рішення | Знаходження числа всіх підмножин даної множини | поняття факторіала | Правила суми і твори | Завдання для самостійного рішення | Перестановки без повторень | Завдання для самостійного рішення |

© um.co.ua - учбові матеріали та реферати