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:

1. Bez kompresji nie istniałyby standardy typu JPEG, DVD, Blu-Ray lub MP3 itp.
2. 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ść i efektywność algorytmów

Złożoność obliczeniową algorytmów można podzielić w kontekście

• czasu wykonania programu czyli złożoność czasowa
• Co to?

Zależy od liczby operacji niezbędnych do ukończenia algorytmu,
jest pewnego rodzaju funkcją wielkości zbioru danych
Możemy wyrazić ją między innymi w jednostkach czasu, jednak nie jest
to wygodne ze względu na różne procesory, w które mogą być wyposażone
komputery, czas wykonywania podobnych operacji może się różnić

• wykorzystania pamięci czyli złożoność pamięciowa
• Co to?
Jest to wielkość pamięci (operacyjnej/masowej) niezbędnej do wykonania algorytmu
(wielkość pamięci zajmowanej przez wszystkie zmienne),
algorytmami, które znacznie zwiększają złożoność pamięciową
są algorytmy rekurencyjne.

! Efektywność algorytmu bierze pod uwagę praktyczne zastosowanie algorytmu w programie !

Poprawność algorytmów i ich skończoność

Algorytm:

• całkowicie poprawny - wszystkie dane wejściowe spełniające warunki początkowe zostaną wyprowadzone wyniki spełniające warunki końcowe i obliczenia zostaną zakończone
• częściowo poprawny - wyniki są poprawne względem warunków początkowych i końcowych
• dobrze określony i uniwersalny - występują w nim polecenia, operacje zrozumiałe oraz kolejność jest jednoznacznie określona

Algorytm który nie jest skończony nie może zostać uznany za poprawny.

Powodem nieskończonego działania algorytmu może być np. błędnie określony warunek itd.

Metody sortowania

• Sortowanie Bąbelkowe jest to prosta metoda sortowania, pozwala poukładać elementy danej tablicy w kolejności rosnącej lub malejącej. Elementami tablicy mogą być cyfry albo litery. Algorytm sortowania bąbelkowego porównuje dwa sąsiadujące elementy tablicy. Jeżeli element n jest większy od elementu n+1, wtedy zostają one zamienione miejscami. Algorytm powtarza się w koło do czasu, kiedy nie zajdą żadne zmiany, czyli do czasu kiedy tablica nie zostanie posortowana. Sortowanie bąbelkowe jest to podstawowy algorytm i warto go znać.

• Sortowanie kubełkowe jest algorytmem przeznaczonym dla pewnej specyficznej grupy danych. Jest podobnym algorytmem do sortowania przez zliczanie. Algorytm jest wydajny w sytuacji, gdy dane rozmieszczone równomiernie. Nazwa wzięła się stąd, że dane wrzucamy do kubełków, które są już z definicji posortowane.

• Sortowanie przez wstawianie jest to rodzaj sortowania możemy porównać do układania kart pokerzysty. Pierwszą kartę wstawiamy w odpowiednie miejsce przesuwając pozostałe, następną także wstawiamy między odpowiednie karty i tak układamy zestaw kart. Sortowanie przez wstawianie można zaliczyć do atrakcyjniejszych algorytmów. ma swoje zalety: jest stabilny, bardzo dobrze zachowuje się w przypadku zbioru posortowanego lub częściowo posortowanego, prosty, dobrze radzi sobie z niedużymi zbiorami.