Delta mi!

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...

Teoria liczb to prawdopodobnie najstarsza dziedzina wiedzy matematycznej, badana intensywnie już w czasach starożytnych (a zapewne jeszcze wcześniej; możliwe, że nawet zanim powstała jakakolwiek cywilizacja operująca przekazem pisemnym).

Niniejszy odcinek jest ostatni z serii. Przez niemal rok, wraz z Łukaszem Rajkowskim, próbowaliśmy pokazać Czytelnikowi, co ciekawego, a przede wszystkim - co zaskakującego, wiąże się z kryptologią. Naszą wielką nagrodą będzie, gdy - po przeczytaniu tych 9 odcinków - choć niewielka część Czytelników chociaż przez chwilę zawaha się, gdy w życiu codziennym będzie stwierdzać, że czegoś się nie da...

Za co kochamy gotówkę? Chyba przede wszystkim za anonimowość transakcji. To znaczy: jeśli Aldona oraz Celina podejmą z banku po banknocie stuzłotowym; następnie Aldona wyda te pieniądze w sklepiku Bogumiła, a Celina u Dobromira; po czym zarówno Bogumił, jak i Dobromir zdeponują zarobione pieniądze z powrotem w banku, to oczywiście bank w żaden sposób nie będzie w stanie stwierdzić, czy klientką Bogumiła była Aldona, czy też może Celina.

Komputery to urządzenia bardzo nietypowe. Same jako takie nie mają sprecyzowanego, jasno zdefiniowanego zadania, do wykonywania którego zostały zaprojektowane. Zadania, które wykonuje komputer, mogą się w czasie zmieniać, a ich określenie odbywa się poprzez pisanie programów komputerowych. Owe programy formułuje się w specjalnym języku (Pascal, C/C++, Java, Python itp.), a następnie zleca komputerowi do wykonania.

Bywa tak, że chcemy o czymś przekonać niedowiarków, jednak w taki sposób, aby uwierzyli, ale też aby za dużo się nie dowiedzieli. Fabularna, nieinformatyczna ilustracja, którą lubię przywoływać, gdy próbuję wyrazić, o co mi chodzi, jest następująca. Wyobraźmy sobie, że potrafię zliczyć liczbę liści na drzewie, jeśli tylko spojrzę na nie przez 5 sekund. Więcej: twierdzę, że umiem to publicznie udowodnić w przeciągu 5 minut, i to tak, że wszyscy mi uwierzą, ale nikt się nie zorientuje, jak ja to robię!

Każdy młody adept sztuki programowania pewnie nie raz słyszał od swych mentorów, że program nie tylko musi działać poprawnie i szybko, ale też musi być napisany w sposób czytelny. Studentów uczy się więc nie tylko języków programowania, algorytmów czy struktur danych, ale też próbuje się im przekazać prawidłowe nawyki dotyczące stylu programowania.

Ważnych otwartych pytań, istotnych wyzwań czy fundamentalnych problemów dla ludzkości pozostało jeszcze wiele. Co ciekawe - zdaje się, że wszystkie je rozstrzygniemy do roku 2058.

Problem szyfrowania przesyłanych wiadomości sięga jeszcze czasów starożytnych, więc naszego nowego deltowego cyklu artykułów o kryptologii prezentowanego w rubryce "A jednak się da!" nie możemy nie zacząć od przypomnienia najstarszego znanego systemu szyfrowania, mianowicie szyfru Cezara. Szyfr ten nie jest specjalnie wyrafinowany...

Tak zwana "kryptografia krzywych eliptycznych" to bardzo modne i popularne pojęcie, które rzeczywiście jest ważne, ale - niestety - o którym mówi się najczęściej niezwykle powierzchownie, bez wchodzenia w "detale matematyczne". Niniejszy artykuł próbuje pójść takiemu podejściu pod prąd - chcemy w elementarny sposób objaśnić, o co tak naprawdę chodzi z tymi krzywymi eliptycznymi.

Zawodowo zajmuję się kryptologią, czyli dziedziną nauki badającą różne aspekty bezpieczeństwa cyfrowego świata. Jest to nauka ścisła, czyli taka, w której królują stricte matematyczne rozumowania. Solą matematyki są, oczywiście, dowody. Również główne wyniki kryptologiczne to właśnie twierdzenia i ich dowody. A twierdzenie to para: założenie i teza. W kryptologii teza zwykle jest podobna: proponowany system jest bezpieczny. Ciekawym i ważnym pytaniem jest jednak wątpliwość: ale przy jakich założeniach?!

Naturalnie, wszystko się zaczyna od tabula rasa. Toteż załóżmy, że dysponujemy wielką niezapisaną tablicą. Po tej tablicy pisać będzie mógł absolutnie każdy, kto tylko chce. Pisać wolno wszystko, należy się jedynie podpisywać. Komunikaty nigdy nie znikają, a budowa tablicy jest taka, że łatwo się zorientować, w jakiej kolejności pojawiały się obecne na niej napisy...

Jednym z ważniejszych osiągnięć informatyki opartej o komputer kwantowy, które zresztą eksponujemy w tym numerze Delty, jest opracowanie efektywnego (wielomianowego od rozmiaru danych) algorytmu na rozkład dużych liczb na czynniki pierwsze. Wspaniały, budzący zachwyt wynik. Nie dość, że przepiękny, korzystający z bardzo ładnego fragmentu matematyki, to jeszcze pozwalający wierzyć, że komputer kwantowy złożony z kubitów jest istotnie lepszy od komputera klasycznego, zawierającego pamięć o bitach. Albo inaczej: że (też prezentowany w tym numerze) model obliczeń komputera kwantowego ma istotnie większą siłę wyrazu (przy założeniu wielomianowego czasu działania) niż klasyczny model Turinga czy inne równoważne.

