Delta mi!

Wyobraź sobie, Czytelniku, że jesteś dość leniwym nauczycielem w podstawówce. Uczniowie mieli zadane, jako pracę domową, ogromne ilości przykładów z tabliczki mnożenia i dodawania w zakresie pięćdziesięciu. Biorąc pod uwagę liczbę dzieci w klasie, sprawdzanie tego to istna męczarnia. Ale przecież można trochę oszukać, np. spośród dziesiątków przykładów, spojrzeć na losowe pięć i przyjąć, że jeśli są dobrze, to reszta też jest pewnie dobrze. A czytania zostaje dużo mniej.

Teoria liczb w wielu miejscach jest zaskakująca i nieprzewidywalna, co – na poziomie elementarnym – objawia się przede wszystkim przez nieregularne i trudne do opisania rozmieszczenie liczb pierwszych w zbiorze liczb naturalnych. Wraz z Piotrem Hofmanem zmierzyliśmy się z tym fenomenem, badając tzw. ciąg EKG: prosty do zdefiniowania, a z bardzo ciekawymi właściwościami.

W  Delcie 7/2009 Marek Cygan opisał pewien sposób radzenia sobie z tym, że dla niektórych trudnych problemów nie potrafimy znaleźć szybkiego algorytmu. Autor rozważał klasę problemów NP-trudnych – czyli takich, których prawdopodobnie nie można rozwiązać w czasie wielomianowym – i pokazywał, że dla wielu z nich można w efektywny sposób skonstruować nie dokładne, lecz przybliżone rozwiązanie.

W naszym zespole badawczym analizujemy wiele różnych zagadnień, które występują w różnych aspektach. Nic w tym dziwnego, wszak algorytmika jest bardzo szeroką dziedziną. Zdarza się i tak, że to samo zagadnienie pojawia się w wielu kontekstach. Taka sytuacja ma miejsce w przypadku problemu drzewa Steinera.

Skojarzenia to bardzo popularny temat. Pojawiają się w różnych miejscach zarówno w informatyce, jak i w matematyce dyskretnej.