Matematyka dyskretna, czyli liczenie po cichu

Prowadzący: Krzysztof Pęczek


Zliczanie, dowodzenie i zbiorów dzielenie
Kategorie:
matematyka

Zapisz się

Opis

Matematyka dyskretna jest w rzeczywistości zbiorczą nazwą na wiele poddziedzin matematyki, które zajmują się badaniem struktur nieciągłych. W tym opisie zawiera się ogrom materiału, między innymi logika matematyczna, kombinatoryka, teoria grafów, prawdopodobieństwo, teoria gier, i wiele wiele innych. Z tego powodu nazwanie warsztatu “Matematyka dyskretna“ jest małym kłamstwem. Jest to temat zbyt duży i w praktyce będziemy się skupiać na ciekawych narzędziach, które pojawiają się w tej dziedzinie. Do nich należą:

  1. Zasada szufladkowa Dirichleta
  2. Interpretacja kombinatoryczna
  3. Zasada włączeń i wyłączeń
  4. Nieporządki, podziały
  5. Funkcje tworzące  
  6. Metody przekształcania wzorów rekurencyjnych na jawna
  7. Lemat Cauchego-Frobeniusa-Burnsidea - co mają permutacje do zliczania

tl;dr będziemy robić kombinatorykę na sterydach

Wymagania

Do zrozumienia warsztatów potrzebna jest wiedza z zakresu kombinatoryki licealnej i trochę analizy:

  1. Czym są permutację, kombinacje bez powtórzeń, wariacje i jak się je zlicza (*)
  2. Reguła mnożenia, reguła dodawania (*)
  3. Czym są zależności rekurencyjne
  4. Jak policzyć pochodną z prostych funkcji (*)
  5. Czym są iniekcje, surjekcje, bijekcje, składanie funkcji

(*) - sprawdzane na zadaniach kwalifikacyjnych

Przydatne rzeczy

Praktyczne:

Pierwsze kilka stron wykładów mogę przydać się w rozwiązywaniu  zadać kwalifikacyjnych:
https://home.agh.edu.pl/~meszka/md_wfis.pdf (Jeżeli ktoś rozumie wszystko co tutaj jest to warsztaty będą zbędne)
Dwie książki, które blisko pokrywają się z materiałem warsztatów to:

  • Matematyka dyskretna - Kenneth A. Ross, Charles R. B. Wright
  • Introductory Combinatorics - Richard Brualdi

Do zaciekawienia:

http://www.deltami.edu.pl/temat/matematyka/kombinatoryka/2011/06/21/Kolorowe_czapeczki/

Będziemy się zajmować tym drugim rodzajem