Matematyka dyskretna 1000-711MAD
Metody zliczania: indukcja, rozwiązywanie równań rekurencyjnych, liczenie sum skończonych, asymptotyka.
Obiekty kombinatoryczne: permutacje, grafy, drzewa, słowa.
Teoria mnogości: zbiory, funkcje, relacje (w tym porządki i relacje równoważności), moce zbiorów.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Student uzyskujący zaliczenie przedmiotu:
- potrafi przeprowadzać dowody indukcyjne, zliczać obiekty, liczyć skończone sumy, rozwiązywać równania rekurencyjne, kombinatorycznie dowodzić własności dwumianu Newtona (K_W06);
- rozumie pojęcia zbiorów, funkcji, relacji i mocy zbiorów, potrafi analizować bijekcje, określać liczność zbioru ilorazowego i klas równoważności, zna i potrafi korzystać z twierdzenia Cantora-Bernsteina (K_W06);
- zna podstawowe struktury danych takie jak drzewa i grafy (K_W06);
- potrafi zastosować powyższą wiedzę i umiejętności do analizowania złożoności prostych algorytmów i badania rozmiaru danych, rozumie potrzebę takiej analizy (K_K02).
Kryteria oceniania
Zaliczenie ćwiczeń na podstawie prac domowych, ocena na podstawie wyników kolokwiów i egzaminu pisemnego.
Literatura
Kenneth A. Ross, Charles R. B. Wright, Matematyka dyskretna, Wydawnictwa Naukowe PWN, 2008
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwa Naukowe PWN, 2008
działy: Matematyka dyskretna 1 oraz Logika i teoria mnogości na http://wazniak.mimuw.edu.pl/
Wiktor Marek, Janusz Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach, PWN, 1991
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: