Algorytmy. Ćwiczenia
34,90 zł
Projektowanie systemów rozproszonych. Wzorce i paradygmaty dla skalowalnych, niezawodnych usług
−30%27,93 zł
PHP 7. Algorytmy i struktury danych
59,00 zł
Java. Kompendium programisty. Wydanie X
179,00 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł

Encyklopedia Algorytmów

Info Tutorial

Witaj w Encyklopedii Algorytmów!
Serwis aktualnie zawiera 42 artykuły, 8 tutoriali i 34 obrazy.

O stronie

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.

Zawartość

Najnowsze artykuły

Najnowsze samouczki

Aby przeglądać strony tematycznie, przejdź do głównej kategorii.

Czy wiesz…

Polecany artykuł

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.

Algorytm najkrótszej krawędzi
Przykładowe wykonanie algorytmu najmniejszej krawędzi
REKLAMA

Zobacz też

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.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość
Polityka prywatnościKontakt