CAM00127

Arytmetyka Komputerowa, algorytmy obliczeniowo

1. Wyjaśnij różnicę pomiędzy liczba maszynową znormalizowaną, a /-denormalizowaną w zapiało matematycznym I reprezentacji bitowej formatu double według standardu IEEE7S4.

IEEE754 ~ liczby zmiennoprzecinkowe liczba maszynowa x«a*m*b^Ae t - znak liczby

m - znormalizowana manty ta b - podstawa systemu liczbowego a - wykładnik c - waga cechy f - waga mantysy

Cff

Ci 1 //

4/    C<cłtOL

ir— __

-i a

r ^ o, /./

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

T. JaW 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 „ąuicksort” wymagają teoretycznie tej samej maksymalnej liczby porównań w celu uporządkowania ciągu. Dlaczego zatem algorytm „ąuicksort" uchodzi za najbardziej efektywny algorytm sortowania?

Najszybszy, prosty do wytłumaczenia i implementaqi. 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 ⁼2ł>    6nz punktu ~ ' wyjaśnij działanie algorytmu

Homera.    \y

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

Pt=K .

^6 »Lmy wiclomfąu i u spoić/} uniki) jtfjtony .iisnnienr widomi,nm

'IrJlC/oiM Willióśc •UeloiiiiailM

P*I?1 1 2f x=-t px=a3=2 dla i=1

px=2*(-1)+1=-l d/a i-2

px=-1*(-i)+js2

d la 1=3

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

(K f

OiA,*—

. Cilg

If-H

U

cA-

u

y filii

K

mmm filii