Історія розвитку комбінаторики та деякі її застосування, Детальна інформація

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

Шифрами користувались не тільки дипломати і заколотники, але й самі вчені. До XVII ст. майже не існувало наукових журналів. Вчені дізнавалися про досягнення своїх колег з книг або приватних листів. Це створювало великі труднощі при опублікуванні нових результатів – адже друкування книг займало роки, а написати про свої відкриття приватним листом було ризиковано – хтось міг присвоїти досягнення, і потім довелося б доводити, що це він не сам вигадав, а дізнався з отриманого листа. Тому часто виникали суперечки на тему переваг. Ще в кінці XVII ст. йшли довгі суперечки на тему пріоритетів між Ньютоном та Лейбніцом (про те, хто першим відкрив диференціальне та інтегральне числення), Ньютоном та Гуком (хто першим сформулював закон всесвітнього тяжіння) та ін.

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

Для того, щоб забезпечити пріоритет і не допустити передчасного розголосу отриманих результатів, вчені в короткій формі формулювали суть відкриття, а потім переставляли в ній літери і відправляли листа з переставленими літерами своїм колегам. Такі тексти з переставленими літерами називаються анаграми. Наприклад слово „Москва” та „смоква” – анаграми. Коли ж друкувалась книга з детальним викладенням результатів, в ній давалася і розшифровка анаграми.

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

Ієрогліфи та клинопис

Навички в розгадці складних шифрів допомогли ученим, коли археологи почали відкопувати камені та черепи з таємними знаками – письменністю, що замовкла декілька тисячоліть тому. Одним з найкращих успіхів у розшифровці було читання французьким філологом Жаном Франсуа Шампольним ієрогліфів, якими писали єгиптяни ще до того, як виникла наука у древніх греків.

У Шампольна були попередники – шведський археолог Д. Окерблад та англійський фізик т. Юнг, які розшифровували єгипетські тексти за допомогою комбінаторного аналізу. В їхніх руках були „білінгви” – написи, які були зроблені одночасно на єгипетській та грецькій мовах. Порівнюючи обидва тексти та помічаючи повторність груп знаків, Окерблад упізнав деякі знаки так званого демотичного письма – пізньої стадії розвитку єгипетського письма. А творець хвильової оптики Томас Юнг полюбляв відпочити від роздумів на фізичні теми і займався то каліграфією, то складанням алфавітів іноземних мов, то... танцями на слабо натягнутому канаті, - на думку Юнга все, що могла зробити одна людина, могла повторити інша. У 1814 р. він взяв з собою на канікули древньоєгипетський папірус і спробував прочитати його. Не маючи потрібної філологічної підготовки, шляхом комбінаторного він отримав цікаві результати, а потім спробував прочитати ієрогліфи. Деяких успіхів він досяг і тут, але далося в знаки недостатнє знання мов – він шукав ієрогліфи не тільки для приголосних, але й для голосних літер, а в єгипетській мові голосні опускаються. Лише Шампольну, котрий поєднав незаурядний комбінаторний дар з глибокими знаннями філології, вдалося прочитати ієрогліфи.

Складність задачі, що постала перед Шампольном, доповнювалась незнанням мови написів та змісту знаків. Проте, виділивши знаки, які на грецькій мові означали імена царів, Шампольна помітив, що деякі знаки в іменах фараонів Птоломея та Клеопатри співпадають. Так були знайдені звучання ієрогліфів, що означали літери „л” та „п” (до цього місця дійшов і Юнг). А потім Шампольн прочитав імена римських імператорів Тиберія та Трояна, давніх фараонів Рамсеса та Тутмеса – ключ до читання ієрогліфів, втрачений декілька тисячоліть тому, був знову отриманий.

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

Ще тісніше пов’язана з комбінаторикою розшифровка клинописів. Історикам вдалося вияснити, що ці надписи було зроблено в епоху Ахеменідів, що правили в Ірані два з половиною тисячоліття тому назад. Були зроблені і припущення про мову надписів. А потім комбінаторний аналіз тексту виявив часте повторення певної групи знаків з семи знаків. Інколи ця група повторювалася двічі підряд з невеликими змінами. І датський вчений Мюнтер вирішив, що ця група означає слово „цар”, а повторення двічі – „цар царів”. Але дізнатись про звучання цих звуків Мюнтер не зумів. Це зробив молодий німецький учитель Гротефенд. Любитель різноманітних головоломок та таємного письма, одного дня він посперечався, що розшифрує клинопис. Аналізуючи поєднання звуків біля титулів „цар” та „цар царів”, Гротефенд побачив, що деякі з них зустрічаються у різних позиціях. Звідси було зроблено висновок, що це ім’я царя, яке в іншій позиції означає „син царя такого-то”. Це дозволило упізнати групу символів і для слова „син”. В одному місці після цієї групи знаків не стояло слово „царя”. Значить, вирішив Гротефенд, цар, про якого тут йдеться, не був сином царя – це був сам засновник династії Дарій, син Гістаспа. А так як Дарій був батьком Ксеркса, то у Гротефенда в руках були звукові значення для знаків, що входили в імена „Гістасп”, „Дарій”, „Ксеркс” – початок розшифровки клинопису розпочався.

