Matematyka dyskretna I
Informacje ogólne
Kod przedmiotu: | WCYIXCNI-MDI |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Matematyka dyskretna I |
Jednostka: | Wydział Cybernetyki |
Grupy: | |
Punkty ECTS i inne: |
2.00
LUB
3.00
LUB
5.00
LUB
4.00
(w zależności od programu)
|
Język prowadzenia: | polski |
Forma studiów: | niestacjonarne |
Rodzaj studiów: | I stopnia |
Rodzaj przedmiotu: | obowiązkowy |
Forma zajęć liczba godzin/rygor: | W 12/x; C 8/+ |
Przedmioty wprowadzające: | Brak przedmiotów kształcenia wprowadzających |
Autor: | dr inż. Krzysztof Pszczoła |
Bilans ECTS: | Udział w wykładach: 12h Udział w ćwiczeniach: 8h Samodzielne studiowanie tematyki wykładów: 24h Samodzielne przygotowanie do ćwiczeń: 24h Przygotowanie do egzaminu: 8h Udział w egzaminie / kolokwium: 2H Sumaryczne obciążenie pracą studenta: 78h, 3 ECTS |
Skrócony opis: |
Przedmiot ma na celu wprowadzenie podstawowych pojęć z zakresu podstaw matematyki, obejmujących logikę formalną, teorię mnogości, teorię predykatów, metody wnioskowania ze szczególnym uwzględnieniem zasady indukcji, relacje ze szczególnym uwzględnieniem relacji równoważności i relacji porządkującej, oraz rekurencję. |
Pełny opis: |
Wykład: 1 Podstawowe oznaczenia i pojęcia Prezentacja przedmiotu. Oznaczenia zbiorów, spójników logicznych, działań na zbiorach, kwantyfikatorów, funkcji, wybranych funkcji całkowitoliczbowych. Podstawowe właściwości działań na zdaniach, wartościach logicznych i zbiorach. Interpretacja typowych zapisów formalnych. 1 2 Rachunek zdań i kwantyfikatorów Zdania, spójniki, zmienne zdaniowe, formuły logiki zdaniowej, funkcje zdaniowe. Postacie normalne formuł. Tautologie rachunku zdań. Formuły równoważne. Zbiory spójników funkcjonalnie pełne. Funkcje zdaniowe. Kwantyfikator ogólny i egzystencjalny. Zasięg kwantyfikatora, zmienne związane i wolne. Kwantyfikatory o ograniczonym zakresie. Tautologie rachunku kwantyfikatorów. 1 3 Metody wnioskowania, indukcja Reguły dowodzenia. Reguła modus ponens, modus tollens, sylogizmy, schemat dowodu niewprost i dowodu apagogicznego. Kwadrat logiczny. Zasada minimum i maksimum. Zasada indukcji matematycznej. Zasada indukcji zupełnej. 2 4 Rachunek zbiorów Sposoby prezentacji zbioru. Zbiór pusty. Równość i inkluzja zbiorów. Działania na zbiorach: dopełnienie, suma, różnica, różnica symetryczna, przecięcie, zbiór potęgowy. Diagramy Venna. Zastosowanie kwantyfikatorów w rachunku zbiorów. 1 5 Relacje Para uporządkowana, iloczyn kartezjański. Relacja dwuczłonowa. Dziedzina i przeciwdziedzina relacji. Relacja odwrotna. Złożenie relacji. Relacja binarna i jej właściwości. Relacja równoważności. Podział zbioru. Zasada abstrakcji. Relacje porządkujące. Relacje liniowego porządku. Zbiory uporządkowane. Elementy maksymalne, minimalne, najmniejsze i największe. Macierz relacji, diagram strzałkowy i diagram Hassego. Kresy. 2 6 Funkcje Funkcja jako relacja. Funkcja częściowa. Dziedzina, przeciwdziedzina funkcji. Injekcje, surjekcje i bijekcje. Funkcja odwrotna. Złożenie funkcji. Obraz, przeciwobraz. Wykres funkcji. Ciągi skończone i nieskończone. Indeksowanie. Indeksowana rodzina zbiorów. Działania uogólnione na zbiorach. Właściwości działań uogólnionych. Produkty uogólnione. Relacje wieloczłonowe. Funkcje wielu zmiennych. 2 7 Teoria mocy Równoliczność zbiorów. Zbiory skończone, nieskończone, przeliczalne i nieprzeliczalne. Właściwości zbiorów przeliczalnych. Liczby kardynalne i ich właściwości. Twierdzenie Cantora. Hipoteza continuum. Działania na liczbach kardynalnych. 1 8 Rekurencje, drzewa binarne Definicja rekurencyjna ciągu liczbowego. Wieża Brahmy. Ciąg Fibonacciego. Rozwiązywanie liniowych równań rekurencyjnych. Równanie charakterystyczne. Złota liczba. Szczególne przypadki rekurencji. Definicja rekurencyjna zbioru. Drzewo binarne i wielomianowe. Definicja rekurencyjna funkcji. Porządek prefiksowy, postfiksowy i infiksowy. Notacja polska i odwrotna notacja polska. 2 Ćwiczenia: 1 Rachunek zdań i kwantyfikatorów Zdania, spójniki, zmienne zdaniowe, formuły logiki zdaniowej, funkcje zdaniowe. Postacie normalne formuł. Tautologie rachunku zdań. Formuły równoważne. Zbiory spójników funkcjonalnie pełne. Funkcje zdaniowe. Kwantyfikator ogólny i egzystencjalny. Zasięg kwantyfikatora, zmienne związane i wolne. Kwantyfikatory o ograniczonym zakresie. Tautologie rachunku kwantyfikatorów. 1 2 Metody wnioskowania, indukcja Reguły dowodzenia. Reguła modus ponens, modus tollens, sylogizmy, schemat dowodu niewprost i dowodu apagogicznego. Kwadrat logiczny. Zasada minimum i maksimum. Zasada indukcji matematycznej. Zasada indukcji zupełnej. 2 3 Rachunek zbiorów Sposoby prezentacji zbioru. Zbiór pusty. Równość i inkluzja zbiorów. Działania na zbiorach: dopełnienie, suma, różnica, różnica symetryczna, przecięcie, zbiór potęgowy. Diagramy Venna. Zastosowanie kwantyfikatorów w rachunku zbiorów. 1 4 Relacje Para uporządkowana, iloczyn kartezjański. Relacja dwuczłonowa. Dziedzina i przeciwdziedzina relacji. Relacja odwrotna. Złożenie relacji. Relacja binarna i jej właściwości. Relacja równoważności. Podział zbioru. Zasada abstrakcji. Relacje porządkujące. Relacje liniowego porządku. Zbiory uporządkowane. Elementy maksymalne, minimalne, najmniejsze i największe. Macierz relacji, diagram strzałkowy i diagram Hassego. Kresy. 2 5 Funkcje Funkcja jako relacja. Funkcja częściowa. Dziedzina, przeciwdziedzina funkcji. Injekcje, surjekcje i bijekcje. Funkcja odwrotna. Złożenie funkcji. Obraz, przeciwobraz. Wykres funkcji. Ciągi skończone i nieskończone. Indeksowanie. Indeksowana rodzina zbiorów. Działania uogólnione na zbiorach. Właściwości działań uogólnionych. Produkty uogólnione. Relacje wieloczłonowe. Funkcje wielu zmiennych. 1 6 Rekurencje, drzewa binarne Definicja rekurencyjna ciągu liczbowego. Wieża Brahmy. Ciąg Fibonacciego. Rozwiązywanie liniowych równań rekurencyjnych. Równanie charakterystyczne. Złota liczba. Szczególne przypadki rekurencji. Definicja rekurencyjna zbioru. Drzewo binarne i wielomianowe. Definicja rekurencyjna funkcji. Porządek prefiksowy, postfiksowy i infiksowy. Notacja polska i odwrotna notacja polska. 1 |
Literatura: |
podstawowa: A. Chojnacki, Jak to rozwiązać? Matematyka dyskretna. Część I, Wojskowa Akademia Techniczna, Warszawa 2017 K. A. Ross, Ch. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2013 H. Matuszewska, W. Matuszewski, Elementy logiki i teorii mnogości dla informatyków, BEL Studio, Warszawa 2003 uzupełniająca: R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2006 H. Rasiowa, Wstęp do matematyki współczesnej, Wydawnictwo Naukowe PWN, Warszawa 2015 G. Mirkowska, Elementy matematyki dyskretnej, Wydawnictwo PJWSTK, Warszawa 2003 http://wazniak.mimuw.edu.pl/ |
Efekty uczenia się: |
W1 ma wiedzę w zakresie podstaw logiki matematycznej, rachunku predykatów oraz teorii mnogości i teorii mocy oraz relacji i funkcji K_W02 U1 umie posługiwać się terminologią logiki, teorii mnogości, relacji i funkcji do interpretowania pojęć z zakresu informatyki K_U03, K_U17 U2 potrafi opisywać w postaci zależności rekurencyjnych wyrażenia opisujące procesy występujące w systemach informatycznych, w szczególności w opisach algorytmicznych tych procesów K_U03, K_U17 |
Metody i kryteria oceniania: |
Moduł kształcenia zaliczany jest na podstawie wyników egzaminu oraz zaliczenia ćwiczeń rachunkowych. Egzamin przeprowadzany jest w formie pisemnej, w indywidualnych przypadkach może być dodatkowy egzamin ustny. W przypadku egzaminu online uzyskanie oceny wyższej niż 3,0 możliwe jest tylko w przypadku zdawania dodatkowego egzaminu ustnego. Warunkiem dopuszczenia do egzaminu jest uzyskanie pozytywnej oceny z zaliczenia ćwiczeń rachunkowych. Zaliczenie ćwiczeń rachunkowych odbywa się poprzez wykonywanie prac domowych, aktywność na zajęciach i kolokwia. W przypadku zajęć online prowadzący zajęcia może podjąć decyzję o nie przeprowadzaniu kolokwiów; w takiej sytuacji do uzyskania oceny wyższej niż 3,0 może być konieczna dodatkowa rozmowa sprawdzająca umiejętności. |
Zajęcia w cyklu "Semestr zimowy 2024/2025" (w trakcie)
Okres: | 2024-10-01 - 2025-02-28 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 8 godzin
Wykład, 12 godzin
|
|
Koordynatorzy: | Krzysztof Pszczoła | |
Prowadzący grup: | Krzysztof Pszczoła | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Zaliczenie na ocenę |
Właścicielem praw autorskich jest Wojskowa Akademia Techniczna.