Matematika diskrete

Matematika diskrete është studimi i strukturave matematikore që mund të konsiderohen "diskrete" (në një mënyrë analoge me variablat diskrete, që kanë një korrespondencë një-me-një( bijeksion) me numrat natyrorë), në vend që të konsiderohen "të vazhdueshme" (në mënyrë analoge me funksionet e vazhdueshme). Objektet e studiuara në matematikën diskrete përfshijnë numra të plotë, grafikë dhe pohime në logjikë. ^[1][2][3] Në të kundërt, matematika diskrete përjashton temat në "matematikën e vazhdueshme" siç janë numrat realë, kalkulusi ose gjeometria euklidiane. Objektet diskrete shpesh mund të numërohen nga numra të plotë; më formalisht, matematika diskrete është karakterizuar si dega e matematikës që merret me bashkësi të numërueshme ^[4] (bashkësi të fundme ose bashkësi me të njëjtën kardinalitet si numrat natyrorë). Megjithatë, nuk ka një përkufizim të saktë të termit "matematikë diskrete". ^[5]

Grafe të tilla janë ndër objektet e studiuara nga matematika diskrete, për vetitë e tyre interesante matematikore, dobinë e tyre si modele të problemeve të botës reale dhe rëndësinë e tyre në zhvillimin e algoritmeve kompjuterike.

Bashkësia e objekteve të studiuara në matematikën diskrete mund të jetë e fundme ose e pafundme. Ka raste ku termi matematikë e fundme ndonjëherë zbatohet për pjesë të fushës së matematikës diskrete që merren me bashkësi të fundme, veçanërisht ato fusha që lidhen me biznesin.

Kërkimi në matematikën diskrete u rrit në gjysmën e dytë të shekullit të 20-t për shkak të zhvillimit të kompjuterëve dixhitalë të cilët veprojnë në hapa "diskret" dhe ruajnë të dhënat në bit "diskret". Konceptet dhe shënimet nga matematika diskrete janë të dobishme në studimin dhe përshkrimin e objekteve dhe problemeve në degët e shkencës kompjuterike, siç janë algoritmet kompjuterike, gjuhët e programimit, kriptografia, vërtetimi i automatizuar i teoremave dhe zhvillimi i softuerëve. Poashtu, zbatimet kompjuterike janë të rëndësishme në zbatimin e ideve të ndryshme nga matematika diskrete në problemet e botës.

Edhe pse objektet kryesore të studimit në matematikën diskrete janë objektet diskrete, shpesh përdoren edhe metodat analitike nga matematika e " vazhdueshme".

Në kurrikulat e ndryshme, matematika diskrete u shfaq fillimisht si një kurs mbështetës i shkencave kompjuterike; përmbajtja e saj ishte në një far mënyre e rastësishme në atë kohë. Kurrikula më pas është zhvilluar në bashkëpunim me përpjekjet e ACM dhe MAA në një kurs që në thelb synon të zhvillojë pjekurinë matematikore tek studentët e vitit të parë; prandaj, sot është një parakusht në disa universitete të ndryshme.^{[6] [7]} Disa tekste shkollore të matematikës diskrete në nivel të shkollës së mesme janë shfaqur gjithashtu. Në këtë nivel, matematika diskrete nganjëherë shihet si një kurs përgatitor, si parakalkulusi në këtë drejtim. ^[8]

Çmimi Fulkerson është dhënë për punime të shquara në matematikën diskrete.

Temat

Shkenca teorike kompjuterike

Kompleksiteti studion kohën e marrë nga algoritmet, siç është kjo rutina e renditjes .

Gjeometria kompjuterike zbaton algoritme kompjuterike për përfaqësimet e objekteve gjeometrike .

