Kombinatoryka


Informacje ogólne

Typ:fakultatywny
Kierunek:Informatyka
Semestr:zimowy
Wymiar zajęć:30 godzin wykładu, 30 godzin ćwiczeń
Punkty ECTS:5

Program

  • Kombinacje, wariacje, permutacje, dwumian Newtona, Symbol Newtona, trójkąt Pascala. Generowanie obiektów kombinatorycznych.
  • Zasada włączania i wyłączania.
  • Rozwiązywanie równań rekurencyjnych.
  • Łacińskie kwadraty, twierdzenie Hall'a o małżeństwach.
  • Ekstremalne własości rodzin zbiorów.
  • Twierdzenie Ramsey'a.
  • Kody korygujące błędy.
  • Zliczanie orbit grupy działającej na zbiorze. Twierdzenie Polya.

Sposób zaliczenia

Ćwiczenia: do oceny końcowej wliczone są punkty za kolokwium i punkty zdobyte za aktywność na zajęciach.
Egzamin: w pierwszym i drugim terminie jest pisemny, przy małej liczbie osób na drugim terminie, możliwy jest egzamin ustny.

Literatura

  • W. Lipski - Kombinatoryka dla programistów, WNT 1992.
  • P.J.Cameron, Combinatorics - Topics, techniques, algorithms, Camridge University Press, 1994.