uzupelnienia_mp.pdf

METODY PROBABILISTYCZNE

I STATYSTYKA

INFORMACJE UZUPEŁNIAJĄCE

SPIS TREŚCI

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

1.1. U WAGI WSTĘPNE ...........................................................................................................3

1.2. S ZACOWANIE RODZAJU / KLASY ZŁOśONOŚCI OBLICZENIOWEJ DANEGO ALGORYTMU .....4

1.3. P RZYKŁADOWE WYZNACZANIE ZŁOśONOŚCI OBLICZENIOWEJ ........................................5

1.4. S YMULACYJNA OCENA ZŁOśONOŚCI ALGORYTMÓW .......................................................8

1.5. P RZYKŁADOWE PYTANIA TESTOWE ..............................................................................12

1.6. Z ADANIA NA ĆWICZENIA RACHUNKOWE ......................................................................14

2. OBLICZANIE NIEZAWODNOŚCI PROSTYCH UKŁADÓW SPRZĘTOWYCH I

SYSTEMÓW PROGRAMOWYCH .................................................................................17

2.1. U WAGI WSTĘPNE .........................................................................................................17

2.2. P OJĘCIE NIEZAWODNOŚCI ............................................................................................18

2.3. P OPRAWNOŚĆ , NIEZAWODNOŚĆ I ODPORNOŚĆ OPROGRAMOWANIA ...............................21

2.4. Z WIĘKSZANIE NIEZAWODNOŚCI OPROGRAMOWANIA ....................................................23

2.5. O BLICZANIE NIEZAWODNOŚCI PODSTAWOWYCH KONFIGURACJI UKŁADÓW

SPRZĘTOWYCH ..................................................................................................................26

2.6. Z ADANIA NA ĆWICZENIA RACHUNKOWE ......................................................................29

3. ANALIZA WYDAJNOŚCI PROSTYCH UKŁADÓW SPRZĘTOWO-

PROGRAMOWYCH - ZASTOSOWANIA TEORII PROCESÓW

STOCHASTYCZNYCH ...................................................................................................30

3.1. U WAGI WSTĘPNE .........................................................................................................30

3.2. O CENA WYDAJNOŚCI OPROGRAMOWANIA ....................................................................31

3.3. P ODSTAWOWE POJĘCIA TEORII MASOWEJ OBSŁUGI ......................................................31

3.4. M ODEL JEDNOKANAŁOWY M / M / L (∞ ,∞) .................................................................35

3.5. M ODEL WIELOKANAŁOWY M / M / S (∞,∞) DLA S ≥ 2 ...................................................36

3.6. P RZYKŁADY ................................................................................................................36

3.7. Z ADANIA NA ĆWICZENIA RACHUNKOWE ......................................................................39

WYKAZ RYSUNKÓW......................................................................................................40

WYKAZ TABEL................................................................................................................40

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

METODY PROBABILISTYCZNE I STATYSTYKA – INFORMACJE UZUPEŁNIAJĄCE

Jednym z przedmiotów podstawowych wymienionych w standardach kształcenia dla kierunku

studiów informatyka na studiach I stopnia jest przedmiot „Metody probabilistyczne

i statystyka” 1 . Minimalna liczba godzin dla tego przedmiotu wynosi 30 dla studiów licencjac-

kich i 60 dla studiów inŜynierskich. Sprawdzony układ godzin dla stacjonarnych studiów in-

Ŝynierskich to 45 godzin wykładów i 30 godzin ćwiczeń rachunkowych. Z kolei dla studiów

niestacjonarnych to układ 30 + 30.

Treści i efekty kształcenia dla tego przedmiotu są następujące:

•

Treści kształcenia: Prawdopodobieństwo dyskretne. Prawdopodobieństwo ciągłe. Warto-

ści oczekiwane. Procesy stochastyczne. Próbkowanie. Estymacja. Testowanie hipotez sta-

tystycznych.

•

Efekty kształcenia – umiejętności i kompetencje: obliczania prawdopodobieństwa zdarzeń,

wartości oczekiwanej, wariancji i odchylenia standardowego; analizy algorytmów pod

względem średniego zachowania; obliczania niezawodności prostych układów sprzęto-

wych i systemów programowych; zastosowania koncepcji procesów stochastycznych do

analizy wydajności prostych układów sprzętowo-programowych; przeprowadzania pro-

stego wnioskowania statystycznego.

Z analizy przedstawionych wymagań wynika, Ŝe:

•