Shkenca teorike e kompjuterave përfshin fusha të matematikës diskrete që lidhen me informatikën. Ajo mbështetet shumë në teorinë e grafikut dhe logjikën matematikore. Brenda shkencës teorike të kompjuterave përfshihet edhe studimi i algoritmeve dhe strukturave të të dhënave. Llogaritshmëria studion atë që mund të mblidhet apo zbritet në parim dhe ka lidhje të ngushta me logjikën, përkundrazi kompleksiteti studion kohën, hapësirën dhe burimet e tjera të marra nga llogaritjet. Teoria e automateve dhe teoria e gjuhës formale janë të lidhura ngushtë përmes llogaritshmërisë. Rrjetet Petri dhe algjebrat e proceseve përdoren për të modeluar sistemet kompjuterike, dhe metodat nga matematika diskrete përdoren për të analizuar qarqet elektronike VLSI. Gjeometria llogaritëse zbaton algoritme të ndryshme në problemet gjeometrike dhe përfaqësimet e objekteve gjeometrike, ndërsa analiza e imazheve kompjuterike i zbaton ato në përfaqësimet e imazheve digjitale. Shkenca teorike e kompjuterave përfshin gjithashtu studimin e temave të ndryshme të vazhdueshme llogaritëse.

Teoria e informacionit

Kodet ASCII për fjalën "Wikipedia", të dhëna këtu në format binar, ofrojnë një mënyrë për të përfaqësuar fjalën në teorinë e informacionit, si dhe për algoritmet e përpunimit të informacionit.

Teoria e informacionit përfshin përcaktimin sasior të informacionit. Ngushtësisht e lidhur është teoria e kodimit e cila përdoret për të hartuar metodën më të shpejtë dhe më të besueshme të transmetimit dhe ruajtjes së të dhënave. Teoria e informacionit përfshin gjithashtu tema të vazhdueshme si: sinjalet analoge, kodimi analog, enkriptimi analog .

Logjikë

Artikulli kryesor: Mathematical logic

Logjika është studimi i parimeve të arsyetimit dhe inferencës së vlefshme, si dhe i qëndrueshmërisë, saktësisë dhe plotësisë . Për shembull, në shumicën e sistemeve të logjikës (por jo në logjikën intuitioniste ) ligji i Peirce-it ((( P→Q)→P)→P) është një teoremë. Për logjikën klasike, ai mund të verifikohet lehtësisht me një tabelë të vërtetësisë. Studimi i provës matematikore është veçanërisht i rëndësishëm në logjikë dhe është grumbulluar në vërtetimin e automatizuar të teoremave dhe verifikimin formal të softuerit.

Formulat logjike kanë struktura diskrete, siç janë edhe provat, të cilat formojnë pemë të fundme ^[9] ose, më përgjithësisht, struktura grafike aciklike të drejtuara^[10][11] (me çdo hap të inferencës që kombinon një ose më shumë degë premisash për të dhënë një përfundim). Vlerat e vërtetësisë së formulave logjike zakonisht formojnë një bashkësi të fundme, përgjithësisht të kufizuara në dy vlera: e vërtetë dhe e gabuar, por logjika mund të jetë edhe me vlera të vazhdueshme. Koncepte të tilla si pemët e provave të pafundme ose pemët e derivimit të pafundëm janë studiuar gjithashtu,^[12] p.sh. logjika infinitare .

Teoria e bashkësive

Artikulli kryesor: Set theory

Teoria e bashkësive është dega e matematikës që studion bashkësitë, të cilat janë koleksione objektesh, të tilla si {e kaltër, e bardhë, e kuqe} ose bashkësia e të gjithë numrave të thjeshtë. Bashkësitë pjesërisht të renditura dhe bashkësitë me relacione të tjera kanë zbatime në disa fusha.

Në matematikën diskrete, bashkësitë e numërueshme janë fokusi kryesor. Fillimi i teorisë së bashkësive si degë e matematikës zakonisht shënohet nga puna e Georg Cantor, i cili ka bërë dallimin midis llojeve të ndryshme të bashkësive të pafundme, i motivuar nga studimi i serive trigonometrike, dhe zhvillimi i mëtejshëm i teorisë së bashkësive të pafundme është jashtë fushëveprimit të matematikës diskrete. Në të vërtetë, puna bashkëkohore në teorinë përshkruese të bashkësive përdor gjerësisht matematikën tradicionale e vazhdueshme.

Kombinatorika

Artikulli kryesor: Combinatorics

