Delta mi!

Abstrakcja (czyli uproszczenie) jest w informatyce wszechobecna. Mając jakiś obiekt, wiemy zazwyczaj, co powinniśmy mu wprowadzić na wejście i czego spodziewać się na wyjściu. Takie informacje nas już w zupełności satysfakcjonują. Możemy używać tego obiektu, stroniąc od szczegółów jego budowy. I tak, tworząc procesor, możemy pominąć to, z czego są zbudowane bramki logiczne. Projektując system operacyjny, nie musimy przejmować się szczegółami budowy procesora, a pisząc zwykły program, nie wnikamy w szczegóły działania systemów operacyjnych. Oczywiście, takie podejście ma mnóstwo zalet. Ma też jednak pewną wadę.

Z artykułu Wojciecha Śmietanki wypływa ważny morał: przystosowanie algorytmu do działania na maszynie równoległej wymaga często zupełnie innego spojrzenia na dany problem. Okazuje się jednak, że nawet w przypadku architektury jednoprocesorowej optymalizacja algorytmu może wymagać od nas całkiem pomysłowych przeróbek. W tym artykule podamy dwa przykłady, w których kluczową okaże się kolejność, w jakiej wykonujemy operacje.

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

Dziesięć lat temu kolejne generacje procesorów charakteryzowały się wykładniczo rosnącą częstotliwością taktowania. Teraz ta sytuacja uległa zmianie. Obecnie to liczba rdzeni w jednym procesorze zaczyna rosnąć wykładniczo. W użytku są już procesory firmy Intel dla zwyczajnych PC-tów mające 8 rdzeni, a co jakiś czas pojawiają się informacje o tym, że niedługo zostanie wyprodukowany procesor o 50 rdzeniach...

O pewnym zadaniu z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara.

Napisanie programu, który generuje rysunek fraktala, idealnie nadaje się na zadanie dla początkującego programisty. Proste reguły prowadzące do powstania skomplikowanych wzorów powodują, że przy stosunkowo niewielkim wysiłku programistycznym można osiągnąć całkiem ambitne efekty wizualne. Ponadto samopodobieństwo fraktali pozwala ćwiczyć jedną z podstawowych koncepcji programistycznych – rekurencję.

W dniach od 5 do 9 kwietnia 2011 r. w Trójmieście odbyły się zawody III stopnia XVIII Olimpiady Informatycznej. W finale wzięło udział 80 zawodników, którzy w ciągu dwóch dni mieli do rozwiązania w sumie sześć zadań programistycznych ocenianych od 0 do 100 punktów.

Jednym z zadań, które zostały postawione przed uczestnikami akademickich drużynowych zawodów programistycznych ACM ICPC Dhaka Regional Contest 2010, było zadanie o nieco mylącym tytule Network Flow (Przepływ w sieci).

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.

Tym razem przyjrzymy się zadaniu Training z Międzynarodowej Olimpiady Informatycznej 2007.

W  Delcie 7/2009 Marek Cygan opisał pewien sposób radzenia sobie z tym, że dla niektórych trudnych problemów nie potrafimy znaleźć szybkiego algorytmu. Autor rozważał klasę problemów NP-trudnych – czyli takich, których prawdopodobnie nie można rozwiązać w czasie wielomianowym – i pokazywał, że dla wielu z nich można w efektywny sposób skonstruować nie dokładne, lecz przybliżone rozwiązanie.

W tym kąciku spróbujemy rozwiązać zadanie Electric needs pochodzące z drużynowych zawodów studenckich z serii ACM ICPC, a konkretnie z mistrzostw Ameryki Łacińskiej 2010.

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.

W naszym zespole badawczym analizujemy wiele różnych zagadnień, które występują w różnych aspektach. Nic w tym dziwnego, wszak algorytmika jest bardzo szeroką dziedziną. Zdarza się i tak, że to samo zagadnienie pojawia się w wielu kontekstach. Taka sytuacja ma miejsce w przypadku problemu drzewa Steinera.

W tym kąciku zajmiemy się rozwiązaniem zadania pochodzącego z jednej z finałowych rund konkursu TopCoder Open 2010, o nazwie Shrooks on the Board.

W sporcie stosowane są różne systemy prowadzenia rozgrywek. Jednym z nich jest tzw.  system pucharowy, w którym zwycięzca meczu kwalifikuje się do dalszych gier, przegrany zaś odpada z turnieju. Aby system był bardziej sprawiedliwy, dokonuje się początkowego rozstawienia przeciwników, tak by teoretycznie najsilniejsi spotkali się jak najpóźniej.

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.

Także w świecie komputerów posługujemy się różnymi miarami. Podstawową jednostką mierzącą ilość danych jest bajt (B).

Czy zastanawiałeś się, drogi Czytelniku, dlaczego wyszukiwarka wyświetla adresy stron będących odpowiedzią na Twoje zapytanie właśnie w takiej, a nie innej kolejności?

Tematem kolejnej edycji Kącika jest zadanie pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej o nazwie Oszczędny kod (ang. Saveit).

W tym odcinku zajmiemy się zadaniem, które zamiast na zawodach, pojawiło się na... kolokwium (z Algorytmów i Struktur Danych). Stanowiłoby ono bardzo ładne zadanie na zawodach.

Tym razem dwa zadania „z haczykiem”.