1tom075

4. INFORMATYKA 152

Metoda stycznych polega na tworzeniu ciągu przybliżeń x₁,x₂,- pierwiastka x, gdzie x, (/ = 1,2,...) są punktami przecięcia stycznych krzywej y = f{x) z osią 0x, poprowadzonych z punktów będących poprzednim przybliżeniem przy założeniu, że jeden z krańców przedziału jest przybliżeniem poprzednim w stosunku do x, (pierwsze przybliżenie). Jeśli f"(x)f(a) > 0, to pierwszą styczną prowadzi się z punktu (a,f(af), natomiast gdy

y

x

Rys. 4.1. Konstrukcja ciągu przybliżeń x_tx₂x₃ pierwiastka x₀ metodą siecznych

Rys. 4.2. Konstrukcja ciągu przybliżeń x_lt x₂, x₃ pierwiastka x₀ metodą stycznych

y

o f"(x)f(b) > 0, to punktem poprzednim w stosunku do jest h. Na rysunku 4.2 przedstawiono przypadek, gdy f"(x) > 0. Ciąg przybliżeń pierwiastka x„ oblicza się według wzorów

Błąd przybliżenia x, określa się wzorem

(4.12)

^    aśxśb

natomiast n-te przybliżenie x„ można oszacować wg wzoru M ,

2 m

£„<— El-, (n = 2,3,...)

gdzie:

M = max \f'\x)\, m = min \f'(x)\

4.5.3. Bazy danych

Przez dane rozumie się informacje zapisane w sposób nadający się do przechowywania i przetwarzania w systemach komputerowych. Dane mogą być proste, jeżeli system nie uwzględnia ich podziału na części, albo złożone. Duże zbiory danych (na ogół złożonych), zorganizowane w sposób, który umożliwia dostęp do nich wielu programów, nazywa się bazami danych.

Dostęp do bazy danych może być bierny, jeżeli umożliwia tylko wgląd w jej zawartość, _a]bo czynny, jeżeli dopuszcza też rozszerzenie lub modyfikacje tej zawartości. System oprogramowania, umożliwiający lub ułatwiający bierny lub czynny dostęp do danej bazy, nazywa się systemem zarządzania tą bazą. Całość, złożona z bazy i systemu jej zarządzania, bvwa nazywana systemem bazy danych*.

Podstawową jednostką organizacji bazy danych jest zwykle rekord („zapis”), składający się z pól, w które są wpisywane elementarne informacje. Rekordy jednakowego typu są grupowane w pliki** o strukturze liniowej, drzewiastej lub sieciowej. Dostęp do rekordu w pliku jest możliwy przez przejście z rekordu sąsiedniego albo przez wskazanie adresu (numeru miejsca) rekordu w pliku. Powiązania między rekordami mogą być realizowane przez stosowne rozmieszczenie ich w pamięci albo przez wpisanie do odpowiednich pól w rekordzie adresów rekordów z nim związanych. Adres rekordu związanego, wpisany w pole rekordu danego, nazywa się wskaźnikiem albo odsyłaczem (ang. pointer), a zbiór rekordów, powiązanych przez wskaźniki, siecią wskaźnikową (odsyłaczową).

Lokalizacja rekordu w pliku bywa uzależniona od jego zawartości, a ściślej od zawartości wybranego pola, zwanego wtedy kluczem (dokładniej: kluczem rozmieszczenia). Odszukiwanie rekordu w pliku również może być związane z zadaną zawartością wybranego pola, zwanego wtedy kluczem odszukiwania. Odszukiwanie jest oczywiście najłatwiejsze, jeżeli klucz odszukiwania jest ten sam co klucz rozmieszczenia.

Jeżeli kolejność rekordów w pliku liniowym jest zgodna z kolejnością (np. alfabetyczną) wartości klucza rozmieszczenia, to plik nazywa się monotonicznym albo posortowanym. Proces porządkowania rekordów w pliku według wartości wybranego klucza nazywa się w związku z tym sortowaniem tego pliku. Nie trzeba dodawać, że odszukiwanie rekordu w pliku posortowanym jest z reguły dużo łatwiejsze niż w pliku o przypadkowej kolejności rekordów.

Innym sposobem rozmieszczania rekordów według wartości wybranego klucza jest ich rozpraszanie (zwane też mieszaniem od ang. to hash — rozpraszać, mieszać), polegające na algorytmicznym przetwarzaniu wartości klucza rozmieszczenia na adres rekordu w pliku w sposób zapewniający możliwie równomierną gęstość rozmieszczenia rekordów w obszarze pliku. Ten sam algorytm, który był stosowany do rozpraszającego rozmieszczania rekordów, stosuje się do ich odszukiwania według zadanej wartości wskazanego klucza. Rozmieszczanie rozpraszające okazuje się szczególnie efektywne w przypadku dużych plików o często modyfikowanej zawartości.

Organizację bazy danych, taką jaką ją „widzi” użytkownik, nazywa się jej organizacją logiczną; rzeczywista postać zapisów i występujących między nimi powiązań tworzy organizację fizyczną bazy. Stosowane obecnie koncepcje organizacji logicznej to organizacje: hierarchiczna, sieciowa i relacyjna.

Stosunkowo prosta organizacja hierarchiczna bazy polega na powiązaniu jej rekordów w drzewo, w którym każdy rekord (oprócz korzenia drzewa) ma dokładnie jeden rekord bezpośrednio nadrzędny i dowolną liczbę rekordów bezpośrednio podrzędnych. Wadą organizacji hierarchicznej jest brak potrzebnych często powiązań poziomych i skrośnych między poszczególnymi węzłami drzewa.

W organizacji sieciowej dopuszcza się, aby każdy rekord miał dowolną liczbę zarówno rekordów bezpośrednio podrzędnych Jak i bezpośrednio nadrzędnych. Organizacja taka ma znacznie większą moc reprezentowania powiązań między poszczególnymi informacjami niż organizacja hierarchiczna; jej wadą jest duży stopień komplikacji struktury samej bazy, a także stosunkowo duża złożoność jeżyków, umożliwiających posługiwanie się tego rodzaju bazami.

" Określenie .,bank danych", stosowane jako synonim terminów ..baza danych” lub „system bazy danych”, wyszło ⁷ użycia.

, .    *⁺ Termin „zbiór”, stosowany niekiedy zamiast terminu ..plik”, może prowadzić do niejasności w przypadkach,

^,edy równolegle używa się go w odniesieniu do zbiorów w sensie teorii mnogości.