W przedmiocie zagadnienia teoretyczne ograniczone są niezbędnego minimum. Pominięto

przykładowe klasyczne tematy dot. np.: twierdzeń granicznych, analizy regresji, estymacji

przedziałowej czy weryfikacji hipotez nieparametrycznych.

•

Rozbudowane są treści dotyczące informatycznych zastosowań rachunku prawdopodo-

bieństwa, statystyki matematycznej i procesów stochastycznych.

W dostępnej literaturze brak jest podręcznika, który zawierałby tak określone treści.

Na dodatek informacje dotyczące zastosowań są publikowane w ograniczonej i niejednolitej

formie. Stan taki był powodem opracowania niniejszego uzupełnienia.

Niniejsze uzupełnienie obejmuje następujące, specjalistyczne zagadnienia:

•

Analizy algorytmów pod względem średniego zachowania;

•

Obliczania niezawodności prostych układów sprzętowych i systemów programowych;

•

Zastosowania koncepcji procesów stochastycznych do analizy wydajności prostych ukła-

dów sprzętowo-programowych.

1 http://www.bip.nauka.gov.pl/_gAllery/23/62/2362/45_informatyka.pdf

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

METODY PROBABILISTYCZNE I STATYSTYKA – INFORMACJE UZUPEŁNIAJĄCE

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

ZACHOWANIA 2

Najlepszym sposobem przyspieszania pracy komputerów jest obarczanie ich mniejszą

liczbą działań - R 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 „ Al-

gorytmy 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 pa-

mię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.

2 Maciej M. Sysło, Anna B. Kwiatkowska, ZłoŜoność obliczeniowa i efektywność algorytmów,

http://www.projekt.gammanet.pl/book/infalg/strony/1/i/30004.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=Algorytmy_i_struktury_danych/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-projektowanie-i-analiza-algorytmow

http://www.wsti.pl/materialy/slajdy2_SO.pdf

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

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:

•

METODY PROBABILISTYCZNE I STATYSTYKA – INFORMACJE UZUPEŁNIAJĄCE

Czas wykonywania obliczeń zaleŜy od danych wejściowych. Przykładowo przy sortowaniu:

•

im krótszy jest ciąg danych tym krótszy jest czas ich posortowania,

im bardziej wstępnie posortowany jest ciąg danych tym krótszy jest czas ich całkowitego

posortowania.

Jak wiadomo dwoma często stosowanymi sposobami podejścia są: rozpatrywanie przypad-

ków najgorszych (złoŜoność pesymistyczna) oraz zastosowanie określonego sposobu uśred-

nienia wszystkich moŜliwych przypadków (złoŜoność oczekiwana).

Ocena złoŜoności obliczeniowej algorytmu moŜe być dokonana teoretycznie lub symulacyj-

nie – jest ona niezaleŜna od środowiska sprzętowo-programowego. Z kolei ocena złoŜoności

czasowej jest zawsze prowadzona w określonym środowisku sprzętowo-programowym.

Na zakończenie rozwaŜań wstępnych naleŜy podkreślić, Ŝe 3 istnieje wiele programów, które

testują róŜne charakterystyki sprzętu komputerowego i oprogramowanie - moc pojedynczej

maszyny, interakcje w systemie klient-serwer (z pojedynczym lub wieloma klientami) czy

liczbę transakcji na sekundę w systemie przetwarzania transakcyjnego.

W miarę jak pojawiają się nowe wersje oprogramowania i sprzętu, zmieniają się składowe

testy benchmarków i ich wagi w obliczaniu wyniku benchmarku - dlatego jednym z warun-

ków uzyskania wiarygodnej oceny w testach porównawczych jest konieczność zastosowania

tej samej wersji benchmarku.

1.2. Szacowanie rodzaju / klasy złoŜoności obliczeniowej danego algorytmu 4

W niektórych prostych przypadkach moŜliwe jest oszacowanie złoŜoności obliczeniowej bez

wykonywania skomplikowanych obliczeń, czy symulacji.

Przykład 1

Wyszukiwanie wartości maksymalnej w ciągu nieposortowanym ZałóŜmy, Ŝe mamy n liczb.

Potrzebujemy przejrzeć kaŜdą z nich po to, by określić, która z nich jest największa. Potrze-

