Дыскрэтная матэматыка

Дыскрэ́тная матэма́тыка – разьдзел матэматыкі, які займаецца вывучэньнем дыскрэтных структураў (г. зн. структураў, да якіх ня можа ўжывацца паняцьце непарыўнасьці, гл. дыскрэтнасьць). Частка дыскрэтнай матэматыкі, якая вывучае канечныя структуры (напрыклад, канечныя групы, графы, машыны Т’юрынга), называецца канечнай матэматыкай.

У пашыраным сэнсе дыскрэтная матэматыка падзяляецца на тэорыю лікаў, вылічальную матэматыку, матэматычную лёгіку, камбінаторны аналіз, а таксама новыя кірункі дасьледаваньняў — тэорыю графаў, тэорыю кадаваньня, цэлалікавае праграмаваньне, тэорыю аўтаматаў, раскладаў, ЭВМ, праграмаваньня й інш., у якіх абʼекты дасьледаваньняў маюць дыскрэтны характар.

Гісторыя

Элемэнты дыскрэтнай матэматыкі ўзьніклі ў глыбокай старажытнасьці й разьвіваліся паралельна зь іншымі разьдзеламі матэматыкі. Напрыклад, тагачасныя тыповыя задачы, зьвязаныя з уласьцівасьцямі цэлых лікаў (вытокі тэорыі лікаў): адшуканьне альгарытмаў складаньня і множаньня натуральных лікаў (Эгіпет, 2-е тысячагодзьдзе да н.э.), задачы падсумоўваньня й дзялімасьці натуральных лікаў у пітагарэйскай школе (VI стагодзьдзе да н. э.).

У Беларусі дасьледаваньні па пытаньнях дыскрэтнай матэматыкі пачаліся ў канцы 1950-х гадоў па ініцыятыве акадэміка Д. А. Супруненкі і вядуцца ў Інстытуце матэматыкі і Абʼяднаным інстытуце праблемаў інфарматыкі (ранейшая назва — Інстытут тэхнічнай кібэрнетыкі) НАН Беларусі і БДУ.

Агульныя падыходы

На практыцы найчасьцей адначасова прысутнічаюць уласьцівасьці неперарыўнасьці й дыскрэтнасьці, канечнасьці й бесканечнасьці; пры рашэньні канкрэтных задач шырока выкарыстоўваецца прыём замены неперарыўнай мадэлі яе дыскрэтным аналягам. У дыскрэтнай матэматыцы разам з пабудовай альгарытмаў рашэньня асобных задач выяўляюцца пытаньні альгарытмічнай вырашальнасьці, ацэнкі вылічальнай складанасьці альгарытмаў, выяўленьня цяжкавырашальных задачаў і іншыя.

Літаратура

На беларускай мове

• Дыскрэтная матэматыка // Беларуская энцыклапедыя: У 18 т.. — Мн.: 1998 Т. 6: Дадаізм — Застава. — С. 293.

На расейскай мове

• Яблонский С. В. Введение в дискретную математику. — М., 1979. (рас.)
• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика: Пер. с англ. — М., 1980. (рас.)
• Пападимитриу Х. Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность: Пер. с англ. — М., 1985. (рас.)