Дискретна математика

Дискретна математика изучава и графове као на слици због занимљивих математичких својстава као и због практичне примене на реалне проблеме и развој рачунарских алгоритама.

Дискретна математика је област математике која проучава структуре које су у својој основи дискретне у смислу да не подржавају или не захтевају појам континуалности.[1][2] Већина ако не сви објекти који се проучавају у дискретној математици су пребројиви скупови, попут целих бројева, коначних графова, и формалних језика.[3][4] Дискретна математика је добила на значају у протеклих неколико деценија услед својих примена у рачунарству. Концепти и нотације из дискретне математике су корисни за изучавање и описивање објеката или проблема у области рачунарских алгоритама и програмских језика. Неке од области чијим изучавањем се бави дискретна математика су: релације, функције, Булова алгебра, групе и групоиди, прстени и поља, полиноми, комплексни бројеви, конструкција поља, системи линеарних једначина, матрице и детерминанте.[5][6]

У универзитетским наставним плановима и програмима, „Дискретна математика“ се појавила током 1980-их, у почетку као курс за подршку рачунарству; њен садржај је у то време био донекле насумичан. Наставни план и програм се након тога развио у сарадњи са напорима ACM и MAA у курс који је у основи намењен развоју математичке зрелости код студената прве године; стога је то данас предуслов за математичке смерове и на неким универзитетима.[7][8] Појавили су се и неки уџбеници дискретне математике за средњошколски узраст.[9] На овом нивоу, дискретна математика се понекад посматра као припремни курс, слично предкалкулусу у овом погледу.[10]

Велики изазови, прошли и садашњи

Многа истраживања у теорији графова била су мотивисана покушајима да се докаже да се све карте, попут ове, могу обојити коришћењем само четири боје, тако да ниједна област исте боје не дели ивицу. Кенет Апел и Волфганг Хакен су то доказали 1976. године.[11]

Историја дискретне математике укључивала је низ изазовних проблема који су усмерили пажњу у области овог поља. У теорији графова, многа истраживања била су мотивисана покушајима да се докаже теорема о четири боје, која је први пут изречена 1852. године, али није била доказана све до 1976. (од стране Кенета Апела и Волфганга Хакена, уз значајну помоћ рачунара).[11]

У логици, други проблем на листи отворених проблема Дејвида Хилберта представљеној 1900. године био је да се докаже да су аксиоми аритметике конзистентни. Друга Геделова теорема о непотпуности, доказана 1931. године, показала је да то није могуће – барем не унутар саме аритметике. Хилбертов десети проблем је био да утврди да ли дата полиномска Диофантова једначина са целобројним коефицијентима има целобројно решење. Јуриј Матијасевич је 1970. године доказао да се то не може учинити.

Потреба за разоткривањем немачких кодова у Другом светском рату довела је до напретка у криптографији и теоријској компјутерској науци, са првим програмабилним дигиталним електронским рачунаром који је развијен у енглеском Блечли парку под вођством Алана Тјуринга и његовог семиналног дела, О израчунљивим бројевима.[12] Истовремено, војни захтеви су мотивисали напредак у истраживању операција. Хладни рат је значио да је криптографија остала важна, са фундаменталним напретком као што је криптографија са јавним кључем који се развијао у наредним деценијама. Операциона истраживања су остала важна као алат у пословању и управљању пројектима, а метод критичног пута развијен је 1950-их. Телекомуникациона индустрија је такође мотивисала напредак у дискретној математици, посебно у теорији графова и теорији информација. Формална верификација исказа у логици била је неопходна за развој софтвера система критичних за безбедност, и напредак у аутоматизованом доказивању теорема је био вођен овом потребом.

Неколико области дискретне математике, посебно теоријске рачунарске науке, теорија графова и комбинаторика, су важне у решавању изазовних проблема биоинформатике повезаних са разумевањем стабла живота.[13]

Тренутно, један од најпознатијих отворених проблема у теоријској информатици је проблем P = NP, који укључује однос између класа сложености P и NP. Клејов математички институт понудио је награду од милион долара за први тачан доказ, заједно са наградама за шест других математичких проблема.[14]

Види још

Референце

  1. ^ Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall, 2008.
  2. ^ Franklin, James (2017). „Discrete and continuous: a fundamental dichotomy in mathematics”. Journal of Humanistic Mathematics. 7 (2): 355—378. doi:10.5642/jhummath.201702.18. Приступљено 30. 6. 2021. 
  3. ^ Weisstein, Eric W. „Discrete mathematics”. MathWorld. 
  4. ^ https://cse.buffalo.edu/~rapaport/191/S09/whatisdiscmath.html accessed 16 Nov 18
  5. ^ Biggs, Norman L. (2002), Discrete mathematics, Oxford Science Publications (2nd изд.), New York: The Clarendon Press Oxford University Press, стр. 89, ISBN 9780198507178, MR 1078626, „Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets. 
  6. ^ Brian Hopkins, Resources for Teaching Discrete Mathematics, Mathematical Association of America, 2008.
  7. ^ Levasseur, Ken; Al Doerr. Applied Discrete Structures. стр. 8. 
  8. ^ Albert Geoffrey Howson, ур. (1988). Mathematics as a Service Subject. Cambridge University Press. стр. 77—78. ISBN 978-0-521-35395-3. 
  9. ^ Rosenstein, Joseph G. Discrete Mathematics in the Schools. American Mathematical Soc. стр. 323. ISBN 978-0-8218-8578-9. 
  10. ^ „UCSMP”. uchicago.edu. 
  11. ^ а б Wilson, Robin (2002). Four Colors SufficeНеопходна слободна регистрација. London: Penguin Books. ISBN 978-0-691-11533-7. 
  12. ^ Hodges, Andrew (1992). Alan Turing: The Enigma. Random House. 
  13. ^ Hodkinson, Trevor R.; John A. N. Parnell (2007). Reconstruction the Tree of Life: Taxonomy And Systematics of Large And Species Rich Taxa. CRC PressINC. стр. 97. ISBN 978-0-8493-9579-6. 
  14. ^ „Millennium Prize Problems”. 2000-05-24. Архивирано из оригинала 08. 01. 2008. г. Приступљено 2008-01-12. 

Литература

Спољашње везе