Дискретна математика та її історія

ВСТУП

 

В останні роки інженери-математики, які займаються прикладними дослідженнями, все більше використовують апарат дискретної математики. Це пояснюється необхідністю створення і експлуатації сучасних ЕОМ, засобів передачі та обробки інформації, автоматизованих систем управління та проектування.

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

В даний час в навчальних планах різних інженерних і особливо ІТ спеціальностей з'явилася дисципліна "Дискретна математика".

Дискретна математика - самостійний напрям сучасної математики. Вона вивчає математичні моделі об'єктів, процесів, залежностей, існуючих в реальному світі, з якими мають справу в техніці, інформатиці та інших галузях знань. Ідея навчання за допомогою комп'ютера з'явилася давно. Перші спроби відносяться до кінця 50-х років. У той час уже була можливість "спілкування" людини з комп'ютером за допомогою використовуваного в якості пристрою введення-виведення телеграфного апарата-телетайпа. З тих пір у всьому світі ведуться безперервні наукові пошуки вирішення проблеми ефективного і дешевого способу навчання за допомогою комп'ютера.[1]

Особливої актуальності для викладачів шкіл і вищих учбових закладів у набувають прикладні програми для допомоги студентам і викладачам у різноманітних розрахунках. Подібних програмних засобів існує безліч і програмісти-розробники готові будувати нові варіанти так званих авторських систем.

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

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

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

Тема дипломної роботи – «Програма для обрахунку вибірок».

Об'єкт дослідження – сучасні методи та засоби комп’ютерного проектування і розробки прикладного програмування.

Предмет дослідження – створенняпрограми для розв’язання комбінаторних задач.

Мета роботи – розробити комп'ютерний програму для студентів і викладачів, яка б відрізнявся від існуючих своєю простотою і зручністю.

Завдання:

1. Проаналізувати стан дослідження даної проблеми в різних

інформаційних джерелах.

2. Обґрунтувати доцільність вибору середовища для створення даної програми.

3. Створити програму для розрахунку вибірок.

4. Зробити опис того, як користуватися розробленою програмою.

5. Зробити аналіз дослідної експлуатації (тестування програмного продукту) і можливих застосувань.

АНАЛІЗ ПРОБЛЕМНОЇ ГАЛУЗІ ТА ПОСТАНОВКА ЗАДАЧІ

 

Дискретна математика та її історія

 

 

Математика є частиною нашої культури. Людина не може вважати себе шірокообразованним, не маючи уявлення про сучасній математиці, її ролі в повсякденному житті, в науці.

Математика (від грецького mathema - наука) - наука, в якій вивчаються просторові форми і кількісні відношення. Математика зародилася в далекій давнині і від народження умовно ділиться на дискретну і континуальну (безперервну) математику. До континуальної математики відноситься все, що містить ідеї теорії меж і безперервності. Все інше - це дискретна математика (discrete mathematics). Головною її специфікою є дискретність, тобто антипод безперервності.

Дискретна математика - область математики, що вивчає дискретні математичні об'єкти і структури [10]. Її елементи виникли в далекій давнині. З незапам'ятних часів відомі комбинаторно-логічні завдання, вирішення яких пов'язане з перебором комбінацій дискретних об'єктів і логічним аналізом виникають варіантів. Деякі з них збереглися до нашого часу в цікавій математиці у вигляді задач-головоломок.

Дискретні системи з найдавніших часів застосовуються в обчислювальній практиці. Широко відомі винайдені в давнину різні системи подання чисел і пов'язані з ними алгоритми виконання арифметичних операцій, рішення рівнянь і т.д., повсюдно були поширені дискретні обчислювальні пристосування: абак, різні види рахунків. Розвиваючись паралельно з іншими розділами математики, елементи дискретної математики були їх складовою частиною. Найважливіші приклади дискретних математичних об'єктів: натуральний ряд чисел; кінцеве безліч елементів довільної природи; функція (відображення) з кінцевого безлічі в кінцеве безліч; слово (послідовність символів) і формальну мову (безліч слів) в кінцевому алфавіті; кінцевий граф і інші. Змістовно дискретний об'єкт зазвичай мислиться як що складається з строго відокремлених один від одного неподільних частин. Об'єкти розглядають як дискретні також в тих випадках, коли з яких-небудь причин відволікаються від властивих їм властивостей безперервності. Слід підкреслити, що розподіл математики на «безперервну» і «дискретну» вельми умовно, тому що вся математика єдина і пронизана глибокими аналогіями. Подібні ідеї і конструкції однаково успішно працюють в різних її розділах. З одного боку, відбувається обмін ідеями і методами між ними, а з іншого - часто виникає необхідність дослідження моделей, що володіють як дискретними, так і безперервними властивостями одночасно. Наприклад, апарат теорії множин і теорії графів використовується при вивченні не тільки дискретних, але і безперервних об'єктів.

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

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

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

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

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

