Delta mi!

Jakiś czas temu koleżanki i koledzy z redakcji Delty poprosili mnie, żebym opisał, czym zajmuję się naukowo, i przedstawił pewien ciekawy wynik, który udało mi się wraz ze współpracownikami niedawno uzyskać. Pisząc ten tekst, postaram się przybliżyć tę właśnie dziedzinę, która mi osobiście wydaje się interesująca chyba dlatego, że rozważa problemy o bardzo prostym sformułowaniu geometrycznym, a mimo to jest w niej więcej znaków zapytania niż odpowiedzi. Badania często okazują się ciekawą kombinatoryką, popartą jednak zwykle geometrycznymi intuicjami. Wiele fundamentalnych pytań otwartych można sformułować bardzo szybko, jedno z nich przybliżę na końcu tego tekstu.

W informatyce wielokrotnie spotykamy się z sytuacjami, gdy tworzone algorytmy są w pewnym stopniu inspirowane przyrodą. Mamy na przykład algorytmy genetyczne, mrówkowe, rojowe czy symulowane wyżarzanie. Okazuje się, że obliczenia mogą być nie tylko inspirowane przez przyrodę, ale również przez przyrodę wykonywane!

W czasach niepewności, wielkich zmian, kryzysów ludzie więcej myślą o sprawach ostatecznych. Czy to nie zbliża się koniec cywilizacji, a może nawet całego świata? W dawnych czasach dobrym wzorem ładu i uporządkowania był Kosmos w dostatecznie dużej skali. No bo przecież nie Ziemia, ze swoją przyziemną nieprzewidywalnością - ale już jej wspólna podróż z Księżycem wokół Słońca, od "zawsze" taka sama, mogłaby stanowić jakiś punkt odniesienia. Albo jeszcze lepiej: popatrzmy na cały Układ Słoneczny! Czy jego leniwie przemierzające przestrzeń planety są oazą spokoju, przewidywalności i stabilności - jeśli nie na wieczność, to może przynajmniej na miliony, lub lepiej miliardy, lat?

W tym kąciku zajmiemy sią zadaniem z finału Potyczek Algorytmicznych 2009.

Zaczniemy od takiego zadania: dla danego -literowego słowa chcemy znaleźć liczbę jego różnych podciągów. Innymi słowy, chcemy odpowiedzieć na pytanie, ile różnych słów możemy uzyskać poprzez wykreślanie niektórych liter ze słowa Dla przykładu rozważmy słowo ABAA. Ma ono dokładnie 10 różnych podciągów: słowo puste, A, B, AA, AB, BA, AAA, ABA, BAA oraz ABAA. Dla uproszczenia będziemy rozważać słowa złożone z liter A i B, ale nasze rozwiązania będą działać dla dowolnego -literowego alfabetu.

Tym razem omówimy zadanie Yet Another Substring Reverse, które pojawiło się na portalu www.codeforces.com.

Wiele zadań konkursowych proponowanych podczas zawodów programistycznych wymaga od uczestników zakodowania zawiłych algorytmów czy skomplikowanych struktur danych. Właśnie takie zadania nie raz i nie dwa, ale wielokrotnie prezentujemy w niniejszej rubryce. Dziś jednak opowiemy o pewnym bardzo specyficznym typie zadań olimpijskich, które zwykle sprowadzają się do znalezienia zwartego wzoru opisującego odpowiedź na pytanie zawarte w zadaniu...

Przyjrzyjmy się problemowi równań napisów: dla ustalonego alfabetu, np. piszemy równania używające liter z tegoż alfabetu oraz zmiennych, które będziemy oznaczać przez Dla uproszczenia pomyślmy o jednym równaniu, np. Rozwiązaniem będą takie napisy, złożone z liter alfabetu, że po podstawieniu pod zmienne uzyskamy takie same napisy....

Tym razem omówimy zadanie "Theater Tickets", które pojawiło się w konkursie Zinc 2018 organizowanym przez firmę Codility.

Jest wiele sposobów zrobienia wrażenia na ludziach, ale jednym z najbardziej popularnych jest wciąż... wygłoszenie przemówienia.

Obliczenia kwantowe wykorzystują ideę superpozycji kwantowej, która pozwala na przygotowanie układów kwantowych w "wielu stanach jednocześnie", w celu uzyskania nieosiągalnego na komputerach klasycznych zrównoleglenia obliczeń i rozwiązania bardzo trudnych problemów matematycznych w czasie nieosiągalnym dla tradycyjnych urządzeń liczących. Przykładem obliczeń prostych dla komputerów kwantowych, a trudnych dla klasycznych, jest rozkład liczby na czynniki pierwsze. Trudność tego problemu jest kluczowa dla bezpieczeństwa ogromnej większości zaszyfrowanej komunikacji internetowej.

