Kompresja stratna i bezstratna

Kompresja danych (ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.
Działaniem przeciwnym do kompresji jest dekompresja.

Kompresja stratna to taka, w której takie odzyskanie jest niemożliwe, jednak główne właściwości zostają zachowane. Np. jeśli kompresowany jest obrazek, nie widać znaczących różnic w stosunku do oryginału. Pomimo to może się już nie nadawać do dalszej przeróbki czy do wydruku, gdyż w tych zastosowaniach wymaga się zachowania innych właściwości.

Kompresja stratna przydaje się np. w telewizji przemysłowej, w której przesłanie wiele razy większego strumienia nieskompresowanego było by niemożliwe. Innym popularnym przykładem kompresji stratnej jest format MP3 szeroko stosowany do zapisania muzyki w postaci cyfrowej. Kolejny powszechny przykład to format jpg z którego korzysta większość cyfrowych aparatów fotograficznych do zapisu wykonanych zdjęć.

Kompresja bezstratna (ang. lossless compression) – ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem, że metoda ta gwarantuje możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.

Najważniejszym twierdzeniem o kompresji bezstratnej jest twierdzenie o zliczaniu.

Zalety kompresji danych: 

+ przesyłanie większej ilości danych w jednostce czasu,
+ przesyłanie tej samej ilości danych w krótszym czasie,
+ zmniejszenie rozmiarów danych przechowywanych na nośnikach.

Wady kompresji danych:
– przed użyciem danych należy je rozpakować,
– w pewnych sytuacjach dekompresja w czasie rzeczywistym lub quasi-rzeczywistym może pochłaniać sporo zasobów systemu komputerowego.

Programy do kompresji danych: 

►potocznie nazywane są „pakerami”, „archiwizatorami” lub „kompresorami”.
►należą do programów narzędziowych, przeznaczonych do umieszczania plików w archiwach i odtwarzania zapisanych w nich informacji.
►posiadają swoje własne formaty i algorytmy kompresji, przeznaczone dla różnego typu danych.

►Pliki możemy skompresować, używając popularnych programów, np. Winzip, Winrar, czy darmowym 7-Zip.
►W efekcie otrzymujemy plik o mniejszym rozmiarze, którego jednak w takiej postaci nie jesteśmy w stanie użyć go bezpośrednio.
►Kompresja z użyciem tego typu programów nie powoduje utraty danych –stąd nazwa KOMPRESJA BEZSTRATNA.

Złożoność algorytmów

1. Złożoność 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.

2. Złożoność obliczeniowa algorytmów

Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności będąca drugą ważną gałęzią teorii obliczeń.

3. 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.

4. Czasowa złożoność algorytmów

Przez czasową złożoność obliczeniową (ang. time computational complexity lub time complexity) rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych. Złożoność czasowa jest zatem pewną funkcją 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.

Prezentacja "Systemy liczbowe"

Link do prezentacji:
https://docs.google.com/presentation/d/1PIuzsZ-tqmYpczRo9EBXqUd8p4gOO_-hUKZsOjMJVzA/edit?usp=sharing

Wysłane streszczenie przeliczania poszczególnych systemów liczbowych przez edziennik całej grupie (link poniżej).
http://home.agh.edu.pl/~byrska/src/4.SystemyLiczb.pdf

Najważniejsze własności algorytmów, ich skończoność i poprawność

1. Najważniejsze własności algorytmów

Algorytm – w matematyce oraz informatyce to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania.Podstawowe cechy

Cechy algorytmów:
- poprawność (algorytm daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa - szybkość działania i pamięciowa - "zasobożerność")

Sposoby prezentacji

Najbardziej przejrzystym sposobem prezentacji są schematy blokowe - narzędzia nakierowane na prezentację kolejnych czynności w projektowanym algorytmie.

2. Poprawność algorytmów

Co to znaczy, że algorytm działa poprawnie? Intuicja podpowiada nam, że chodzi tu o to, by dla dowolnych danych uzasadnić zgodność uzyskanych wyników z zamierzeniami. Aby jednak taką zgodność ustalić ponad wszelką wątpliwość, musimy jasno sformułować intencje, podać tzw. specyfikację algorytmu.

Specyfikacją algorytmu nazywać będziemy parę własności: <wp, wk>, gdzie wp jest warunkiem początkowym, a wk warunkiem końcowym. Intuicyjnie, warunek początkowy to ten, który mają spełniać dane początkowe, a warunek końcowy to ten, który ma być spełniony po wykonaniu algorytmu. Ogólnie, oba warunki powinny opisywać zależności między zmiennymi przed i po wykonaniu algorytmu.

3. 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.