Zostań zawodnikiem

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.

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

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.

27.11.2009 - Anna Piekarska
Trudność

Sito Eratostenesa

Już starożytni Grecy zastanawiali się nad zagadnieniem liczb pierwszych. Aktualnie problem zdaje się wciąż nie być dostatecznie zbadany. Jednak dziś wiemy nieco więcej niż kiedyś. Do rozwoju teorii przyczynił się zdecydowanie Eratostenes - wymyślił tzw. Sito Eratostenesa czyli dość prosty algorytm znajdowania liczb pierwszych. Prosty oczywiście dla małych liczb. Wciąż nie znamy algorytmu wielomianowego na faktoryzację.

26.11.2009 - Marcin Oczeretko
Trudność

Wyszukiwanie binarne

    W jaki sposób szybko znajdować wartości w posortowanym zbiorze? Istnieje sprytny sposób na sprawne rozwiązywanie tego problemu - wyszukiwanie binarne. Poniższy artykuł umożliwi Wam zapoznanie się z tym potężnym i zarazem bardzo prostym algorytmem.

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Algorytm Dijkstry

Zagadnienie znajdowania najkrótszej ścieżki jest dość często spotykane. Czasem widać je wprost, czasem jest jednak tylko małą częścią trudniejszego problemu, jednak niezbędną, by go rozwiązać.

25.11.2009 - Karol Konaszyński
TrudnośćTrudność

Najdłuższy podciąg rosnący

Wszędzie otaczają nas liczby: większe, mniejsze - żadnej reguły! Trzeba jednak to wszystko ogarnąć i znaleźć jakieś prawidłowości wśród nich. W tym artykule zajmiemy się znajdowaniem najdłuższego podciągu rosnącego, czyli światełko w tunelu dla tych, którzy nie lubią chaosu. Zapraszam do zabawy z liczbami!

25.11.2009 - Damian Rusak
Trudność

Podstawy algorytmów tekstowych

Aby przyswoić zasady działania algorytmów tekstowych trzeba znać podstawowe zagadnienia i definicje z tej dziedziny. Może się wydawać, że nie ma nic bardziej intuicyjnego od posługiwania się tekstem i językiem, jednak to co te pojęcia oznaczają z informatycznego punktu widzenia może być początkowo zaskakujące. Poniższy artykuł ma na celu prezentację (mam nadzieję, w miarę ciekawy sposób) terminologii, której znajomość pozwala nauczyć się wielu fascynujących algorytmów tekstowych.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com