Co najmniej od wprowadzenia do matematyki tzw. aksjomatów Zermela-Fraenkla, a wśród nich (zapewne najbardziej spektakularnego) pewnika wyboru (ang. axiom of choice), kwestie dotyczące istnienia rozmaitych struktur matematycznych lub specyficznych odwzorowań między nimi cieszą się ogromnym zainteresowaniem, a liczne nietrywialne twierdzenia o ich istnieniu uznawane są za fundamentalne, głębokie czy nawet doniosłe. Oprócz samego pewnika wyboru (który orzeka o istnieniu pewnego zbioru lub funkcji) i równoważnych mu warunków (jak np. twierdzenie o dobrym uporządkowaniu lub Lemat Kuratowskiego-Zorna), znane są także jego słabsze logicznie następstwa, które również stanowią ważne narzędzie w dowodzeniu twierdzeń egzystencjalnych. Jednym z nich jest twierdzenie Tichonowa (o zwartości produktu kartezjańskiego), które nadało pojęciu zwartości ogromne znaczenie nie tylko w topologii, ale także w całej matematyce. Niniejszy wykład będzie poświęcony właśnie pojęciu zwartości i wyjaśnieniu, dlaczego jest to ważna metoda w niekonstruktywnych dowodach egzystencjalnych.

Prawdopodobnie wszyscy wiemy, że komputery nie rozwiążą za nas wszystkich problemów. Ale które w takim razie rozwiążą? Na warsztatach dowiemy się, co tak naprawdę da się wyrazić w formie algorytmu, jak opisać takie wyrażalne problemy w sposób matematyczny i precyzyjny, i czemu absolutnie kluczowe jest pojęcie rekurencji. Będziemy do tego używać dwóch różnych języków: funkcji rekurencyjnych, czyli pracowitego budowania trudnych algorytmów z operacji „dodawania jedynki”, oraz rachunku lambda, czyli świata, gdzie wszystko jest funkcją. Do wszystkich wyników spróbujemy dojść sami, a dodatkową ciekawostką jest fakt, że oba te języki opisu algorytmów powstały jeszcze przed tym, zanim ludzkość stworzyła pierwsze współczesne komputery.

Pracuje w Katedrze Algorytmiki, gdzie zajmuje się analizą algorytmów i kombinatoryką. Oprócz studentów uczy też (z dużą przyjemnością) licealistów z V LO w Krakowie, udziela się przy Olimpiadzie Informatycznej Juniorów i organizuje studenckie zawody programistyczne. Pasjonat muzyki chóralnej (szczególnie renesansowej) oraz literatury fantastycznej.

Graf nazywamy planarnym, jeśli da się go narysować na płaszczyźnie bez przecięć. Na zajęciach poznamy podstawowe własności takich grafów, w szczególności wzór Eulera determinujący, jak powiązane są liczby wierzchołków, krawędzi i ścian takiego grafu. Omówimy również, jak dobrze można pokolorować takie grafy oraz ważne twierdzenie o czterech kolorach, które zmieniło sposób patrzenia na matematyczne dowody wspierane komputerowo. Będzie też okazja poćwiczyć poznaną wiedzę na zadaniach.