9157474579

	ćwiczeniowego oraz egzaminu pisemnego lub ustnego z teorii przedstawionej na wykładzie. Wynikowa ocena z ćwiczeń jest połową wartości sumy ocen z dwóch kolokwiów, zaokrągloną do najbliższej regulaminowej oceny.
Nazwiska i imiona osób prowadzących: prof. dr hab. Michał Jacymirski

Założenia i cele przedmiotu:

Wykład:

Przedstawienie głównych pojęć i metod matematyki dyskretnej.

Ćwiczenia:

Wykształcenie umiejętności zastosowania pojęć i twierdzeń matematyki dyskretnej.

Treści programowe:

Wykłady:

Elementy logiki matematycznej: pojęcie zdania logicznego, zdania złożone, rachunek zdań i tautologje. Predykat. Rachunek predykatów. Twierdzenia matematyczne i jego dowód. Indukcja matematyczna. Rekurencja. Zależności rekurencyjne.

Zbiory skończone i nieskończone. Działania na zbiorach. Zbiory liczbowe i ich własności.

Pojęcie relacji. Działania na relacjach. Relacje równoważności. Grupowanie i porządkowanie. Relacje uporządkowania na zbiorach. Odwzorowania i ich zastosowania. Kombinatoryka: zliczanie i generowanie obiektów kombinatorycznych, prawo sumy, prawo iloczynu, wariacje bez powtórzeń i z powtórzeniami, kombinacje bez powtórzeń i z powtórzeniami.

Grafy i drzewa. Pojęcia grafu. Graf skierowany. Cykl, droga i graf Eulera. Rodzaje grafów (Hamiltona, planarne, dwudzielne). Drzewa. Algorytmy przeszukiwania w głąb i wszerz. Struktury algebraiczne. Algebry Boole’a. Wyrażenia i funkcji boolleowskie. Sieci logiczne. Wprowadzenie do teorii grup. Grupa permutacji.

Ćwiczenia:

Rachunek zdań: równoważności logiczne.

Dowody indukcyjne. Wykorzystanie zasady rekurencji.

Operacje na zbiorach.

Metody reprezentacji relacji. Operacje na relacjach. Relacje grupowania i porządkowania.