Delta mi!

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.

Jeśli mam przybliżyć komuś pojęcie złożoności czasowej, zazwyczaj opowiadam mu następujący problem. Dany jest ciąg liczb całkowitych a naszym celem jest znaleźć jego fragment - czyli spójny podciąg - którego suma elementów jest jak największa.

W numerze 10/2010 Delty pojawił się artykuł Wojciecha Plandowskiego, w którym autor po ciężkich bojach pokazuje rozwiązanie pewnego konkretnego typu równania na słowach. Mogłoby się wydawać: udało się, sprawa skończona. Tymczasem przy okazji w artykule pojawia się definicja i kilka ważnych własności słów pierwotnych, a stąd już tylko mały krok do innej ciekawej rodziny słów, mianowicie do słów pierwszych. To dobry pretekst, by coś o nich opowiedzieć.

W tym kąciku omówimy zadanie Różne słowa z Obozu Naukowo-Treningowego im. A. Kreczmara w 2013 roku.

Skoro dotychczas szło nam tak dobrze, spróbujmy pójść za ciosem i zaproponować bardzo oszczędną reprezentację drzew już niekoniecznie binarnych (ale wciąż ukorzenionych)...

Wiele struktur danych w komputerze można reprezentować w postaci drzewa binarnego. Aby przechować takie drzewo w pamięci komputera, należy dla każdego węzła zapamiętać numer jego lewego i prawego syna oraz, jeśli to potrzebne, numer węzła będącego jego ojcem. Wystarczą nam do tego trzy tablice.

Tym razem omówimy zadanie o drogach stanowych (State Roads) z pierwszej rundy zawodów Yandex.Algorithm 2013. Zadanie to można sformułować w języku teorii grafów, a do tego w ujęciu dynamicznym...

W tym kąciku zmierzymy się z zadaniem Karty z Potyczek Algorytmicznych 2013. Oryginalne sformułowanie zadania dotyczyło kart perforowanych, my jednak przedstawimy je nieco inaczej, przy okazji wprowadzając niejawnie kilka nieznaczących uproszczeń.

Cztery parametry. Tym, co najczęściej robi się w grafach dwudzielnych, jest znajdowanie najliczniejszego skojarzenia. Można jednak rozważać aż cztery – parami dualne – parametry powiązane z najliczniejszym skojarzeniem...

Kiedy rozwiązujemy jakiś problem informatyczny, często naszym celem jest podanie jak najefektywniejszego algorytmu. Jednak czasem możemy natknąć się przy tym na „ścianę” – danego problemu nie da się rozwiązać tak efektywnie, jak byśmy tego chcieli. Najpowszechniej znanym przykładem opisanego zjawiska jest klasa problemów NP-zupełnych. O problemach z tej klasy (a należy do niej wiele naturalnych i praktycznych zagadnień) podejrzewa się, że nie da się ich rozwiązać w czasie wielomianowym względem rozmiaru danych wejściowych. Niestety, tylko podejrzewa się, a rozstrzygnięcie tej hipotezy (znanej też jako ?) jest obecnie najsłynniejszym otwartym problemem informatyki teoretycznej.

O zadaniu z Akademickich Mistrzostw Polski w Programowaniu Zespołowym (2012)

Jeśli potrzebne nam są do czegoś liczby pierwsze z pewnego początkowego zakresu, zazwyczaj wyznaczamy je za pomocą sita Eratostenesa...

W tej edycji kącika omówimy zadanie pt. Podlewanie ogórków (naprawdę!) z rundy 2A konkursu TopCoder Open 2012.

Tym razem omówimy zadanie z pogranicza informatyki i muzykologii, które pojawiło się na Bałtyckiej Olimpiadzie Informatycznej w bieżącym roku.

Tym razem w kąciku lekko zmodyfikowana wersja zadania Listonosz z konkursu Wielka Przesmycka 2004.

W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

Wyobraź sobie, Drogi Czytelniku, że jesteś kapitanem okrętu wojennego i w trakcie jednej z misji znalazłeś się na środku morza leżącego na terytorium wroga. Wiesz, że wróg rozmieścił w tej strefie pewną (skończoną) liczbę radarów. Każdy radar ma określony zasięg, być może różny w przypadku różnych radarów, i jest w stanie wykryć każdy podejrzany obiekt, który znajdzie się w jego zasięgu. Naszym siłom wywiadowczym udało się wykraść plan rozmieszczenia radarów. Na jego podstawie chcesz stwierdzić, czy możesz wydostać się z wrogich wód niezauważony przez radary.

W dniach 14–18 maja br. w Warszawie odbyły się finały najstarszego i najbardziej prestiżowego konkursu informatycznego na świecie, ACM International Collegiate Programming Contest (ACM ICPC), nazywanego też Akademickimi Mistrzostwami Świata w Programowaniu Zespołowym.

