Matematyka dyskretna

Wykład ma charakter podstawowy i bazuje na efektach kształcenia uzyskanych przez studentów w ramach zajęć kursowych z logiki i teorii mnogości. Obejmuje podstawy kombinatoryki i teorii grafów, modele i metody rekurencyjne. Ćwiczenia mają za zadanie doprowadzić do umiejętności dobierania odpowiedniego modelu dyskretnego do sytuacji praktycznej, a także do umiejętności stosowania odpowiednich technik obliczeniowych, formułowania argumentacji i dowodów.

Student:

zna i rozumie pojęcie dowodu indukcyjnego, kombinatorycznego, konstruktywnego, nie wprost,

zna i rozumie pojęcie rekurencji, zna i rozumie podstawowe przykłady ciągów rekurencyjnych i ich związek z podstawowymi algorytmami;

zna i rozumie pojęcie rekurencji liniowej, pojęcie przestrzeni rozwiązań i jej wymiaru,

zna i rozumie metodę wielomianu charakterystycznego w odniesieniu do rekurencji liniowej jednorodnej i niejednorodnej,

zna i rozumie notację "O duże", w odniesieniu do ciągów i do czasu działania algorytmu,

zna i rozumie pojęcie permutacji, wariacji z powtórzeniami i bez, kombinacji z powtórzeniami i bez, oraz sposoby ich obliczania w sytuacjach praktycznych,

zna i rozumie pojęcie grafu i modele jego opisu,

zna podstawowe twierdzenia dotyczące stopni wierzchołków w grafie, izomorfizmu grafów, istnienia / nieistnienia ścieżek i cykli Eulera oraz Hamiltona, planarności grafu,

zna i rozumie pojęcie drzewa i podstawowe własności drzew.

MA1_W01, MA1_W02, MA1_W05, MA1_W06)

potrafi w sposób zrozumiały, w mowie i na piśmie, przedstawiać poprawne

rozumowania matematyczne, formułować twierdzenia i definicje;

posługuje się rachunkiem zdań i kwantyfikatorów; potrafi poprawnie używać

kwantyfikatorów także w języku potocznym;

umie prowadzić łatwe i średnio trudne dowody metodą indukcji zupełnej;

potrafi definiować funkcje i relacje rekurencyjne;

potrafi rozwiązywać rekurencje liniowe stopnia k,

umie modelować i rozwiązywać problemy dyskretne,

umie ocenić podstawowe własności grafów.

(MA1_U01, MA1_U02, MA1_U03, MA1_U29)

jest gotów do identyfikacji ograniczeń własnej wiedzy i dalszego

samokształcenia;

jest gotów formułować pytania, służące pogłębieniu własnego zrozumienia

danego tematu lub odnalezieniu brakujących elementów rozumowania;

jest przygotowany do samodzielnego wyszukiwania informacje w literaturze,

także w językach obcych.

(MA1_K01, MA1_K02, MA1_K06)