Matematyka dyskretna


Informacje ogólne

Typ:obowiazkowy
Kierunek:Informatyka studia licencjackie
Semestr:1,2
Wymiar zajęć:60 godzin wykładu, 60 godzin ćwiczeń
Punkty ECTS:6+7

Program

  • Kombinatoryka, ciągi, permutacje, funkcje, podzbiory, symbolNewtona, zasada włączania/wyłączania, zastosowania, generowanie podzbiorówi permutacji.
  • System dwójkowy, szesnastkowy i inne, zmiana bazy,reprezentacja liczb w komputerze,poszukiwania binarne.
  • Rachunek prawdopodobieństwa, zdarzenia, zmienne losowe, rozkład dwumianowy.
  • Funkcje boolowskie, wyrażenia boolowskie, sprowadzanie do postacinormalnej. Sieci boolowskie (sumator), operacje boolowskie nawektorach, funkcja parity.
  • Podzielność liczb, arytmetyka modularna, relacja kongruencji, algorytm Euklidesa,rozkład liczb na czynniki pierwsze, chińskie twierdzenie o resztach,szybkie potęgowanie,testy pierwszości.
  • Abstrakcyjne struktury danych: stosy, kolejki, drzewa.
  • Grafy, drzewa, drzewa rozpinające, algorytm szukającyminimalnego drzewa rozpinającego, izomorfizm grafów, kolorowanie grafów,grafy skierowane, cykle Hamiltona, algorytmyszukania cykli, algorytm szukania najkrótszej ścieżki.
  • Rekurencja, funkcje rekurencyjne, rozwiązywanie równań rekurencyjnych.

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 i 2.

Literatura

  • A. Szepietowski - Podstawy informatyki, Wyd. UG 2000.
  • A. Szepietowski - Matematyka dyskretna, maszynopis w sieci http://julia.ug.edu.pl/~matszp.
  • W. Lipski - Kombinatoryka dla programistów, WNT 1982.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest - Wprowadzenie do algorytmów, WNT 1998.
  • N. Koblitz - Wykład z teorii liczb i kryptografii, WNT 1995.