Delta mi!

Tym razem omówimy zadanie Or, które pojawiło się w 2018 roku na Junior Balkan Olympiad in Informatics w Timisoarze (Rumunia).

Tym razem omówimy zadanie Zalesianie, które pojawiło się na finale zawodów drużynowych XII Olimpiady Informatycznej Gimnazjalistów.

Tematem tego artykułu jest mnożenie macierzy, ale zaczniemy od problemu nieco prostszego - mnożenia wielomianów...

Spójrzmy na dwa grafy na poniższym rysunku. Wyglądają zupełnie inaczej, prawda?

Autor w sposób popularnonaukowy przybliża kluczowe pojęcia informatyki teoretycznej związane z teorią obliczeń i algorytmiką. Książka jest napisana w formie opowieści; autor ilustruje omawiane pojęcia przykładami zaczerpniętymi z życia codziennego oraz z popularnych książek czy filmów.

Tym razem omówimy zadanie Egzamin, które pojawiło się w 2010 roku na Junior Balkan Olympiad in Informatics w Szumen (Bułgaria).

Dawno, dawno temu, wierzono, że fundamentalne zasady rządzące światem są proste. Kiedy dziedzina nauki, zwana obecnie informatyką, dopiero raczkowała, naukowcy byli przekonani, że dla każdego problemu obliczeniowego można znaleźć efektywny algorytm, o ile poświęci się na to wystarczająco dużo czasu, kredy oraz kawy. Pojęcie "efektywnego algorytmu" oznaczało początkowo algorytm o czasie działania proporcjonalnym do rozmiaru danych wejściowych, ale i algorytmy o złożoności obliczeniowej czy były do zaakceptowania.

Tym razem omówimy zadanie z XII OIG.

Tym razem wyjątkowo nie omówimy żadnego nowego zadania. Wrócimy za to do problemu przedstawionego w w artykule Złośliwy problem i kubełkowe struktury danych...

Tym razem omówimy dwa zadania z zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

Tym razem omówimy zadanie Bajtockie kółeczko z pierwszego etapu zawodów drużynowych X Olimpiady Informatycznej Gimnazjalistów.

Tym razem omówimy dwa zadania z IX International Autumn Tournament in Informatics, który odbył się w listopadzie 2017 roku w Szumem w Bułgarii.

Tym razem omówimy dwa zadania, które na pierwszy rzut oka wyglądają podobnie, jednak w istocie są różne. Pierwsze z nich pochodzi z II etapu IX Olimpiady Informatycznej Gimnazjalistów, zaś drugie z Bałkańskiej Olimpiady Informatycznej Juniorów w 2015 roku.

Tym razem omówimy zadanie z pierwszego dnia Pierwszej Olimpiady Informatycznej Juniorów (EJOI), która odbyła się w Sofii we wrześniu 2017 roku.

Za siedmioma górami, za siedmioma rzekami - gdzieś pod Warszawą - znajduje się niewielka miejscowość. W tej miejscowości stoi mały domek. A tak się składa, że w domku tym mieszkają Bartek i Agatka wraz z rodzicami.

Dzisiejsze zadanie pochodzi z VIII. Olimpiady Informatycznej Gimnazjalistów w roku szkolnym 2013/2014.

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

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

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

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