Algorytm

Algorytm genetyczny, schemat blokowy (1) Przykład zapisu algorytmu za pomocą schematu blokowego

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

Zapis algorytmu

Algorytm można zapisać na różne sposoby. Najczęściej stosowane metody zapisu algorytmu to:

  • język naturalny (opis słowny),
  • schemat blokowy,
  • pseudokod (zapis przypominający język programowania, jednak nie będący nim),
  • język programowania.

Złożoność obliczeniowa

Do oceny algorytmu zazwyczaj wyznacza się jego złożoność czasową i pamięciową, czyli zależność pomiędzy rozmiarem danych wejściowych a czasem wykonania algorytmu i ilością wymaganej pamięci. Czas działania algorytmu jest wyrażony jako liczba operacji elementarnych (np. operacji porównania czy przypisania), które trzeba wykonać. Obliczanie czasu w fizycznych jednostkach byłoby znacznie mniej uniwersalne, ponieważ zależałoby to m.in. od szybkości komputera. Aby uprościć analizę, najczęściej bierze się pod uwagę wyłącznie wybrane operacje, określane jako operacje dominujące – są to operacje, których liczba wykonań jest proporcjonalna do liczby wykonań wszystkich operacji elementarnych.

Zazwyczaj nie jest potrzebna postać funkcji określającej złożoność, ale jedynie jej rząd wielkości. Jest to określane jako asymptotyczna złożoność obliczeniowa. Do oznaczania tej złożoności powszechnie stosuje się tzw. notację dużego O. Notacja ta określa asymptotyczne ograniczenie górne funkcji złożoności. Jeśli funkcja jest rzędu O(g(n)), to dla wystarczająco dużego n spełniona jest zależność 0≤f(n)≤cg(n), gdzie c jest stałą.

Powszechnie uznaje się, że akceptowalne są algorytmy o złożoności co najwyżej wielomianowej (O(nk), gdzie k nie zależy od rozmiaru danych wejściowych). Algorytmy o złożonościach wyższych rzędów (np. O(kn), O(n!), O(nn)) w praktyce działają w rozsądnym czasie tylko dla danych wejściowych o niewielkich rozmiarach.

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
  • Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
Ocena: +2 Tak Nie
Liczba głosów: 2.

Dodano: 27 czerwca 2017 18:10, ostatnia edycja: 30 stycznia 2019 15:49.

REKLAMA

Zobacz też

Symulowane wyżarzanie – jedna z technik projektowania algorytmów heurystycznych (metaheurystyka). Cechą charakterystyczną tej metody jest występowanie parametru sterującego zwanego temperaturą, który maleje w trakcie wykonywania algorytmu. Im wyższą wartość ma ten parametr, tym bardziej chaotyczne mogą być zmiany. Podejście to jest inspirowane zjawiskami obserwowanymi w metalurgii – im większa temperatura metalu, tym bardziej jest on plastyczny.

Jest to metoda iteracyjna: najpierw losowane jest pewne rozwiązanie, a następnie jest ono w kolejnych krokach modyfikowane. Jeśli w danym kroku uzyskamy rozwiązanie lepsze, wybieramy je zawsze. Istotną cechą symulowanego wyżarzania jest jednak to, że z pewnym prawdopodobieństwem może być również zaakceptowane rozwiązanie gorsze (ma to na celu umożliwienie wyjście z maksimum lokalnego).

Prawdopodobieństwo przyjęcia gorszego rozwiązania wyrażone jest wzorem e(f(X)−f(X'))/T (rozkład Boltzmanna), gdzie X jest poprzednim rozwiązaniem, X' nowym rozwiązaniem, a f funkcją oceny jakości – im wyższa wartość f(X), tym lepsze rozwiązanie. Ze wzoru można zauważyć, że prawdopodobieństwo przyjęcia gorszego rozwiązania spada wraz ze spadkiem temperatury i wzrostem różnicy jakości obu rozwiązań.

→ Czytaj całość

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość
Polityka prywatnościKontakt