Wydział Matematyki, Informatyki i Mechaniki UW

Chcemy odwiedzić n miast tak, aby przebyta przez nas trasa była jak najkrótsza. Jest to słynny problem NP-trudny, co oznacza, że najprawdopodobniej nie da się napisać programu komputerowego, który zawsze w rozsądnym czasie znajdowałby najkrótszą trasę. A jednak powstał program komputerowy, który znalazł najkrótszą trasę dla 49603 "historycznych" miejsc w USA. Czy praktyce udało się oszukać teorię? Podczas wykładu zobaczymy, że w rzeczywistości był to efekt współpracy teorii i praktyki. Dowiemy się, jak działa algorytm zastosowany we wspomnianym programie i skąd wiadomo, że znaleziona trasa jest faktycznie najkrótsza.

       Jakie najmniejsze pole powierzchni może mieć przykrywka, która pozwoli przykryć bardzo cienkiego robaka o długości jeden, niezależnie od tego, jak on się ułoży? Jak wybrać ścieżkę, która wyprowadzi nas najszybciej z lasu, którego kształt znamy, ale nie znamy swojego w nim położenia?
       Tak można sformułować dwa geometryczne problemy, które, mimo iż brzmią lekko, łatwo i przyjemnie, wcale nie są proste. Zostały postawione ponad 50 lat temu i do dziś nie doczekały się pełnego rozwiązania. 
        Podczas wykładu przedstawiona zostanie historia dążenia do rozwiązania problemów, przykładowe pokrywki, którymi można przykryć robaka, przykładowe kształty lasów, dla których wiadomo, jak szukać najkrótszej drogi do wyjścia. I zupełnie nietrywialne dowody niektórych z tych faktów...

Ile kart powinna tak naprawdę mieć talia do gry w Dobble? Jak daleko zajdzie armia pionków, jeśli mogą one poruszać się po nieskończonej planszy, tylko przeskakując jednego z sąsiadów? W znalezieniu odpowiedzi na te pytania pomogą nam liczby: reszty z dzielenia i rozwiązania pewnego równania kwadratowego.

Przeglądając się odbiciu w lustrze, możemy odkryć wiele ciekawych sytuacji w geografii, technice, biologii i chemii, medycynie i farmacji, fizyce, zdobnictwie, krystalografii, a nawet zobaczyć rzeczy, które nie istnieją - wszystko będzie związane z najbardziej zagadkowym pojeciem matematyki, jakim jest orientacja. Trop zaprowadzi nas nawet do pytania, skad biorą się pojęcia, których używamy.

Biało-czarny smok porwał do niewoli nieskończenie wielu rycerzy-matematyków. Na szczęście każdy z nich ma na hełmie białe lub czarne pióro, nikt jednak nie zna koloru pióra na swoim własnym hełmie. Smok wymyślił okrutną regułę — pożre wszystkich, którzy nie zgadną koloru swojego piórka. Na szczęście, prawie wszyscy rycerze-matematycy mogą ujść z życiem!... O ile... założymy, że prawdziwy jest bardzo naturalny aksjomat, zwany aksjomatem wyboru. Zastanowimy się, jakie jeszcze przedziwne ma on konsekwencje, rozmawiając o fantastycznych obiektach i zjawiskach ze świata matematyki — słowniku wszystkich słów oraz cudownym rozmnażaniu pomarańczy.