Diskret matematik er studiet af matematiske strukturer, der er diskrete snarere end kontinuerte. I modsætning til reelle tal, der varierer "jævnt", studerer diskret matematik objekter som f.eks. hele tal, grafer og logiske udsagn. Disse objekter varierer ikke jævnt, men har tydelige, adskilte værdier. Diskret matematik udelukker derfor emner inden for "kontinuert matematik" som f.eks. regning og analyse. Diskrete objekter kan ofte tælles ved hjælp af hele tal. Matematikere siger, at dette er den gren af matematikken, der beskæftiger sig med tællelige mængder (mængder, der har samme kardinalitet som delmængder af de naturlige tal, herunder rationale tal, men ikke reelle tal). Der findes imidlertid ingen præcis, universelt anerkendt definition af begrebet "diskret matematik". Mange gange beskrives diskret matematik mindre ved det, der er inkluderet, end ved det, der er udelukket: kontinuerligt varierende mængder og beslægtede begreber.

Mængden af objekter, der studeres i diskret matematik, kan være endelig eller uendelig. Udtrykket finite matematik anvendes undertiden på dele af det diskrete matematiske område, der beskæftiger sig med finitte mængder, især de områder, der er relevante for erhvervslivet. I praksis dækker diskret matematik både teoretiske emner (f.eks. beviser og abstrakte strukturer) og anvendte emner (f.eks. algoritmeanalyse og datastrukturer).

Forskningen i diskret matematik voksede i sidste halvdel af det 20. århundrede, hvilket til dels skyldes udviklingen af digitale computere, som arbejder i diskrete trin og lagrer data i diskrete bits. Begreber og notationer fra diskret matematik er nyttige til at studere og beskrive objekter og problemer inden for datalogi, f.eks. computeralgoritmer, programmeringssprog, kryptografi, automatiseret teoremprøvning og softwareudvikling. Til gengæld er computerimplementeringer af betydning for anvendelsen af idéer fra diskret matematik på virkelige problemer, f.eks. inden for operationsforskning.

Selv om de vigtigste studieobjekter i diskret matematik er diskrete objekter, anvendes der ofte også analytiske metoder fra kontinuert matematik. Eksempler er brugen af genererende funktioner, asymptotik og analytisk kombinatorik, hvor værktøjer fra analyse og komplekse variable hjælper med at løse tælleproblemer for diskrete strukturer.

Nøglebegreber

  • Kombinatorik: tælleprincipper, permutations- og kombinationsberegninger, inklusion-eksklusion, partitionsproblemer og genererende funktioner.
  • Grafteori: grafer som modeller for netværk (noder og kanter), stier, kredse, sammenhæng, farvningsproblemer, matchning, mindste spændtræer og korteste veje.
  • Logik og bevisteknikker: udsagnslogik, prædikatslogik, induktion, konstruktion af beviser, kontraposition og modstridsbeviser — fundamentalt for korrekthed og verifikation af algoritmer.
  • Diskret sandsynlighed: sandsynlighedsrum med tællelige udfald, forventning, varians, sandsynlighedsfordelinger og stokastiske processer med diskret tid.
  • Tal- og modulær aritmetik: restklasser, kongruenser, primtal og anvendelser i kryptografi (f.eks. RSA) og hashing.
  • Teori om formal sprog og automater: regulære og kontekstfrie sprog, endelige automater, pushdown-automater og deres relation til kompilatorer og mønstergenkendelse.
  • Kombinatoriske designs og koder: fejlretning og detektion, kodeteori, blokdesigns og anvendelser i kommunikation og lagring.
  • Algoritmer og kompleksitet: analyseteknikker for køretid og plads, store-O notation, NP-sværhed og klassifikation af problemer efter beregningsmæssig vanskelighed.

Anvendelser i datalogi

  • Algoritmer og datastrukturer: valg af effektive strukturer (lister, træer, heaps, grafer) og bevis for korrekthed og kompleksitet. Eksempler: søgealgoritmer, sortering, grafalgoritmer som BFS, DFS, Dijkstras og Kruskal.
  • Kryptografi og sikkerhed: brug af primtal, modulær aritmetik og diskrete logaritmeproblemer til at bygge sikre krypteringssystemer, digitale signaturer og nøgleudveksling.
  • Datakommunikation og netværk: grafer som modeller for netværkstopologier, routing, flowproblemer og ressourceallokering.
  • Databaser og informationssøgning: indeksering, hashing, søgealgoritmer og teorier om kompleksitet for forespørgsler.
  • Formel verifikation og automatiseret bevisførelse: anvendelse af logik, satser og model-checking for at sikre software- og hardware- korrekthed.
  • Fejlretning og lagring: koder til pålidelig datalagring og overførsel (f.eks. Reed–Solomon, Hamming-koder).
  • Maskinlæring og dataanalyse: diskrete optimeringsmetoder, grafbaserede algoritmer og probabilistiske modeller på diskrete datasæt.

Metoder og værktøjer

Diskret matematik bruger en række teknikker til at formulere og løse problemer. Blandt de mest brugte er matematiske beviser (direkte, induktion), tællemetoder, anvendelse af rekurrence-relationsløsning, genererende funktioner, greedy-algoritmer, dynamisk programmering og reduktioner mellem problemer for at vise kompleksitet. Computerværktøjer som CAS-systemer, SAT-solvere og automatiserede teorembevisere supplerer håndværket og gør det muligt at kontrollere større strukturer eller udforske konstruktioner eksperimentelt.

Grænser og samspil med andre felter

Selvom fokus er på diskrete objekter, er grænsen til kontinuert matematik ofte flydende. Fagområder som spektral grafteori anvender lineær algebra og analyse til at studere grafer; diskret Fourier-transform og numeriske metoder binder diskret og kontinuert teori sammen. Derudover er der stærke forbindelser til operationsanalyse, statistik, og matematisk logik.

Uddannelse og videre læsning

Diskret matematik er ofte et obligatorisk eller tidligt fag på datalogiske og ingeniørmæssige uddannelser, netop fordi det giver fundamentale værktøjer til at tænke præcist om algoritmer, datastrukturer og beregningsproblemer. For videre fordybelse kan man studere avancerede emner som kombinatorisk optimering, kompleksitetsteori, kodeteori, og formelle bevismetoder.

Kort sagt: Diskret matematik er en bred og praktisk gren af matematikken, som leverer både grundlæggende teorier og konkrete redskaber til at modellere, analysere og løse problemer i datalogi og beslægtede områder.