Przeskocz do treści

Delta mi!

  1. obrazek

    Informatyka

    XX Olimpiada Informatyczna

    W dniach 12-15 marca 2013 r. w Warszawie odbyły się zawody III stopnia jubileuszowej, XX Olimpiady Informatycznej. Do finału zostało zakwalifikowanych 96 zawodników. W ciągu dwóch dni zawodów finałowych zawodnicy mieli do rozwiązania w sumie sześć zadań programistycznych ocenianych od 0 do 100 punktów.

  2. Informatyka

    Krzaczki na ekranie

    ASCII. Podstawowym sposobem reprezentacji znaków we współczesnych komputerach jest przyjęty w 1967 r. ASCII (czyt. aski, ang. American Standard Code for Information Interchange). Definiuje on 128 znaków, wśród których znajdują się 33 niedrukowalne znaki sterujące, znak odstępu, 52 litery (wielkie i małe litery alfabetu angielskiego), 10 cyfr i 32 znaki interpunkcyjne. ASCII przyporządkowuje każdemu znakowi liczbę z zakresu 0–127 (lub równoważnie szesnastkowo 0–7F).

  3. obrazek

    Algorytmy

    Problemy 3sum-trudne w geometrii

    Kiedy rozwiązujemy jakiś problem informatyczny, często naszym celem jest podanie jak najefektywniejszego algorytmu. Jednak czasem możemy natknąć się przy tym na ścianę” – danego problemu nie da się rozwiązać tak efektywnie, jak byśmy tego chcieli. Najpowszechniej znanym przykładem opisanego zjawiska jest klasa problemów NP-zupełnych. O problemach z tej klasy (a należy do niej wiele naturalnych i praktycznych zagadnień) podejrzewa się, że nie da się ich rozwiązać w czasie wielomianowym względem rozmiaru danych wejściowych. Niestety, tylko podejrzewa się, a rozstrzygnięcie tej hipotezy (znanej też jako math?) jest obecnie najsłynniejszym otwartym problemem informatyki teoretycznej.

  4. Algorytmy Informatyczny kącik olimpijski

    Infiltracja

    Tym razem zajmiemy się zadaniem z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym 2012, które odbyły się w Warszawie. Zadanie zatytułowane Infiltration zostało rozwiązane przez 31 spośród 112 drużyn i było średnim pod względem trudności zadaniem na tych zawodach.

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

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

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

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

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

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

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

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

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