Wydział Matematyki, Informatyki i Mechaniki UW

Nasz genom składa się z około 6 miliardów pojedynczych nukleotydów i ta informacja (pochodząca od obojga rodziców) opisuje wszystkie nasze cechy dziedziczne. To wie dziś prawie każdy, ale nie każdy zastanawia się jak ta informacja jest przechowywana w naszych komórkach. Kiedy uświadomimy sobie, że te 6 miliardów znaków mieści się na małej pamięci USB, to myślimy, że to zminiaturyzowany zapis. Jednak biologicznie, te 2 metry DNA są upakowane w każdej z dziesiątek bilionów naszych komórek, podczas gdy bilion pamięci USB ważyłby ponad milion ton! Dodatkowo, chromosomy te nie mogą być powrzucane do jąder komórkowych losowo, bo mogłyby poplątać się podczas ich kopiowania przy podziale komórki. Co więcej, każda komórka podczas swojego życia musi „uruchamiać” produkcję RNA z tysięcy genów, a więc fizycznie „odszukać” te miejsca w odpowiednich momentach. Jak zrealizować strukturę 3D chromosomów, która zapewni te wszystkie cechy naraz? Zrozumienie i opisanie tych skomplikowanych struktur to ogromne zadanie badawcze stojące przed nauką, ale na tym wykładzie zajmiemy się obliczeniowymi aspektami tego problemu. Między innymi odpowiemy na pytania: Jak opisać strukturę chromosomów składających się z miliardów części. Czy możemy rozróżnić struktury od siebie? Czy każda komórka ma chromosomy ułożone tak samo? Czy możemy obliczyć postać struktury, której nie widać nawet pod mikroskopem elektronowym?

Opowiem o tym, jak patrząc na sieć powiązań, wskazać najważniejszy element. Zagadnienie to nazywane jest "analizą centralności". Ma ono bardzo dużo zastosowań - od wyznaczanie najbardziej wpływowych osób w sieciach społecznych, przez kluczowe węzły w infrastrukturze drogowej czy informatycznej, aż po analizę istotności genów w sieciach biologicznych. W swojej prezentacji skupię się na sieciach terrorystycznych i pytaniu, jak znaleźć terrorystę, który jest "mózgiem" operacji. Czy jest to możliwe, analizując jedynie sieć znajomości i interakcji? Patrząc na siatkę terrorystyczną, która przeprowadziła zamach na World Trade Center 11 września 2001 roku, zobaczymy, jak działają podstawowe miary centralności. Zastanowimy się także, których terrorystów powinniśmy "wyeliminować" z sieci, aby zapobiec atakowi przez rozbicie siatki terrorystycznej na części. Z pomocą przyjdzie nam tu teoria gier, a konkretniej metody oparte na rozwiązaniach gier koalicyjnych.

Ewolucję można traktować jako swego rodzaju obliczenie. Bardzo upraszczając oblicza ona nowe pokolenie ze starego (oczywiście używając po drodze losowości). Osobniki bardziej dostosowane do środowiska średnio zostawiają więcej potomków. Można by więc uważać, że ewolucja „dąży do“ stworzenia osobników idealnych. Ale czy aby na pewno? W przyrodzie istnieją dwa najbardziej powszechne sposoby rozmnażania: rozmnażanie bezpłciowe i rozmnażanie płciowe. Rozmnażanie bezpłciowe jest zapewne bardziej powszechne, ale nietrudno zauważyć, że bardziej zaawansowane organizmy zazwyczaj rozmnażają się płciowo. Można więc z tego wysnuć wniosek, że rozmnażanie płciowe jest niejako lepsze. W informatyce opracowano algorytmy wzorujące się na obu metodach rozmnażania w celu znajdowania optymalnych obiektów w pewnej puli możliwości. Algorytmy przeszukujące przestrzeń rozwiązań w sprytny sposób można uznawać za analog rozmnażania bezpłciowego. Z kolei na rozmnażaniu płciowym wzorują się z kolei tak zwane algorytmy genetyczne. Wydaje się, że algorytmy wzorujące się na algorytmach płciowych powinny zdecydowanie wygrywać z tymi wzorującymi się na algorytmach bezpłciowych. A jednak tak nie jest! Powszechnie używa się symulowanego wyżarzania, które jest algorytmem przeszukującym przestrzeń możliwości. A niektóry bardzo szanowani naukowcy twierdzą nawet, że algorytmy genetyczne nie sprawdzają się w praktyce. Gdzie w takim razie tkwi haczyk? Może ewolucja wcale nie tworzy osobników optymalnych. Co więc w takim razie może optymalizować? Zastanowimy się tym problemem i spróbujemy udzielić chociaż częściowej odpowiedzi.

