Delta mi!

Tym razem zajmiemy się zadaniem Nurkowanie z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w 2007 roku.

Jednym z pierwszych zadań, z jakimi musi zmierzyć się każdy uczący się algorytmów lub programowania, jest znajdowanie minimum w tablicy (ciągu liczb). Oznaczmy taką tablicę przez

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

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

Jedną z najlepiej znanych metod wyznaczania liczb pierwszych jest sito Eratostenesa. Opiera się ona na spostrzeżeniu, w zasadzie oczywistym, że jak wyrzucimy wszystkie liczby złożone, to zostaną same liczby pierwsze...

W tym artykule omówimy zadanie Prostokąt arytmetyczny z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2011.

W tym miesiącu opiszemy zadanie Monety, które pojawiło się na Potyczkach Algorytmicznych w roku 2010.

Poszukiwanie pierwiastków wielomianu jest jednym z podstawowych zagadnień rozważanych we wszystkich naukach ścisłych. W tym artykule zajmiemy się czymś znacznie prostszym: sprawdzaniem, czy dana liczba jest pierwiastkiem zadanego wielomianu.

W tym kąciku rozwiążemy zadanie Prostokąty (Rectangles), które pojawiło się w 2007 roku na konkursie organizowanym przez MIT w serwisie spoj.pl.

W tym miesiącu omówimy zadanie, które rozwiązywali uczestnicy Obozu Naukowo-Treningowego im. A. Kreczmara w 2009 r.

Któż z nas nie bawił się jako dziecko w chowanego? Zabawa ta sprawia dzieciom wiele radości, mimo że z algorytmicznego punktu widzenia jest bardzo prosta. Jeżeli bowiem wszyscy ukrywający się czekają uczciwie w swoich kryjówkach, to zawsze uda się ich znaleźć – wystarczy, jeżeli szukający przejrzy wszystkie miejsca.

W grafie nieskierowanym możemy obliczyć stopień każdego wierzchołka, czyli liczbę krawędzi incydentnych z tym wierzchołkiem. Przykładowo, dla grafu-koperty otrzymujemy w ten sposób ciąg stopni 4, 4, 3, 3, 2. Wykonanie takiego przekształcenia dla danego grafu jest naprawdę proste. Możemy jednak postawić pytanie odwrotne: czy mając dany ciąg liczb, możemy stwierdzić, czy odpowiada on stopniom wierzchołków jakiegoś grafu nieskierowanego, a jeśli tak, zrekonstruować ten graf?

Zadanie omawiane w tym kąciku pochodzi z obozu treningowego drużyn rosyjskich z 2008 roku (autor zadania: Andrew Stankevich).

Aby opisać falę akustyczną, wytwarzaną przez głośnik, musimy podać, jak ciśnienie powietrza zmienia się w czasie – do tego wystarczy znać przebieg jednej wielkości – wychylenia membrany głośnika. Jeśli nasz głośnik jest podłączony do komputera, to stosowny opis fali jest produkowany przez kartę dźwiękową, która z kolei pobiera dane zapisane na jakimś nośniku danych. Na początku lat 80. XX wieku pojawił się nowy nośnik danych audio: płyta CD.

Kilkanaście lat temu zgubiłem się w lesie. Nie na tyle, żeby sytuacja była beznadziejna...

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.