Korzystając z popularnych serwisów internetowych, błyskawicznie znajdziemy najkrótszą trasę między dwoma miastami. A co, gdybyśmy chcieli znaleźć najkrótszą trasę, która pozwoli po wyruszeniu z domu odwiedzić wszystkie interesujące nas miasta i wrócić do punktu wyjścia?

Tym razem omówimy zadanie "Beautiful Password", które pojawiło się na konkursie Cuprum 2018 organizowanym przez firmę Codility.

W tym odcinku omówimy rozwiązanie zadania "Cyfrowy ciąg", które pojawiło się w eliminacjach do zawodów Romanian Master of Informatics.

Jak bardzo inteligentna jest współczesna sztuczna inteligencja (artificial intelligence, AI)? W przeciwieństwie do tego, co przedstawia fantastyka naukowa, AI jest na razie dość mało zaawansowana, żeby nie powiedzieć - prymitywna. Rzeczywistość i fantastykę naukową wiele różni; daleko nam jeszcze do stworzenia androidów i maszyn, które potrafią myśleć i funkcjonować jak ludzie. Mimo to współczesna AI stanowi nieodłączną część naszego życia, chociaż często możemy nie zdawać sobie z tego sprawy...

Podczas odbywającego się w 1900 roku w Paryżu Drugiego Międzynarodowego Kongresu Matematyków jeden z referatów wygłosił wybitny niemiecki matematyk David Hilbert. W swoim wystąpieniu zawarł on listę dwudziestu trzech zagadnień matematycznych stanowiących, jego zdaniem, szczególne wyzwanie dla matematyków w rozpoczynającym się XX wieku. Większość z nich doczekała się rozwiązania. Inne, jak słynna hipoteza Riemanna, pozostają otwarte, inspirując kolejne pokolenia naukowców.

W tym odcinku omówimy rozwiązanie zadania XORanges, które pojawiło się na trzecich zawodach European Junior Olympiad in Informatics (Maribor, Słowenia).

Jest kwiecień 2019 roku. Tej zimy grypa przeszła bez rozgłosu; ciekawe, jak wyglądała zachorowalność w poprzednich latach? Oczywiście, najprościej bezpośrednio zwrócić się do ludzi, którzy takie informacje zbierają, np. w Pracowni Monitorowania i Analizy Sytuacji Epidemiologicznej w Zakładzie Epidemiologii Chorób Zakaźnych i Nadzoru w Narodowym Instytucie Zdrowia Publicznego - Państwowy Zakład Higieny. Ale co zrobić, jeśli nie chcielibyśmy zawracać im głowy swoją skromną osobą i nagabywać o udostępnienie części bazy danych, a potem - gdy już się zgodzą (a na pewno się zgodzą, bo to bardzo mili ludzie) - zanudzać ich pytaniami o to, jak w tej bazie dostać się do tego fragmentu, który jest nam potrzebny... Może jednak lepiej na początek spróbować samodzielnie wykorzystać to, co i tak już Pracownia publikuje na swoich stronach internetowych?

W tym odcinku omówimy rozwiązanie zadania "123-Pairs", które pojawiło się na "Code Festival 2016".

Czy pokazując poprawność algorytmu, warto sięgnąć po matematyczne twierdzenia? Jak najbardziej! Przekonamy się o tym, rozważając problem zbalansowanego rozwoju w 2-wymiarowych systemach dodawania wektorów ( Vector Addition Systems - VAS), ubrany w historyjkę o zawodniku i trenerze.

Każdy czytelnik Delty wie, że jednym z podstawowych pojęć w matematyce jest funkcja. Matematycy nie tylko odmieniają to słowo przez wszystkie przypadki (może z wyjątkiem wołacza), ale również tworzą od niego słowa pochodne (mamy wszak równania funkcyjne czy analizę funkcjonalną). Część czytelników Delty wie również, że programiści nie pozostają matematykom dłużni - funkcje zrobiły w programowaniu doprawdy zawrotną karierę i są obecne w zdecydowanej większości języków programowania. Spróbujemy wyjaśnić, czym różni się "funkcja" matematyka od "funkcji" programisty.

W tym odcinku omówimy rozwiązanie zadania "Kwadraty liczb naturalnych", które pojawiło się na finale Zawodów Indywidualnych XIII Młodzieżowej Olimpiady Informatycznej.

Sztuczna inteligencja (SI), która wymyka się spod kontroli i prowadzi wojnę z ludzkością, to motyw stale pojawiający się w filmach futurystycznych. Czy wizje filmowców mogą stać się rzeczywistością?