Delta mi!

Po długiej przerwie wracamy z przeglądem informatycznej terminologii. Trzeci odcinek bestiariusza dotyczyć będzie akronimów związanych z formatami danych dla dokumentów i multimediów.

Tym razem omówimy dwa zadania z jubileuszowej X Olimpiady Informatycznej Gimnazjalistów w roku szkolnym 2015/2016.

Cyberprzestępcy, strzeżcie się! Najmniejszy Wasz ślad nie ukryje się bowiem przed Frankiem Bieżącym, prywatnym detektywem, specjalizującym się w algorytmach wyszukiwania...

Mówi się, że nie ma ludzi nieomylnych. Zgubiony minus w równaniu może doprowadzić do szału niejednego matematyka czy fizyka. Podobnie jak zgubiony średnik, znak równości czy inna literówka potrafi sprawić, że informatycy poświęcają pisaniu programu więcej czasu, niż mieli zamiar. Dziś chciałbym porozmawiać o błędach w programowaniu. Ale nie takich zwykłych. W niniejszym artykule przedstawię kilka kategorii błędów, które zdarzają się bardzo rzadko, ale gdy już się zdarzą, wprawiają w zdumienie nawet doświadczonych programistów.

Tym razem omówimy rozwiązanie zadania Metro z I etapu XI Olimpiady Informatycznej Gimnazjalistów w roku szkolnym 2016/2017.

Każdy chyba, nawet zupełnie nieznający się na informatyce, zgodzi się, że lepiej, żeby programy działały szybko niż wolno. Tylko co to znaczy szybko?

Czy zastanawialiście się kiedyś nad tym, czym jest inteligencja? Większość definicji zakłada posiadanie zdolności do rozumowania, uczenia się, adaptacji do zmieniającego się otoczenia. Najczęściej mówi się o inteligencji ludzi i zwierząt - organizmów mających mózg, a więc organ biologiczny. Czy inteligencja musi być jednak domeną jedynie istot, które uważamy obecnie za żywe? Wielu Czytelników słyszało zapewne również o inteligencji "sztucznej", określanej tak dlatego, że nie występuje ona w sposób naturalny w przyrodzie, ale w emergentny sposób pojawia się w maszynach i algorytmach tworzonych dzięki innej inteligencji, np. człowieka.

W tym miesiącu omówimy zadanie Liczby, które pojawiło się podczas rundy 72. na portalu codeforces.com.

Wydaje się, że moc, szybkość obliczeniowa współczesnych komputerów, bazujących na krzemie, osiąga swoje plateau wynikłe z ograniczeń natury materiałowej. Jednocześnie w wielu dziedzinach życia codziennego, poczynając od prób unikania korków w planowanej podróży, poprzez minimalizację kosztochłonności produkcji aż po liczne zaawansowane zagadnienia badawcze z zakresu teorii sterowania, staramy się optymalizować nasze postępowanie. Wobec wspomnianych ograniczeń sprzętowych pozostaje nam poszukiwanie nowych algorytmów dla optymalizacji lub zupełnie nowych paradygmatów obliczeniowych - być może kwantowych?

W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

"Informacja jest fizyczna" powiedział Rolf Landauer, fizyk, któremu zawdzięczamy zrozumienie faktu, że usunięcie 1 bitu informacji z pamięci komputera wiąże się z nieuniknionym wytworzeniem ciepła o wartości gdzie jest temperaturą otoczenia, a stałą Boltzmanna. Był to wynik, który pokazał, że warto myśleć o fizycznych podstawach przetwarzanej przez nas informacji, aby zrozumieć ograniczenia i perspektywy dalszego rozwoju komputerów. Dziś wiemy, że materia na poziomie mikroskopowym opisywana jest przez prawa fizyki kwantowej...

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

24 maja 2000 roku Instytut Matematyczny Claya ogłosił listę siedmiu Problemów Milenijnych, czyli zagadnień, które zostały uznane za najważniejsze otwarte problemy matematyczne opierające się rozwiązaniom od lat. Wśród nich był jeden problem zaliczany do informatyki teoretycznej, o którym wielu Czytelników zapewne słyszało. Chodzi oczywiście o tytułowy problem: "Czy P=NP"? Jest on powszechnie uznawany za najważniejsze pytanie informatyki teoretycznej.

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

W miejscowości jest fryzjer, nazwijmy go superfryzjerem, który strzyże tych i tylko tych mieszkańców miejscowości, którzy nie strzygą siebie samych. Czy superfryzjer strzyże siebie samego? Chwila namysłu pokazuje, że obie możliwości są wykluczone: nie może on strzyc siebie samego, bo strzyże tylko tych, którzy siebie sami nie strzygą; gdyby zaś sam się nie strzygł, to musiałby się strzyc, bo strzyże wszystkich tych, którzy sami się nie strzygą. A zatem, superfryzjer nie może istnieć! Pokażemy jak z powyższego faktu otrzymać różne twierdzenia matematyczne, odpowiednio definiując mieszkańców miejscowości oraz to, kto kogo strzyże.

W tym miesiącu omówimy zadanie o zagadkowym tytule Hacker Cups and Balls. Pojawiło się ono na obozie w Petrozawodsku, przygotowującym do finałów zawodów ACM ICPC. Treść opowiada o kubkach i kulkach...

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

W tym miesiącu omówimy zadanie Palindromic Subsequence, które pojawiło się na konkursie SRM 708 na platformie Topcoder.

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.

Inspiracją do napisania tego artykułu jest znana, popularna i - do czego chcę Czytelnika przekonać - całkiem niełatwa łamigłówka zwana Sudoku. Problem polega na uzupełnieniu częściowo wypełnionej planszy w taki sposób, żeby każdy wiersz i każda kolumna oraz każdy z 9 tzw. regionów zawierał wszystkie cyfry od 1 do 9. Czy nie przypomina to pewnego innego równie znanego problemu natury kombinatorycznej? Tak, to problem Uzupełniania Kwadratów Łacińskich, których wynalazcą był Leonhard Euler. Być może zainspirował innych, by w przyszłości stworzyli Sudoku...

W dniach 10-13 kwietnia 2017 r. w Warszawie odbyły się zawody III stopnia XXIV Olimpiady Informatycznej.

W dzisiejszym świecie cyfrowym mamy do czynienia z olbrzymią ilością danych, wielu Czytelników słyszało zapewne modne ostatnio hasło "Big Data". I trzeba sobie z tym radzić, a problemy mogą pojawiać się w nieoczekiwanych miejscach. Przyzwyczajeni jesteśmy do myślenia, że programy mają pewne dane na wejściu i te dane są tam na stałe, program może je w dowolnym momencie przeczytać. Czasami jednak nie do końca przystaje to do rzeczywistości...

Superkomputery pomagają w badaniach przyrody, projektowaniu urządzeń i leków. Czym są, jak działają, jakich używają procesorów, jak szybko liczą? Odpowiedzi na te pytania zilustrujemy przykładami kilku superkomputerów, w tym czterech najszybszych na świecie oraz największego w Polsce.

Programowanie, czyli tworzenie programów i gier, to świetny sposób na rozwijanie kreatywnego, a zarazem logicznego myślenia. Wielu wydaje się ono skomplikowane, ale wcale nie musi być trudne! Jednym z narzędzi, które pozwala w prosty i ciekawy sposób nauczyć się podstaw, jest Scratch - środowisko stworzone przez naukowców z MIT, dzięki któremu bez znajomości specjalistycznego języka każdy może spróbować swoich sił w tworzeniu gier czy animacji.

W tym miesiącu omówimy zadanie Waga z finału Potyczek Algorytmicznych 2016.