Klasyfikacja algorytmów

Klasyfikacja algorytmów

Sekwencyjny

algorytmy z rozgałęzieniami

Cykliczne

Mieszane

Podział algorytmów ze względu na przeznaczenie

algorytmy numeryczne (matematyczne) — wykonują obliczenia numeryczne;

algorytmy przeszukujące — badają określony zbiór danych w celu wyszukania określonego elementu lub elementów;

algorytmy porządkujące — ustawiają wybrane dane według określonego kryterium;

algorytmy rekurencyjne — rozwiązują zadanie, które można podzielić na mniejsze części będące kopią wzorca:

algorytmy szyfrujące / deszyfrujące — służą do szyfrowania danych:

algorytmy kompresji danych — Optymalny kompresji zapisu danych.

Podział algorytmów ze względu na sposób konstruowania

„dziel zwyciężaj" — problem jest dzielony na kilka mniejszych problemów. które znów są dzielone na mniejsze — a2 do momentu, gdy otrzymamy problemy łatwe do rozwiązania; mniejsze problemy rekurencyjnie, a następnie ich rozwiązania Są łączone, aby OtrzvnaĆ rozwiązanie zadania początkowego; to z najlepszych metod rozwiązywania zadań; przykładem może tu znajdowanie nai- mniejszego elementu zbioru CZY liczb:

pmgramowanie dynamiczne — metoda podobna do poprzedniej, czyli problem jest dzie- lony na kilka mniejszych. a ich rozwiązania wykorzystuje Się do problemu wyjściowego; można je stosować, gdy podproblemy nie są niezależne, czyli kiedy podproblemy mogą zawierać te same podproblemy;

metoda zachłanna — wykonuje takie działanie, które w danej Chwili wydaje Się naj. korzystniejsze; ten rodzaj algorytmu nie ocenia, CZY w kolejnych krokach jest Sens wykonywać dane działanie. tylko podejmuje decyzje lokalnie optymalne:

poszukiwanie i wyliczanie — zbiór danych jest przeszukiwany aż do znalezienia rozwłazama;

algorytmy heurystyczne — algorytm, który nie zapewnia ływności rozwiązania zadania Optymalnego, tylko daje dobre rozwiązanie w określonym czasie.

Gdy tworzymy algorytm, a potem na jego — program komputerowy, musimy pamiętać o oszczędności pamięci i Czasu Obliczeń. W celu algorytmu wprowadzono pojęcie złożoności obliczeniowej która jest ilością Cza- Su niezbędnego do rozwiązywania problemu w Od liczby danych wejściowych. To pojęcie dotyczy złożoności pamięcimvei i czasowej. Złożoność pamișiowa zależy od wielkości pamięci komputerowej potrzebnej do wyko. nania algorytmu w postaci programu komputerowego. ZbżonoŚĆ Czasowa pozwala na Określenie Czasu do wykonania algorytmu.

Istnieją następujące metody zapisu algorytmu:

słowny opis — mało konkretny sposób opisu algorytmu; rozpoczyna się dyskusją, w jaki sposób można rozwiązać dane zadanie; pozwala na wybór metody rozwiązania danego problemu;

lista kroków — dokładny sposób opisywania obliczeń i ich kolejności; poszczególne kroki zawierają opis operacji, które maja być wykonane przez algorytm; kroki Są rowane zgodnie z kolejnością ich wykonywania;

schemat blokowy — najpopularniejszy sposób, który Opiera się na blokach Oraz połączeniach między nimi; tu zapisane operacje, które mają być wykonane, a połączenia za pomocą Strzałek wyznaczają ich wykonywania;

drzewo algorytmiczne (drzewo — w drzewie algorytmu można wyróżnić korzeń — wierzchołek, w którym rozpoczynają sie działania algorytmu, wierzchołki pośrednie, w których są umieszczane operacie wykonywane w algorytmie, oraz wierzcholki końcowe (tzw. liście), które odpowiadają różnym wynikom zakończenia obliczeń w algorytmie;

pseudokod — przy wykorzystaniu tego sposobu rezygnujemy z reguł składniowych danego języka programowania na rzecz czytelności instrukcji;

język algorytmiczny (język programowania) —najbardziej ścisły i zrozumiały dla komputera opis algorytmu; algorytm zapisany w języku programowania nazywamy programem.

PRZYKŁAD 1

Rozważmy zadanie polegające na wyświetleniu w postaci ciągu rosnącego trzech liczb a, b, c. Drzewo algorytmiczne tego zadania będzie miało postać jak na rysunkiu poniżej: