8719220776

METODY PROBABILISTYCZNE I STATYSTYKA - INFORMACJE UZUPEŁNIAJĄCE

1. ANALIZA ALGORYTMÓW POD WZGLĘDEM ŚREDNIEGO ZACHOWANIA¹

1.1. Uwagi wstępne

Istnieje wiele problemów, których człowiek nie jest w stanie rozwiązywać, posługując się nawet najszybszymi z istniejących komputerów. Nawet kolejne generacje coraz szybszych komputerów niewiele zmieniają tę sytuację. Panuje powszechne przekonanie, że cała nadzieja w coraz szybszych algorytmach. To przekonanie najlepiej oddają następujące powiedzenia:

•    Najlepszym sposobem przyspieszania pracy komputerów jest obarczanie ich mniejszą liczbą działań - /?alf Gomory, szef ośrodka badawczego IBM.

•    Największe przyspieszenie osiąga się nie pedałem gazu, a głową - Ferrari.

Analiza algorytmu obejmuje ocenę poprawności wykonywanych na jego podstawie obliczeń oraz ocenę złożoności algorytmu. W wyniku oceny złożoności algorytmu określane są zasoby potrzebne do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są czas wykonywania obliczeń, niezbędna pamięć czy liczba procesorów. Za twórców podstaw oceny złożoności uważani są Juris Hartmanis i Richard Stearns.

Podejście do oceny poprawności obliczeń przedstawiono w rozdziale 5 „Obliczanie niezawodności prostych układów sprzętowych i systemów programowych”.

Ocena złożoności algorytmów jest szczegółowo omawiana w ramach przedmiotu „Algorytmy i złożoność”, stąd po krótkim wprowadzeniu dalsze rozważania ograniczono zgodnie z tytułem rozdziału do analizy algorytmów pod względem średniego zachowania.

Wyróżnia się trzy rodzaje złożoności:

•    Złożoność obliczeniowa - liczba elementarnych operacji wykonywanych w algorytmie.

•    Złożoność czasowa - czas wykonania algorytmu.

•    Złożoność pamięciowa - wielkość pamięci potrzebnej do przechowywania danych, oraz pośrednich i końcowych i wyników obliczeń

Złożoność czasowa określona jest przez złożoność obliczeniową oraz dodatkowo zależy od parametrów wykorzystywanych komputerów i ich systemów operacyjnych, języków w których były napisane programy, użytych kompilatorów itp.

Wraz z zmniejszaniem cen układów elektronicznych nawet najtańsze komputery maja pamięci operacyjne o dużej pojemności, co spowodowało zmniejszenie znaczenia złożoności pamięciowej.

Złożoność obliczeniowa z reguły nie zależy wyłącznie od rozmiaru danych, ale może się znacznie różnić dla danych wejściowych o identycznym rozmiarze.

3

1

Maciej M. Sysło, Anna B. Kwiatkowska, Złożoność obliczeniowa i efektywność algorytmów, http://www.proiekt.gammanet.p1/book/infalo/stronv/l/i/30Q04.html Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Projektowanie i analiza algorytmów, ftp://ftp.helion.pl/online/proalg/proalg-1 .pdf

Algorytmy i struktury danych/Wstęp: poprawność i złożoność algorytmu,

http://wazniak.mimuw.edu.pl/index.php?title=Algorvtmv i struktury danvch/Wst%C4%99p: poprawno%C5 %9B%C4%87 i z%C5%82o%C5%BCono%C5%9B%C4%87 algorytmu Złożoność obliczeniowa:

http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87 obliczeniowa http://bonito.pl/k-71070781-proiektowanie-i-analiza-algorvtmow http://www.wsti.pl/materialv/slaidv2 SO.pdf

Data ostatniej aktualizacji: piątek, 29 października 2010