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ć wielokrotne 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.

1. 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
• n² - złożoność kwadratowa
• n^k - złożoność wielomianowa
• 2ⁿ - złożoność wykładnicza
• n! - złożoność wykładnicza, ponieważ n!>2ⁿ już od n=4
• 
• 2.Czasowa

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

3. Pamięciowa
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.

Algorytm z pętlą Zagnieżdoną

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 *.
Lista kroków:
1. Zacznij algorytm.
2. Zmiennej i przypisz wartość jeden: i:=1.
3. Jeśli i jest większe od n, przejdź do kroku 4;
w przeciwnym wypadku
3.1. Zmiennej j przypisz wartość jeden: j:=1;
3.2. Jeśli j jest większe od m,
przejdź do nowego wiersza;
zwiększ licznik i o jeden (i:=i + 1);
wróć do kroku 3;
w przeciwnym wypadku
wyprowadź ('*');
zwiększ licznik j o jeden (j:=j + 1);
wróć do kroku 3.2;
4. Zakończ algorytm.

PROGRAM


#include <iostream>


using namespace std;


int main ()


{


int n, m, i, j;


cout << "Podaj n: ";


cin >> n;


cout << "Podaj m: ";


cin >> m;


for (i=0; i<m; i++)


{


for (j=0; j<m; j++)


cout << "*";


cout << endl;


}


return 0;


}

Funkcje zwracają wartość w C++

Funkcja zwracająca wartość- wylicza wartość i odsyła tę wartość do funkcji wywołującej.Musi zawierać instrukcję return, która ma być zwrócona do funkcji wywołującej.
Zwracana wartość może być:
- zmienną
- stałą
- wyrażeniem.

Parametr- wartość przekazywana funkcji, a wartość zwracana to wartość przekazywana z funkcji.

Rodzaje zmiennych ze względu na zasięg:
- globalne
- lokalne.

W C++ zmienne globalne deklarujemy poza funkcjami, lokalne- można wewnątrz funkcji.

Co to znaczy że zmienne globalne mogą zostać przesłonięte?
Jeżeli zadeklarujemy w procedurze lub funkcji zmienną lokalną o takiej samej nazwie jak zmienna globalna, to zmienna globalna zostanie przesłonięta, co oznacza, że używana będzie zmienna lokalna a nie globalna.

Parametry możemy przekazywać na dwa sposoby:
- przez wartość
- przez referencję.

Parametry formalne przekazywane przez wartość w treści danej procedury lub funkcji są traktowane jak zmienne lokalne. Ewentualne operacje wykonywane na tych parametrach wewnątrz procedury lub funkcji nie powodują zmian wartości odpowiadających im parametrów aktualnych.

W procedurze lub funkcji, w której parametry przekazywane są przez zmienną (przez referencję), operacje wykonywane w treści procedury na parametrach formalnych w momencie wywołania danej procedury powoduję wykonanie tych operacji na odpowiednich parametrach aktualnych.

Stosowanie procedur i funkcji w językach programowania

1. Modele programowania
-liniowe
-strukturalne
-modularne
-obiektowe
-zdarzeniowe

2. Programowanie zastępujące i wstępujące

Programowanie zstępujące (projektowanie zstępujące, ang. top-down design) – rozwiązanie programistyczne polegające na zdefiniowaniu problemu ogólnego poprzez podzielenie na podproblemy, które są dzielone na jeszcze mniejsze podproblemy aż do rozwiązań oczywistych, łatwych do zapisania. Następnie złożenie z rozwiązań podproblemów niższego rzędu rozwiązań problemów wyższego rzędu aż do całkowitego rozwiązania problemu
Programowanie wstępujące Jest to długoletnią zasadą stylu programowania, że elementy funkcjonalne programu nie powinny być zbyt duże. Jeśli jakiś fragment programu urośnie ponad etap, w którym jest łatwo zrozumiały, staje się masą złożoności, która ukrywa błędy tak łatwo, jak duże miasto ukrywa zbiegów. Takie oprogramowanie będzie ciężkie do czytania, ciężkie do testowania i ciężkie do debugowania.

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

Podprogramy standardowe cechują się następującymi zaletami:efektywność zwykle takie podprogramy, przygotowane przez profesjonalne firmy, są starannie opracowane, często w całości lub w istotnej części, w asemblerze bądź języku maszynowym i odpowiednio zoptymalizowane,brak błędów wszechstronne testowanie skutkuje brakiem lub ograniczeniem błędów takich podprogramów,standaryzacja pozwala na ujednolicenie oprogramowania, interfejsów użytkownika i ułatwia konserwację kodu,ułatwienie i skrócenie kodowania uwalnia programistę od definiowania standardowych operacji,programowanie hybrydowe często takie podprogramy są dostępne w kilku językach programowania i systemach.

Algorytm iteracyjny iloczyn n liczb

SPECYFIKACJA
Zadanie: Oblicz iloczyn n liczb całkowitych.
Dane: n dowolnych liczb całkowitych, kolejno zapamiętywanych w zmiennej a.
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ą liczbę a iloczyny=iloczyn*a
5.Jeśli i nie równa się n, zwiększ licznik o 1 (i=i+1) i wróć do kroku 3

#include <iostream>
using namespace std;
float liczba1, liczba2, liczba3;
int main()
{
cout << "Podaj wartosc boku a" << endl;
cin >> liczba1;
cout << "Podaj wartosc boku b" << endl;
cin >> liczba2;
cout << "Pole prostokata wynosi: " << endl;
liczba3 = liczba1*liczba2;
cout << liczba3;
return 0;

}

Poprawność algorytmów

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