Nie jest aż tak trudno założyć firmę informatyczną. Potrzebny jest do tego dobry pomysł na produkt, którego ludzie będą chcieli używać (na przykład urządzenie elektroniczne, program komputerowy lub portal internetowy), oraz kilku programistów-zapaleńców, którzy będą skłonni poświęcić kilka miesięcy życia na stworzenie wstępnej, działającej wersji produktu. W ten właśnie sposób powstała większość znanych obecnie firm z branży technologii informacyjnych, takich jak Microsoft (początkowo związany z interpreterem języka BASIC), Apple (pierwszym produktem był komputer do samodzielnego złożenia), Google (wyszukiwarka) czy Facebook (portal społecznościowy)...

Tym razem omówimy zadanie Robot sortujący (ang. Robotic Sort) z Mistrzostw Europy Środkowej w Programowaniu Zespołowym 2007 (CERC 2007).

Jednym z pierwszych zadań, z jakimi musi zmierzyć się każdy uczący się algorytmów lub programowania, jest znajdowanie minimum w tablicy (ciągu liczb). Oznaczmy taką tablicę przez

Jedną z najlepiej znanych metod wyznaczania liczb pierwszych jest sito Eratostenesa. Opiera się ona na spostrzeżeniu, w zasadzie oczywistym, że jak wyrzucimy wszystkie liczby złożone, to zostaną same liczby pierwsze...

W tym artykule omówimy zadanie Prostokąt arytmetyczny z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2011.

Poszukiwanie pierwiastków wielomianu jest jednym z podstawowych zagadnień rozważanych we wszystkich naukach ścisłych. W tym artykule zajmiemy się czymś znacznie prostszym: sprawdzaniem, czy dana liczba jest pierwiastkiem zadanego wielomianu.

Jeśli chcemy rozwiązać układ równań – taki zwykły, dwa równania liniowe z dwiema niewiadomymi – za pomocą komputera, całkiem wygodnie jest użyć metody wyznaczników...

W grafie nieskierowanym możemy obliczyć stopień każdego wierzchołka, czyli liczbę krawędzi incydentnych z tym wierzchołkiem. Przykładowo, dla grafu-koperty otrzymujemy w ten sposób ciąg stopni 4, 4, 3, 3, 2. Wykonanie takiego przekształcenia dla danego grafu jest naprawdę proste. Możemy jednak postawić pytanie odwrotne: czy mając dany ciąg liczb, możemy stwierdzić, czy odpowiada on stopniom wierzchołków jakiegoś grafu nieskierowanego, a jeśli tak, zrekonstruować ten graf?

W tym kąciku omówimy pierwsze zadanie z finału konkursu Google Code Jam 2010.

W tym numerze Delty dużo uwagi poświęcono ciągowi EKG, który zarówno z matematycznego, jak i z informatycznego punktu widzenia przejawia wiele interesujących własności. W kąciku kontynuujemy temat ciekawych ciągów liczbowych. Zajmiemy się zadaniem Ciąg z finału II Olimpiady Informatycznej Gimnazjalistów, w którym poproszono uczestników o wyznaczenie -tego wyrazu pewnego ciągu, zwyczajowo wiązanego z nazwiskiem matematyka Solomona Golomba.

Po przeczytaniu artykułu Marcina Pilipczuka trudno nie odnieść wrażenia, że nasz zasób wiedzy o zachowaniu ciągu EKG opiera się przede wszystkim na wynikach eksperymentów komputerowych, natomiast dowody otrzymanych w ten sposób hipotez pojawiają się z pewnym opóźnieniem.

W Bajtocji można spotkać wędrownych treserów pcheł. Pchły uczone są tańca, polegającego na wykonywaniu precyzyjnych skoków w rytm muzyki. Dokładnie wygląda to tak: treser układa na stole w rządku ponumerowane kolejno żetony. Na każdym żetonie, oprócz jego numeru, jest również napisany numer żetonu, na który powinna z niego skoczyć pchła – na każdym żetonie ten numer jest inny. Następnie treser ustawia po jednej pchle na każdym z żetonów i włącza muzykę. Na początku każdego taktu każda z pcheł wykonuje skok wprost na żeton, którego numer jest napisany na żetonie, na którym w danej chwili stoi.

Tym razem zajmiemy się trochę innymi kwadratami niż zazwyczaj. Chodzi mianowicie o napisy postaci czyli sklejenie jakiegoś słowa (ciągu liter) z nim samym. Przykładowymi kwadratami występującymi w języku polskim są słowa mama, kankan, rowerowe, wałowało, esemesem.