Delta mi!

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.

W ostatnim już odcinku bestiariusza przedstawimy garść akronimów, poruszając tematy związane ze społecznym odbiorem technologii informacyjnych.

Szósty odcinek cyklu przybliży nam kilka bardziej technicznych akronimów związanych z oprogramowaniem (software)...

W piątym odcinku bestiariusza przybliżymy kilka bardziej technicznych akronimów związanych ze sprzętem komputerowym (ang. hardware). Wspominaliśmy już o ENIAC-u, jednym z pierwszych komputerów, którego nazwa też była akronimem. Przykłady innych komputerów z tamtych czasów to EDVAC (Electronic Discrete Variable Automatic Computer), PDP (Programmed Data Processor) i pierwszy komputer wykorzystany w biznesie LEO (Lyons Electronic Office).

W czwartym odcinku przyjrzymy się kilku akronimom o specyficznej budowie lub historii...

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.

W jubileuszowym odcinku kącika omówimy zadanie Równoważność palindromiczna, które pojawiło się na Obozie Naukowo-Treningowym im. A. Kreczmara w 2010 roku.

W listopadowym kąciku omawiamy zadanie Kosmita z Internetowych Mistrzostw Polski w Programowaniu z roku 2006.

Tym razem omówimy zadanie Świąteczny łańcuch, które rozwiązywali w tym roku uczestnicy drugiego etapu XXIII Olimpiady Informatycznej.

W tym miesiącu omówimy zadanie Icy Roads z obozu w Petrozawodsku z roku 2013.

Tym razem na warsztat weźmiemy zadanie Remote Rover, które pojawiło się na jednym z konkursów TopCoder w roku 2005. Naszym zadaniem jest znalezienie najszybszej trasy dla marsjańskiego łazika poruszającego się po zróżnicowanym terenie.

W tym miesiącu zadanie Tower of Hay, które pojawiło się na konkursie USACO Open Gold w roku 2009.

Wyobraźmy sobie ucznia, który ma napisać esej na temat gospodarki w południowych rejonach Brazylii. Powiedzmy, że historia ta dzieje się w czasach, gdy dostęp do Internetu nie był tak powszechny jak teraz. Uczeń w celu zgromadzenia potrzebnych materiałów udaje się do biblioteki, z której wypożycza rocznik statystyczny oraz kseruje potrzebne strony z encyklopedii. Następnie wraca do domu i zabiera się do pisania...

W drugim odcinku bestiariusza przedstawimy popularne akronimy związane z sieciami komputerowymi...

Zagadnienie kolorowania cyklu niejednokrotnie pojawiało się na konkursach programistycznych, m.in. na Mistrzostwach Europy Środkowej w Programowaniu Zespołowym (zadanie Beijing Guards z roku 2004), czy też Mistrzostwach Polski w Programowaniu Zespołowym (zadanie Słoneczna wyspa z roku 2010).

Dana jest -elementowa tablica którą chcemy odwrócić, czyli spowodować, że jej elementy będą zapisane w kolejności

Tym razem omówimy rozwiązanie zadania Zapis wieżowy z Akademickich Mistrzostw Polski w Programowaniu Zespołowym z 2006 roku.

W tym miesiącu rozwiążemy zadanie Darmowe rozmowy z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w roku 2011.

W zeszłym miesiącu zajmowaliśmy się uogólnieniem następującego zadania: dla danego kwadratu rozmiaru podzielonego na pól, z których niektóre były zabronione, należało znaleźć prostokąt o największym polu, który nie zawierał żadnego zabronionego pola. W tym numerze rozważymy jeszcze inną wariację tego zadania, a mianowicie będziemy szukać największych prostokątów, które zawierają co najwyżej zabronionych pól (nazwiemy je prostokątami prawie pustymi).