Zastanówmy się nad następującym pytaniem: czym jest komputer? Sądzę, że odpowiedź na tak zadane pytanie może zależeć w znacznej mierze od tego, kogo o to pytamy. Taka sytuacja nie jest, oczywiście, czymś wyjątkowym. Jeśli zamiast informatyką zajmiemy się cukiernictwem i zapytamy: czym jest tort, to też różne osoby będą różnie odpowiadać...

W tym odcinku IKO omówimy zadanie Gra w karty, które pojawiło się podczas pierwszej rundy konkursu "Potyczki Algorytmiczne 2016".

Świat informatyki teoretycznej pełen jest hipotez, które badacze przyjmują po prostu na wiarę. Niektórzy wierzą, na przykład, że inni wierzą, że istnieje bezpieczna kryptografia klucza publicznego (albo jeszcze konkretniej: wierzą, że szyfrowanie RSA jest bezpieczne). Co ciekawe, najpopularniejsze hipotezy informatyczne bynajmniej nie są równoważne, a relacje między nimi mogą zaskakiwać.

Internet to bez wątpienia jedno z najważniejszych osiągnięć ludzkości w XX wieku. Jest to ogromna sieć komputerów z całego świata, która umożliwia szybką komunikację. Co więcej, jest tak zaprojektowana, aby uzyskać bardzo dużą niezawodność. To znaczy, jeśli jakiś węzeł w sieci, jakiś kabel łączący pewne węzły, czy nawet spora część wszystkich węzłów i kabli, ulegnie awarii, to i tak reszta sieci będzie potrafiła się komunikować, znajdując ad hoc nowe ścieżki między nieuszkodzonymi węzłami.

Przypomnijmy starą zagadkę o przeprawie przez rzekę...

Drogi Czytelniku Majsterkowiczu! W tym odcinku Migawki wreszcie będzie ciekawie. Opiszemy, jak samodzielnie skonstruować prawdziwy zegarek mechaniczny!

Małe Twierdzenie Fermata ma również taki dowód...

Tak zwany Problem Stopu to problem decyzyjny, którego wejściem jest jakiś program i jakieś dane a którego rozwiązaniem (wyjściem) jest stwierdzenie, czy program uruchomiony na danych zakończy swoje działania w skończonym czasie.

W tym miesiącu proponujemy zadanie Przeciąganie liny, które pojawiło się w podwarszawskim Józefowie, podczas zeszłorocznej Bałtyckiej Olimpiady Informatycznej. Zadanie opisuje problem optymalizacji znanej wakacyjno-urlopowej zabawy. Co ciekawe, warstwa fabularna proponowanego rozwiązania - choć pozostaje w podobnych klimatach - to jednak odchodzi od liny na rzecz plecaka.

W noworocznym kąciku omówimy zadanie Wykrywanie wrednej usterki pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej, która odbyła się w Kazaniu (Rosja). Autorzy zadania oczekują od nas, że pomożemy zdiagnozować usterkę, która wkradła się do bazy danych zaimplementowaną przez niefrasobliwego inżyniera Ilszata.

Jak wiadomo, problemy dzielimy zasadniczo na te łatwe i na te trudne. Dla człowieka taki podział jest oczywiście bardzo subiektywny. Dla komputera - jak się zaraz okaże - są to pojęcia naprawdę ostre i zupełnie precyzyjne.

Od komputera oczekujemy przede wszystkim precyzji i dokładności. Program szukający wzorca w edytowanym tekście czy arkusz kalkulacyjny podsumowujący nasze miesięczne wydatki ma po prostu dać poprawny wynik. Wszelkie przejawy niedeterminizmu, losowości czy jakiejś niestabilności przywołują skojarzenia z działaniem niepożądanym. Zwykle to prawda: dobry program ma obliczyć, narysować czy wyanimować dokładnie to, czego od niego chcemy. Okazuje się jednak, że czasem losowość jest nie tylko wskazana, ale wręcz niezbędna.

W tym artykule zakładam, że Czytelnik choć trochę programował. W szczególności zna podstawy jakiegoś języka programowania, np. Pascala. Jeśli to podstawowe założenie jest spełnione, to - jestem o tym przekonany - mogę śmiało założyć, że jest mu znane również pojęcie tablicy...

Lubię próżnie mówić o sobie, że jestem matematykiem. Bardziej precyzyjnie to jestem informatykiem, ale przecież informatyka to gałąź matematyki, więc w zasadzie nie oszukuję. Czasem, gdy ktoś mnie ciągnie za język, i pojawi się to, z niejasnych powodów nielubiane przeze mnie, słowo na "i", to i tak od razu uściślam: tak, jestem informatykiem, ale informatykiem teoretycznym. Zawsze miałem to dziwne przekonanie, że "teoretyczny" znaczy w jakimś sensie lepszy, ważniejszy, mądrzejszy, głębszy.

Nie będę ukrywał. Jestem zawsze niezmiernie sceptyczny, gdy podchodzę do książek o matematykach, napisanych przez nie-matematyków. Tak więc, gdy trafiła w moje ręce książka Roberta Kanigela pt. Człowiek, który poznał nieskończoność, reklamowana jako świetna biografia Srinivasy Ramanujana, to od razu sprawdziłem, kim jest autor.

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.