Delta mi!

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

Nikt nie lubi sprawdzania swojej pracy, prawda? Udało nam się rozwiązać zadanie, bo wpadliśmy na pomysł i potrafiliśmy go zrealizować. Podobnie programista często potrafi napisać cały kod potrzebny do wykonania zadania, nim go choć raz uruchomi, by sprawdzić, czy program robi to, co było zamierzone. W taki „wir pracy” każdy z nas nieraz wpadł. W końcu właśnie w tym czujemy się najlepiej – w rozwiązywaniu problemów.

W tym kąciku proponuję zadanie polecane przez mojego korespondenta w Jekaterynburgu, mieście znanym również z turnieju Ural Sport Programming Championship, którego zeszłoroczną atrakcją był bezwzględny pojedynek pięciu najlepszych drużyn z Rosji z pięcioma najlepszymi drużynami z Chin. Popatrzmy na zadanie, którego nie udało się rozwiązać żadnej z nich!

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

To, co widzisz, przeglądając strony takie jak Facebook lub Gmail, nazywamy interfejsem użytkownika. Jeden serwis często ma bardzo dużo odmian interfejsów użytkownika, np. Facebook oglądany przez przeglądarkę internetową w telefonie wygląda zupełnie inaczej niż na komputerze. Pewnie o tym wiesz. Ale czy wiesz, że większość tych serwisów ma jeszcze jeden interfejs użytkownika, zupełnie nieznany, a przeznaczony tylko i wyłącznie dla programistów?

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.

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.

Wyobraźmy sobie, że wchodzimy do lokalu znanej sieci pizzerii i zamawiamy swoją ulubioną pizzę. Kelner czym prędzej biegnie z naszym zamówieniem do kuchni i już po chwili rozpoczyna się proces wytwórczy. Z czego składa się taka pizza? Zasadniczo jest to płaskie ciasto w kształcie koła, posmarowane sosem pomidorowym, na którym układa się różne dodatki, a całość posypuje serem i wstawia na jakiś czas do pieca. Trudno chyba o prostszy przepis. Kucharz przystępuje zatem do dzieła, jednak na potrzeby naszej historyjki wyobraźmy sobie, że przygotowuje on naszą pizzę od podstaw. I to samiuteńkich podstaw...

Co wspólnego ma ocean i system USOS? Okazuje się, że znacznie więcej niż tylko literę „o” występującą w obydwu słowach.

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.

Algorytm to sposób rozwiązania pewnego problemu. Informatyka i matematyka od dawna badają różnego rodzaju problemy, szukając dla nich algorytmów, najczęściej możliwie szybkich. My jednak tym razem postąpimy wręcz przeciwnie: zajmiemy się algorytmami wyjątkowo wolnymi.

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

Jak każdy system informatyczny, USOS wymaga implementacji rozmaitych algorytmów, których zadaniem jest realizacja procesów gospodarczych (w ramach uczelni). Projektowanie algorytmów to pasjonująca dziedzina aktywności ludzkiej. Wszyscy lubią programować. Reszta informatyki praktycznej wydaje się nudna...

W tak dużej organizacji, jaką jest uczelnia wyższa, przy tak dużej liczbie uczestniczących w zajęciach studentów i wykładowców oraz tak bogatej ofercie dydaktycznej, przygotowanie dla wszystkich studentów indywidualnych planów zajęć, zgodnie z ich zainteresowaniami i preferencjami, to duże wyzwanie logistyczne...

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

Zapewne każdy z nas dobrze zna muszkę owocówkę (drosophila melanogaster, co tłumaczy się dosłownie jako ciemnobrzucha miłośniczka rosy). Dla większości ta dobra znajomość niekoniecznie musi budzić dobre skojarzenia – być może z uwagi na jej natrętny muszy charakter i masową obecność letnią porą w pobliżu nieopatrznie zostawionych bez przykrycia słodkich owoców. Niemal równie powszechna jest wiedza o jej zasługach naukowych w dziedzinie genetyki. Mało kto zdaje sobie sprawę z tego, że to nie pies Łajka, a właśnie muszka była pierwszą ziemską istotą, która wybrała się w podróż kosmiczną. Ale czy ktoś uwierzy, że muszka pomogła również w rozwiązywaniu pewnego problemu z pogranicza matematyki i informatyki?

Co da się obliczyć, a czego się nie da? Dziś informatycy pytają o to rutynowo w kontekście przeróżnych problemów, jednak pierwsza odpowiedź na to pytanie pojawiła się na dobrą sprawę, jeszcze zanim ktokolwiek zdążył je zadać, i wprawiła środowisko naukowe w zakłopotanie.

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.

Mówi się, że każdy nosi w plecaku buławę. Akurat w odniesieniu do studenta prawdziwe jest powiedzenie, że każdy nosi w kieszeni komputer i wcale to nie oznacza, że studiuje informatykę. Może określenie „komputer” jest nieco na wyrost, choć to całkiem sprawny „komputerek”, z własnym procesorem, pamięcią, magistralą i systemem operacyjnym. Mowa o ELS, czyli Elektronicznej Legitymacji Studenckiej.

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

Szanowny Czytelniku, okazuje się, że obok zwykłego świata, znanego wszystkim nam od dziecka, istnieje też świat alternatywny, w którym jest zanurzone studiowanie i ogół pracy wielu polskich uczelni. Co więcej, świat ten pozwala na teleportację do analogicznych światów stowarzyszonych z uczelniami innych krajów. Ten alternatywny świat to USOS...