Wojskowa Akademia Techniczna - Centralny System Uwierzytelniania
Strona główna

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) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
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
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 8 godzin więcej informacji
Wykład, 12 godzin więcej informacji
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ę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Wojskowa Akademia Techniczna.
ul. gen. Sylwestra Kaliskiego 2, 00-908 Warszawa 46 tel: +48 261 839 000 https://www.wojsko-polskie.pl/wat/ kontakt deklaracja dostępności mapa serwisu USOSweb 7.1.0.0-9 (2024-12-18)