Matematyka dyskretna to dziedzina matematyki, która zajmuje się badaniem struktur i obiektów o charakterze dyskretnym, czyli takich, które są skończone lub przeliczalne. W przeciwieństwie do analizy matematycznej, która zajmuje się ciągłymi funkcjami i przestrzeniami, matematyka dyskretna skupia się na obiektach, które można policzyć lub opisać za pomocą skończonych zbiorów. Jest to kluczowa dziedzina dla informatyki, kryptografii, teorii grafów, logiki i kombinatoryki.
Kluczowe zagadnienia matematyki dyskretnej:
Teoria liczb:
Badanie własności liczb całkowitych, takich jak podzielność, liczby pierwsze, kongruencje.
Algorytm Euklidesa – znajdowanie największego wspólnego dzielnika (NWD).
Małe twierdzenie Fermata – jeśli p jest liczbą pierwszą, to a^{p-1}\equiv1 (\text{mod }p) dla a niepodzielnego przez p.
Kombinatoryka:
Zliczanie obiektów i konfiguracji, np. permutacje, kombinacje, wariacje.
Teoria grafów:
Badanie grafów, czyli struktur składających się z wierzchołków połączonych krawędziami.
Grafy skierowane i nieskierowane – różnice w kierunkach krawędzi.
Drzewa – grafy bez cykli.
Kolorowanie grafów – przypisywanie kolorów wierzchołkom tak, aby sąsiednie wierzchołki miały różne kolory.