Kompresja i dekompresja

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

Kompresja bezstratna- dane otworzone są identyczne:
- teksty
- programy komputerowe
- bazy danych
- niektóre rodzaje grafiki
- pliki z innymi danymi (np. arkusz kalkulacyjny).

Kompresja stratna- dane odtworzone są podobne:
- dźwięki
- muzyka
- obrazy
- filmy.

Systemy liczbowe

System liczbowy to zbiór reguł służących do zapisywania, odczytywania i nazywania liczb.
W artykule tym przedstawię, najprościej jak się da, nie pomijając kluczowych teorii matematycznych sposoby zamiany liczb dziesiętnych na binarne, ósemkowe, szesnastkowe i BCD.

Dwójkowy system liczbowy to system pozycyjny o podstawie "2". Zapis liczb odbywa się przy użyciu cyfr "0" i "1".
Np. zapis (1001)2= 1*23+ 0*22+ 0*21+ 1*20=(9)10
Taki jest zasadniczy sposób przedstawienia kodu dwójkowego, łatwiej zrozumieć działanie tego kodu przy zaprezentowaniu innego sposobu na przeliczanie kodu.
Wyobraźmy sobie, że chcemy zapisać liczbę dziesiętną "sześć" (6)10 w kodzie binarnym. Aby to zrobić można podzielić tę liczbę przez 2 aż wynik osiągnie zero. Czyli:
6 |2 to 3 reszty 0 bo (3*2)= 6
3 |2 to 1 reszty 1 bo (1*2)+ 1(reszty)=3
1 |2 to 0 reszty 1 MSB bo (0*2)+ 1=1

Najpopularniejszy z nich jest system dziesiętny zwany też decymalnym lub arabskim. Jako cyfr używa się w nim liczb :
0 , 1 , 2 , 3 , 4 , 5 , 5 , 6 , 7 , 8 i 9.
W systemie tym liczby przedstawiane są w postaci potęg liczby 10. System ten został wymyślony przez Hindusów jednak do Europy trafił za pośrednictwem Arabów. Na starym kontynencie został oficjalnie wprowadzony w XVI wieku, zastępując mniej wydajny system rzymski.

Innym popularnym sposobem zapisywania liczb, również używanym w komputerach jest system szesnastkowy, znany pod inną nazwą jako hexogonalny. System ten stasuje się w zapisywaniu nazw kolorów umieszczanych na stronach sieci Web. W systemie tym cyfry stanowią nie tylko liczby od 0 do 9 ale też pierwsze litery alfabetu łacińskiego, czyli w tym wypadku litery: A , B , C , D , E , F. Aby odróżnić liczbę zapisana w systemie hexagonalnym zaczynającą się na litery alfabetu, poprzedza się ja znakiem 0 nie mającym znaczenia pozycyjnego w liczbie, zaś na końcu takiej liczby stawiamy znak h oznaczający system liczbowy.

Efektywność algorytmów

Złożoność obliczeniowa algorytmu jest pojęciem teoretycznym.W praktyce bardziej interesuje nas efektywność algorytmu, która bierze pod uwagę praktyczne zastosowanie algorytmu w programie.

Złożoność obliczeniowa algorytmów

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.

• Przez czasową złożoność obliczeniową rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych.Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów
• Złożoność pamięciowa określa z kolei liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.

• Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych. 
• Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych. 
• Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych

Skończoność algorytmów

Algorytm jest skończony, jeżeli gwarantuje wyznaczenie wyniku w skończonej liczbie kroków.

Algorytm, który nie jest skończony, nie może zostać uznany za poprawny, bowiem nigdy nie spowoduje wyznaczenia poprawnego wyniku.

Algorytm powinien być skończony dla wszystkich danych wejściowych , to znaczy, że żadna ich kombinacja, dopuszczona przez specyfikacje problemu nie powinna powodować sytuacji , w której algorytm się nie kończy.

Poprawność algorytmów

Algorytm jest poprawny, jeżeli rozwiązuje problem zgodnie ze specyfikacją problemu (zadania).

• Algorytm jest całkowicie poprawny , jeśli dla wszystkich danych wejściowych spełniających warunki początkowe wyprowadzi wyniki spełniające warunki końcowe i obliczenia zostaną zakończone
• Algorytm jest częściowo poprawny , jeśli dla obliczeń, które się skończą , ich wyniki są poprawne względem względem warunków początkowych i końcowych.W tym przypadku nie jest konieczne wykazanie , że obliczenia kończą się dla wszystkich poprawnych danych.