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

Typy danych c++

Pojęcie zmiennej

Programy jakie do tej pory napisaliśmy, wyświetlały jedynie tekst na ekranie. Aplikacje, które wypisują tylko i wyłącznie komunikaty są zazwyczaj mało interesujące. Biblioteka <iostream> pozwala nam nie tylko wypisywać tekst, ale również wczytywać dane do zmiennych. Zanim jednak zapoznamy się z instrukcją wczytywania, należy zapoznać się z pojęciem zmiennej. Zmienna, jak sama nazwa wskazuje będzie się zmieniać w trakcie programu. Zmienna to pewien stosunkowo mały obszar w pamięci, w którym możemy przechowywać dane różnego typu np. liczby całkowite, liczby rzeczywiste (zmiennoprzecinkowe), znak, tekst oraz kilka innych wartości, które będą nas w przyszłości interesowały. Nie można jednak wszystkiego zapisywać do jednej zmiennej. Każda zmienna ma swoje przeznaczenie, wielkość i właściwości. Na zmiennych liczbowych możemy wykonywać operacje matematyczne, w innych z kolei możemy przechowywać tekst. 

Typy danych

Zasięg zmiennej

Rodzaje zmiennych

Mimo że w języku C i C++ występuje wiele rodzajów zmiennych, to ze względu na tematykę tej lekcji zajmiemy się tylko jednym podziałem zmiennych. Wszystkie zmienne można podzielić na zmienne globalne i zmienne lokalne.

W dużym uproszczeniu różnica między tymi dwoma rodzajami zmiennych jest następująca: zmienne globalne są to takie zmienne, które są dostępne w całym programie i przez cały czas jego działania, natomiast zmienne lokalne są dostępne tylko w pewnej części programu, zazwyczaj tylko w pewnej chwili działania programu, a nie przez cały czas.

Zmienne globalne

Zaletą zmiennych globalnych jest to, że są one widoczne w całym programie. Nie miało to dużego znaczenia w przypadku naszych dotychczasowych programach, jednak nabierze bardzo dużego znaczenia, kiedy przedstawię Ci pojęcie funkcji w C++.

Zmienne globalne deklaruje się (i ewentualnie inicjalizuje) pomiędzy blokiem dołączonych plików nagłówkowych a funkcją main. Ponieważ są to zwykłe zmienne (mają tylko dodatkowe właściwości), to deklaracja, inicjalizacja oraz posługiwanie się tymi zmiennymi wygląda dokładnie tak samo, jak to robiliśmy w dotychczasowych programach.

Ponieważ zmienne globalne są widoczne w całym programie, zatem są również widoczne wewnątrz funkcji main. Oznacza to, że wewnątrz funkcji main (oraz wszystkich innych funkcji), możemy dokonywać wszystkich operacji jakie są tylko możliwe dla zmiennej danego typu.

                                                           

                                          Zmienna lokalna

zmienna zdefiniowana i dostępna wyłącznie w określonym bloku programu, tworzona w momencie wejścia do tego bloku oraz usuwana z pamięci w momencie wyjścia z danego bloku. Tym samym zasięg zmiennej lokalnej oraz czas jej życia pokrywają się i obejmują blok, w którym zmienna lokalna jest zdefiniowana. Zmienna lokalna ma więc określony, ograniczony zakres istnienia i dostępności. To w jakich blokach programowych można tworzyć zmienne lokalne definiuje składnia konkretnego języka programowania. Typowymi blokami, w których można w różnych językach programowania tworzyć zmienne lokalne, są moduły, podprogramy oraz w pewnych językach programowania także instrukcje blokowe (lub inne instrukcje strukturalne, np. pętla for w języku C[1][2][3] i inne). Zmienna lokalna w danym bloku przesłania zdefiniowaną zmienną globalną lub zmienną lokalną z bloku nadrzędnego o tym samym identyfikatorze. Tym samym programista nie może wprost, za pomocą danego identyfikatora, w bloku o zdefiniowanej zmiennej lokalnej, odwołać się do zmiennej zewnętrznej o tym samym identyfikatorze co zdefiniowana zmienna lokalna, choć może to zrobić za pomocą innych konstrukcji, jeżeli są dostępne w danym języku programowania, np. selekcja, wskaźniki, przemianowanie, nakładanie zmiennych lub inne.

Stosowanie procedur i funkcji

1. Modele programowania
-liniowe  Program liniowy (w skrócie PL) jest to problem minimalizacji/maksymalizacji liniowej funkcji celu o 
n$n$ argumentach x1,x2,…,xn$x_1,x_2,\dots ,x_n$ przy zachowaniu pewnej liczby równości lub nierówności liniowych (będziemy je nazywać ograniczeniami) zawierających zmienne xi$x_i$.

-strukturalne  paradygmat programowania opierający się na podziale kodu źródłowego programu na procedury i hierarchicznie ułożone bloki z wykorzystaniem struktur kontrolnych w postaci instrukcji wyboru i pętli. Rozwijał się w opozycji do programowania wykorzystującego proste instrukcje warunkowe i skoki. Programowanie strukturalne zwiększa czytelność i ułatwia analizę programów, co stanowi znaczącą poprawę w stosunku do trudnego w utrzymaniu „spaghetti code” często wynikającego z użycia instrukcji goto.