bujemy zatem n operacji ("spojrzeń) - liczba potrzebnych operacji jest proporcjonalna do roz-

miaru ciągu - więc złoŜoność liniowa - O(n).

Przykład 2

Wyszukiwanie danej liczby w ciągu posortowanym.

Pomyślmy jakąś liczbę od 1 do 1000. MoŜna ją zgadnąć zadając maksymalnie 10 pytań na

które odpowiada się tak lub nie. A oto pytania:

Czy ta liczba jest mniejsza od 500?

Jeśli tak, to czy jest mniejsza od 250?

Jesli nie, to czy jest mniejsza od 375?

Jeśli nie, to czy jest mniejsza od 438?

Jeśli nie, to czy jest mniejsza od 469?

Jeśli tak, to czy jest mniejsza od 443?

Jeśli tak, to czy jest mniejsza od 440?

Jeśli tak, to tą liczbą jest 439.

Idea jest taka, Ŝe dzięki temu, Ŝe ciąg jest posortowany, w kolejnych krokach pomniejszany

jest o połowę zakres, w którym znajduje się liczba dzięki temu potrzebne jest ok. log 2 1000

operacji - a więc występuje tu złoŜoność logarytmiczna - O(log 2 n).

3 http://pl.wikipedia.org/wiki/Testowanie_wzorcowe

4 http://forum.ks-ekspert.pl/topic/111411-algorytmy-zlozonosc-obliczeniowa/

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

•

METODY PROBABILISTYCZNE I STATYSTYKA – INFORMACJE UZUPEŁNIAJĄCE

Przykład 3

Sortowanie przez wybieranie.

Mamy nieposortowany ciąg o n elementach i posortowany o 0 elementach. Szukamy naj-

mniejszego elementu w ciągu nieposortowanym i wstawiamy go na koniec posortowanego

ciągu, tyle razy, aŜ posortowany ciąg będzie miał n elementów, a nieposortowany 0. Taki stan

uzyskamy wtedy, gdy wszystkie n elementów z nieposortowanego przerzucimy w posortowa-

ny. Musimy zatem n razy wyszukać najmniejszy element w ciągu - a wyszukiwanie najmniej-

szego elementu, jak wiemy z 1. przykładu, ma złoŜoność O(n) (liniową). Zatem wykonanie n

razy operacji o złoŜoności n wymaga n*n operacji, czyli ma złoŜoność kwadratową O(n*n) =

O(n 2 ).

Najczęściej algorytmy mają złoŜoność czasową proporcjonalną do funkcji:

•

log(n)- złoŜoność logarytmiczna

•

n - złoŜoność liniowa

•

nlog(n) - złoŜoność liniowo-logarytmiczna

•

n 2 - złoŜoność kwadratowa

•

n k - złoŜoność wielomianowa

•

2 n - złoŜoność wykładnicza

1.3. Przykładowe wyznaczanie złoŜoności obliczeniowej 5

Ocenimy złoŜoność obliczeniową sortowania przez wstawianie, które polega na pobieraniu

kolejnych elementów ciągu i poszukaniu dla niego odpowiedniego miejsca na liście elemen-

tów uporządkowanych. Gdy miejsce zostanie znalezione, to elementy listy się rozsuwa i w tak

ustalone miejsce „wkłada” ostatnio pobrany element.

Algorytm sortowania przez wstawianie moŜna porównać do sposobu układania kart pobiera-

nych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aŜ do wyczer-

pania talii. KaŜdą pobraną kartę porównujemy z kartami, które juŜ trzymamy w ręce i szuka-

my dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejące-

go). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w

ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. In-

sertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym koń-

cu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbo-

wych?

n! - złoŜoność wykładnicza, poniewaŜ n!>2 n juŜ od n=4

Przykład

Ciąg liczb do sortowania: 12,14,11,16,13

Realizacja:

1) 12 14 11 16 | 13 - element ostatni jest początkiem listy uporządkowanej

2) wybiera się element leŜący tuŜ przed elementem ostatnim (liczba 16 – na miejscu czwar-

tym) i porównuje się z elementem listy (13), element 16 > 13 zatem liczbę 13 przesuwa się na

miejsce czwarte, a na zwolnione miejsce piąte wstawia się liczbę 16. Po tym kroku mamy

więc 12 14 11 | 13 16

3) wybiera się następny element (11), i porównuje z elementami listy. PoniewaŜ 11 < 13 to

liczba 11 pozostaje na swoim, trzecim miejscu. Zatem otrzymujemy 12 14 | 11 13 16.

5 http://www.gamedev.pl/files/articles/megatutorial/M_B.pdf

http://xion.org.pl/files/texts/mgt/html/M_B.html

http://pl.wikipedia.org/wiki/Sortowanie_przez_wstawianie

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

•

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: