4962385660

Rozwiązanie algorytmiczne polega na podaniu algorytmu tzn. takiego opisu działań przy pomocy operacji elementarnych, który zastosowany do poprawnych danych wejściowych daje oczekiwane wyniki.

Rozróżniamy wykonywanie algorytmów od działania twórczego.

Problemy dotyczące algorytmów:

1.    Język: jaki jest zbiór instrukcji elementarnych?

2.    Rozstrzygalność: czy istnieje algorytm rozwiązujący dany problem?

3.    Analiza poprawności: czy algorytm działa poprawnie, tzn. robi to co ma robić?

4.    Analiza złożoności: czy algorytm działa szybko?

5.    Analiza numeryczna: czy algorytm działa dokładnie?

2.3 Sortowanie liczb

•    Dane wejściowe: liczba naturalna n i ciąg liczb ai, a2,..., a_n.

•    Wynik: permutacja a'i, a^,..., o!_n ciągu a\,a2, ■ ■ ■ ,a_n taka, że a\ < a'₂ < ... < o!_n.

Przykład. Dane: 2,7,4,5,1. Wynik: 1,2,4,5,7.

Jak do tego problemu podejść systematycznie? Na przykład tak jak sortujemy rozdane karty w brydżu.

Zapis algorytmu (sortowanie przez wkładanie). (A[j] - j-ty element).

dla j:=2 do n wykonuj k:=A[j] ;

dopóki i>0 oraz A[i]>k wykonuj A[i+1] : =A [i] ; i:=i-l;

A[i+1] :=k;

Przykład.

2

2

2

1

7

4

4

2

4	5	1
7	5	1
5	7	1
4	5	7

Dane :

Wynik :

2.4 Analiza złożoności algorytmu

Analiza złożoności algorytmu jest to przewidywanie ile zasobów potrzeba do wykonania algorytmu.

Zasoby:

1.    pamięć;

2.    połączenia komunikacyjne;

3.    czas działania (dla nas najważniejszy).

5