e zeszyt: marca 2014

piątek, 21 marca 2014

Obliczanie numeryczne

Całkowanie numeryczne – metoda numeryczna polegająca na przybliżonym obliczaniu całek oznaczonych. Termin kwadratura numeryczna, często po prostu kwadratura, jest synonimem całkowania numerycznego, w szczególności w odniesieniu do całek jednowymiarowych. Dwu- i wyżejwymiarowe całkowania nazywane są czasami kubaturami, choć wyraz kwadratura również niesie to znaczenie dla całkowania w wyższych wymiarach.

Metoda prostokątów:

Prawdopodobnie najprostszym wzorem jest metoda punktu środkowego (midpoint rule):

$\int\limits_{x_*}^{x_*+h} f(x) dx \approx h f\left( x_* + \frac h 2 \right)$

Jeśli funkcja $f(x)$ zmienia się w niewielkim stopniu na przedziale $(x_*, x_*+h)$ , reguła taka da dobre przybliżenie całki.
Integration rectangle.png

Metoda trapezów:

Metoda trapezów polega na tym, że figurę ABCD zastępujemy figurą złożoną z trapezów wpisanych, tzn. krzywą aproksymujemy linią łamaną w nią wpisaną. Przedział całkowania $(a,b)$ dzielimy przy tym na $n$ równych części o długościach:

$h:=\frac{b-a}{n}$ .

Punktami podziału (końcami części) są wówczas:

$x_i = a+(i-1)h, \quad i=1\dots n+1.$

Wówczas pole figury złożonej z trapezów wynosi

$S_{n}=\frac{y_{1}+y_{2}}{2}h+\frac{y_{2}+y_{3}}{2}h+...+\frac{y_{n}+y_{n+1}}{2}h=h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right)$

gdzie

$y_{i}:=f(x_{i})$ – wartości funkcji w punktach podziału.

Stąd otrzymujemy wzór przybliżony w metodzie trapezów:

$\int\limits_{a}^{b}f(x)dx \approx h\left(\frac{y_{1}}{2}+y_{2}+y_{3}+...+y_{n}+\frac{y_{n+1}}{2}\right) = \frac{h}{2}\sum_{i=1}^{n}\left(f(x_{i})+f(x_{i+1})\right)$

Oszacowanie błędu tej metody wynosi

$R_{n}:=\left|\int\limits_{a}^{b}f(x)dx-S_{n}\right|\leq{\frac{(b-a)^{3}M^\prime{'}}{12n^{2}}}$

gdzie: $M^\prime{'}:=\max_{\langle a,b\rangle}|f^\prime{'}|$

Calkowanie numeryczne-metoda trapezow.png

poniedziałek, 17 marca 2014

Sortowanie przez scalanie oraz sortowanie szybkie

Sortowanie przez scalanie

Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .

W tej metodzie wyróżniamy dwa etapy:

PODZIAŁ

- Faza wykonywana jest rekurencyjnie , polega na podzieleniu ciągu na podciągi zawierające jedną wartość

SCALANIE

- realizowana jest podczas łączenia podciągów i polega na scalaniu ich, z jednoczesnym sortowaniem

Wynika stąd, że głównym celem jest tutaj scalenie dwóch uporządkowanych ciągów w jeden posortowany. Załóżmy, że w tablicy mamy dwa uporządkowane podciągi, które chcemy scalić. Kopiujemy pierwszy z lewej strony tablicy podciąg ( mający mniejsze indeksy!!! ) do dodatkowej tablicy. Następne porównujemy parami kolejne wyrazy podciągów i wstawiamy do tablicy te, które są mniejsze.

Sortowanie Szybkie

•Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1]

W każdym kolejnym kroku...

•Powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.

•

Realizacje każdego

kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : środek – T [(lewy+prawy/2]. Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego ŚRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe środek, a z prawej elementu T[j] większy/równy środek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu środek.

Najmniejszy i największy element ciągu

Algorytm rekurencyjnego znajdowania największego i najmniejszego elementu zbioru wykorzystuje metodę dziel i zwyciężaj. Zbiór danych dzielony jest na podzbiory, w których bardzo łatwo określić element największy i najmniejszy. Jeśli zbiór ma jeden element, to stanowi on zarówno maximum, jak i minimum. Jeśli zbiór ma dwa elementy, to większy element stanowi maximum zbioru, mniejszy element stanowi minimum zbioru, warunkiem brzegowym rekurencji jest uzyskanie podzbiorów jedno- lub dwuelementowych.

Sortowanie

Sortowanie – jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.

Elementy o równej wartości będą występowały, po posortowaniu, w takiej samej kolejności jaką miały w zbiorze nieposortowanym.

SPOSOBY SORTOWANIA:

sortowanie bąbelkowe (ang. bubblesort) – $O(n^2)$
sortowanie przez wstawianie (ang. insertion sort) – $O(n^2)$
sortowanie przez zliczanie (ang. counting sort lub count sort) – $O(n+k)$ , wymaga $O(n+k)$ dodatkowej pamięci
sortowanie kubełkowe (ang. bucket sort) – $O(n)$ , wymaga $O(k)$ dodatkowej pamięci

sortowanie przez wybieranie (ang. selection sort) $O(n^2)$ – może być stabilne po odpowiednich zmianach.