Kombinatorika studion mënyrat se si strukturat diskrete mund të kombinohen ose rregullohen. Kombinatorika enumerative përqendrohet në numërimin e numrit të objekteve të caktuara kombinatorike p.sh. mënyra dymbëdhjetëfish ofron një kornizë të unifikuar për numërimin e permutacioneve, kombinimeve dhe ndarjeve. Kombinatorika analitike merret me numërimin (përcaktimin e numrit) e strukturave kombinatorike duke përdorur mjete nga analiza komplekse dhe teoria e probabilitetit. Në dallim nga kombinatorika enumerative e cila përdor formula të qarta kombinatorike dhe funksione gjeneruese për të përshkruar rezultatet, kombinatorika analitike arrijë të marrë formula asimptotike. Kombinatorika topologjike merret me përdorimin e teknikave nga topologjia dhe topologjia algjebrike/topologjia kombinatorike në kombinatorikë. Teoria e projektimit është një studim i projektimeve kombinatorike, të cilat janë koleksione të nëngrupeve me veti të caktuara të kryqëzimit. Teoria e ndarjes studion probleme të ndryshme të numërimit dhe asimptotikës që lidhen me ndarjet e numrave të plotë, dhe është e lidhur ngushtë me seritë q, funksionet speciale dhe polinomet ortogonale. Fillimisht një pjesë e teorisë dhe analizës së numrave, teoria e ndarjes tani konsiderohet pjesë e kombinatorikës ose një fushë e pavarur. Teoria e renditjes është studimi i bashkësive pjesërisht të renditura, si të fundme poashtu dhe të pafundme.

Teoria e grafeve ka lidhje të ngushta me teorinë e grupeve . Ky graf i tetraedrit të cunguar lidhet me grupin alternativ A4 _.

Teoria e grafikeve, studimi i grafeve dhe rrjeteve, shpesh konsiderohet si pjesë e kombinatorikës, por është rritur mjaftueshëm dhe është dalluar mjaftueshëm, me llojet e veta të problemeve të ndryshme, për t'u konsideruar si një lëndë e etme.^[13]Grafikat janë një nga objektet kryesore të studimit në matematikën diskrete. Ato janë ndër modelet më të përhapura të strukturave natyrore dhe të bëra nga njeriu. Ato mund të modelojnë shumë lloje marrëdhëniesh dhe dinamikash procesesh në sistemet fizike, biologjike dhe sociale. Në shkencën kompjuterike, ato mund të përfaqësojnë rrjete komunikimi, organizimin e të dhënave, rrjedhën e llogaritjes etj. Në matematikë ato janë të dobishme në gjeometri dhe në pjesë të caktuara të topologjisë, p.sh. teoria e nyjeve. Teoria algjebrike e grafeve ka lidhje të ngushta me teorinë e grupeve dhe teoria topologjike e grafeve ka lidhje të ngushta me topologjinë. Gjithashtu ka grafe të vazhdueshme; megjithatë, për pjesën më të madhe, kërkimi në teorinë e grafeve bie në fushën e matematikës diskrete.

Teoria e numrave

Spirali Ulam i numrave, me pikselë të zinj që tregojnë numra të thjeshtë . Ky diagram lë të kuptohet modelet në shpërndarjen e numrave të thjeshtë.

Teoria e numrave merret me vetitë e numrave në përgjithësi, veçanërisht numrat e plotë. Ajo ka zbatime në kriptografi dhe kriptanalizë, veçanërisht në lidhje me aritmetikën modulare, ekuacionet diofantine, kongruencat lineare, kuadratike, numrat e thjeshtë dhe testimin e primalitetit. Aspekte të tjera diskrete të teorisë së numrave përfshijnë gjeometrinë e numrave. Në teorinë analitike të numrave, përdoren edhe teknika nga matematika e vazhdueshme. Temat që shkojnë përtej objekteve diskrete përfshijnë numrat transcendentalë, përafrimin diofantin, analizën p-adike dhe fushat e funksioneve.

Strukturat algjebrike

Artikulli kryesor: Abstract algebra