Początki programowania strukturalnego przypadają na Lata 60. XX wieku, a ważnym głosem w dyskusji o programowaniu strukturalnym był list Edsgera Dijkstry Goto Statement considered harmful.

Język programowania zgodny z paradygmatem programowania strukturalnego nazywa się językiem strukturalnym.

-modularne paradygmat programowania zalecający stosowanie nadrzędności modułów w stosunku do procedur i bloków tworzących program. Moduł grupuje funkcjonalnie związane ze sobą dane oraz procedury i jest reprezentacją obiektu jednokrotnie występującego w programie. Programowanie takie wykorzystywane jest przez wyspecjalizowane języki programowania, np. Ada, Modula-2, Pascal, Fortran90.

-obiektowe  paradygmat programowania, w którym programy definiuje się za pomocą obiektów – elementów łączących stan(czyli dane, nazywane najczęściej polami) i zachowanie (czyli procedury, tu: metody). Obiektowy program komputerowy wyrażony jest jako zbiór takich obiektów, komunikujących się pomiędzy sobą w celu wykonywania zadań.

Podejście to różni się od tradycyjnego programowania proceduralnego, gdzie dane i procedury nie są ze sobą bezpośrednio związane. Programowanie obiektowe ma ułatwić pisanie, konserwację i wielokrotne użycie programów lub ich fragmentów.

Największym atutem programowania, projektowania oraz analizy obiektowej jest zgodność takiego podejścia z rzeczywistością – mózg ludzki jest w naturalny sposób najlepiej przystosowany do takiego podejścia przy przetwarzaniu informacji.

-zdarzeniowe metodologia tworzenia programów komputerowych, która określa sposób ich pisania z punktu widzenia procesu przekazywania sterowania między poszczególnymi modułami tej samej aplikacji. Programowanie sterowane zdarzeniami jest mocno powiązane ze środowiskami wieloprocesowymi (nie mylić z komputerami wieloprocesorowymi), z graficznymi środowiskami systemów operacyjnych oraz z programowaniem obiektowym.

Jest to paradygmat programowania, według którego program jest cały czas „bombardowany” zdarzeniami (events), na które musi odpowiedzieć, i zakładający, że przepływ sterowania w programie jest całkowicie niemożliwy do przewidzenia z góry.Jest też używane przez wysoce wydajne serwery sieciowe – zdarzeniami są tu żądania połączenia, nadejście danych do odbioru, zwolnienie się miejsca w buforach wysyłania odbiorów, itd

2. Programowania zstępujące i wstępujące


3.Zalety stosowania podprogramów (procedur i funkcji)

Algorytm z pętlą zagnieżdżoną

1.Specyfikacja
Zadanie: Napisz listę kroków algorytmu, który umożliwi wyprowadzenie na ekran
monitora prostokąta o bokach n, m, narysowanego za pomocą znaków
(m- liczba znaków * w poziomie, n- liczba znaków *w pionie).
Wnętrze prostokąta powinno być wypełnione znakami *.

Dane: liczby naturalne dodatnie, określające ilość znaków *
w prostokącie o bokach m, n.

Wynik: prostokąt o wymiarach m x n, zbudowany ze znaków.

2.Schemat blokowy

3.Listing
#include <iostream>
using namespace std;
int main ()
{
    int i, j, n, m;
    cout << "Wprowadz wartosc n: ";
    cin >> n;
    cout << "Wprowadz wartosc m: ";
    cin >> m;
    for (i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
   cout << "*";
        cout << endl;
    }
    return 0;

}

Algorytym Iteracyjny iloczyn n liczb

1.Specyfikacja
Iteracja polega na wielokrotnym powtarzaniu tej samej operacji.
Iteracje implementujemy , stosując tzw. pętlę. Z pętlą mamy do czynienia,
gdy w pewnym kroku alogrytmu wracamy do jednego z wcześniejszych kroków,
co powoduje, że kroki te mogą zostać wykonane wiele razy.

Zadanie: Oblicz iloczyn n liczb całkowitych
Dane: n dowolnych liczb całkowitych kolejno zapamiętywanych w zmiennej a.
Wynik: wartość iloczynu: iloczyn.
Lista kroków:
1. Zacznij algorytm
2. Zmiennej iloczyn oraz zmiennej  i przypisz wartość jeden: iloczyn:=1; i:=1.
3. Wprowadż liczbę całkowitą i zapamiętaj ją w zmiennej a.
4. Pomnóż iloczyn przez wprowadzoną liczbe a: iloczyn := iloczyn x a.
5. Jeśli i nie równa się n, zwiększ licznik o jeden (i:=i+1) i wróc do kroku 3.
6. Wprowadź wynik: iloczyn.
7. Zakończ algorytm.
2.Schemat blokowy

3.Listing programu

#include <iostream>
using namespace std;
int main()
{
    int i, a, iloczyn, n;
    cout << "Podaj liczbe do przemnozenia ";
    cin >> n;
    iloczyn=1;
    for (i=0; i<n; i++)
    {
        cout  << "podaj " << i+1 << " liczbe ";
        cin >> a;
        iloczyn*=a;
    }
    cout << "iloczyn to: " << iloczyn;
    return 0;

}