Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
1. Omów pojęcie: złożoność obliczeniowa algorytmów.
złożoność obliczeniowa - nakład czasu lub zasobów maszyny realizującej algorytm, niezbędny dla jego prawidłowego wykonania
Analiza algorytmów - złożoność obliczeniowa jest podstawową własnością określaną dla algorytmów. Zadaniem analizy algorytmu jest określenie tej złożoności, a co za tym idzie realizowalności algorytmu.
Czynniki wpływające na złożoność algorytmów:
a) Rozmiar zadania - rozmiar danych niezbędnych dla realizacji algorytmu. Bierze się pod uwagę:
rozmiar danych wejściowych
rozmiar danych roboczych
rozmiar danych wyjściowych
b) Czas działania algorytmu - liczba kroków przekładająca się na czas faktycznej pracy maszyny realizującej algorytm. Istotne znaczenie mają w tym przypadku:
złożoność rozwiązywanego zadania
sposób konstrukcji algorytmu
wydajność maszyny realizującej obliczenia
Złożoność zasobowa (pamięciowa) - wyrażana w skali zajętości zasobów (PAO, pamięci zewnętrznych itp.) niezbędnych dla realizacji algorytmu
Złożoność czasowa - wyrażana w skali czasy wykonania algorytmu (liczba kroków, aproksymowany czas rzeczywisty
2. Jaka jest istota zasady dekompozycji i abstrakcji w programowaniu?
Bardzo często w naszym codziennym działaniu rozwiązując różne problemy posługujemy się następującymi metodami:
Dekompozycji - dzielimy większy problem na mniejsze - łatwiejsze do ogarnięcia umysłem podproblemy. Wydzielone fragmenty możemy dzielić w miarę potrzeb na jeszcze mniejsze kawałki.
Abstrakcji - każdy z podproblemów rozwiązujemy oddzielnie abstrahując w tym czasie od pozostałych podproblemów.
Po złożeniu wszystkich rozwiązanych podproblemów uzyskujemy rozwiązanie całości.
3. Przedstaw przykład ilustrujący wykorzystanie zjawiska iteracji i zjawiska rekurencji.
a)iteracyjne wykonanie funkcji Fibbonaciego
long int petlaFib(int a)
{
register int i=2, ostatni=0, zm1;
long int zm2 =1;
if (a<2) return a;
else
{
for ( ; i<=a; ++i) {
zm1 = zm2;
zm2 += ostatni;
ostatni = zm1;
}
return zm2;
}
b) rekurencyjne wykonanie funkcji Fibbonaciego
long int Fib (int a)
{
if (a<2)
return a;
else
return Fib(a-2) + Fib (a-1);
}
4. Wymień i omów podstawowe proste predefiniowane typy danych w języku C.
Całkowite:
char (opcjonalnie unsigned char) - ma rozmiar pojedynczej jednostki pamięci potrzebnej do przechowania znaku w systemie czyli zazwyczaj 1 Bajt. W C nie ma rozróżnienia między typem znakowym a całkowitym, zatem zmienną char można inicjować zarówno znakiem (w pojedyncych cudzysłowach!!!), lub liczbą całkowitą
short (opcjoalnie unsigned short) - zazwyczaj ma rozmiar pomiędzy char a int, czyli najczęściej 2 Bajty
int (opcjonalnie unsigned int) - ma rozmiar naturalnego rejestru w procesorze (w przypadku x86 są to 32 bity, Ultra sparc 64 bity). Zmienna lub stała tego typu może być dodatnia, ujemna lub równa zero. Zakres wartości zależy od komputera
long (opcjonalnie unsigned long) - W teorii zmienna większa niż int, w praktyce często identyczna z int.
Zmiennoprzecinkowe:
float - Zmienna rzeczywista pojedynczej precyzji (odpowiednik real z pacala)
double - Zmienna rzeczywista podwójnej precyzji (odpowiednik extended z pascala)
5. Omów metodę deklarowania i sposób realizacji zmiennych wskaźnikowych.
Wskaźnik jest specjalnym typem danych. Zmienna typu wskaźnikowego przechowuje adres (wskazanie do) innego obiektu (zmiennej) w pamięci operacyjnej. Wskazania poprzez typy wskaźnikowe można traktować tak jak nazwane adresy w pamięci operacyjnej. Dzięki wskaźnikom można w stosunkowo prosty sposób operować na adresach w pamięci operacyjnej.
Dwa podstawowe operatory dla typów wskaźnikowych to:
operator zwracający wartość przechowywaną pod konkretnym wskazaniem – oznaczany gwiazdką - *
operator zwracający adres zmiennej wskazywanej – oznaczany „ampersandem” - &
Deklaracja zmiennej wskaźnikowej w języku C:
typ *zmienna_wskaźnikowa
(znak gwiazdki oznacza wskaźnik - jest on bardzo ważny!!!)
(zmienna_wskaźnikowa = = wskazanie na zmienną)
Deklaracja wskaźnika na zmienną całkowitoliczbową
int *p;
(p = = wskazanie na zmienną)
Deklaracja wskaźnika na zmienną całkowitoliczbową
int p, q; (*p- wskaźnik na zmienną całkowitoliczbową; q - zmienna całkowitoliczbowa)
Ustawienie wskazania z p na q:
p = & q; (znak & (ampersand) oznacza ustawienie wskazania adresowego dla wskaźnika)
Ustawienie wskazania na zmienną całkowitoliczbową:
int *p, q;
p = &q;
Podstawienie wartości liczby:
q = 150; (ustawienie wartości przez zmienną wskazywaną)
lub
*p = 150; (ustawienie wartości przez zmienną wskaźnikową – odwołanie niejawne do zmiennej q)
Inkrementacja wartości wskaźnika „p” oznacza przejście do adresu:
„p + liczba bajtów dla wskazywanego przez p”
dekrementacja wartości wskaźnika „p” oznacza przejście do adresu:
„p - liczba bajtów dla wskazywanego przez p”
Dla wskaźnika do typu char będzie to przechodzenie co 1 bajt,
Dla wskaźnika do typu int będzie to przechodzenie co 2 bajty,
Dla wskaźnika do typu float - przechodzenie co 4 bajty
Dla wypisania wartości wskaźników w funkcji printf stosuje się operator konwersji: %p.
Język C w sposób wyjątkowy utożsamia wskaźniki i tablice. Tak faktycznie, to w wyniku deklaracji zmiennej tablicowej, środowisko języka C tworzy wskaźnik na początek tej tablicy. Miejsca na pozostałe elementy tablicy są zajmowane w zależności od rozmiaru tablicy. Tablica zajmuje spójny obszar pamięci operacyjnej. Tak więc do tablic możemy odnosić się w sposób tradycyjny, tzn. przy pomocy nazwy zmiennej z indeksem tablicy: tab[i] lub stosując arytmetykę wskaźników. Takie traktowanie tablic jest szczególnie przydatne dla tzw. tablic otwartych i łańcuchów znaków - bez wstępnego określenia ich długości. Środowisko języka C jest w stanie na bieżąco reagować na aktualne potrzeby programisty w tym zakresie. Takich cech nie ma większość innych języków programowania.
Kiedy do wskaźnika p podstawiamy wskazanie na tablicę tab nie używamy znaku & (ampersand). Wynika to z tego, że zmienna tablicowa jest niejawnie realizowana przez środowisko języka C jako wskaźnik do początku tablicy. Wtedy stosujemy podstawienie:
p=tab;
Stosowanie arytmetyki wskaźników przy tablicach jest możliwe, ale niezbyt wygodne. Lepiej jest wykorzystywać zwykłe indeksowanie tablic - efekt jest ten sam w obu przypadkach. Należy zwrócić uwagę na różnicę pomiędzy poniższymi wyrażeniami:
*p++; /*zwiększa wskazanie p do następnego elementu*/
*(p+1) /*daje wskazanie do następnego bez zwiększania p*/
6. Przedstaw definicję liniowej struktury danych.
Liniową strukturą danych nazywamy strukturę danych S=(D, R, e), w której relacja porządkująca N opisuje powiązania pomiędzy elementami odpowiednio dla poszczególnych rodzajów list.
gdzie:
D – oznacza zbiór danych elementarnych di, i = 1,..,|D| (i – jest indeksem poszczególnych danych),
R={rwe, N} – jest zbiorem dwóch relacji określonych na strukturze danych:
• relacja wejścia do struktury danych S,
• relacja następstwa (porządkująca) strukturę S,
e – jest elementem wejściowym do struktury danych S (nie jest to dana wchodząca w skład struktury danych S).
Wyróżniamy cztery rodzaje list (jednopoziomowych):
• jednokierunkowe listy niecykliczne
• dwukierunkowe listy niecykliczne
• jednokierunkowe listy cykliczne (pierścienie jednokierunkowe)
• dwukierunkowe listy cykliczne (pierścienie dwukierunkowe)
7. Omów podstawowe metody realizacji liniowych struktur danych.
Realizacje sekwencyjne - wtedy, gdy z góry znamy maksymalny rozmiar przetwarzanej struktury liniowej i z góry chcemy zarezerwować dla niej określony zasób (pamięć operacyjne, pamięć zewnętrzna). W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych statycznych,
Realizacje łącznikowe - wtedy, gdy rozmiar struktury nie jest z góry znany i w czasie jej przetwarzania może istnieć konieczność dodawania do niej nowych elementów lub ich usuwania. W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych dynamicznych (wskaźnikowych),
Realizacje łącznikowo-sekwencyjne - połączenie obu powyższych metod - wtedy gdy konieczny jest odpowiedni balans pomiędzy zmiennymi statycznymi i dynamicznymi
8. Omów logikę kolejki FIFO.
Kolejka (ang. FIFO - First In, First Out; pierwszy na wejściu, pierwszy na wyjściu) - liniowa struktura danych, znaczeniowo odpowiadająca nazwie: nowe dane dopisywane są na końcu kolejki, a jako pierwsze obsługiwane są dane z początku.
Specjalną modyfikacją jest kolejka priorytetowa - każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet, który modyfikuje kolejność późniejszego wykonania. Oznacza to, że pierwsze na wyjściu niekoniecznie są te dane, które w kolejce oczekują najdłużej, ale te o największym priorytecie.
Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w systemach operacyjnych ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym procesom.
Przeciwieństwem kolejki jest stos, bufor (ang. LIFO - Last In, First Out; ostatni na wejściu, pierwszy na wyjściu), w którym jako pierwsze obsługiwane są dane wprowadzone jako ostatnie.
9. Omów logikę stosu.
Stos (ang. LIFO - Last In, First Out; ostatni na wejściu, pierwszy na wyjściu), jest liniową strukturą danych, na której można wykonać dwie operacje: odłożenia elementu na stos i zdjęcia elementu ze stosu, i w której jako pierwsze obsługiwane są dane wprowadzone jako ostatnie. Odłożenie elementu na stos powoduje, że znajduje się on na tzw. wierzchołku stosu i może być jako pierwszy zdjęty ze stosu. Odłożenie kolejnego elementu na stos uniemożliwia dostęp do poprzednio odłożonych elementów – mogą być zdejmowane tylko w porządku odwrotnym do odkładania.
10. Omów ideę tablic rzadkich.
Tablice rzadkie są jednym z przypadków liniowych struktur danych. Ich cechą charakterystyczną jest to, że przechowują one jedynie wartości niezerowe.
Pozycja tablicy z wartością zerową nie występuje.
W tablicy są więc przechowywane wyłącznie wartości znaczące(różne od wartości domyślnej).
Tablice rzadkie realizujemy wyłącznie w postaci łącznikowej
11. Przedstaw przykłady realizacji tablic rzadkich.
Tablice rzadkie są jednym z przypadków liniowych struktur danych. Ich cechą charakterystyczną jest to, że przechowują one jedynie tzw. wartości niezerowe,
Po prostu pozycja tablicy z wartością zerową nie występuje (brak pozycji w macierzy oznacza wartość zerową),
W tablicy są więc przechowywane wyłącznie wartości znaczące (tzn. różne od ustalonej z góry wartości domyślnej)
Tablice rzadkie realizujemy wyłącznie w postaci łącznikowej (dynamiczne struktury danych)
Macierze rzadkie mogą być wykorzystywane do implementacji macierzy incydencji grafów
Częstym zastosowaniem jest przechowywanie obrazów rastrowych (szczególnie wtedy, gdy na obrazie jest mało „zapalonych” punktów)
Program pobierający wartości i tworzący z nich tablice rzadką; zero jako wartość nie znacząca
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct list{
int nrkol;
struct list *nextkol;
struct elem *start;
};
struct elem{
int nrwier;
int wart;
struct elem *nextelem;
};
int main (void)
{
struct list *lista;
struct elem *element;
struct list *prvlista;
struct list *aktlista;
struct elem *aktelem;
int tmp,dalej=1,ok=1;
int kolumna,dana,wiersz;
lista=NULL;
element=NULL;
clrscr ();
do
{ //pobieranie danych
printf("dana: ");
scanf("%d",&dana);
printf("kolumna: ");
scanf("%d",&kolumna);
printf("wiersz: ");
scanf("%d",&wiersz);
if(dana!=0)
{
aktlista=lista;
//jezeli pusta lista
if(aktlista==NULL)
{
lista=malloc(sizeof(struct list));
lista->nrkol=kolumna;
element=malloc(sizeof(struct elem));
element->wart=dana;
element->nextelem=NULL;
element->nrwier=wiersz;
lista->nextkol=NULL;
lista->start=element;
}
else //lista niepusta
{
if(kolumna<aktlista->nrkol) //wstawiamy kol przed pierwsza
{
lista=malloc(sizeof(struct list));
lista->nrkol=kolumna;
element=malloc(sizeof(struct elem));
element->wart=dana;
element->nextelem=NULL;
element->nrwier=wiersz;
lista->nextkol=aktlista;
lista->start=element;
}
if(kolumna==aktlista->nrkol) //wstaiwamy do pierwszej kolumny
{
aktelem=aktlista->start;
while(aktelem->nrwier!=wiersz && aktelem->nextelem!=NULL)
{
aktelem=aktelem->nextelem;
}
if(aktelem->nrwier==wiersz) //jezeli juz istnieje
{ //to zmieniamy
aktelem->wart=dana;
}
else //jezeli nie istnieje to tworzymy nowy
{ //na koncu listy
aktelem->nextelem=malloc(sizeof(struct elem));
aktelem->nextelem->nextelem=NULL;
aktelem->nextelem->wart=dana;
aktelem->nextelem->nrwier=wiersz;
}
}
if(kolumna>aktlista->nrkol) //wstawiamy kolumne po pierwszej
{
{
while(kolumna>aktlista->nrkol && aktlista->nextkol!=NULL)
{
prvlista=aktlista;
aktlista=aktlista->nextkol;
}
if(aktlista->nextkol==NULL) //wstawiamy na koniec listy{
if(kolumna==aktlista->nrkol) //do istniejacej kolumny
{
aktelem=aktlista->start;
while(aktelem->nrwier!=wiersz && aktelem->nextelem!=NULL)
{
aktelem=aktelem->nextelem;
}
if(aktelem->nrwier==wiersz)
{
aktelem->wart=dana;
}
else
{
aktelem->nextelem=malloc(sizeof(struct elem));
aktelem->nextelem->nextelem=NULL;
aktelem->nextelem->wart=dana;
aktelem->nextelem->nrwier=wiersz;
}
}
else
{
if(aktlista->nrkol<kolumna)
// wstawiamy na koniec listy do nowej kolumny
{
aktlista->nextkol=malloc(sizeof(struct list));
aktlista->nextkol->nextkol=NULL;
aktlista->nextkol->nrkol=kolumna;
element=malloc(sizeof(struct elem));
element->nextelem=NULL;
element->wart=dana;
element->nrwier=wiersz;
aktlista->nextkol->start=element;
}
else
{
prvlista->nextkol=malloc(sizeof(struct list));
prvlista->nextkol->nextkol=aktlista;
prvlista->nextkol->nrkol=kolumna;
element=malloc(sizeof(struct elem));
element->nrwier=wiersz;
element->wart=dana;
element->nextelem=NULL;
prvlista->nextkol->start=element;
}
}
}
else//wstawiamy kolumne pomiedzy 2 istniejace
{
prvlista->nextkol=malloc(sizeof(struct list));
prvlista->nextkol->nextkol=aktlista;
prvlista->nextkol->nrkol=kolumna;
element=malloc(sizeof(struct elem));
element->nextelem=NULL;
element->nrwier=wiersz;
element->wart=dana;
prvlista->nextkol->start=element;
}
}
}
}
}
printf("czy dalej? 0-nie");
scanf("%d",&dalej);
}while(dalej);
//wypisywanie listy
aktlista=lista;
do
{
if(aktlista->nextkol==NULL) ok=0;
aktelem=aktlista->start;
while(aktelem->nextelem!=NULL)
{
printf("dana: %d kolumna: %d wiersz: %d\n",aktelem->wart,\
aktlista->nrkol,aktelem->nrwier);
aktelem=aktelem->nextelem;
}
printf("dana: %d kolumna: %d wiersz: %d\n",aktelem->wart,\
aktlista->nrkol,aktelem->nrwier);
aktlista=aktlista->nextkol;
}while(ok);
getche ();
return 0;
}
12. Omów definicję tablicy rozproszonej.
Definicja tablicy rozproszonej (z haszowaniem)
Tablicą rozproszoną nazywamy trójkę uporządkowaną T=( K,D,h ) , gdzie
K={k1, k2, k3,….,kn} — zbiór kluczy,...