|
|||||||
ВСТУПОсновні способи подання інформації є дискретними: слова і інші конструкції мов і граматик, табличні дані, дані статистичні, тощо.Переклад слова дискрет – частка, тобто, дискретна інформація – це інформація у вигляді виділених часток. Математичні методи обробки, аналізу та перетворень і є предметом дискретної математики (іноді вживаються назви «скінчена математика», або навіть «конкретна математика»). Історія дискретної математики пов'язана з розв'язанням складних проблем, що зосереджувались на розгляді областей в межах площини. В теорії графів багато досліджень було викликано спробами довести теорему чотирьох кольорів, вперше сформульовану в 1852 році, але не доведену до 1976 (Кеннет Аппель і Вольфганг Хакен — довели використовуючи суттєву допомогу комп'ютера). У логіці прикладом таких задач є друга проблема зі списку Давида Гільберта, який був представлений в 1900 році. В ній йдеться про доведення, що арифметичні аксіоми послідовні. Друга теорема Геделя про неповноту формалізованої арифметики, доведена в 1931 році, показала, що це було неможливо — принаймні, як мінімум не в межах арифметичної послідовності. Десята проблема Гільберта повинна була визначити, чи має дане діофантове рівняння цілі коефіцієнтами та цілі рішення. У 1970 році Юрій Матіясевіч довів, що цього не може бути. Необхідність розбити німецькі коди Другої світової війни призвело до досягнень в області криптографії та теоретичної інформатики, з першою запрограмованою цифровою електронною обчислювальною машиною, розробленою в Англії. У той же час, військові вимоги мотивували досягнення в галузі дослідження операцій. Холодна війна означала, що криптографія залишалася важливою наукою, з фундаментальними досягненнями, такі як шифрування з відкритим ключем, які розробляються в наступних десятиліттях. Дослідження операцій залишаються важливими в якості інструменту управління бізнесом і проектами. Телекомунікаційна промисловість також мотивувала прогрес у дискретній математиці, особливо в теорії графів і теорії інформації. Формальна перевірка тверджень в логіці була необхідна для розробки програмного забезпечення критичних для безпеки систем. В даний час одним з найбільш відомих відкритих проблем в теоретичній інформатиці є P = NP проблема, яка включає в себе відношення між класами складності P і NP. Математичний інститут Clay запропонував $ 1 млн. USD приз за перший правильний доказ, поряд з призами для шести інших математичних проблем.
|
|||||||
|