Elementy analizy algorytmóW



Pobieranie 29,51 Kb.
Data15.01.2018
Rozmiar29,51 Kb.

ELEMENTY ANALIZY ALGORYTMÓW

  1. Każdy algorytm powinien wykazywać następujące cechy:

  • poprawność – rozwiązuje zadany problem, dla którego go utworzono

  • skończoność – realizuje program dla wszystkich danych

  • złożoność i efektywność – rozwiązuje problem dobrze wykorzystując zasoby sprzętowe.

  1. Poprawność:

  • całkowita poprawność – dla wszystkich danych wejściowych obliczenia zostaną zakończone

  • częściowa poprawność – dla wszystkich danych, dla których obliczenia się zakończą wyniki będą poprawne.

  • dobra określoność – polecenia i operacje są zrozumiałe dla użytkownika i kolejność jest właściwie określona

  • uniwersalność – związana jest z problemem, który algorytm rozwiązuje, umożliwienie rozwiązania wszystkich zadań zgodnych ze specyfikacją problemu.

Przykład: Analiza algorytmu iteracyjnie (wielokrotne powtarzanie) rozwiazującego

a wprowadź n

b zmiennej silnia nadaj wartość 1

c zmiennej i nada j wartość 1

d zmiennej silnia przypisz jej wartość pomnożoną przez i

e zwiększ wartość i o 1



f jeżeli i > n idź do g, jeśli nie idź do d

g wyprowadź wynik: silnia

Dla każdej wprowadzone danej wynik silnia spełnia warunek końcowy, dla wszystkich wprowadzonych danych obliczenia kończą się. Ewentualne przyszłe sygnalizowane przez program błędy będą konsekwencją tylko i wyłącznie złego zapisu w konkretnym języku programowania (składniowe, nie logiczne)

Implementacja w JavaScript:



function Silnia_I(n)

{

wynik = 1;

for (k = 1; k <= n; ++k)

{

wynik *= k;

}

return wynik;

}

Zadanie. Sprawdź działanie algorytmu dla n = 5.




  1. Skończoność algorytmu polega na tym, że algorytm gwarantuje rozwiązanie problemu w skończonej liczbie kroków. Poniższy algorytm ma za zadanie wypisać wszystkie liczby naturalne nieparzyste z zadanego przedziału:

podaj a

podaj b


sprawdź nieparzystość a

dopóki a parzyste wykonuj

zwiększ wartość a o 2

wypisz a


Brakuje sprawdzenia nieparzystości a na początku. Pętla nie znajdując nieparzystego a będzie w nieskończoność dodawać 2. Należałoby po sprawdzeniu nieparzystości i uzyskaniu wartości logicznej 0 dodać jeden do bieżącej wartości a.

  1. Zadanie: Podaj własny przykład błędnego, nieskończonego algorytmu.

  2. Złożoność obliczeniowa algorytmu – zależy od liczby niezbędnych do ukończenia działania operacji. Zależy od wielkości zbioru danych, na jakich pracuje algorytm. Np. Wypisywanie elementów bez powtórzeń wymaga obok zdefiniowania samej tablicy wymaga kilku kroków: wylosowanie, zaokrąglenia, sprawdzenia wartości logicznych wyrażeń, wypisanie. Podstawowe operacje to losowanie i porównanie. Zwiększenie ilości wymiarów tablicy spowoduje zwiększenie liczby kroków.



  1. Zadanie: Powyższą implementację w JavaScript zapisz w postaci pseudojęzyka (jak w punkcie2).

  2. Złożoność pamięciowa to wielkość pamięci niezbędna do wykonania, czyli wielkość pamięci zajmowana przez zmienne i pliki programu. Szczególnie obciążają pamięć algorytmy rekurencyjne (odwołujące się do samej siebie). Dane są układane na stos (liniowa struktura danych, ww której dane są układane na „wierzch” i z niego pobierane. Wielkość zajmowanej pamięci zależy od głębokości rekurencji.

  3. Efektywność algorytmu polega na tym, że rozwiązuje on dany problem w możliwie najmniejszej liczbie kroków, co przekłada się na czas, i przy najmniejszym obciążeniu pamięci. Ocenia się ją w praktyce. Dobrym przykładem może być przeszukiwanie zbioru liczb naturalnych w poszukiwaniu liczb pierwszych – podniesienie górnej granicy wyszukiwania znacząco wpłynie na czas pracy, gdyż liczba operacji rośnie znacząco.

  4. Przykłady algorytmów zawierających błędy – znajdź je:

  • algorytm sprawdzający czy słowo jest palindromem:

  1. znajdź ilość liter słowa n

  2. sprawdź czy f (n) = f (1), gdzie f (n) to litera na n-tej pozycji

  3. sprawdź czy dla każdego k < n/2 jest spełniony warunek: f (k) = f (n – k)

  4. jeżeli 2 i 3 spełnione to jest to palindrom

  • algorytm sortowania bąbelkowego:

  1. wczytaj elementy do tablicy (jednowymiarowej) o rozmiarze n

  2. dla wszystkich par sąsiednich elementów sprawdź czy t[i] > t[i-1] - jeśli nie zamień je miejscami

  3. powtórz procedurę z punktu 2 n razy

  4. wypisz posortowane elementy

Przykład sortowania bąbelkowego w JavaScript








...





Palindromy





Podaj wyraz:











©operacji.org 2017
wyślij wiadomość

    Strona główna