Ulubione zadania mistrzów, Zostań zawodnikiem, Dla zawodników

01.12.2011 - Michał Karpiński
TrudnośćTrudność

Otoczka wypukła

Znajdowanie otoczki wypukłej jest jednym z podstawowych problemów w geometrii obliczeniowej. Fakt, że w ciągu ostatnich 50 lat powstało bardzo wiele publikacji na temat tego zagadnienia świadczy o jego znaczeniu w dziedzinie algorytmiki. W niniejszym artykule zajmiemy się znajdowaniem otoczki wypukłej na płaszczyźnie.

01.12.2011 - Michał Karpiński
TrudnośćTrudność

Trie

Podstawową strukturą danych wykorzystywaną w algorytmach tekstowych jest drzewo trie (czyt. tri lub traj). Jest to kolejne rozwiązanie dla problemu wyszukiwania wzorca (i nie tylko). Z drzew trie korzystamy, gdy liczba zapytań jest na tyle duża, że nie opłaca się użycie klasycznych metod takich jak KMP czy BM (szczególnie gdy tekst wejściowy składa się ze sporej liczby słów). Drzewa te nadają się np. do sprawdzania poprawności pisowni.

22.11.2011

Wielka Przesmycka Reloaded 2011 - omówienie zadań

W tym roku mieliśmy dla Was 6 zadań. Każde z nich w dwóch wersjach, basic i professional, różniących się limitami na dane wejściowe. W niektórych zadaniach (Mona Lisa, Drużyna) wersja professional wymagała rozwiązania o lepszej złożoności czasowej, w niektórych (Nobel, Mrówki) chcieliśmy w ten sposób sprawdzić czy umiecie udowodnić poprawność Waszego algorytmu, a w jeszcze innych (Połącz kropki, To może być toczeń) zmiana limitów sprawiała, że zadanie wymagało diametralnie innego podejścia.

09.02.2011 - Anna Piekarska
TrudnośćTrudność

Beetle

W 2009 roku udało mi się dostać do reprezentacji Polski na Bałtycką Olimpiadę Informatyczną. Zadaniem, które sprawiło mi najwięcej radości (chociażby dlatego, że udało mi się je rozwiązać pomimo tego, że początkowo wydawało mi się dość trudne), było beetle. Jest na tyle ciekawe, że chciałabym je Wam przedstawić.

18.10.2010 - Łukasz Zatorski
Trudność

Wprowadzenie do zachłanności i dynamiki

czyli krótki podręcznik dobrego złodzieja.

O tym kiedy wolno być zachłannym, a kiedy wybieranie tego co najlepsze nie zawsze popłaca, co musimy wiedzieć pakując swój plecak lub wydając resztę oraz jak znaleźć optymalne rozwiązanie nie uciekając się się do magii.

03.10.2010 - Michał Karpiński
TrudnośćTrudnośćTrudność

Drzewce

Drzewa zrównoważone to niezwykle przydatne struktury danych. Można ich użyć np. do tworzenia słowników, w których kluczowym jest wykonywanie wszystkich operacji w jak najlepszym czasie. Strukturą, którą będziemy się zajmowali w niniejszym artykule jest drzewiec (z ang. treap), który łączy w sobie cechy binarnego drzewa przeszukiwań i kopca (również binarnego).

03.10.2010 - Damian Rusak
TrudnośćTrudność

Algorytm Bellmana-Forda

Znajdowanie najkrótszej ścieżki w grafie ma wiele wariantów. Przyjrzyjmy się takiemu: statek kosmiczny podróżuje między galaktykami - niektóre podróże są kosztowne czasowo - wehikuł po prostu leci przez przestrzeń kosmiczną. Ale ma też czasem możliwość skorzystać z tuneli czasoprzestrzennych - nie dość, że zmienia położenie, to jeszcze cofa się w czasie. Jak wtedy znaleźć najszybszą drogę z jednej galaktyki do drugiej?

02.10.2010 - Michał Karpiński
TrudnośćTrudność

Mosty i punkty artykulacji

Umiejętność wyszukiwania mostów i punktów artykulacji przydaje się nie tylko w konkursach algorytmicznych. Wszędzie tam, gdzie mamy do czynienia ze strukturą grafu np. sieć dróg, torów kolejowych, kabli internetowych wiedza zawarta w niniejszym artykule okazuje się niezbędna. Można śmiało powiedzieć, że temat, którym się będziemy zajmować to kolejny ważny krok na drodze do zostania mistrzem teorii grafów.

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Najdłuższy wspólny podciąg

Problem najdłuższego wspólnego podciągu jest niezwykle istotny zarówno z punktu widzenia informatyki, jak i pozornie odłegłych od niej dziedzin nauki - np. biologii. Niezależnie od tego czy chcemy skutecznie podpowiadać poprawną pisownię, czy może szukamy podobieństw w strukturze dwóch łańcuchów DNA, algorytmy obliczające najdłuższy wspólny podciąg okażą się niesłychanie przydatne.

01.10.2010 - Michał Karpiński
Trudność

