Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Podstawy teorii mnogości i matematyki dyskretnej.
Koordynator przedmiotu:
dr Piotr Godlewski, pgod@mini.pw.edu.pl , +4822234-663-89-56
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
2 / rok ak. 2011/2012
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład45h
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Algebra liniowa i analiza matematyczna - semestr 1
Limit liczby studentów:
Cel przedmiotu:
Umiejętność posługiwania się poznanymi pojęciami.
Treści kształcenia:
1. RACHUNEK ZDAŃ. Funktory zdaniotwórcze. Tautologie. Reguły dowodzenia. 2. RACHUNEK FUNKCJI ZDANIOWYCH. Pojęcie funkcji zdaniowej. Kwantyfikatory. Zmienna wolna oraz zmienna związana kwantyfikatorem.Tautologie rachunku funkcyjnego, które nie są uogólnieniem tautologii rachunku zdań. 3. ALGEBRA ZBIORÓW. Podstawowe twierdzenia algebry zbiorów. Różnica symetryczna zbiorów. Dopełnienie zbioru. Ciało zbiorów. Pojęcie pary uporządkowanej. Iloczyn kartezjański zbiorów. 4. SUMY I ILOCZYNY UOGÓLNIONE ZBIORÓW. 5. AKSJOMATYCZNE UJĘCIE LICZB NATURALNYCH. Aksjomat indukcji zupełnej. Definicje indukcyjne. Podstawowe własności liczb natural- nych wyprowadzane przy pomocy aksjomatu indukcji zupełnej. Przykłady dowodów indukcyjnych. 6. RELACJE DWUCZŁONOWE. RELACJA RÓWNOWAŻNOŚCI. Funkcja jako relacja dwuczłonowa. Podstawowe typy relacji w X x X : zwrotna, symetrycz- na, przechodnia, itd. Relacja równoważności. Przestrzeń ilorazowa. 7. PRZYKŁADY RELACJI RÓWNOWAŻNOŚCI i odpowiadających im przestrzeni ilorazowych: ARYTMETYKA MODULARNA, konstrukcja zbioru liczb wymiernych oraz konstrukcja zbioru liczb rzeczywistych. 8. MOCE ZBIORÓW. Pojęcie i podstawowe własności równoliczności zbiorów. Aksjomat istnienia liczb kardy- nalnych. Zbiory przeliczalne. Zbiory mocy continuum. Twierdzenie Cantora-Bernsteina. Zbiór potęgowy. Twierdzenie Cantora. 9. ZBIORY UPORZĄDKOWANE. Relacje porządkujące. Elementy maksymalne i minimalne. Lemat Kuratowskiego-Zorna. Relacje liniowo porządkujące. Relacje dobrze porządkujące. Liczby porządkowe. 10. FUNKCJE CAŁKOWITOLICZBOWE. Funkcje sufitu i podłogi. Potęgi kroczące. Rozkład liczb naturalnych na czynniki pierwsze. Kongruencje liczbowe. 11. ELEMENTY KOMBINATORYKI. Zasada szufladkowa. Permutacje. Wariacje. Kombinacje. Zasada włączania i wyłączania. Podziały. Twierdzenie Halla. 12. METODY MATEMATYKI DYSKRETNEJ. Metoda zaburzeń. Rachunek różnicowy. Funkcje tworzące. Zastosowania funkcji tworzą- cych. 13. ELEMENTY TEORII GRAFÓW. Drogi, ścieżki, kontury. Ciągi graficzne. Drzewa. Dendryty. Charakterystyki liczbowe grafów prostych. Zliczanie drzew. Grafy dwudzielne. Kolorowalność. Grafy z wagami. Planarność.
Metody oceny:
brak
Egzamin:
Literatura:
1. Rasiowa, H. : Wstęp do matematyki współczesnej. Wydawnictwo naukowe PWN, Warszawa (2005). 2. Krempa, J., Mażbic-Kulma, B. : Elementy logiki, teorii mnogości i algebry. Wydawnictwa Naukowo-Techniczne, Warszawa (1977). 3. Mostowski, A.W., Pawlak, Z. : Logika dla inżynierów ( Seria : Biblioteka Naukowa Inżyniera). Wydawnictwo naukowe PWN, Warszawa (1970). 4. Grygiel, J. : Wprowadzenie do matematyki dyskretnej. Akademicka Oficyna Wydawnicza EXIT, Warszawa (2007). 5. Wilson, R.J. : Wprowadzenie do teorii grafów. Wydawnictwo naukowe PWN, Warszawa (1998).
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się