Nauki matematyczne

W roku 1959 wybitny holenderski informatyk Edsger W. Dijkstra zaproponował sposób wyznaczania najkrótszej trasy przejazdu pomiędzy wybranymi miastami w Holandii. Choć w zamyśle Dijkstry było  wykazanie możliwości zastosowań komputerów w innych obszarach niż obliczenia numeryczne, to okazało się, że wraz z rozwojem komputerów jego algorytm przyczynił się do rozwoju dziedziny informatyki zwanej algorytmiką, jak też stał się podstawą powszechnie dostępnej nawigacji internetowej, bez której trudno sobie wyobrazić współczesne podróże. Na wykładzie w przystępny sposób przedstawimy oryginalny algorytm Dijkstry, jego historię i zastosowania.

Weźmy mapę Polski i połóżmy ją na ziemi, dbając o to, żeby nie wystawała poza granice kraju. Wtedy pewien punkt Polski i odpowiadający mu punkt na mapie leżą w tym samym miejscu!

Opisana sytuacja to ilustracja do twierdzenia Banacha o przekształceniu zwężającym, czyli takim, które zbliża do siebie punkty. Zgodnie z tym twierdzeniem przekształcenie zwężające musi mieć punkt stały - taki, który przez to przekształcenie nie jest ruszany z miejsca. Dlaczego? Jak go znaleźć? Czy takich punktów może być kilka? Do czego taki punkt może się przydać? O tym wszystkim opowiem na wykładzie.

Program współbieżny to program złożony z wielu wykonujących się jednocześnie procesów. Najczęściej współpracują one ze sobą w celu rozwiązania pewnego problemu lub wykonania pewnej pracy. Współpraca ta często wymaga jednak wymiany informacji, np. wyników częściowych obliczonych przez poszczególne procesy. Takie wyniki częściowe mogą być na przykład zapisywane w zmiennych. Okazuje się jednak, że zmiana wartości zmiennej, nie może być wykonywana współbieżne i wymaga umiejętnej synchronizacji procesów. Na przykładzie prostych programów zobaczymy, dlaczego taka synchronizacja jest niezbędna i do jakich subtelnych błędów może prowadzić jej brak. Przekonamy się też, jak bardzo nieintuicyjna jest analiza programu współbieżnego. Na koniec zobaczymy, że wykonanie na współczesnym procesorze poprawnie zsynchronizowanego programu współbieżnego może nas mocno zaskoczyć!

Grafy są obiektami, które łączą w sposób niezwykle efektowny świat zagadek i łamigłówek logicznych, oraz świat matematyki. Nawet najtęższe umysły uczonych uderza elegancja z jaką sformułować można w ich języku najbardziej skomplikowane nawet problemy. Począwszy od rozwiązania zagadnienia mostów w Królewcu przez Eulera w 1736 roku, przez problem komiwojażera, aż do budzącego liczne kontrowersje wspomaganego komputerowo dowodu twierdzenia o czterech barwach - grafy przeszły długą drogę inicjacji w świat pełnoprawnych i ważnych obiektów matematycznych badanych współcześnie przede wszystkim przez informatyków, a także fizyków, chemików, biologów, socjologów czy wszelkiej maści inżynierów. Grafy stanowią nie tylko ważny obiekt badawczy, ale też wygodne narzędzie do komunikowania problemów pomiędzy specjalistami z różnych dziedzin nauki. Również w świadomości osób pasjonujących się matematyką grafy stały się wdzięcznymi obiektami, ilustrującym układy znajomości, turnieje, konfiguracje geometryczne, a także niebanalne problemy wykonalności określonych konstrukcji lub procesów, na przykłady tytułowych przejść. Właśnie temu ostatniemu zagadnieniu przyjrzymy się w trakcie wykładu, posługując się zupełnie intuicyjną wersją pojęcia grafu. Motywacją naszych rozważań będzie następujący problem.

Dwóch wspinaczy porusza się po paśmie górskim. Czy jest możliwe, żeby obydwaj spotkali się na szczycie startując równocześnie odpowiednio z przeciwległych krańców tego pasma, by w każdym momencie wspinaczki znajdować się na tej samej wysokości? Problem ten ma, w zależności od dopuszczalnego poziomu skomplikowania kształtu pasma górskiego, bogatą literaturę. Podczas mojego wykładu zapoznamy się z wersją problemu pozwalającą na skorzystanie z metod teorii grafów.

Zanim przedyskutujemy to ciekawe zagadnienie i sprecyzujemy dokładnie po jakim paśmie górskim pozwolić chcemy naszym wspinaczom się poruszać, zilustrujemy pojęcie grafu przejścia na przykładach kilku prostych łamigłówek. Do zrozumienie wykładu nie jest potrzebna żadna wiedza, poza umiejętnością odróżniania liczb parzystych od nieparzystych. Pozwoli nam ona sformułować lemat o uściskach dłoni i zastosować go zbadania problemu równoległej wspinaczki.