RSS
 

Archiwum dla kategorii ‘1. Istota postępowania algorytmicznego’

Złożoność algorytmów

02 paź

Długość oczekiwania na wynik działania programu zależy od wielkości danych wejściowych oraz od zastosowanego algorytmu, a także od środowiska, w którym program został uruchomiony, czyli od procesora, pamięci czy systemu operacyjnego.

Ile operacji elementarnych wykona algorytm A na danych wejściowych x? Spodziewana odpowiedź: Algorytm A dla danych x wykona f(x) operacji elementarnych.

Niech A będzie algorytmem. Koszt algorytmu A, oznaczany przez KA(x), to liczba wykonanych przez algorytm A operacji elementarnych, przy danych wejściowych x.

Operacjami dominującymi nazywa się operacje elementarne decydujące o czasie wykonywania danego algorytmu.

Wyznaczenie dokładnej złożoności obliczeniowej algorytmu bywa zadaniem trudnym. Za zadowalające uważa się określenie rzędu funkcji ograniczającej złożoność obliczeniową algorytmu z dołu i z góry. Często przyjmuje się, że złożoność obliczeniowa algorytmu jest funkcją rozmiaru danych wejściowych algorytmu n. Uważa się, że funkcja g(n) jest rzędem funkcji ograniczającej funkcję f(n) z góry, jeżeli można znaleźć taki argument n0, że dla wszystkich n > n0, wykres funkcji f(n) leży pod wykresem funkcji c * g(n), dla pewnej stałej dodatniej c. Analogicznie, intuicje związane są z pojęciem rzędu funkcji ograniczającej złożoność algorytmu z dołu.

Analiza efektywności algorytmów

Dla algorytmu Suma, niezależnie od przyjętego zbioru operacji dominujących:
Tsuma(n) ϵ O(n).

CZASY DZIAŁANIA ALGORYTMÓW PRZY DANEJ ZŁOŻONOŚCI CZASOWEJ
Czasy działania algorytmów przy danej złożoności czasowej

 

Algorytm, od problemu do programu

01 paź

Algorytm jest ściśle określoną procedurą obliczeniową, która dla danych wejściowych produkuje żądane dane wyjściowe, zwane wynikiem. Algorytm jest ciągiem kroków obliczeniowych, przekształcanych dane wejściowe w dane wyjściowe.

Analiza algorytmów jest działem informatyki zajmującym się oceną i optymalizacją algorytmów rozwiązywania problemów informatycznych. Głównym zadaniem tego działania jest jest szykanie odpowiedzi na następujące pytania:
- Czy dany problem może by rozwiązany przy wykorzystaniu dostępnych zasobów?
- Czy istnieje algorytm rozwiązywania danego problemu?
- Czy znaleziony algorytm jest optymalny?
- Czy zastosowanie znalezionego algorytmu rzeczywiście rozwiązuje problem?

Od problemu do algorytmu
Mając jakiś konkretny problem, wystarczy zakwalifikować go do pewnej znanej klasy problemów, pobrać z biblioteki gotowy algorytm i zapisać go w ulubionym języku programowania. Proces taki jest nazywany kodowaniem. Następnie pozostaje już tylko uruchomić program i czekać na wyniki.

Gdy problem nie daje się łatwo zakwalifikować do znanych klas problemów należy ustalić, które parametry rozpatrywanego problemu są dane, tj. mogą stanowić dane wejściowe algorytmu, a których parametrów problemu się poszukuje, tj. będą stanowiły wynik działania algorytmu. Następnie należy przejść do konstrukcji algorytmu. Konstrukcja ta zależy od złożoności problemu i wiedzy oraz pomysłowości. Ostatnim etapem jest realizacja algorytmu w konkretnym języku programowania. Czynności realizowane od przedstawienia problemu po dostarczenie gotowego programu są nazywane łącznie programowaniem.

Każdy algorytm musi spełniać następujące warunki:
- skończoność opisu: tekst opisujący algorytm jest skończony,
- efektywność i wydajność:
a) efektywność: algorytm,
b) wydajność: zadanie,
- terminacja: po skończonej liczbie kroków wszystkie kroki algorytmu zostaną wykonane,
- jednoznaczność: przebieg algorytmu jest jednoznaczny (deterministyczny) w każdym kroku.

Biorąc pod uwagę praktyczne wykorzystanie algorytmów, często również zakłada się następujące ich własności:
- adaptacyjność – małe zmiany w specyfikacji problemu powodują niewielkie zmiany w algorytmie,
- wytrzymałość – niepoprawne dane wejściowe nie powodują powstawania niepoprawnego wyniku,
- optymalność – algorytm znajduje rozwiązanie przy minimalnym wykorzystaniu zasobów.