Delta mi!

Na artykule Problemy 3sum-trudne w geometrii autor podał trzy wersje problemu PolygonContainment, które są uważane za trudne – nie umiemy ich rozwiązać w czasie (istotnie) lepszym niż kwadratowy. Uważni Czytelnicy na pewno zauważyli, że nie jest tam wspomniane o wersji, w której wielokąty są wypukłe i dopuszczamy dowolne przesunięcia (ale nie obroty). Ten brak jest w pełni uzasadniony, gdyż tę wersję problemu można rozwiązać w czasie liniowym względem liczby wierzchołków wielokątów, co pokażemy poniżej.

W tym kąciku zajmiemy się zadaniem Quadrilaterals z obozu w Petrozawodsku w 2006 roku. Na płaszczyźnie dane jest  punktów w położeniu ogólnym (tzn. żadna trójka punktów nie leży na jednej prostej). Należy wyznaczyć liczbę czworokątów wypukłych, których wierzchołki znajdują się wśród podanych punktów.

Dany jest graf nieskierowany Kliką nazwiemy taki podzbiór wierzchołków  że każde dwa wierzchołki w zbiorze  są połączone krawędzią w grafie  Problem znalezienia w grafie kliki o jak największej liczbie wierzchołków jest NP-zupełny, a jak wiadomo, dla takich problemów nikt jeszcze nie pokazał algorytmu wielomianowego. Podobne trudności są z algorytmem dla problemu zliczania klik w grafie, choć tutaj stosowną klasę złożoności stanowią tzw. problemy #P-zupełne.

Zadanie Odśnieżanie z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara można sformułować w języku teorii grafów następująco. W nieskierowanym, ważonym, spójnym grafie  wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każdą parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.

Wyobraźmy sobie następującą grę. Na stole w jednym rzędzie leży  monet o różnych nominałach. Dwoje graczy – Ania i Bartek – wykonuje na przemian ruchy, zaczyna Ania. Ruch polega na zabraniu jednej monety z lewego lub prawego końca rzędu. Wynikiem gry jest, oczywiście, suma nominałów monet zgromadzonych przez każdego z graczy. Jak powinna grać Ania, by uzyskać jak największą sumę, jeśli wie ona, że Bartek będzie grał optymalnie (tzn. będzie starał się zmaksymalizować swoją sumę)?

W tym miesiącu omówimy zadanie, które pojawiło się w pierwszej edycji konkursu Potyczki Algorytmiczne, w roku 2005.

Wyobraźmy sobie biedną sierotkę, której macocha nakazała oddzielić groch od fasoli. Chcąc nie chcąc, dziewczę siada w kącie izby przed pokaźnym kopcem grochu pomieszanego z fasolą i zaczyna pracę. Praca jest niezwykle monotonna: sierotka bierze nasiono z górki i jeśli to fasola, odrzuca je na lewą stronę, a jeśli groch – na prawą; i tak w kółko...

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.

W pewnym mieście fryzjer goli tylko tych, którzy nie golą się sami. Kto goli fryzjera? – to pytanie jest powszechnie znane jako paradoks Russella, nazwany tak na cześć matematyka Bertranda Russella (1872–1970), który w swoim słynnym dziele Principia Mathematica (napisanym wspólnie z Alfredem Whiteheadem) dał podwaliny pod fundament matematyki oparty na logice.

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

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

O ciekawych problemach związanych z kapeluszami pisaliśmy już w  Delcie nie raz, ale że dobrego nigdy za wiele, napiszemy też i w tym numerze, tyle że inaczej.

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.

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.

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

Weźmy długi pasek papieru i złóżmy go na pół. Następnie, nie rozkładając, złóżmy go w tę samą stronę jeszcze dwa razy. W końcu, rozprostujmy złożenia tak, by papier zginał się pod kątem  Otrzymamy obiekt jak na rysunku 1.

Oglądając szpargały, jakie w sposób nieunikniony gromadzą się w redakcyjnych szufladach, znalazłem plan lekcji wydany przez Deltę latem 1982 roku – kartonik, format B4.

O tym jak szybko można obliczać współczynniki dwumianowe .

Tym razem omawiamy zadanie o układaniu planu zajęć. Zadanie to pojawiło się na Obozie Naukowo-Treningowym im. A. Kreczmara w 2007 r.