Laboratorium Podstaw Informatyki
Kierunek Elektrotechnika
Ćwiczenie 3.1
Statyczne struktury danych
Tablice, Wektory, Macierze
Zakład Metrologii AGH
Kraków 1997
Wprowadzenie
Ogólna deklaracja tablicy ma postać:
TYP Nazwa[ROZMIAR];
gdzie TYP jest dowolnym typem, np. typem prostym, wskaźnikowym, definiowanym. W szczególności TYP może być typem złożonym tablicowym, co umożliwia deklarowanie tablic wielowymiarowych (podrozdział 1.3, przykład (c)). Nazwa jest identyfikatorem tablicy, a ROZMIAR określa ilość elementów typu TYP w tablicy. Znaczenie poszczególnych składników pomogą zrozumieć poniższe deklaracje.
#define ILOSC_SAL 21
int iloscMiejsc[ILOSC_SAL]; /* tablica ILOSC_SAL elementów typu prostego int */
#define IL_BP 128
void *BlokiPamieci[IL_BP]; /* tablica IL_BP elementów typu wskaźnikowego*/
struct {
int typKomputera;
int rokZakupu;
float cena;
} Komputery[10]; /* tablica 10 elementów typu struktura */
typedef struct { int typKomputera; int rokZakupu; float cena;} OPIS_KOMPUTERA;
OPIS_KOMPUTERA Komputery[10]; /* jw. ale z użyciem typu definiowanego */
float Macierz[10][5]; /* tablica 10 elementów typu tablica 5 elementów typu float */
Pozycje poszczególnych elementów (indeksy) numeruje się od 0 dla pierwszego elementu do ROZMIAR-1.
Tablica, macierz, wektor
Nazw innych niż tablica używa się dla przypadków szczególnych. Dla tablicy zawierającej dane numeryczne (zmiennoprzecinkowe) używa się nazwy macierz. Dla macierzy jednowymiarowej używa się nazwy wektor.
Inicjowanie i przypisanie
Język C nie dopuszcza użycia operatora przypisania do zmiany wartości zmiennej tablicowej. Przez przypisanie zmieniać można jedynie elementy tablic. Następująca konstrukcja jest więc niepoprawna:
char Nazwisko[30];
Nazwisko=”Kowalski”; /* BŁĄD - przypisanie do zmiennej tablicowej */
strcpy(Nazwisko, ”Kowalski”); /* DOBRZE - użycie funkcji bibliotecznej */
Dopuszczalna jest inicjowanie zmiennych tablicowych zewnętrznych i statycznych ( ale nie automatycznych [Kernighan, Ritchie]) wartościami początkowymi, jak w następującym przykładzie:
char Nazwisko[30]=”Kowalski”; /* DOBRZE - zmienna zewnętrzna */
funkcja() {
char Imie[15]=”Jan”; /* BŁĄD - zmienna automatyczna */
...
}
W przypadku gdy przy inicjowaniu nie określa się rozmiaru tablicy, kompilator określa go na podstawie ilości elementów inicjujących. Np. dla inicjowania:
float OcenyZInformatyki[]={5.0, 5.0, 6.0, 4.5, 6.0};
tablica OcenyZInformatyki ma rozmiar 5 elementów typu float.
Przykłady
Poszczególne przykłady z tego paragrafu są rozwijane w odpowiedniej części ćwiczeniowej.
a) deklaracja 30-elementowej tablicy znakowej:
char Nazwisko[30];
b) deklaracja tablicy 24 struktur typu STUDENT z użyciem typu definiowanego:
typedef struct {
char Nazwisko[30];
char Imie[15];
short czyMaZaleglosci;
float SredniaOcen;
} STUDENT;
STUDENT Studenci_E53[24];
c) Deklaracja i użycie tablicy elementów typu tablica elementów zmiennoprzecinkowych:
#define ILOSC_MIAST 50
#define Krakow 0
#define Kielce 1
// enum MIASTO {Krakow, Kielce};
float OdleglosciMiedzyMiastami[ILOSC_MIAST][ILOSC_MIAST];
main() {
...
OdleglosciMiedzyMiastami[Krakow][Kielce]=114.0; /* drogowa */
OdleglosciMiedzyMiastami[Kielce][Krakow]=112.0; /* kolejowa */
...
}
Tak zadeklarowaną tablicę używa się jak dwuwymiarową macierz.
Zastosowania
Ze względu na ograniczone możliwości opisu zjawisk pojedynczymi wartościami, obszar zastosowania tablic jest tak szeroki, że trudno spotkać program, który by ich nie używał. Najpopularniejszym typem tablic są tablice znakowe, zawierające elementy typu char. Tym rodzajem tablic ćwiczący będzie się zajmował w zadaniu 1. Możliwości wykorzystania typów złożonych w tablicach pozna w zadaniu 2. Przydatne w zastosowaniach obliczeniowych macierze, czyli tablice wartości numerycznych, wykorzysta w zadaniu 3.
Typ tablicowy, z jego wadą związaną z ograniczonym rozmiarem pamięci komputera, tj. niezmiennym rozmiarem wyznaczanym w momencie kompilacji, skonfrontowany zostanie ze strukturami dynamicznymi w ćwiczeniu następnym.
Zadanie 1 - tablice znakowe
Zgodnie z uwagami z punktu 1.2 język C nie dopuszcza użycia operatora przypisania do zmiany wartości zmiennej tablicowej. Ponadto niemożliwe jest stosowanie innych operatorów do zmiany wartości tego typu zmiennych, choć poprawiłoby to przejrzystość kodu. Spójrzmy na trzy wersje funkcji konkatenacji (połączenia) trzech ciągów, dla deklaracji:
#include <string.h.>
char Nazwisko[30]=„Kowalski”; /* Zmienne zewnętrzne - inicjowanie poprawne */
char Imie[15]=„Jan”;
char NazwiskoImie[45];
funkcja1() {
/* Czytelnie i niepoprawnie. Operatora + nie można stosować do typu tablicowego */
NazwiskoImie=Nazwisko + ” ” + Imie;
}
funkcja2() {
/* Poprawnie, ale nieczytelnie i nieefektywnie */
dl= strlen(Nazwisko);
for(i=0;i<=dl;i++) NazwiskoImie[i]=Nazwisko[i];
NazwiskoImie[dl++]=` `;
NazwiskoImie[dl]=`\0';
dl1=strlen(Imie)+1;
for(i=dl;i<dl+dl1;i++) NazwiskoImie[i]=Imie[i-dl];
}
funkcja3() {
/* Poprawnie, czytelnie i efektywnie */
strcpy(NazwiskoImie, Nazwisko);
strcat(NazwiskoImie, ” ”);
strcat(NazwiskoImie, Imie);
}
Operacje na tablicach znakowych w języku C, jak kopiowanie, łączenie, wyszukiwanie, zamiana, polegają na wywołaniu odpowiedniej funkcji bibliotecznej zadeklarowanej w pliku nagłówkowym string.h jak w wersji 3 przykładu. Sposób ich działania jest podobny do tego z wersji 2, ale zoptymalizowany i przetestowany przez profesjonalistów.
Odwracanie tablicy znakowej
Najprostsze rozwiązanie zadania odwracania tablicy znaków to jej przepisanie do tablicy docelowej w odwrotnym porządku. Odwróconą tablicę należy zakończyć znakiem `\0', przyjętym w języku C do zaznaczania końca tablic znakowych.
#define MAX_CIAG 100
void Odwroc(char tablica[]) {
int i, N=strlen(tablica);
char kopia[MAX_CIAG];
for(i=0;i<N;i++) kopia[i]=tablica[N-1 - i];
kopia[N]=`\0';
printf(„ORYGINAL: <%s>\n”, tablica);
printf(„KOPIA: <%s>\n”, kopia);
}
Wadą tego rozwiązania jest brak możliwości przekazania odwróconej tablicy do funkcji wywołującej (kopia jest zmienną automatyczną tworzoną na stosie po wejściu do funkcji Odwroc() i niszczoną po wyjściu z niej). Pierwszą metodą obejścia tego ograniczenia jest umieszczenie tablicy docelowej na stercie przez alokację dynamiczną i jej usunięcie po wykorzystaniu. Druga metoda to przekazanie tablicy docelowej z funkcji wywołującej. Trzecia metoda to prowadzenie zmian bezpośrednio na tablicy źródłowej. Przy implementacji udoskonalonego algorytmu odwracania tablicy znakowej wykorzystamy trzecią metodę.
Zaimplementuj następujący algorytm odwracania tablicy znakowej:
Dla elementów tablicy S o długości N Operacja ↔ oznacza zamianę wartości. Funkcja odwracająca z deklaracją: void Odwroc(char tablica[]); powinna operować na tablicy źródłowej. Do zamiany wartości elementów tablicy zdefiniuj funkcję z deklaracją: void Zamien(char tablica[], int idx1, int idx2); Wypisz odwróconą tablicę znaków w funkcji main() po wywołaniu funkcji Odwroc(). |
Proste algorytmy sortowania
Zadanie sortowania [Wirth] stosuje się zwykle dla bardziej skomplikowanych danych niż tablica znakowa. Jest to jednak doskonały przykład dla celów dydaktycznych. Sortować można tylko takie dane, które można porównywać. Czy znaki mają wartość? Tak, podobnie do uporządkowania w alfabecie, każdy znak (litera, cyfra, znak semigraficzny) ma określone miejsce w zestawie znaków komputera. Dzięki temu możliwe jest przypisanie znaku do zmiennej całkowitej, a nawet indeksowanie tablicy znakami.
Zajmiemy się w tym punkcie tzw. prostymi algorytmami sortowania, wymagającymi rzędu N2 porównań, gdzie N jest rozmiarem tablicy. Mimo dużego kosztu czasowego wykonania, algorytmy te są łatwe, naturalne i co najważniejsze użyteczne dla małych N.
Metoda prostego wybierania [Wirth, str. 74] opisana jest algorytmem:
Dla elementów tablicy S o długości N
dla i∈<0, N-2>: S[i] ↔ { MIN(S[k]), k∈<i, N-1> }
Przykładowa implementacja tego algorytmu, z sortowaniem ciągu znaków - parametru wywołania programu, wygląda następująco:
#include <stdio.h> /* deklaracje wejscia/wyjscia */
#include <string.h> /* deklaracje operacji na tablicach znakowych */
#define MAX_N 20
void Sortuj(char[]);
void Zamien(char[], int, int);
int IndeksNajmniejszego(char[], int, int);
int main(int argc, char* argv[]) {
char Kopia[MAX_N+1];
if(argc<2) return 1;
strncpy(Kopia, argv[1], MAX_N);
Sortuj(Kopia);
printf(„Tablica oryginalna: \t[%s]\n”, argv[1]);
printf(„Tablica posortowana: \t[%s]\n”, Kopia);
return 0;
}
void Sortuj(char tablica[]) {
int N=strlen(tablica);
int i;
for(i=0;i<N-1;i++) Zamien(tablica, i, IndeksNajmniejszego(tablica, i, N-1));
}
void Zamien(char tablica[], int idx1, int idx2) {
char tmpChar;
if(idx1!= idx2) {
tmpChar=tablica[idx1];
tablica[idx1]=tablica[idx2];
tablica[idx2]=tmpChar;
}
}
int IndeksNajmniejszego(char tablica[], int idx1, int idx2) {
int i, idxMinChar;
idxMinChar=idx1;
for(i=idx1+1;i<=idx2;i++) {
if(tablica[i]<tablica[idxMinChar]) idxMinChar=i;
}
return idxMinChar;
}
Zadaniem do wykonania jest implementacja innego algorytmu sortowania.
Metoda sortowania bąbelkowego [Wirth, str. 77] opisana jest algorytmem:
Dla elementów tablicy S o długości N Zaimplementuj ten algorytm. Wykorzystaj funkcję zamiany z poprzedniego przykładu. |
Najszybszym znanym algorytmem sortowania jest Quick-Sort [Wirth], który będzie omawiany na zajęciach poświęconych rekurencji.
Zadanie 2 - złożony typ podstawowy
Typem składowym tablicy może być typ złożony, np. struktura. Zapis inicjowania elementów tablicy ma w takim przypadku postać złożoną. Dla przykładowej deklaracji zewnętrznej tablicy bez użycia typu definiowanego (patrz pkt. 1.3):
struct {
char Nazwisko[30];
char Imie[15];
short czyMaZaleglosci;
float SredniaOcen;
} Studenci[4]={
{„Kowalski”, „Jan”, 0, 5.0},
{„Nowak”, „Maciej”, 1},
{„Kowalczyk”, „Marek”, 0, 4.0}
};
inicjowane są 3 pierwsze elementy tablicy, z nieokreśloną wartością zmiennej SredniaOcen dla drugiego elementu. Dostęp do poszczególnych elementów struktur łączy indeksowanie z wyborem elementu struktury. Np. przypisanie wartości do zmiennej czyMaZaleglosci drugiego elementu tablicy ma postać:
#define TAK 1
...
Studenci[1].czyMaZaleglosci = TAK;
Pełne dane osobowe
dodaj opcję wypisywania na ekranie listy studentów przez wypełnienie funkcji WypiszListeStudentow(). Użyj formatu: lp, nazwisko, imie, średnia ocen, czy ma zaległości. Pole lp jest indeksem w tablicy studentów powiększonym o 1. dodaj do struktury STUDENT pole Oceny do zapamiętania 15 danych typu float. Dodaj funkcję obsługi tego pola (modyfikacja wybranej oceny z wykorzystaniem funkcji gets() i atof()), usuń składową SredniaOcen struktury STUDENT i dodaj funkcję wyliczania średniej z ocen w tablicy Oceny. Wartość 0.0 oznacza brak oceny i nie wpływa na wartość średniej. Brak ocen daje średnią 0.0. Zmodyfikuj funkcję WypiszListeStudentow() do nowego sposobu opisu średniej ocen. |
Filtracja danych
Zadanie filtracji danych polega na wydzieleniu ze zbioru informacji tylko tej, która spełnia zadane warunki. W naszej aplikacji warunki mogłyby obejmować wszystkie pola struktury STUDENT. Ograniczymy się do zadawania warunku na nazwisko.
Uzupełnij program studenci o opcję filtracji danych studentów na podstawie wzorca - nazwiska lub jego początkowej części. Po zadaniu wzorca filtracji funkcja WypiszListeStudentow() powinna wypisywać dane tylko dla studentów o nazwisku pasującym do wzorca. Zadanie wzorca pustego oznacza jego usuniecie. Sugerowane rozwiązanie to oddzielny moduł filtracji z deklaracjami przygotowanymi w pliku nagłówkowym filtry.h:
char WzorzecNazwiska[MAX_NAZWISKO]; |
Wzorzec zadany jako początkowa część nazwiska, mimo użyteczności w tym zastosowaniu, nie jest uniwersalny. Często stosowany, zwłaszcza w powłokach i programach narzędziowych systemu Unix, jest opis wzorca tzw. wyrażeniem regularnym.
Zadanie 3 - macierze, czyli tablice wartości zmiennoprzecinkowych
Jak pokazano w przykładzie 1.3.c deklarowanie tablicy dwuwymiarowej jest w istocie deklarowaniem tablicy tablic. Adresowanie poszczególnych elementów uzyskuje się przez podwójne indeksowanie, co upodabnia notację do tradycyjnego zapisu matematycznego.
Planowanie trasy
Program wyznaczania długości wybranej trasy biegnącej przez miasta wojewódzkie może operować na danych o odległościach miast w województwach przyległych. Takie rozwiązanie wykorzystamy w programie droga. W obecnej wersji program podaje odległość między dwoma miastami wojewódzkimi przyległych województw. Jeśli podano jedną nazwę miasta, lub jeśli województwa nie są przyległe, program podaje województwa przyległe pierwszego z nich. Odległości drogowe opisane są w tabeli odległości wypełnianej zawartością pliku tekstowego. Opisy są dublowane.
Zadaniem do wykonania, po zapoznaniu się ze źródłami programu, jest taka jego modyfikacja, aby przez sumowanie odległości wyznaczał długość dowolnej trasy drogowej. Wywołanie: droga Krakow Tarnow Rzeszow Przemysl powinno skutkować wypisaniem na ekranie informacji:
Odległosc drogowa: Z kolei wywołanie: droga Krakow Kielce Warszawa powinno skutkować wypisaniem na ekranie informacji:
Odległosc drogowa: |
Zastanówmy się nad stopniem wykorzystania pamięci w tak skonstruowanej aplikacji. Przyjmując średnią ilość województw przyległych do danego równą 5, uzyskujemy wykorzystanie 10 elementów tablicy w 49-elementowym wierszu, tj. około 20%. W profesjonalnym zastosowaniu należałoby pomyśleć bądź o umieszczeniu dodatkowej informacji w pozostałych polach (np. odległości drogowe i kolejowe czy najkrótsze odległości między wszystkimi miastami), bądź o zmianie struktury danych opisującej odległości. Drugą wadą jest niewygoda związana z koniecznością podawania miast na trasie. W większości zastosowań użytkownik oczekuje zaproponowania dobrej trasy między dwoma punktami. Jest to jednak problem z dziedziny optymalizacji dyskretnej, odległej od tematu ćwiczenia.
Operacje macierzowe - dodawanie, mnożenie, transpozycja
Powszechnie stosowane w obliczeniowych zastosowaniach komputerów są operacje macierzowe [Kaczorek]. W szczególności wszystkie metody numerycznego rozwiązywania układów równań różniczkowych zwyczajnych i cząstkowych, jak metody różnic skończonych, elementów skończonych, elementów brzegowych, sprowadzają się do operacji macierzowych. Dostępne są biblioteki funkcji realizujących najczęstsze operacje macierzowe, jak np. dobrze udokumentowana biblioteka Numerical Recipes [Press, Flannery, Teukolsky, Vetterling] rozprowadzana w postaci źródłowej.
Naszym zadaniem jest opracowanie biblioteki funkcji realizujących podstawowe operacje macierzowe: dodawanie, mnożenie i transpozycję. Przyjmiemy stały rozmiar macierzy N i przekazywany parametrem n rozmiar używany. Użyj następujących deklaracji zmiennych zewnętrznych i funkcji:
#define N 10 Przetestuj opracowane funkcje, przez kompilację z modułem głównym programu macierze i uruchomienie programu. |
Podobnie jak w poprzednim zadaniu, pojawia się problem z wykorzystaniem pamięci. Przy używanym wymiarze macierzy 2x2 wykorzystujemy 4/100=4% elementów macierzy. Taką cenę płaci się za statyczną alokację dużych struktur danych, wykorzystanych w pełni tylko w szczególnych przypadkach. Profesjonalne funkcje biblioteczne wykorzystują w takich zastosowaniach dynamiczny przydział pamięci.
Dla tych, którzy chcą wiedzieć więcej - informacje dodatkowe
Tablice a wskaźniki
W języku C [Kernighan, Ritchie] nazwa tablicy jest w czasie kompilacji zamieniana na wskaźnik do jej początku. Wynika z tego równoważność następujących operacji przypisania:
int tab[10];
int *p;
p=tab; /* jest równoważne: */
p=&tab[0];
Indeksowanie tablicy można zapisać w sposób równoważny za pomocą wskaźnika i przesunięcia, tj.:
int tab[10];
int *p=&tab;
tab[5]=2; /* jest równoważne: */
*(p+5)=2;
Nazwa tablicy nie jest zmienną wskaźnikową. Jest stałą wyznaczaną w momencie linkowania programu i z tego powodu nie można zmieniać jej wartości instrukcjami programu.
Tablice a pamięć komputera
Istotny w niektórych zastosowaniach jest sposób rozmieszczania przez kompilator elementów zmiennych tablicowych. W przypadku jednowymiarowym tablica jest umieszczana element za elementem, w obszarze wynikającym z zadeklarowanej klasy zmiennej tablicowej. Nazwa tablicy wskazuje pierwszy jej element. W przypadku tablic wielowymiarowych autorzy języka C przyjęli zasadę najszybszej zmienności ostatniego indeksu tablicy przy sekwencyjnym przesuwaniu się w pamięci. Przykładowo dla deklaracji:
char znaki[3][2]={{`a', `b'}, { `c', 'd'}, {`e', `f'}};
obraz pamięci zawierającej tablicę znaki ma postać:
|
|
znaki[0][0] |
a |
znaki[0][1] |
b |
znaki[1][0] |
c |
znaki[1][1] |
d |
znaki[2][0] |
e |
znaki[2][1] |
f |
|
|
Powyższą deklarację należy rozumieć jako trzyelementową tablicę, której elementami są tablice dwóch elementów typu char. Przyjęto więc naturalny sposób kolejnego umieszczania elementów tablic.
Dla tych, którzy chcą być najlepsi - zadania dodatkowe
Rachunek zespolony
Jedną z możliwości implementacji rachunku zespolonego jest przyjęcie za typ zespolony tablicy dwóch elementów typu zmiennoprzecinkowego.
#define REAL 0
#define IMAG 1
typedef double[2] COMPLEX;
void dodaj(COMPLEX x, COMPLEX y, COMPLEX z) {
z[REAL]=x[REAL]+y[REAL];
z[IMAG]=x[IMAG]+y[IMAG];
}
...
COMPLEX a, b, c;
a[REAL]=b[REAL]=1;
a[IMAG]=b[IMAG]=2;
dodaj(a,b,c);
Dla porównania implementacja typu zespolonego w postaci struktury [Press, Flannery, Teukolsky, Vetterling] daje notację odwołań do składowych oszczędniejszą o jeden znak. Przy wywołaniu funkcji jej parametry typu struct są kopiowane na stos w przeciwieństwie do typu tablicowego, dla którego kopiowany jest wskaźnik. Dlatego w optymalnej pod względem szybkości implementacji należy przekazać adres struktury COMPLEX, co wiąże się z komplikacją notacji, jak w poniższym przykładzie.
typedef struct {double real, imag;} COMPLEX;
COMPLEX a, b, c;
void dodaj(COMPLEX *x, *y, *z) {
z->real=x->real+y->real;
z->imag=x->imag+y->imag;
}
...
a.real=b.real=1;
a.imag=b.imag=2;
dodaj(&a, &b, &c);
Zwięzła notacja jest istotna nie tylko ze względu na objętość kodu źródłowego, ale również dla osiągnięcia przejrzystości i czytelności kodu. Dużą wadą poprzednich implementacji jest zapis operacji w postaci wywołań funkcji. Dużo wygodniejszy i czytelniejszy byłby tradycyjny zapis matematyczny. Takie możliwości daje język C++, obiektowe rozszerzenie języka C [Stroustrup]. Umożliwia on definiowanie operatorów dla definiowanego typu, co upraszcza np. zapis operacji dodawania zmiennych zespolonych do postaci:
c=a+b;
Nie jest to jedyne udogodnienie tego języka. Zalecamy jego studiowanie po zakończeniu kursu języka C.
Opracuj bibliotekę funkcji realizujących operacje dodawania, odejmowania, mnożenia, dzielenia i wyznaczania liczby sprzężonej dla liczb zespolonych. Wybierz definicję typu zespolonego i sposób zwracania wyniku do funkcji wywołującej. Utwórz plik nagłówkowy z deklaracjami koniecznymi do użycia biblioteki. Przetestuj działanie funkcji dla wybranych danych testowych. |
Metoda najmniejszej sumy kwadratów
Często spotykanym problemem w technice jest określenie współczynnika zależności liniowej dwóch wielkości, opisanej równaniem:
Y=aX+e
gdzie e jest losowym zakłóceniem o wartości średniej równej 0.
Przykładem może być wyznaczanie rezystancji rezystora przez pomiar prądu przez niego płynącego i napięcia między jego zaciskami. Zgodnie z prawem Ohma, wielkości X z powyższego wzoru odpowiada prąd, wielkości Y napięcie, parametr a odpowiada rezystancji R, a e jest przypadkowym błędem pomiaru napięcia (zakładamy dokładny pomiar prądu).
Istnieje wiele metod wyznaczenia przybliżenia ap współczynnika a na podstawie wektorów odpowiadających sobie N par X-Y. Metoda najmniejszej sumy kwadratów opracowana przez Gaussa daje rozwiązanie spełniające warunek najmniejszej sumy S kwadratów odległości:
S=∑(Y-ap*X)2
W wyniku procedury wyznaczenia minimum wartości S w funkcji ap (poprzez analityczne różniczkowanie i rozwiązanie równania liniowego), otrzymujemy wzór metody LMS (ang. Least Mean Square - Najmniejszej Sumy Kwadratów) [Mańczak, Nahorski]:
ap=(XT*X)-1*XT*Y
Opracuj funkcję realizującą wyznaczanie metodą LMS rezystancji rezystora na podstawie danych wejściowych - wyników pomiaru napięcia z jego zacisków i prądu przez niego płynącego. Wartości prądu są dokładne, a pomiar napięcia obarczony jest błędem przypadkowym o wartości średniej równej 0. Wybierz sposób wprowadzania danych do programu (np. z pliku z wartościami w kolumnach, lub wprowadzane interakcyjnie przez użytkownika). Przyjmij ograniczenie ilości danych wejściowych. |
Szybka dyskretna transformata Fouriera
Reprezentacje sygnału w dziedzinie czasu (przebieg czasowy) i w dziedzinie częstotliwości (widmo częstotliwościowe) łączy przekształcenie (transformata) Fouriera. Dla sygnału czasowego h(t) jego transformata H(f) jest zdefiniowana jako [Borodziewicz, Jaszczak]:
Zadanie wyznaczania widma częstotliwościowego sygnału dyskretnego (tj. spróbkowanego w określonym przedziale czasu) hk o długości N, realizuje dyskretna transformata Fouriera:
(6.3.1)
Dla szczególnego przypadku ilości próbek sygnału równej potędze liczby 2 stosuje się algorytm FFT szybkiej transformaty Fouriera, wykorzystujący możliwość rozdzielenia obliczeń w danym kroku na dwa niezależne składniki. Przez rekurencyjne stosowanie tego zabiegu osiąga się zmniejszenie rzędu ilości wykonywanych operacji z N2 do N*log2(N).
Zaimplementuj ogólny algorytm dyskretnej transformaty Fouriera wg. wzoru (6.3.1) o złożoności rzędu N2. Sprawdź jego działanie dla testowego sygnału złożonego z dwóch sygnałów sinusoidalnych i drugiego sygnału o postaci fali prostokątnej (ze znanym rozkładem częstotliwościowym). Zapoznaj się z opisem algorytmu FFT w dokumentacji biblioteki Numerical Recipes in C. Zaimplementuj go. Porównaj swoją implementację z jego implementacją biblioteczną. Przeprowadź testy jak dla ogólnego algorytmu. |
Literatura
Borodziewicz W. Jaszczak K.: Cyfrowe przetwarzanie sygnałów; WNT, Warszawa 1987
Bjorck A., Dahlquist G.: Metody numeryczne; PWN, Warszawa 1987
Jankowski M.: Elementy grafiki komputerowej; WNT, Warszawa 1990
Kaczorek T.: Macierze w Automatyce i Elektrotechnice; WNT, Warszawa 1984
Kernighan B. W., Ritchie D. M.: Język C; WNT, Warszawa 1988
Mańczak K., Nahorski Z.: Komputerowa identyfikacja obiektów dynamicznych; PWN, Warszawa 1983
Press W.H., Flannery B.P., Teukolsky S.A., Vetterling W.T.: Numerical Recipes in C; Cambridge University Press 1988
Stroustrup B.:Język C++; WNT, Warszawa 1992
Wirth N.: Algorytmy + Struktury Danych = Programy; WNT, Warszawa 1989
Laboratorium Podstaw Informatyki Strona 2
Zakład Metrologii AGH