Розвиток дискретної математики, її багатогранні зв’язки з іншими галузями науки і безпосередньо виробництвом вплинули і на нові підходи до питань викладання математики. Хочемо ми того чи ні, але в співвідношенні розділі математики які вивчаються у вищих навчальних закладах та в школі, повинна значно посилитись роль дискретних розділів на противагу неперервним. Більше того, таке посилання буде досить сприятливим для цілей викладання, оскільки дискретна математика, через свій скінчений характер, значно доступніша для початківців, ніж класичний математичний аналіз; вона скоріше може зацікавити тих, хто навчається, викличе менше труднощів і тому більше підходить для викладання навіть на ранніх стадіях навчання.

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

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

Наявність знань з дискретної математики у інженерів-програмістів важко переоцінити, бо їх глибоке ґрунтовне знання грає велику роль у фундаментальній математичній підготовці – як в плані формування у студентів певного рівня математичної культури, так і в плані формування в них наукового світогляду, особливо з таких компонентів, як розуміння сутності прикладної і практичної спрямованості навчання математиці, оволодіння методом математичного моделювання, вмінням здійснювати між предметні зв’язки[1].

Дискретна математика має такі розділи:

- математична логіка;

- математична кібернетика;

- теорія функціональних схем;

- спільна алгебра;

- комбінаторика;

- комбінаторна логіка;

- вибірки;

- теорія графів;

- машинна арифметика;

- теорія алгоритмів;

- теорія ігор;

- теорія кодування;

- теорія автоматів;

- теорія множин;

- теорія чисел;

- теорія формальних граматик;

- вираховуюча геометрія;

- теорія булевих функцій;

- логічне програмування;

- функціональне програмування;

- булева алгебра;

- комбінаційна логіка;

- секвенціальна логіка;

- асинхронна логіка;

- математична лінгвістика;

- теорія штучного інтелекту;

- теорія розкладів[6].

Комбінаторика

 

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

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

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

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

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

Комбінаторика як наука стала розвиватися в VIII ст. одночасно з виникненням теорії ймовірностей, так як для вирішення ймовірностних задач, необхідно було підрахувати кількість різних комбінацій елементів. Перші наукові дослідження по комбінаториці провів італійський вчений Дж. Кардано, Н. Тартальє (близько 1499-1557), Г. Галілей (1564-1642) та французький вчений В. Паскаль (1623-1662). Комбінаторику, як самостійний розділ математики, першим став розглядати німецький вчений Г. Лейбніц в своїй роботі «Про мистецтво комбінаторики», опублікований в 1666 році. Він також вперше ввів термін «Комбінаторика».

У 1896 році американський математик Еліаким Гастінгс Мур (1862-1932) ввів термін «тактична конфігурація» в статті «Tacticalmemoranda», розуміючи під цим терміном систему n множин, які мають, відповідно, а1, а2, …, an елементів. До тактичних конфігурацій Мур відносить поєднання, розміщення, системи рішень задачі Кіркмана про 15 учнів, підгрупи деяких груп. Він демонструє широкий спектр задач по геометрії, теорії груп, які приводять до тактичних положень або використовують тактичні положення.

Термін «тактика» ввів в математику англійський математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 році. Сильвестр визначає тактику як розділ математики, вивчаючий положення елементів один відносно одного. В цій сфері цього розділу, знаходиться, на думку Сильвестра, теорія груп, комбінаторний аналіз та теорія чисел.

В сучасному суспільстві з розвитком обчислювальної техніки комбінаторика «добилася» нових успіхів. Так, за допомогою ЕОМ була розв’язана комбінаторна задача, відома під назвою «проблема чотирьох кольорів»: вдалося доказати, що будь-яку мапу можна розмалювати чотирма кольорами так, щоб ніякі дві країни, які мають спільну границю, не були пофарбовані в один і той же колір[2].

Комбінаторика, пройшовши багатовіковий шлях розвитку, знайшовши власні методи дослідження, з одного боку, широко використовується при рішенні задач алгебри, геометрії, аналізу, з іншого боку, сама використовує геометричні, аналітичні та алгебраїчні методи дослідження. В кінці XVIII ст. вчені, які відносяться до школи комбінаторики Гинденбурга, спробували побудувати спільну комбінаторну теорію, використовуючи нескінченні ряди. Дослідники цієї школи вивчили велику кількість перетворень рядів: множення, ділення, піднесення до степеня, виведення коренів, перетворення рядів, розкладання трансцендентних функцій[3].

В наш час комбінаторика має велике значення в різних сферах. Із комбінаторними величинами мають справу представники різних спеціальностей: вченому – хіміку, біологу, конструктору, диспетчеру, і т.д. Підсилення інтересу до комбінаторики в останній час пояснюється бурхливим розвитком кібернетик та обчислювальної техніки[4].

Таким чином, комбінаторика – це розділ дискретної математики, орієнтований на вирішення задач вибору та положенням елементів деякої множини у відповідності із заданими правилами та обмеженнями. Кожне таке правило вирішує спосіб побудови деякої комбінаторної конфігурації, тому комбінаторний аналіз (комбінаторика) займається вивченням властивостей комбінаторних конфігурацій, умовами їх існування, алгоритмами побудови та оптимізацією цих алгоритмів[5].