Дискре́тна матема́тика — галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру. До таких структур може бути віднесено скінченні групи, скінченні графи, а також деякі математичні моделі перетворювачів інформації, скінченні автомати, машини Тюрінга тощо. Розділ дискретної математики, що вивчає їх, називається скінче́нною матема́тикою. Іноді саме це поняття розширюють до дискретної математики. Крім вказаних скінченних структур, дискретна математика вивчає деякі системи алгебри, нескінченні графи, обчислювальні схеми певного вигляду, клітинні автомати тощо.
Історія дискретної математики
Історія дискретної математики пов'язана з розв'язанням складних проблем, які привернули увагу в цій області. В теорії графів багато досліджень було викликано спробами довести теорему чотирьох кольорів, вперше сформульовану 1852 року, але не доведену до 1976 (Кеннет Аппель і Вольфганг Хакен — довели, використовуючи суттєву допомогу комп'ютера).
У логіці прикладом таких задач є друга проблема зі списку Давида Гільберта, який був представлений в 1900 році. В ній йдеться про доведення, що арифметичні аксіоми є несуперечливими. Друга теорема Геделя про неповноту формалізованої арифметики, доведена 1931 року, показала, що це довести неможливо — принаймні, в межах арифметики. Десята проблема Гільберта повинна була визначити, чи має дане діофантове рівняння цілі коефіцієнти та цілі розв'язки. У 1970 році Юрій Матіясевич довів, що цього не може бути.
Необхідність розкрити німецькі коди Другої світової війни призвела до досягнень в області криптографії та теоретичної інформатики, а також до появи першої програмованої цифрової електронної обчислювальної машини, розробленої в Англії. У той же час, військові вимоги мотивували досягнення в галузі дослідження операцій. Холодна війна означала, що криптографія залишалася важливою наукою з фундаментальними досягненнями, такими як шифрування з відкритим ключем, які розроблялися в наступних десятиліттях. Дослідження операцій залишається важливим розділом, як інструмент управління бізнесом і проєктами. Телекомунікаційна промисловість також спонукала прогрес у дискретній математиці, особливо в теорії графів та теорії інформації. Формальна перевірка тверджень в логіці була необхідною для розробки програмного забезпечення .
В даний час однією з найвідоміших відкритих проблем в теоретичній інформатиці є P = NP проблема, яка включає в себе відношення між класами складності P та NP. Математичний інститут Clay запропонував приз $ 1 млн. USD за перше правильне доведення, поряд із призами для шести інших математичних проблем.
Теоретична інформатика
Теоретична інформатика включає в себе області дискретної математики, що мають відношення до обчислень. В значній мірі вона спирається на теорію графів та логіку. В межах теоретичної інформатики вивчаються алгоритми для обчислення математичних результатів. Обчислюваність вивчає, які задачі можуть бути обчислені в принципі, і близько пов'язана з логікою, а складність визначає час, якого ці обчислення потребують. Теорія автоматів і теорія формальної мови близько пов'язані з обчислюваністю. Мережі Петрі та числення процесів використовуються при моделюванні обчислювальних систем, а методи дискретної математики використовуються в аналізі електричних схем VLSI.
При розв'язуванні геометричних задач застосовують алгоритми обчислювальної геометрії, тоді як до представлення зображень використовують дискретний аналіз комп'ютерного зображення. Теоретична інформатика також включає вивчення різних неперервних обчислювальних тем.
Теорія інформації
Теорія інформації — це розділ кібернетики, в якому за допомогою математичних методів вивчаються способи вимірювання інформації та методи її кодування з метою стиснення і надійної передачі каналами зв'язку.
При формальному поданні знань кожному досліджуваному об'єктові ставиться у відповідність числовий код, зв'язки між об'єктами так само подаються кодами. Для переведення неформальних даних до формального цифрового вигляду застосовуються спеціальні таблиці кодування. Найпростіший приклад такої таблиці — ASCII (American Standard Code for Information Interchange), що керує символами чисел від 0 до 127.
Інформація може бути двох видів: дискретна (цифрова) та неперервна (аналогова). Неперервна інформація — це дані, що одержані при неперервному за часом процесі змінювання деякої випадкової величини і описуються неперервними (аналоговими) функціями.
Дискретна інформація — це цифрові дані, одержані в результаті квантування (дискретизації) неперервної величини за часом, рівнем або тим і іншим одночасно. Дискретну інформацію зберігати й обробляти набагато простіше, оскільки вона являє собою послідовність чисел. У двійковій системі числення дискретна інформація являє собою послідовність 0 та 1.
Логіка
Математична логіка (теоретична логіка, символічна логіка) — розділ математики, що вивчає докази і питання підстав математики. «Предмет сучасної математичної логіки різноманітний.». Відповідно до визначення П. С. Порецького, «математична логіка є логіка по предмету, математика за методом». Відповідно до визначення Н. І. Кондакова, «математична логіка — другий, після традиційної логіки, щабель у розвитку формальної логіки, що застосовує математичні методи та спеціальний апарат символів і досліджує мислення за допомогою числень (формалізованих мов).» Це визначення відповідає визначенню С. К. Кліні: математична логіка — це «логіка, що розвивається за допомогою математичних методів». Також А. А. Марков визначає сучасну логіку «точною наукою, яка застосовує математичні методи». Всі ці визначення не суперечать, а доповнюють одне одного.
Застосування в логіці математичних методів стає можливим тоді, коли судження формулюються деякою точною мовою. Такі точні мови мають дві сторони: синтаксис і семантику. Синтаксисом називається сукупність правил побудови об'єктів мови (зазвичай званих формулами). Семантикою називається сукупність угод, що описують наше розуміння формул (або деяких з них) і дозволяють вважати одні формули правильними, а інші — ні.
Важливу роль в математичній логіці мають поняття дедуктивної теорії та обчислення. Обчисленням називається сукупність правил виводу, що дозволяють вважати деякі формули виведеними. Правила виведення поділяються на два класи. Одні з них безпосередньо кваліфікують деякі формули як виведені. Такі правила виведення прийнято називати аксіомами. Інші ж дозволяють вважати виведеними формули , синтаксично пов'язані деяким заздалегідь певним способом з кінцевими наборами виведених формул. Широко застосовуваним правилом другого типу є правило modus ponens: якщо виведено формули , то виводиться й формула .
Відношення числень до семантики виражається поняттями семантичної придатності та семантичної повноти обчислення. Обчислення О називається семантично придатним для мови М, якщо будь-яка вивідна в О формула мови М є правильною. Аналогічно, обчислення О називається семантично повним в мові М, якщо будь-яка правильна формула мови М є вивідною в О.
Математична логіка вивчає логічні зв'язки та відношення, що лежать в основі логічного (дедуктивного) виводу з використанням мови математики.
Багато які з розглянутих в математичній логіці мов мають семантично повні й семантично придатні обчислення. Зокрема, відомий результат К. Геделя про те, що так зване класичне числення предикатів є семантично повним і семантично придатним для мови класичної логіки предикатів першого порядку. З іншого боку, є чимало мов, для яких побудова семантично повного і семантично придатного обчислення неможливе. В цій області класичним результатом є теорема Геделя про неповноту, яка стверджує неможливість семантично повного й семантично придатного числення для мови формальної арифметики.
Варто зазначити, що на практиці множина елементарних логічних операцій є обов'язковою частиною набору інструкцій всіх сучасних мікропроцесорів, і відповідно входить до мови програмування. Це є одним з найважливіших практичних додатків методів математичної логіки, що вивчаються в сучасних підручниках інформатики.
Теорія множин
В основі теорії множин лежать первинні поняття: множина та елемент множини. Елемент множини перебуває щодо множини у відношенні бути елементом множини (позначається як Символ (від — «бути») введений італійським математиком Джузеппе Пеано. — «x є елемент множини A»). Серед похідних понять найважливішими є наступні: порожня множина — множина, яка не містить елементів, позначається зазвичай ; підмножина і надмножина — множина, яка складається тільки з елементів іншої множини, та множина, до якої належать усі елементи іншої множини, відповідно; сімейство множин; простір (універсум) — множина, що є надмножиною всіх множин; конституента.
Над множинами визначено наступні операції: об'єднання (або сума) (позначається як ); перетин (або добуток) (позначається як ); різниця (позначається як рідше ); симетрична різниця (позначається як рідше ). доповнення (позначається як або );
Для множин визначено наступні бінарні відношення: відношення рівності (позначається як ); відношення включення (позначається як або ).
Комбінаторика Комбінато́рика (комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.
Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття.
Комбінаторика пов'язана з багатьма іншими розділами математики. Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво». Іноді під комбінаторикою розуміють ширший розділ дискретної математики, що включає теорію графів.
Приклади комбінаторних конфігурацій і задач
Для формулювання та розв'язання комбінаторних задач використовують різні моделі комбінаторних конфігурацій. Прикладами комбінаторних конфігурацій є:
Розміщення з елементів по — упорядкований набір з різних елементів деякої -елементної множини;
Перестановка з елементів (наприклад чисел ) — всякий упорядкований набір з цих елементів. Перестановка також є розміщенням з елементів по ;
Поєднання з по — набір елементів, вибраних з даних елементів. Набори, що відрізняються тільки порядком проходження елементів (але не складом), вважаються однаковими, цим поєднання відрізняється від розміщення;
Композиція числа — всяке представлення у вигляді впорядкованої суми цілих додатних чисел;
Розбиття числа — всяке представлення у вигляді невпорядкованої суми цілих додатних чисел.
Прикладами комбінаторних завдань є: Скількома способами можна розмістити предметів в скриньках так, щоб виконувалися задані обмеження? Скільки існує функцій з -елементної множини в -елементній, що задовольняють заданим обмеженням? Скільки існує різних перестановок з гральних карт? Відповідь: ( факторіал), тобто, або приблизно 8,0658 × 1067. При грі в кості кидаються два кубики, і кількість очок, що випали, додаються; скільки існує таких комбінацій, що сума очок на верхніх гранях дорівнює дванадцяти? Розв'язання: Кожен можливий результат відповідає функції (Аргумент функції — це номер кубика, значення — число на верхній грані). Очевидно, що лише дає потрібний результат . Таким чином існує лише одна функція, яка ставить у відповідність 1 число , і число . Або, іншими словами, існує лише одна комбінація, така, що сума очок на верхніх гранях дорівнює дванадцяти.
Теорія графів