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}$.