Witaj w Encyklopedii Algorytmów!
Serwis aktualnie zawiera 49 artykułów, 9 tutoriali
i 41 obrazów.
Encyklopedia algorytmów to strona internetowa opisująca wybrane zagadnienia z dziedziny algorytmiki. Jest ona kierowana do osób interesujących się algorytmiką, np. do studentów informatyki. Strona ma przedstawiać omawiane zagadnienia w sposób jak najbardziej przystępny, a jednocześnie możliwie fachowy. Oprócz typowych artykułów strona zawiera też samouczki (tutoriale), które przedstawiają wybrane algorytmy na przykładach, krok po kroku.
Aby przeglądać strony tematycznie, przejdź do głównej kategorii.
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
Algorytm działa podobnie do algorytmu Kruskala poszukującego minimalnego drzewa rozpinającego. Polega on na kolejnym dołączaniu do rozwiązania najkrótszych spośród dopuszczalnych krawędzi.
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.
Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).
Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.
Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).