Informacje ogólne

Typ:obowiazkowy

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.