CAM00129

Arytmetyka komputerowa, algorytmy obllratntefll

1. Wyjaśnij różnicę pomiędzy liczba maazynową znormalizowaną, a    ^w **P^,#ł*

matematycznym I mprazantacjl bitowej formatu doublt według atandardu IEEE754.

IEEE754 - liczby zmiennoprzecinkowe liczba maszynowa x»t*m*b*e a - znak liczby

m - znormalizowana mantyaa b - podstawa systemu liczbowego e - wykładnik c * waga cechy f - waga mantyay

i r

tf 3 fyT

B

9oW»r

tm

4- y

7

r i §> A

i

Gdy mantysa należy do prawostronnie otwartego przedziału [1, b) jest znormalizowana. M jest stale, a E się zmienia i wtedy przesunięciu ulega przecinek. Liczba zdenormalizowana pojawia się, gdy mamy niedomiar.

‘27 Jaki jest cel stosowania liczb maszynowych zdenormalizowanych. Co oznacza pojęcie „precyzja arytmetyki**.

Cel: zmniejszenie niedomiaru w otoczeniu zera. Precyzja arytmetyki - błąd pomiaru czasu.

3.    Wyjaśnij pojęcia niestabilności numerycznej algorytmu i złego uwarunkowania zadania numerycznego.

Algorytm jest niestabilny numerycznie , jeżeli małe błędy obliczeniowe popełnione w jednym etapie obliczeń, powodują wystąpienie dużych błędów w następnych etapach obliczeń.

Zadanie numeryczne jest źle uwarunkowane, jeśli małym zmianom warunków początkowych towarzyszą duże zmiany wyników Miarą uwarunkowania są odpowiednio definiowane wskaźniki.

4.    Algorytmy „bąbelkowy” i „quicksort” wymagają teoretycznie tej samej maksymalnej liczby porównań w celu uporządkowania ciągu. Dlaczego zatem algorytm „quicksort” uchodzi za najbardziej efektywny algorytm sortowania?

Najszybszy, prosty do wytłumaczenia i implementacji Opiera się na technice "dziel i zwyciężaj". Pesymistyczny czas jego działania wynosi 0(n2), a średni 0(n*lg(n)).

5. Na przykładzie wielomianu pti) ⁼ &    /raz punktuj ⁼ "1 wyjaśnij działanie algorytmu

Homera.    \y

Schemat Homera jest optymalnym algorytmem obliczania wartości wielomianu. Wielomian p(x) zapisuje się następująco:    .

11| 1 pSfl    §MEH|

p—,[u. .i, u ■ y iImią

ilnnyeunuhtr wielomianu

"L ohljC/Ollil USIlloic iNidlMIiiillltl

1 łW*

p=&T?2f

x=-T px=a3=2 dla i=1

px=2*(“1)+1*“1

dla i=2

px=-1*(“1)⁺1^iC2

dla i=3

px=2*(-1)+2=0

i

[ifc ■

mr N

oAr*

ii|g|

*tT

<w> c

IB

H

H

Bi