Paradoks jest słowem z języka powszechnego i bywa źle interpretowany. Niekiedy ludzie mylnie używają go w znaczeniu czegoś niezrozumiałego, zaskakującego. Nawet w języku nauki przyjęły się określenia "paradoks bliźniąt" czy "paradoks EPR (Einsteina, Podolskiego, Rosena)", które miały podważyć mechanikę kwantową przez doprowadzenie do sprzeczności ze zdrowym rozsądkiem. Takie paradoksy zyskały wytłumaczenie i fizycy poradzili sobie z nimi. Dzisiejsi fizycy widzą w nich co najwyżej trudność intelektualną lub rachunkową, a nie sprzeczność. Tymczasem prawdziwy paradoks logiczny, chociaż często zaskakujący, nie jest po prostu niemożliwym do wytłumaczenia faktem, tylko powstaje wskutek pomieszania dwóch światów: świata opisu ze światem przedmiotu tego opisu. Jeszcze Arystoteles, budując fundamenty współczesnej nauki, ostrzegał przed błędnymi definicjami, w których definiujemy obiekty za pomocą nie do końca zdefiniowanych pojęć. Zauważmy, jak przy tym podejściu trudnym przedmiotem do zdefiniowania staje się logika, o której trzeba mówić używając praw logiki, zwanych wtedy, dla osłabienia dysonansu, zdrowym rozsądkiem. Starożytni Grecy doskonale zdawali sobie sprawę z problemu. Znane są liczne paradoksy, w tym bodaj najważniejszy paradoks Eubulidesa (kłamcy). Z niego można wywieść parę innych znanych paradoksów, jak choćby spór Protagorasa z Euathlosem, paradoks cyrulika na wyspie rządzonej przez tyrana, czy rozmowę matki z krokodylem, który porwał jej dziecko. O tych paradoksach, metodach ich rozpoznawania i unikania opowiem na wykładzie z licznymi przykładami.

Wybory, według Konstytucji, powinny być (wśród innych ważnych przymiotników) równe i proporcjonalne. Czy są takie? Kto, jak nie matematyk, powinien to sprawdzić! Sprawdzimy, jak działają wybory do sejmu w Polsce. Czy większość mandatów może dostać mniejszość? Czy zawsze więcej głosów, to lepiej? Zastanowimy się nad tym, czy w ogóle możliwe są wybory proporcjonalne, z matematycznego punktu widzenia. A jeśli nie wybory proporcjonalne, to może większościowe, gdzie w każdym okręgu wygrywa jeden kandydat? Zobaczymy, jak bardzo ich wynik może zależeć od metody głosowania. Ale czy da się rozstrzygnąć, która metoda głosowania jest najlepsza? I kto o tym decyduje? Przyjrzymy się też wyborom w innych krajach, np. wyborom prezydenckim w USA. Kto o tym decyduje to ważne pytanie również przy okazji zastanawiania się nad granicami okręgów wyborczych. Pokażemy, jak bardzo można wpłynąć na wynik wyborów, jedynie sprawnie ustalając ich mapę! Na koniec zastanowimy się nad tym, na czym nam zależy w wyborach. Jakie cechy powinien spełniać system wyborczy, żeby był sensowny. Poszukamy też możliwie sensownego systemu, choć - ostrzegam - będzie trzeba pójść na jakiś kompromis.

Na zajęciach wykonamy z papieru parę papierowych „sztuczek”, które na pierwszy rzut oka wydaja się niewykonalne. Nie zapomnij wziąć nożyczek!