Postęp w dziedzinie komputerów dokonuje się niezwykle szybko. Trzydzieści lat temu komputer był w polskich domach nowością, a dziś nie wyobrażamy sobie bez niego życia. Rozwój technologii i oprogramowania powoduje konieczność wymyślania przez producentów coraz to nowych nazw, w których gąszczu użytkownikom komputerów łatwo się zagubić. Często zdarza się też, że pewną nazwę znamy jedynie jako akronim, ale nie bardzo wiemy, co się kryje w jego rozwinięciu. W tej kolumnie spróbujemy przybliżyć Czytelnikom choć część informatycznej terminologii. W pierwszym odcinku powiemy dość ogólnie o tym, co siedzi w naszym komputerze.

W tym miesiącu zajmiemy się dość klasycznym zadaniem. Dany jest kwadrat rozmiaru podzielony na pól, przy czym niektóre pola są zabronione. Dowolny zawarty w tym kwadracie prostokąt, który nie zawiera żadnego pola zabronionego, nazwiemy prostokątem pustym. Należy znaleźć pusty prostokąt o jak największym polu.

W pierwszej części tego artykułu pokazaliśmy, że dla szczególnej klasy grafów (kraty i ich podgrafy), istnieje działający w czasie wielomianowym algorytm, który wyznacza liczbę doskonałych skojarzeń dla dowolnego grafu z tej klasy. Ten wynik można uogólnić na szerszą klasę grafów - a konkretnie na grafy planarne, czyli takie, które można narysować na płaszczyźnie tak, by żadne z ich krawędzi się nie przecinały.

Zajmiemy się takim oto zadaniem: dana jest szachownica rozmiaru i kostek domina, z których każda może przykryć dwa sąsiednie pola szachownicy. Na ile sposobów możemy przykryć całą szachownicę?

W kąciku kontynuujemy przygodę z zadaniami, do których rozwiązania przydaje się znajomość problemu plecakowego. Tym razem w nieco trudniejszej jego wersji, w której każdy przedmiot ma swój rozmiar oraz wartość Standardowe pytanie, które możemy wtedy zadać, to np. jaka jest największa sumaryczna wartość przedmiotów, które możemy zapakować do plecaka, nie przekraczając jego udźwigu

Tym razem zadanie Candies z Bałtyckiej Olimpiady Informatycznej z 2010 roku.

Dzisiejsze zadanie pochodzi z VII obozu informatycznego ILOCAMP.

Rozpoczynając na początku lat 80. XX wieku studia doktoranckie na Uniwersytecie w Erlangen, Karlheinz Brandenburg raczej nie przypuszczał, że wyniki jego pracy przyczynią się do zrewolucjonizowania branży muzycznej na całym świecie. A zaczęło się od tego, że jego promotor, profesor Dieter Seitzer, rozważał zagadnienie przesyłania muzyki liniami telefonicznymi...

W tym kąciku omówimy zadanie Wiercenia, które pojawiło się na Potyczkach Algorytmicznych w roku 2009.

W tym miesiącu omówimy zadanie Kuglarz z pierwszej rundy Potyczek Algorytmicznych 2014. Tytułowy kuglarz zaprasza przechodniów do następującej gry...

Jednym z najtrudniejszych zadań, z którym mierzyli się uczestnicy światowych finałów konkursu ACM ICPC w roku 2014, było zadanie pt. Metal Processing Plant.

W tym kąciku omówimy zadanie Filary, które pojawiło się na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym 2014. Zadanie, pomimo prostej treści i (jak się za chwilę przekonamy) całkiem prostego rozwiązania, sprawiło sporo kłopotów drużynom startującym w zawodach i ostatecznie zostało rozwiązane tylko przez jedną z nich.

Niektórzy znajdują co rano na progu swojego domu butelkę ze świeżym mlekiem. Kubuś Puchatek każdego ranka znajduje tam garnczków miodu. Garnczki są różnej wielkości i Kubuś każdego dnia stara się opróżniać je w innej kolejności...

W tym kąciku omówimy zadanie Fotoradary, które pojawiło się w 2013 roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

W tym miesiącu omówimy zadanie Sequence, które pojawiło się na tegorocznej edycji Bałtyckiej Olimpiady Informatycznej.

Zadanie Skarb pojawiło się w kwalifikacjach do konkursu Google Code Jam 2013.