Przeszukiwanie grafu w głąb (DFS)

Algorytm przeszukiwania w głąb ( ang. depth first search ) jest jedną z najprostszych metod przechodzenia po grafie. Jednocześnie, metoda ta jest używana jako podstawa do wielu bardziej skomplikowanych algorytmów grafowych. Z tego powodu wiedza na temat przechodzenia grafu w głąb jest niezbędna dla osób rozpoczynających swoją przygodę z algorytmiką.

07.06.2010 - Filip Sieczkowski
TrudnośćTrudnośćTrudnośćTrudność

Trwałe struktury danych

W tym artykule opowiem nieco o zupełnie odmiennym od standardowego podejściu do tworzenia struktur danych ─ strukturach trwałych, a także przedstawię implementacje kilku najpopularniejszych struktur ─ stosów, drzew wyszukiwań binarnych i kolejek ─ w wersji trwałej.

23.02.2010 - Tomasz Górzny
TrudnośćTrudnośćTrudnośćTrudność

Answer these queries

W tym artykule prezentuję rozwiązania trzech zadań ze SPOJa. Wszystkie pochodzą z (dość długiego) cyklu "Answer these queries" i (mimo dość podobnie wyglądających sformułowań) wymagają połączenia kilku różnych, i to dość nietrywialnych, pomysłów. Ze względu na zróżnicowany poziom trudności lekturę polecam zarówno początkującym, jak i starym wyjadaczom.

19.02.2010 - Wiktor Janas
TrudnośćTrudnośćTrudnośćTrudność

Query on a tree III

Każdy może czasem potrzebować k-tego elementu w n-wierzchołkowym drzewie. Przedstawimy kilka sposobów, mniej lub bardziej efektywnych, jak go znaleźć. Po drodze dowiemy się dlaczego STL wcale nie jest taki fajny, jak szukać mediany i że oszczędzanie połowy pracy na każdej operacji daje świetne efekty.

15.12.2009 - Łukasz Zatorski
Trudność

Zabawa z drzewami

„Głupiec i mędrzec nie widzą tego samego drzewa.” - mawiał William Blake. Drzewa dostarczają życiodajnego tlenu, w słoneczny dzień służą cieniem, a ich abstrakcyjne odpowiedniki są nieodzownym elementem arsenału dobrego programisty. Tylko, no właśnie, o czym dokładnie mowa i jak się do tego zabrać? W poszukiwaniu kilku klasycznych problemów informatycznych dotyczących drzew zapraszam do... Puszczy Amazońskiej.

14.12.2009 - Michał Karpiński
Trudność

Drzewa przeszukiwań binarnych

 skrócie BST (ang. binary search tree), jak sama nazwa wskazuje, ma strukturę drzewa binarnego. Tego typu drzewa stosuje się do szybkiego wyszukiwania jak również do realizacji bardziej abstrakcyjnych struktur danych. Uważam, że każda osoba chcąca zgłębić tajniki algorytmiki powinna zaznajomić się z drzewem BST, ponieważ jest to jedna z podstawowych struktur danych.

10.12.2009 - Kacper Król
Trudność

Wstęp do Teorii Grafów

W niniejszym artykule przedstawimy parę pojęć i zagadnień, dzięki którym będziemy mogli w konkretny sposób opisywać problemy, a także w łatwy sposób rozwiązywać je. Mowa tu o grafach. [Początki tej dziedziny sięgają XVIII wieku, kiedy to właśnie za pomocą tej struktury – grafu – udało się rozwiązać problem pewnego spaceru]. Zapraszam zatem do lektury!

09.12.2009 - Dominik Rusak
Trudność

Krótki wstęp do algorytmów geometrycznych

    Geometria jest dziedziną matematyki, która zazwyczaj budzi rozmaite, najcześciej przeciwstawne uczucia. Jedni uważają ja za nudną - tym się dziwię. Inni dostrzegają piękno zajmowania się obiektami geometrycznymi, wymagającego pomysłowości, cierpliwości i nieraz chwili iluminacji.

03.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Arytmetyka modularna

Arytmetyka modularna jest kolejnym narzędziem matematycznym ułatwiającym infomatykom rozwiązywanie problemów algorytmicznych.

02.12.2009 - Krzysztof Piecuch
TrudnośćTrudność

Zasada włączeń i wyłączeń

W informatyce - podobnie jak w życiu - niektóre problemy łatwiej rozwiązać, a inne trudniej. W niniejszym artykule pokażemy jak problem trudny rozwiązać za pomocą problemów łatwiejszych. Problemem jakim się zajmiemy będzie liczenie elementów sumy zbiorów.

30.11.2009 - Michał Karpiński
Trudność

Kopiec (binarny)

Kopiec jest to tablicowa struktura danych mająca duże znaczenie w algorytmice, jako że jest podstawą dla bardziej skomplikowanych obiektów. Jeśli chcesz bliżej poznać tą przypominającą drzewo strukturę, to niniejszy artykuł jest dla Ciebie.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com