Strukturat algjebrike shfaqen si shembuj diskretë dhe shembuj të vazhdueshëm në plot raste të ndryshme. Algjebrat diskrete përfshijnë: algjebrën booleane të përdorur në portat logjike dhe programim; algjebrën relacionale të përdorur në bazat e të dhënave; versionet diskrete dhe të fundme të grupeve, unazave dhe fushave janë të rëndësishme në teorinë e kodimit algjebrik; gjysmëgrupet dhe monoidet diskrete shfaqen në teorinë e gjuhëve formale .

Analogët diskretë të matematikës së vazhdueshme

Në matematikën e vazhdueshme, ekzistojnë shumë koncepte dhe teori që kanë versione diskrete, siç janë kalkulusi diskret, transformimet diskrete të Furierit, gjeometria diskrete, logaritmet diskrete, gjeometria diferenciale diskrete, kalkulusi i jashtëm diskret, teoria diskrete e Morsit, optimizimi diskret, teoria e probabilitetit diskret, shpërndarja diskrete e probabilitetit, ekuacionet e diferencës, sistemet dinamike diskrete.

Kalkulusi i diferencave të fundme, analiza diskrete dhe kalkulusi diskret

Në llogaritjen diskrete dhe llogaritjen e diferencave të fundme, një funksion i përcaktuar në një interval të numrave të plotë zakonisht quhet sekuencë. Një sekuencë mund të jetë një sekuencë e fundme nga një burim të dhënash ose një sekuencë e pafundme nga një sistem dinamik diskret. Një funksion i tillë diskret mund të përcaktohet në mënyrë eksplicite nga një listë, ose nga një formulë për termin e tij të përgjithshëm (termi i n-t), ose mund të jepet në mënyrë implicite nga një relacion përsëritjeje ose ekuacion diference. Ekuacionet e diferencave janë të ngjashme me ekuacionet diferenciale, por zëvendësojnë diferencimin duke marrë diferencën midis termave ngjitur; ato mund të përdoren për të përafruar ekuacionet diferenciale ose të studiohen vetëm ato. Shumë pyetje dhe metoda që kanë të bëjnë me ekuacionet diferenciale kanë homologë për ekuacionet e diferencave. Aty ku ka transformime integrale në analizën harmonike për të studiuar funksione të vazhdueshme ose sinjale analoge, ka transformime diskrete për funksione diskrete ose sinjale dixhitale. Përveç hapësirave metrike diskrete, ka hapësira më të përgjithshme diskrete topologjike, hapësira metrike të fundme, hapësira topologjike të fundme .

Kalkulusi i shkallës kohore është një mbledhje e teorisë së ekuacioneve të diferencës me atë të ekuacioneve diferenciale e cila ka zbatime në fushat që kërkojnë modelim të njëkohshëm të të dhënave diskrete dhe të vazhdueshme. Një mënyrë tjetër për të krijuar një situatë të tillë është nocioni i sistemeve dinamike hibride.

Gjeometri diskrete

Gjeometria diskrete dhe gjeometria kombinatorike kanë të bëjnë me vetitë kombinatorike të koleksioneve diskrete të objekteve gjeometrike. Një temë e vjetër në gjeometrinë diskrete është vendosja e pllakave në plan.

Në gjeometrinë algjebrike, koncepti i një lakore mund të zgjerohet në gjeometri diskrete duke marrë spektrat e unazave polinomiale mbi fusha të fundme si modele të hapësirave afine mbi atë fushë, dhe duke lejuar që nënvarietetet ose spektrat e unazave të tjera të ofrojnë lakoret që shtrihen në atë hapësirë. Edhe pse hapësira në të cilën shfaqen lakoret ka një numër të fundëm pikash, lakoret nuk janë aq shumë grup pikash sesa analoge të lakoreve në mjedise të vazhdueshme. Për shembull, çdo pikë e formës ${\displaystyle V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}$ për ${\displaystyle K}$ një fushë mund të lexohet ose si ${\displaystyle \operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K}$, një pikë, një pikë së bashku me një afërsi përreth saj. Varietetet algjebrike gjithashtu kanë një nocion të përcaktuar mirë të hapësirës tangjente të quajtur hapësira tangjente Zariski, duke i bërë shumë karakteristika të analizës matematike të zbatueshme edhe në mjedise të fundme.

Modelim diskret