Tym razem zadanie Smok z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2005, które odbyły się na Uniwersytecie Jagiellońskim.

W tym kąciku dwa zadania z cyklu naszych ulubionych, tzn. na pierwszy rzut oka ciężkie do ugryzienia, ale mające ładne i krótkie rozwiązania.

Tym razem zajmiemy się zadaniem Routing z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym z 2006 roku...

W tym kąciku omówimy dwa zadania z Potyczek Algorytmicznych 2012. Pomimo krótkich rozwiązań, zadania te wymagały od zawodników niemałej dozy pomysłowości.

Czy komputery potrafią myśleć? Ta kwestia nurtuje informatyków od ponad pół wieku. W 1950 roku angielski matematyk Alan Turing zadał podobne, ale bardziej precyzyjne pytanie. A mianowicie, czy komputer (lub program komputerowy) jest w stanie przekonać człowieka, że sam również jest istotą ludzką. Turing zaproponował wtedy następujący test (który dziś, na jego cześć, zwany jest testem Turinga). Jeśli człowiek-sędzia podczas rozmowy prowadzonej w języku naturalnym (ale za pośrednictwem pisma) równocześnie z człowiekiem oraz z programem komputerowym nie będzie w stanie stwierdzić, który z interlokutorów jest który – to taki program zalicza test Turinga.

Tym razem w kąciku zadanie Świetliki, z którym mierzyli się finaliści Potyczek Algorytmicznych 2013.

Ten numer Delty jest zdominowany przez tematykę skojarzeń w grafach. Dla przypomnienia: graf nieskierowany to zbiór wierzchołków połączonych krawędziami, skojarzenie zaś w tym grafie to taki podzbiór krawędzi  że każdy wierzchołek grafu jest incydentny z co najwyżej jedną krawędzią z 

W tym kąciku zajmiemy się zadaniem Dwóch generałów, które pochodzi z Uniwersyteckich Zawodów Informatycznych organizowanych przez Uniwersytet Jagielloński, a konkretnie z konkursu z października 2009 roku.

Nasz znajomy informatyk zdecydował się zainwestować część swoich oszczędności na giełdzie papierów wartościowych. Jak na informatyka przystało, do grania na giełdzie postanowił zaprząc komputer. W tym celu, korzystając z najnowszych trendów sztucznej inteligencji, napisał program, który na podstawie przeszłych notowań giełdowych przewiduje, jak kurs akcji będzie się zmieniał w przyszłości, i podejmuje decyzje o kupnie bądź sprzedaży. Nasz znajomy przetestował program, uruchamiając go na dużym zbiorze archiwalnych notowań. Zastanawia się teraz, jak dobrze jego program sobie poradził – stanął zatem przed problemem wyznaczenia najlepszej możliwej gry na giełdzie, jeśli znamy wszystkie notowania.

W tym kąciku zajmiemy się zadaniem Delayed search, które pojawiło się w 2004 r. w konkursie Internet Problem Solving Contest, organizowanym co roku przez Słowaków. Zadanie jest wariacją na temat znanej zabawy „zgadnij, o jakiej liczbie myślę”...

W tym kąciku omówimy Dwa torty – kolejne zadanie z finałowej rundy Potyczek Algorytmicznych 2012.

Za pomocą kolorowania wielomianów można udowodnić Zasadnicze twierdzenie algebry w zaskakująco elementarny sposób...

Jednym z klasycznych problemów algorytmicznych jest tzw. problem plecakowy...

ASCII. Podstawowym sposobem reprezentacji znaków we współczesnych komputerach jest przyjęty w 1967 r. ASCII (czyt. aski, ang. American Standard Code for Information Interchange). Definiuje on 128 znaków, wśród których znajdują się 33 niedrukowalne znaki sterujące, znak odstępu, 52 litery (wielkie i małe litery alfabetu angielskiego), 10 cyfr i 32 znaki interpunkcyjne. ASCII przyporządkowuje każdemu znakowi liczbę z zakresu 0–127 (lub równoważnie szesnastkowo 0–7F).