Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy i struktury 

danych

WYKŁAD 9 

dr inż. Krzysztof Pancerz

 

Krzysztof Pancerz

Algorytmy i struktury danych

Miara informacji

●

A – zbiór wiadomości wysyłanych przez źródło

●

a – wiadomość ze zbioru A

●

Miara zawartości informacji w wiadomości a:

–

p(a) – prawdopodobieństwo wysłania wiadomości a 

I

=log

2

1

p

a

 

Krzysztof Pancerz

Algorytmy i struktury danych

Entropia

●

A – zbiór wiadomości wysyłanych przez źródło

●

●

Entropia (średnia zawartość informacyjna 

wiadomości):

–

p(a

i

) – prawdopodobieństwo wysłania wiadomości a

i

 

Entropia jest maksymalna dla wiadomości jednakowo 

prawdopodobnych, wówczas                  .



H

=

∑

i

=1

n

p

a

i

log

2

1

p

a

i



A

={a

1,

a

2,

... ,a

n

}



H

=log

2

n

 

Krzysztof Pancerz

Algorytmy i struktury danych

Kodowanie Huffmana

●

W wyniku kodowania Huffmana otrzymujemy zestaw 

kombinacji kodowych o średniej długości zbliżonej do 

średniej zawartości informacyjnej wiadomości 

(entropii).

●

Twierdzenie o kodowaniu źródłowym:

–

Konstrukcja kodu o średniej długości kombinacji 
kodowej mniejszej od entropii źródła nie jest możliwa, 

jeżeli żądamy, aby odbierane dane były dekodowane w 
ujściu danych w sposób jednoznaczny.  

 

Krzysztof Pancerz

Algorytmy i struktury danych

Etapy numerycznego rozwiązywania równania 

nieliniowego

Etap 1

Początkowe  przybliżenie  poszukiwanego  pierwiastka  równania 
nieliniowego  (np.  przedział,  w  którym  znajduje  się  dokładnie  jeden 
pierwiastek).

Etap 2

Bardziej dokładne wyznaczenie poszukiwanego pierwiastka. Stopień 
dokładności określony jest przez zadany, dopuszczalny błąd. 

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda bisekcji 

(połowienia przedziału, równego podziału)

Dane jest równanie f(x)=0.

Zakładamy, że:

●

 funkcja f jest ciągła w przedziale domkniętym [a,b],

●

 wewnątrz przedziału [a,b] znajduje się dokładnie jeden pierwiastek,

●

 zachodzi nierówność f(a)f(b)<0.

Kolejne (w i-tym kroku) przybliżenie pierwiastka obliczamy ze wzoru: 

x

i

=

a

i

b

i

2

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda bisekcji 

x1 – pierwsze przybliżenie pierwiastka
x2 – drugie przybliżenie pierwiastka
x3 – trzecie przybliżenie pierwiastka
...

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda bisekcji 

(połowienia przedziału, równego podziału)

wczytaj(a,b,e)
x←a
dopóki ( |f(x)|>e ) wykonuj
{

x←(a+b)/2
jeśli( znak(f(a)) ≠ znak(f(x)) ) wykonaj 
{ b←x }
w przeciwnym razie
{ a←x }

}
wypisz (x)

a,b – końce przedziału, w którym poszukujemy pierwiastka
e – dopuszczalny błąd znalezienia pierwiastka
f – dana funkcja nieliniowa

 

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda siecznych 

(regula falsi)

Dane jest równanie f(x)=0.

Zakładamy, że:

●

 funkcja f jest ciągła w przedziale domkniętym [a,b],

●

 wewnątrz przedziału [a,b] znajduje się dokładnie jeden pierwiastek,

●

 zachodzi nierówność f(a)f(b)<0. 

Kolejne (w i-tym kroku) przybliżenie pierwiastka obliczamy ze wzoru: 

x

i

=a

i

−

b

i

−a

i

 f a

i



f

b

i

− f a

i



 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda siecznych 

x1 – pierwsze przybliżenie pierwiastka
x2 – drugie przybliżenie pierwiastka
...

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda siecznych

wczytaj(a,b,e)
x←a
dopóki ( |f(x)|>e ) wykonuj
{

x←a-( (b-a)f(a)/(f(b)-f(a)) )
jeśli( znak(f(a)) ≠ znak(f(x)) ) wykonaj
{ b←x }
w przeciwnym razie
{ a←x }

}
wypisz (x)

a,b – końce przedziału, w którym poszukujemy pierwiastka
e – dopuszczalny błąd znalezienia pierwiastka
f – dana funkcja nieliniowa

 

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda stycznych (Newtona)

Dane jest równanie f(x)=0.

Zakładamy, że:

●

 funkcja f jest ciągła w przedziale domkniętym [a,b],

●

 wewnątrz przedziału [a,b] znajduje się dokładnie jeden pierwiastek,

●

 zachodzi nierówność f(a)f(b)<0. 

Kolejne (w i-tym kroku) przybliżenie pierwiastka obliczamy ze wzoru: 

x

i

=a

i

−

f

a

i



f '

a

i



 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda stycznych

x1 – pierwsze przybliżenie pierwiastka
x2 – drugie przybliżenie pierwiastka
...

 

Krzysztof Pancerz

Algorytmy i struktury danych

Metoda stycznych (Newtona)

wczytaj(a,e)
x←a
dopóki ( |f(x)|>e ) wykonuj
{

x←a-(f(a)/f'(a))
a←x

}
wypisz (x)

a – punkt startowy, od którego zaczynamy poszukiwanie pierwiastka
e – dopuszczalny błąd znalezienia pierwiastka
f – dana funkcja nieliniowa

 

 

Krzysztof Pancerz

Algorytmy i struktury danych

Porównanie metod

Metoda bisekcji
ZALETA: - przy spełnionych założeniach wstępnych metoda zawsze 
prowadzi do rozwiązania
WADA: -metoda nieefektywna (zbieżność metody jest bardzo wolna, 
szybkość zbieżności zupełnie nie zależy od funkcji f)

Metoda siecznych
ZALETA: - przy spełnionych założeniach wstępnych metoda zawsze 
prowadzi do rozwiązania
WADA: - powolna zbieżność metody

Metoda stycznych
ZALETA: - metoda najszybciej zbieżna
WADY: - metoda wymaga obliczania wartości pochodnej
- zbieżność metody zależy od wyboru punktu startowego (dla pewnych 
punktów metoda może nie być zbieżna)