Matematyka dyskretna


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia licencjackie
Semestr:1
Wymiar zajęć:30 godzin wykładu, 30 godzin ćwiczeń
Punkty ECTS:10

Program

  • Indukcja matematyczna. Kombinatoryka: zliczanie i generowanie obiektów kombinatorycznych (ciągi, permutacje, funkcje, podzbiory) (symbol Newtona).
  • Elementy logiki i teorii mnogości. Funktory rachunku zdań, prawa rachunku zdań. Pojęcie zbioru i działania na zbiorach. Relacje równoważności.
  • System dwójkowy, szesnastkowy i inne; zmiana bazy, arytmetyka w systemie dwójkowym. reprezentacja liczb w komputerze. Funkcje boolowskie, wyrażenia boolowskie, sieci boolowskie.
  • Podzielność liczb. Relacja kongruencji, algorytm Euklidesa.
  • Proste struktury danych. Listy, stosy, kolejki, drzewa, drzewa binarne, drzewa wyrażeń arytmetycznych.
  • Rekurencja. Rekurencyjne wywoływanie procedury, funkcje rekurencyjne, sposoby rozwiązywania równań rekurencyjnych.
  • Grafy. Definicje, reprezentacja komputerowa, podgraf, ścieżki, drzewa, grafy planarne, izomorfizm grafów, pokolorowanie grafów. Podstawowe algorytmy grafowe.

Sposób zaliczenia

Zaliczenie ćwiczeń: podstawą zaliczenia jest wynik pozytywny z dwóch kolokwiów. Punktowna jest również praca na ćwiczeniach.
Egzamin pisemny po semestrze 1.

Literatura

A. Szepietowski, Matematyka dyskretna, Wyd. UG 2004.