Przeskocz do treści

Delta mi!

  1. Algorytmy

    Sortowanie biegunowe a dualizacja

    Jedną z najczęściej wykonywanych operacji w geometrii obliczeniowej jest sortowanie biegunowe (zwane też kątowym) zbioru math punktów na płaszczyźnie względem wybranego punktu. Innymi słowy, chcemy uporządkować punkty math według współrzędnej kątowej w układzie biegunowym zaczepionym w wybranym punkcie math Stosując jeden z efektywnych algorytmów sortowania, operację tę można zrealizować w czasie math

  2. Algorytmy

    Programy liniowe, gry i algorytmy

    Czy programy liniowe mają coś wspólnego z informatyką? Okazuje się, że bardzo wiele. Po pierwsze, istnieją (bardzo ciekawe!) efektywne algorytmy rozwiązujące programy liniowe. Ponadto, programy liniowe są kluczowym narzędziem w optymalizacji kombinatorycznej, algorytmach aproksymacyjnych czy algorytmach online...

  3. Informatyka

    Strumienie, czyli pochwała lenistwa

    „Tato, jak policzyć do nieskończoności?” – takie pytanie zadał mi niedawno mój czteroletni syn. Odpowiedziałem coś w stylu „nigdy nie skończysz”. W każdym razie liczenie do nieskończoności może się relatywnie szybko znudzić, może więc to zadanie, jak wiele innych monotonnych zadań, powierzyć komputerowi? A czy komputer potrafi policzyć do nieskończoności?

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

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

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

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

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

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

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

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

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

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

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