Przeskocz do treści

Delta mi!

  1. Algorytmy

    Zawieramy wielokąty

    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.

  2. Algorytmy Informatyczny kącik olimpijski

    Czworokąty wypukłe

    W tym kąciku zajmiemy się zadaniem Quadrilaterals z obozu w Petrozawodsku w 2006 roku. Na płaszczyźnie dane jest math 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.

  3. Algorytmy

    Kliki

    Dany jest graf nieskierowany math Kliką nazwiemy taki podzbiór wierzchołków math że każde dwa wierzchołki w zbiorze math są połączone krawędzią w grafie math  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.

  4. Algorytmy Informatyczny kącik olimpijski

    Odśnieżanie

    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 math  wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każ parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.

  5. Algorytmy

    Zliczanie podziałów liczby: algorytm Eulera

    Podziały liczb są ciekawymi obiektami kombinatorycznymi o dosyć skomplikowanych własnościach. W tym artykule przedstawimy dwa algorytmy zliczania takich obiektów. Pierwszy prosty algorytm będzie działał w czasie math  i pamięci math natomiast drugi, pochodzący od Eulera i oparty na tzw. liczbach pentagonalnych, w czasie math  i pamięci math

  6. Algorytmy Informatyczny kącik olimpijski

    Dwa przyjęcia

    W niedawno wydanej książce W poszukiwaniu wyzwań – zbiorze zadań z konkursów programistycznych – Filip Wolski opisał rozwiązanie zadania Dwa przyjęcia z finału XII Olimpiady Informatycznej. W zadaniu tym występuje math osób, z których niektóre się znają (wiemy które). Chcemy podzielić ten zbiór na dwa rozłączne podzbiory (przyjęcia) w taki sposób, aby zmaksymalizować liczbę osób, które mają parzystą liczbę znajomych na przyjęciu, na którym przebywają...

  7. Algorytmy

    Największy wspólny dzielnik

    Podobnie jak wyznaczanie liczb pierwszych, problem znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych ma klasyczne i zapewne wszystkim Czytelnikom znane rozwiązanie. Mowa oczywiście o algorytmie Euklidesa, jednym z najstarszych do dziś używanych algorytmów. Jest to rozwiązanie bardzo proste w implementacji, a w wersji z dzieleniem – efektywne: pozwala wyznaczyć NWD dwóch liczb nie większych niż math w czasie math W pewnych przypadkach istnieją jednak rozwiązania asymptotycznie szybsze.

  8. obrazek

    Internet

    Dlaczego niepotrzebne nam hasło do skrzynki mailowej?

    Zapewne zdecydowana większość Czytelników ma skrzynkę poczty elektronicznej. Dostęp do skrzynki uzyskuje się przez podanie w specjalnym formularzu na stronie internetowej nazwy użytkownika i hasła. Te dane są następnie szyfrowane i wysyłane do serwera pocztowego, który porównuje je z umieszczonymi na nim wzorcami. Tak, w dużym uproszczeniu, wygląda proces weryfikacji użytkownika na serwerze.

  9. obrazek

    Informatyka

    XX OLIMPIADA INFORMATYCZNA

    Drodzy Czytelnicy Delty, przedstawiamy Wam zadania zawodów I stopnia jubileuszowej, XX Olimpiady Informatycznej. Tych z Was, którzy chcą wziąć udział w Olimpiadzie, zobowiązujemy do przeczytania „Zasad organizacji zawodów XX OI”, w których zawarte są najważniejsze informacje o tym, w jaki sposób należy przygotować swoje rozwiązania. Rozwiązania należy zgłaszać przez stronę sio.mimuw.edu.pl, na której znajdują się także wybrane odpowiedzi na pytania zawodników, narzędzia do sprawdzania rozwiązań pod względem formalnym oraz forum służące do wymiany doświadczeń między zawodnikami. Termin nadsyłania rozwiązań przedstawionych tu zadań I etapu upływa 12 listopada 2012 roku.

  10. Algorytmy Informatyczny kącik olimpijski

    Drogi

    W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

  11. Algorytmy

    Ucieczka

    Wyobraź sobie, Drogi Czytelniku, że jesteś kapitanem okrętu wojennego i w trakcie jednej z misji znalazłeś się na środku morza leżącego na terytorium wroga. Wiesz, że wróg rozmieścił w tej strefie pewną (skończoną) liczbę radarów. Każdy radar ma określony zasięg, być może różny w przypadku różnych radarów, i jest w stanie wykryć każdy podejrzany obiekt, który znajdzie się w jego zasięgu. Naszym siłom wywiadowczym udało się wykraść plan rozmieszczenia radarów. Na jego podstawie chcesz stwierdzić, czy możesz wydostać się z wrogich wód niezauważony przez radary.

  12. Informatyka

    O sierotce, co chciała się mózgiem elektronowym wyręczyć

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