Matematyka 2: Skrzynka z narzędziami młodego kombinatoryka dr Paweł Naroski Wykład składa się z trzech niezależnych częci. Omówione sš w nich narzędzia kombinatoryczne, takie jak zasada szufladkowa Dirichleta, zasada dwoistoci oraz zasada włšczeń i wyłšczeń. Każde z nich mimo swej prostoty i oczywistoci jest wysoce skutecznym rodkiem przy rozwišzywaniu problemów natury kombinatorycznej, czyli skończonej. Aktualnie ajbardziej owocnym polem takich zastosowań jest informatyka. Na przykład zasada szufladkowa jest głównym argumentem w jednym z najważniejszych twierdzeń teorii automatów i obliczeń, tzw. lematu o pompowaniu. Z kolei zasada włšczeń i wyłšczeń jest podstawš działania wielu szybkich algorytmów, np. algorytmów kolorowania wierzchołkowego grafów.
napomoc