Në matematikën e aplikuar, modelimi diskret është analogu diskret i modelimit të vazhdueshëm. Në modelimin diskret, formulat diskrete i përshtaten të dhënave. Një metodë e zakonshme në këtë formë modelimi është përdorimi i marrëdhënies së përsëritjes. Diskretizimi ka të bëjë me procesin e transferimit të modeleve dhe ekuacioneve të vazhdueshme në homologë, shpesh me qëllim lehtësimin e llogaritjeve duke përdorur përafrime. Analiza numerike ofron një shembull të rëndësishëm.

Sfidat

Shumë kërkime në teorinë e grafeve u motivuan nga përpjekjet për të vërtetuar se të gjitha hartat, si kjo, mund të ngjyrosen duke përdorur vetëm katër ngjyra në mënyrë që asnjë zonë me të njëjtën ngjyrë të mos ndajë një skaj. Kenneth Appel dhe Wolfgang Haken e vërtetuan këtë në vitin 1976. ^[14]

Historia e matematikës diskrete ka përfshirë një numër sfidash të cilat kanë përqendruar vëmendjen brenda fushës. Në teorinë e grafeve, shumë kërkime u motivuan nga përpjekjet për të vërtetuar teoremën e katër ngjyrave, e deklaruar për herë të parë në vitin 1852, por që nuk u vërtetua deri në vitin 1976 (Kenneth Appel dhe Wolfgang Haken, duke përdorur ndihmë të konsiderueshme kompjuterike). ^[14]

Në logjikë, problemi i dytë në listën e problemeve të hapura të David Hilbertit të paraqitura në vitin 1900 ishte të vërtetonte se aksiomat e aritmetikës janë te pandryshueshme. Teorema e dytë e paplotësisë së Gödelit, tregoi se kjo nuk ishte e mundur të paktën jo brenda vetë aritmetikës. Problemi i dhjetë i Hilbertit ishte të përcaktonte nëse një ekuacion polinomial i dhënë Diofantine me koeficientë të plotë ka një zgjidhje të plotë. Në vitin 1970, Yuri Matiyasevich vërtetoi se kjo nuk mund të bëhej .

Nevoja për të thyer kodet gjermane në Luftën e Dytë Botërore deyroi në përparime në kriptografi dhe shkencën teorike të kompjuterave, me kompjuterin e parë dixhital elektronik të programueshëm që u zhvillua në Bletchley Park të Anglisë me udhëzimin e Alan Turing dhe veprës së tij themelore, Mbi Numrat e Llogaritshëm.^[15] Lufta e Ftohtë bëri që kriptografia të mbetej e rëndësishme, me përparime themelore si kriptografia me çelës publik që u zhvilluan në vijim. Industria e telekomunikacionit ka motivuar gjithashtu përparime në matematikën diskrete, veçanërisht në teorinë e grafeve dhe teorinë e informacionit. Verifikimi formal i pohimeve në logjikë ka qenë i nevojshëm për zhvillimin e softuerëve të sistemeve kritike për sigurinë, dhe përparimet në vërtetimin e automatizuar të teoremave janë nxitur nga kjo nevojë.

Gjeometria kompjuterike ka qenë një pjesë e rëndësishme e grafikës kompjuterike e përfshirë në videolojërat dhe mjetet e dizajnit të ndihmuara nga kompjuteri .

Disa fusha të matematikës diskrete, veçanërisht shkenca teorike kompjuterike, teoria e grafeve dhe kombinatorika, janë të rëndësishme në zgjedhjen e problemeve sfiduese të bioinformatikës që lidhen me kuptimin e pemës së jetës. ^[16]

Një nga problemet më të famshme të hapura në shkencën teorike të kompjuterave është problemi P = NP, i cili përfshin marrëdhënien midis klasave të kompleksitetit P dhe NP . Instituti i Matematikës Clay ka ofruar një çmim prej 1 milion dollarë amerikanë për provën e parë të saktë, së bashku me çmime për gjashtë probleme të tjera matematikore.^[17]

Shih edhe

• Stampa:Portal Mathematics

• Skema e matematikës diskrete
• Cyberchase, një shfaqje që u mëson fëmijëve matematikë diskrete