Matematyka dyskretna

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$p jest liczbą pierwszą, to $a^{p-1}\equiv1 (\text{mod }p)$a^{p-1}\equiv1 (\text{mod }p) dla $a$a niepodzielnego przez $p$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.