Комбінаторика дозволила прочитати і крито-мікенське лінійне письмо. Перші надійні основи розшифровки цієї писемності заклала Аліса Д. Кобер, яка захистила у 1932 р. докторську дисертацію по математиці у Колумбійському університеті. Поряд з дослідженнями по чистій математиці вона багато сил приділяла розшифровці давніх писемностей. Вивчивши знаки критського письма, Аліса встановила, що це письмо складається зі складів. Далі вона помітила, що в текстах, котрі вона досліджує деякі слова зустрічаються у трьох різних формах, які відрізняються одна від одної декількома останніми знаками. А далі вона почала складати „лінгвістичні рівняння” для складів, що дозволили їй знайти склади з однаковими приголосними, але з різними голосними, і однаковими голосними, і різними приголосними. В результаті Кобер отримала координатну сітку, в якій замість осей координат стояли номери голосних і приголосних літер. У цієї сітки був лише один недолік – ніхто не знав, які саме голосні та приголосні формують цю систему координат.

Лише через два роки після смерті дослідниці молодий англійський архітектор Майкл Вентріс, розширюючи її координатну сітку, спробував вгадати значення деяких голосних – число голосних менше числа приголосних, і розбір краще починати з них. Одна із спроб закінчилася вдало – текст заговорив на мові, досить нагадувавши грецьку. Але це не була класична грецька мова „Іліади” та „Одіссея”, а грецька мова більш ранньої епохи. Вентрису допоміг завершити розшифровку видатний знавець ранньої грецької мови Чедвік. Використовуючи імена царів та списки географічних назв, дослідники розшифровували один склад за іншим. А потім почалася швидка розшифровка – три десятки знаків отримали своє значення. Це був повний тріумф комбінаторного підходу, що був заснований наступним методом, сформульованим Вентрисом: „при спробі дешифрувати документи на незнайомій мові, що були написані невідомим листом, перший крок складається в отриманні тих фактів, які самі даються в руки при розгляді наявних документів. Суть другого кроку у тому, що дослідник шляхом ретельного аналізу і логічної дедукції виявляє, які висновки можна зробити з цих основних фактів”.

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

Комбінаторика в біології

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

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

Однією з найбільш складних загадок в біології ХХ ст. була будова „ниток життя” – молекул білка і нуклеїнових кислот. Виявилося, що молекули білка – це об’єднання декількох довгих ланцюгів, що складалися з 20 амінокислот.

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

Найбільшим досягненням комбінаторного підходу до проявів життя можна вважати розшифровку будови дезоксирибонуклеїнової кислоти (ДНК), зроблену в Кембриджі Ф. Криком та Дж. Уотсоном у 1953 р.. було відомо, що ДНК грає важливу роль в наслідуванні властивостей організмів. Це залучало до її вивчення багатьох дослідників.

Хімічний пасьянс

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

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

І все ж Мендєлєєв спробував піти забороненим шляхом, групуючи схожі елементи один з одним. Він зробив і наступний, найскладніший крок, спробував розмістити в правильному порядку і групи. Як писав пізніше сам Дмитро Іванович: „шукати щось, хоча б гриби, чи якусь залежність, не можна інакше, як дивлячись та пробуючи”. Для того щоб „дивитися і пробувати”, він почав підбирати, написавши на окремих картках назви елементів з їхніми атомними масами та властивостями даного елемента, схожі елементи та атомні маси.

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

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

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

Комбінаторика епохи комп’ютерів

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

Положення справ змінилося після того, як були створені ЕВМ. Тепер такі абстрактні образи математики, як математична логіка, загальна алгебра, формальні граматики, стали прикладними – для складання алгоритмічних мов, на яких пишуть програми для машин, потрібні спеціалісти саме з цих областей математики. Важливу роль почали відігравати різноманітні схеми, дослідження сітківок та їх властивості. Додатки до економіки поставили перед математиками нові типи проблем, що відносяться до математичного програмування та до цілочисельного програмування (якщо при рішенні задачі виявиться, що най економніше буде грузити по 3,5 автомашини, то рішення доведеться переглянути).