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

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

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

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

Гісторыя[правіць | правіць зыходнік]

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

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

Агульныя падыходы[правіць | правіць зыходнік]

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

Літаратура[правіць | правіць зыходнік]

  • Дыскрэтная матэматыка // Беларуская энцыклапедыя: У 18 т. Т. 6: Дадаізм — Застава / Рэдкал.: Г. П. Пашкоў і інш. — Мн.: БелЭн, 1998. С. 293.
  • Яблонский С.В. Введение в дискретную математику. М., 1979.
  • Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика: Пер. с англ. М., 1980.
  • Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность: Пер. с англ. М., 1985.