Delta mi!

W tej pracy przedstawimy groźne zjawisko - błąd wiszących referencji - jakie występuje w programowaniu obiektowym, np. w C++, Pascalu, C. W kolejnym artykule omówimy rozwiązanie pozwalające wyeliminować ten błąd. Zacznijmy od krótkiej ekspozycji problemów, jakie napotykamy podczas zarządzania pamięcią obiektów w każdym języku programowania obiektowego.

W tym miesiącu omówimy zadanie New Year and Forgotten Tree, które pojawiło się na konkursie Good Bye 2015 na platformie Codeforces.

Drogi Czytelniku Majsterkowiczu! W tym odcinku Migawki wreszcie będzie ciekawie. Opiszemy, jak samodzielnie skonstruować prawdziwy zegarek mechaniczny!

W tym odcinku prezentujemy najtrudniejsze zadanie z zeszłorocznej Międzynarodowej Olimpiady Informatycznej.

Tak zwany Problem Stopu to problem decyzyjny, którego wejściem jest jakiś program i jakieś dane a którego rozwiązaniem (wyjściem) jest stwierdzenie, czy program uruchomiony na danych zakończy swoje działania w skończonym czasie.

Sprawdzanie poprawności dowodów matematycznych często wymaga sporej wiedzy i ogromu nużącej pracy. O ile dochodzenie do zrozumienia istoty dowodu, czyli dlaczego dane twierdzenie matematyczne zachodzi, może sprawiać Czytelnikowi dużo satysfakcji, o tyle weryfikowanie wszystkich szczegółów dowodu jest zajęciem dość niewdzięcznym. Z tego powodu od wielu już lat trwają badania nad zaprzęgnięciem komputerów do tej żmudnej części pracy...

W informatyce losowość jest bardzo przydatna. Często bardzo ułatwia rozumowania, pozwala na piękne i klarowne argumenty używające, na przykład, metody probabilistycznej. Nieraz łatwo znaleźć algorytm używający losowości (randomizowany) i działający szybko, podczas gdy znalezienie szybkiego algorytmu deterministycznego jest trudne lub w ogóle takiego nie znamy. Z losowością jest jednak pewien problem...

W niniejszym artykule chciałbym przedstawić Czytelnikom technikę, która może okazać się pomocna przy rozwiązywaniu różnych problemów informatycznych.

W tym miesiącu proponujemy zadanie Przeciąganie liny, które pojawiło się w podwarszawskim Józefowie, podczas zeszłorocznej Bałtyckiej Olimpiady Informatycznej. Zadanie opisuje problem optymalizacji znanej wakacyjno-urlopowej zabawy. Co ciekawe, warstwa fabularna proponowanego rozwiązania - choć pozostaje w podobnych klimatach - to jednak odchodzi od liny na rzecz plecaka.

Wyobraź sobie, Czytelniku, że jesteś dość leniwym nauczycielem w podstawówce. Uczniowie mieli zadane, jako pracę domową, ogromne ilości przykładów z tabliczki mnożenia i dodawania w zakresie pięćdziesięciu. Biorąc pod uwagę liczbę dzieci w klasie, sprawdzanie tego to istna męczarnia. Ale przecież można trochę oszukać, np. spośród dziesiątków przykładów, spojrzeć na losowe pięć i przyjąć, że jeśli są dobrze, to reszta też jest pewnie dobrze. A czytania zostaje dużo mniej.

W tym miesiącu omówimy zadanie Nim 3, które pojawiło się na Obozie Naukowo-Treningowym im. A. Kreczmara w 2013 roku.

W noworocznym kąciku omówimy zadanie Wykrywanie wrednej usterki pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej, która odbyła się w Kazaniu (Rosja). Autorzy zadania oczekują od nas, że pomożemy zdiagnozować usterkę, która wkradła się do bazy danych zaimplementowaną przez niefrasobliwego inżyniera Ilszata.

Jak wiadomo, problemy dzielimy zasadniczo na te łatwe i na te trudne. Dla człowieka taki podział jest oczywiście bardzo subiektywny. Dla komputera - jak się zaraz okaże - są to pojęcia naprawdę ostre i zupełnie precyzyjne.

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.

Czy już naprawdę nawet w Delcie musi być o seksie? Sytuacja wygląda trochę jak rozprawa "Słoń a Polska", przy czym w XIX wieku niektórym wszystko kojarzyło się ze sprawą polską, a teraz z czymś nieco innym. Zaniepokojonych Czytelników spieszymy uspokoić, że rzeczy nie mają się aż tak źle, bo artykuł naprawdę dotyczy rozmnażania płciowego i informatyki.

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.

Od komputera oczekujemy przede wszystkim precyzji i dokładności. Program szukający wzorca w edytowanym tekście czy arkusz kalkulacyjny podsumowujący nasze miesięczne wydatki ma po prostu dać poprawny wynik. Wszelkie przejawy niedeterminizmu, losowości czy jakiejś niestabilności przywołują skojarzenia z działaniem niepożądanym. Zwykle to prawda: dobry program ma obliczyć, narysować czy wyanimować dokładnie to, czego od niego chcemy. Okazuje się jednak, że czasem losowość jest nie tylko wskazana, ale wręcz niezbędna.

Czy każdy problem da się rozwiązać? Pesymiści odpowiedzą, że nie - życie nie jest łatwe. A optymiści? Być może niektórzy powiedzą, że przy odpowiednim podejściu tak. Nie będziemy jednak z nimi dyskutować, bo Czytelnicy Delty dobrze wiedzą, że nie chodzi nam tutaj przecież o życiowe problemy. Trzeba więc sprecyzować pytanie: co uważamy za problem i czym miałoby być jego rozwiązanie?

Gdy mówimy, że coś jest złożone, zazwyczaj chcemy wyrazić, że jest w jakimś sensie skomplikowane, nietrywialne, składa się z wielu prostszych elementów...

W tym miesiącu, chcąc polecić Czytelnikom kącika książkę Zaprzyjaźnij się z algorytmami, przedstawimy jedno zadanie z tej pozycji. Wybieramy się na wyprawę w góry.

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

W tym artykule zakładam, że Czytelnik choć trochę programował. W szczególności zna podstawy jakiegoś języka programowania, np. Pascala. Jeśli to podstawowe założenie jest spełnione, to - jestem o tym przekonany - mogę śmiało założyć, że jest mu znane również pojęcie tablicy...

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.

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.