Delta mi!

W dniach 12-16 kwietnia 2016 r. w Warszawie odbyły się zawody III stopnia XXIII Olimpiady Informatycznej. Zostało do nich zakwalifikowanych 96 zawodników. W ciągu dwóch dni zawodów finałowych zawodnicy mieli do rozwiązania w sumie sześć zadań programistycznych ocenianych od 0 do 100 punktów.

Tym razem zajmiemy się zadaniem, które pojawiło się na kolokwium dla studentów pierwszego roku informatyki na Uniwersytecie Warszawskim.

Czym jest Bitcoin? Najkrótsza odpowiedź na to pytanie brzmi: kryptowalutą. Ale nie w takim sensie krypto-, jak w słowie kryptoreklama. Pierwszy człon tego terminu pochodzi od kryptologii, czyli nauki kojarzącej nam się głównie z szyframi i maszyną szyfrującą Enigma używaną przez Niemców podczas wojny. To właśnie twierdzenia i konstrukcje z tej dziedziny stoją za funkcjonowaniem i bezpieczeństwem Bitcoina.

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

W swojej pracy astronomowie często korzystają z katalogów będących wynikiem wielkich przeglądów nieba. Zebrane w nich dane poddawane są różnorakim analizom. Ważne jest przy tym, aby katalogi charakteryzowały się jak największą kompletnością i jednorodnością. Niejednokrotnie podczas analizy statystycznej dobrze poznanych typów obiektów wykrywane są źródła rzadko spotykane lub wykazujące niezwykłe zachowanie. Dlatego też odpowiedni sposób klasyfikacji obserwowanych obiektów jest bardzo istotnym, o ile nie najistotniejszym krokiem, który należy wykonać przed przystąpieniem do zaawansowanego badania właściwości fizycznych obserwowanych obiektów niebieskich.

Piętnastego marca stracona została rubież intelektualnej przewagi człowieka nad sztuczną inteligencją, za jaką była uznawana maestria gry w Go. Zakończyła się ostatnia, piąta partia między AlphaGo, programem firmy DeepMind (będącej własnością Google) i Lee Se-dolem (9 dan - najwyższy stopień wtajemniczenia), jednym z najlepszych, jeżeli nie najlepszym zawodowym graczem. AlphaGo wygrał pierwsze trzy rozgrywki. Lee Se-dol wygrał czwartą i, po niezwykle zaciętej walce, przegrał ostatnią.

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 tym miesiącu omówię zadanie Wielomian, które pojawiło się na finale Potyczek Algorytmicznych w 2005 roku.

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

Książka telefoniczna, katalog w bibliotece, lista płacy w przedsiębiorstwie, spis lokatorów domu, mały rocznik statystyczny, karty pracy robotników jakiegoś przedsiębiorstwa, katalog znaczków pocztowych, kartoteka przestępców, kartoteka pacjentów w przychodni lekarskiej - wszystko to są przykłady zbiorów informacji.

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.

Najwytrwalsi Czytelnicy Delty mogą znać tę zagadkę. Pojawia się ona w wielu wariantach, my zajmiemy się wersją błotną.

W rozważaniach naszych nie będziemy chwilowo dążyli do ścisłej definicji algorytmu ani do formalizacji zapisu algorytmów. Celem naszym będzie wyrobienie u Czytelnika przekonania, że algorytm jest uściśleniem przepisu postępowania prowadzącego do zamierzonego celu.

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

Otworzyłem mój pierwszy numer Delty z marca 1979 roku. Czytam adres Redakcji: nazwa ulicy, numer budynku, numer pokoju, kod pocztowy, nazwa miasta. Nie podano e-maila ani strony www. Nawet nie ma numeru telefonu. Wtedy telefon (stacjonarny, bo o komórkach nikt nie słyszał) był w naszym kraju trudno osiągalnym dobrem luksusowym. Programy komputerowe pisało się na papierze i oddawało do wyperforowania na kartach lub taśmie, by po kilku dniach otrzymać wydruk z wynikami. Komputer widzieli nieliczni. Sieć komputerowa - taki termin jeszcze nie istniał w języku polskim.

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ę?

Tym razem omówimy zadanie Fiber-optic Network, które pojawiło się na zeszłorocznych zawodach ACM-ICPC Asia Mudanjiang Regional Contest.

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