Informatyka MIMUW

Wprowadzenie

Matematyka dyskretna to zbiorcza nazwa działów matematyki, zajmujących się badaniem struktur nieciągłych, czyli skończonych lub co najwyżej przeliczalnych. Matematyka dyskretna stała się popularna w ostatnich latach dzięki zastosowaniom w informatyce, która w sposób naturalny zajmuje się jedynie strukturami skończonymi. Oto niektóre działy i tematy mające bardzo silny związek z matematyką dyskretną:

• logika,

• teoria mnogości,

• algebra struktur skończonych,

• algebra liniowa,

• kombinatoryka,

• teoria liczb,

• algorytmika,

• teoria informacji,

• złożoność obliczeniowa,

• rachunek prawdopodobieństwa,

• teoria grafów,

• teoria i częściowych porządków.

Wiele z powyższych zagadnień będzie omawiane w trakcie późniejszych kursów. Część już poznaliście w trakcie kursów:

• Logika i teoria mnogości,

• Algebra liniowa z geometrią analityczną,

do których będziemy się często odwoływać.

W trakcie kursu Matematyka dyskretna 1 i jego rozszerzenia Matematyka dyskretna 2 skoncentrujemy się natomiast na następujących zagadnieniach:

• Matematyka dyskretna 1
  • kombinatoryka,
  • teoria grafów,
  • teoria liczb.

• Matematyka dyskretna 2:
  • zaawansowana teoria grafów,
  • teoria grup i ciał skończonych,
  • elementy kryptografii.

Notacja:

• Oznaczenia zbiorów:
  • \( \mathbb{N} \) - zbiór liczb naturalnych, czyli \( {\{ {0,1,2,\ldots} \}\ } \). Tak, tak \( 0 \) jest liczbą naturalną!
  • \( \mathbb{Z} \) - zbiór liczb całkowitych,
  • \( \mathbb{Q} \) - zbiór liczb wymiernych,
  • \( \mathbb{R} \) - zbiór liczb rzeczywistych,
  • \( \mathbb{C} \) - zbiór liczb zespolonych.

• Oznaczenia niektórych funkcji:
  • \( \log x \) - to logarytm z liczby \( x \) przy podstawie \( 10 \),
  • \( \lg x \) - to logarytm z liczby \( x \) przy podstawie \( 2 \),
  • \( \lfloor x\rfloor \) - to największa liczba całkowita nie większa od \( x \),
  • \( \lceil x\rceil \) - to najmniejsza liczba całkowita nie mniejsza od \( x \).

\( \begin{array} {|c|c|c|} \hline \textrm{Podłoga}: & \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} & \lfloor x\rfloor \textrm{to największa liczba całkowita mniejsza lub równa} \quad x \\ \hline \textrm{Sufit}: & \mathbb{R} \ni x \mapsto \lceil x\rceil \in \mathbb{Z} & \lceil x\rceil \textrm{to najmniejsza liczba całkowita większa lub równa} \quad x \\ \hline \end{array} \)

I tak na przykład:

\( \begin{array} {|c|c|c|} \hline x & \lfloor x\rfloor & \lceil x\rceil \\ \hline 2 & 2 & 2 \\ \hline -2 & -2 & -2 \\ \hline 2.5 & 2 & 3 \\ \hline -2.5 & -3 & -2 \\ \hline pi & 3 & 4 \\ \hline \end{array} \)

Przykład

Funkcji \( \lfloor x\rfloor \) w połączeniu z funkcją logarytmu można użyć do wyliczania liczby cyfr liczby naturalnej \( k \) zapisanej w układzie dziesiętnym. Jest to mianowicie

\( \lfloor \log_{10}k \rfloor+1 \)

Podobnie

\( \lfloor \log_{2}k \rfloor+1 \)

jest liczbą bitów potrzebnych do zapisania liczby naturalnej \( k \).

W dalszym ciągu przyjmujemy, że jeśli nie jest napisane jakie wartości może przyjmować zmienna, to przyjmuje ona wartości z \( \mathbb{N} \).