Matematyka dyskretna

Kurs matematyki w zakresie szkoły średniej

przedmiot obligatoryjny

godziny kontaktowe: 30 godz. wykładu + 30 godz. ćwiczeń;

zadania domowe i bieżące przygotowanie się do ćwiczeń 50 godz.

przygotowanie się do egzaminu 40 godz.

egzamin 3 godz.

Po ukończeniu kursu student:

* formułuje i dowodzi podstawowe twierdzenia arytmetyki (tw. o dzieleniu z resztą, o nieskończoności zbioru liczb pierwszych, zasadnicze tw. arytmetyki, chińskie tw. o resztach, małe twierdzenie Fermata) (K_W01);

* definiuje podstawowe struktury kombinatoryczne (permutacje, kombinacje, wariacje) (K_W01);

* rozumie terminologię teorii grafów i posługuje się nią (K_W01).

Po ukończeniu kursu student:

* zapisuje liczby w dowolnym systemie pozycyjnym (por. K_W01, KW_06);

* prowadzi obliczenia przy użyciu algorytmu Euklidesa i rozszerzonego algorytmu Euklidesa (por. K_W01);

* rozwiązuje liniowe kongruencje i układy kongruencji (por. K_W01);

* analizuje zbiory kombinatoryczne i oblicza liczbę elementów ( K_U01);

* dostrzega zależności rekurencyjne (por. K_U01);

* rozwiązuje rekurencję liniową (por. K_U01).

Po ukończeniu kursu student rozumie i posługuje się podstawową terminologią z zakresu arytmetyki, kombinatoryki i teorii grafów. (K_K05)

- wykład informacyjny (konwencjonalny)

- ćwiczeniowa

Celem zajęć jest zaznajomienie słuchaczy z podstawami teorii liczb oraz kombinatoryki. 

• Elementy teorii liczb:
  • Twierdzenie o dzieleniu z resztą, systemy pozycyjne.
  • Największy wspólny dzielnik i algorytm Euklidesa.
  • Liczby pierwsze i zasadnicze twierdzenie arytmetyki.
  • Kongruencje, chińskie twierdzenie o resztach.
  • Przykłady zastosowań teorii liczb (sumy kontrolne, szyfr RSA).
• Elementy kombinatoryki:
  • Podstawowe obiekty kombinatoryczne.
  • Metoda bijektywna.
  • Reguła włączania i wyłączania.
  • Rekurencja.
• Elementy teorii grafów

• R. Graham, D. Knuth, O. Patashnik, Matematyka konkretna, PWN, Warszawa 1996.
• V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997.
• K.A. Ross, C.R.B. Wright, Matematyka dyskretna, PWN, Warszawa 2000.
• Wilson, Wprowadzenie do teorii grafów, PWN, dowolne wydanie,
• W. KraśkiewiczNotatki z wykładu, dostępne na stronie przedmiotu w systemie moodle.

Zaliczenie ćwiczeń na podstawie prac pisemnych.

Egzamin pisemny obejmujący znajomość twierdzeń i wzorów (sformułowanie, uzasadnienie, zastosowania w problemach praktycznych i rachunkowych).