Kompresja

Kompresja z łacińskiego"compressio" znaczy "ściśnięcie", znaczy zmniejszenie objętości. W informatyce odnosi się do zmniejszania objętości i wielkości danych, umożliwiający do odtworzenia pierwotnych danych.

Dekompresją nazywamy proces odtworzenia pierwotnych danych. Na rysunku poniżej przedstawiono schemat wykonywania kompresji i dekompresji:





Zastosowania kompresji:



Bez kompresji nie istniałyby standardy typu JPEG, DVD, Blu-Ray lub MP3 itp.
Pozwala ona na efektywne używanie łączy telekomunikacyjnych, jest m.in stosowana w modemach



Rodzaje kompresji:

stratna (lossy compression) - w tej kompresji dane odtworzone są podobne do danych pierwotnych i na ogół różnią się od nich w sposó trudny do zauważenia.
dźwięki
muzyka - format MP3
obrazy- format JPG
filmy - format MPEG
Bazuje ona na niedoskonałości ludzkich zmysłów. Nie dostrzegają one niewielkich zmian barw, różnic w dżwięku lub w fakturze obrazu. Do widocznej utraty jakości może doprowadzić wieloktrotne powtarzanie cyklu kompresji i dekompresji.



bezstratna (lossless compression) - w tej kompresji dane odtworzone są identyczne z danymi pierwotnymi
teksty
programy komputerowe
bazy danych
pliki z innymi danymi jak arkusze kalkulacyjne itp.
niektóre rodzaje grafik - format GIF i TIFF itd.

Złożoność algorytmów

Złożoność obliczeniowa czasowa i pamięciowa algorytmów


-Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też złożoności pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od danych wejściowych z zakresu danego zagadnienia.


Przykładowo można by rozpatrzyć rozkład liczb na czynniki pierwsze. Przewidzieć można, że (niezależnie od zastosowanego algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Tę cechę podziela większość zagadnień obliczeniowych – im większe rozmiary danych wejściowych, tym więcej zasobów (czasu, procesorów, pamięci) jest koniecznych do wykonania danych obliczeń. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.


Kolejnym problemem jest fakt, iż złożoność zwykle nie zależy wyłącznie od rozmiaru danych, ale może się znacznie różnić dla danych wejściowych o identycznym rozmiarze. Dwoma często stosowanymi sposobami podejścia są:
rozpatrywanie przypadków najgorszych – złożoność pesymistyczna
zastosowanie określonego sposobu uśrednienia wszystkich możliwych przypadków – złożoność oczekiwana


 Czasowa złożoność obliczeniowa

Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od sposobu realizacji algorytmu, użytego kompilatora oraz maszyny, na której algorytm wykonujemy. Dlatego w charakterze czasu wykonania rozpatruje się zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.


Kolejny problem polega na tym, w jakim języku programowania formułować będziemy algorytmy oraz co można założyć mówiąc o maszynie, na której algorytm ten będzie wykonywany. Istniejące komputery różnią się między sobą istotnymi (z punktu widzenia konstruowania algorytmów) parametrami, jak na przykład liczbą i rozmiarem rejestrów, udostępnianymi operacjami matematycznymi, a ponadto podlegają ciągłym ulepszeniom. Wobec tego algorytmy analizuje się, wykorzystując abstrakcyjne modele obliczeń. Do popularnych modeli należą maszyna RAM, maszyna Turinga i maszyna wskaźnikowa (ang. pointer machine).


Pamięciowa złożoność obliczeniowa

Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć maszyny abstrakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej wyrażonej w bitach lub bajtach.



Złożoność obliczeniowa

Jest to jeden z najważniejszych parametrów charakteryzujących algorytm. Decyduje on o efektywności całego programu. Podstawowymi zasobami systemowymi uwzględnianymi w analizie algorytmów są czas działania oraz obszar zajmowanej pamięci. Na złożoność czasową składają się dwie wartości: pesymistyczna, czyli taka, która charakteryzuje najgorszy przypadek działania oraz oczekiwana. Najczęściej algorytmy mają złożoność czasową proporcjonalną do funkcji:
log(n)- złożoność logarytmiczna
n - złożoność liniowa
nlog(n) - złożoność liniowo-logarytmiczna
n2 - złożoność kwadratowa
nk - złożoność wielomianowa
2n - złożoność wykładnicza
n! - złożoność wykładnicza, ponieważ n!>2n już od n=4