Materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.


Laboratorium metodyki programowania

Ćwiczenie 10: Problemy występujące w bardziej złożonych programach

Scenariusz

  1. Student loguje się do systemu LOP (Laboratorium Otwartego Programowania).
  2. Student przechodzi do katalogu roboczego dla zajęć LMP.
  3. Student pobiera z repozytorium kod programów.
  4. Po wyjaśnieniach prowadzącego student przystępuje do kompilacji i uruchomienia programów. Porównuje wynik działania z kodem źródłowym.
  5. Student modyfikuje programy według wskazówek prowadzącego (patrz opis szczegółowy). Powtarza próbę kompilacji i uruchomienia.
  6. Ćwiczenie zaliczeniowe: student rozszerza funkcjonalność programu według zamówienia prowadzącego.

Opis szczegółowy

W trakcie trzech zajęć zmierzymy się z wyzwaniami pracy nad cokolwiek złożonym programem.

Rozpoczęcie pracy

Zajęcia będą prowadzone na komputerze stud.iem.pw.edu.pl. W celu rozpoczęcia pracy należy zalogować się na tym komputerze za pomocą usługi ssh. Można w tym celu wykorzystać albo dostępny w każdym praktycznie systemie Unix/Linux program ssh albo klienta SSH dla systemu Windows - PuTTY. Na maszynach studenckich w IETiSIP PW można podnieść różne dystrybucje Uniksa/Linuksa lub system Windows, ale w każdej z nich jest zainstalowane oprogramowanie ssh.

Do logowania na maszynie stud.iem.pw.edu.pl należy użyć takiego samego loginu i hasła jakie wykorzystywane są do dostępu do usług wydziałowych (poczta, e-dziekanat, itd.).

Po zalogowaniu się należy przejść do utworzonego na pierwszych zajęciach katalogu lmp:

 cd lmp

Kod do zajęć

lmp10.tgz

Problem

Otrzymujecie Państwo kod, który jest rozwiązaniem następującego zadania projektowego:


Program wyznaczający aproksymację zadanego ciągu danych pomiarowych.

Celem projektu jest napisanie programu, który będzie aproksymował zadany ciąg dwuwymiarowych danych (par liczb) gładką funkcją.

Zagadnienie aproksymacji danych pomiarowych opisane jest stosunkowo prosto w materiałach do wykładu z metod numerycznych dr. Tomasz Chwieja (AGH) (slajd nr 2, lewa kolumna); używane tam funkcje sklejane opisane są w wykładzie o interpolacji tego samego autora (slajdy 28-33).


Projektowanie programu

Aby rozpocząć projektowanie programu powinniśmy przede wszystkim dobrze zrozumieć, na czym polega problem, który mamy rozwiązać. Wyobraźmy sobie zestaw pomiarów otrzymanych na jakichś zajęciach laboratoryjnych. Na przykład załóżmy, że celem pomiarów było ustalenie charakterystyki nagrzewania wody w zbiorniku i efektem godzinnych pomiarów była lista zawierająca wartość temperatury w kolejnych minutach (pomiar wykonywany co 3 minuty):

0       0,0
3       4,0
6       8,3
9       11,6
12      15,2
15      17,2
18      21,9
21      25,0
24      28,0
27      34,1
30      33,7
33      36,4
36      38,9
39      41,4
42      41,7
45      46,0
48      48,2
51      50,3
54      72,3
57      54,2
60      56,0

Gdybyśmy chcieli przedstawić te dane w formie wykresu, to na przykład użycie programu OpenOffice Calc pozwoli otrzymać coś takiego:

Co pozwala odczytać pewną tendencję, ale zostało zapewne dość poważnie zniekształcone przez błędy pomiarowe - choćby ten z 54 minuty.

Wyobraźmy sobie teraz, że mamy dane przedstawione na kolejnym rysunku:

i chcemy napisać program, który pozwoli aproksymować te punkty funkcją, której postać możemy kontrolować - na przykład zielony wykres na kolejnym rysunku:

Po tym wstępie możemy już przejść do projektowania programu: przede wszystkim będziemy potrzebowali źródła danych testowych. Aby rozwiązać ten problem możemy napisać prosty generator:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4 #include <time.h>
   5 
   6 double fun( double x ) {
   7         double r= ((double)rand() - RAND_MAX/2.0)/RAND_MAX/5; // +-10%
   8         return (1+r)*(10*x*x*x*x+5*x*x*x+x*x);
   9 }
  10 
  11 int main( int argc, char **argv ) {
  12         int n= argc > 1 ? atoi( argv[1] ) : 100;
  13         double a= argc > 2 ? atof( argv[2] ) : -3;
  14         double b= argc > 3 ? atof( argv[3] ) : 2;
  15         FILE *out= argc > 4 ? fopen( argv[4], "w" ) : stdout;
  16 
  17         srand( argc > 5 ? atoi(argv[5]) : time(NULL) );
  18 
  19         int i;
  20         double dx = (b-a)/(n-1);
  21 
  22         for( i =0; i < n; i++ ) {
  23                 fprintf( out, "%g %g\n", a+i*dx, fun(a+i*dx) );
  24         }
  25         fclose( out );
  26 
  27         return 0;
  28 }

Wyposażeni w źródło danych możemy teraz zająć się naszym programem. Podzielimy go na kilka modułów:

We właściwie napisanym programie będziemy w stanie dość łatwo wymieniać najbardziej interesujący moduł, a więc Maker. W kodzie, który Państwo otrzymujecie znajdują się trzy przykładowe Makery:

Wszystkie Makery mają ten samy interfejs (makespl.h), co pozwala łatwo wymieniać je przy niezmienionym pozostałym kodzie.

Interpolator i aproksymator wykonują zadanie przez sformułowanie i rozwiązanie układu równań. Wykorzystują w tym celu prostą bibliotekę zawartą w katalogu gaus i implementującą algorytm eliminacji Gaussa z wyborem elementu dominującego.

Praca z kodem

Przede wszystkim powinni Państwo przeanalizować go i zrozumieć. Nie jest go bardzo dużo (łącznie niecałe 700 linii + niecałe 500 linii w katalogu gaus), ale zobaczycie, że zadanie nie jest trywialne ;-) Może być potrzebne tłumaczenie prowadzącego - nie wahajcie się o nie prosić.

Kod nie jest idealny - można go w wielu miejscach ulepszyć i Waszym zadaniem będzie także wskazanie takich miejsc. Pozwoli to łatwo sprawdzić, czy naprawdę go rozumiecie.

Jak uruchomić program? Po ściągnięciu kodu powinniście mieć katalog z następującą zawartością:

oer:~/tmp/lmp10/gr1> ls
aproksymator_na_bazie.c  gaus  interpolator.c  main.c  Makefile  makespl.h  points.c  points.h  prosta.c  splines.c  splines.h  test
oer:~/tmp/lmp10/gr1>

Po pierwsze kompilujemy bibliotekę gaus:

oer:~/tmp/lmp10/gr1> cd gaus
oer:~/tmp/lmp10/gr1/gaus> make
cc    -c -o matrix.o matrix.c
cc    -c -o pivot.o pivot.c
cc    -c -o piv_ge_solver.o piv_ge_solver.c
ar rvs libge.a matrix.o pivot.o piv_ge_solver.o
ar: creating libge.a
a - matrix.o
a - pivot.o
a - piv_ge_solver.o
oer:~/tmp/lmp10/gr1/gaus>

teraz możemy już skompilować aproksymator

oer:~/tmp/lmp10/gr1/gaus> cd ..
oer:~/tmp/lmp10/gr1> make
cc    -c -o main.o main.c
cc    -c -o splines.o splines.c
cc    -c -o points.o points.c
cc -I gaus -c aproksymator_na_bazie.c
cc -o aprox  main.o splines.o points.o aproksymator_na_bazie.o -L gaus -l ge
oer:~/tmp/lmp10/gr1>

i uruchomić go:

oer:~/tmp/lmp10/gr1> ./aprox
Usage: ./aprox -s spline-file [-p points-file] [ -g gnuplot-file [-f from_x -t to_x -n n_points ] ]
            if points-file is given then
               reads discrete 2D points from points-file
               writes spline approximation to spline-file
               - number of points should be >= 4
            else (points-file not given)
               reads spline from spline-file
            endfi
            if gnuplot-file is given then
               makes table of n_points within <from_x,to_x> range
               - from_x defaults to x-coordinate of the first point in points-file,
               - to_x defaults to x-coordinate of the last point
               - n_points defaults to 100
               - n_points must be > 1
            endif
oer:~/tmp/lmp10/gr1>

Korzystając z powyższych wskazówek uruchamiamy program z danymi testowymi:

./aprox -s spl -p test/dane.1 -g myplot -f 5.1 -t 5.7 -n 300

otrzymując:

Możemy narysować dane i nasz wykres:

oer:~/tmp/lmp10/gr1> gnuplot

        G N U P L O T
        Version 4.2 patchlevel 5
        last modified Mar 2009
        System: Linux 2.6.31.14-0.6-desktop

        Copyright (C) 1986 - 1993, 1998, 2004, 2007 - 2009
        Thomas Williams, Colin Kelley and many others

        Type `help` to access the on-line reference manual.
        The gnuplot FAQ is available from http://www.gnuplot.info/faq/

        Send bug reports and suggestions to <http://sourceforge.net/projects/gnuplot>


Terminal type set to 'x11'
gnuplot> plot 'test/dane.1', 'myplot'
gnuplot>

Otrzymamy rysunek gnuplot.png

Wykorzystując plik spl możemy rysować aproksymację dla innych przedziałów nie korzystając już z punktów:

oer:~/tmp/lmp10/gr1> ./aprox -s spl  -g innyplot -f 5.6 -t 5.997 -n 300
oer:~/tmp/lmp10/gr1> gnuplot

        G N U P L O T
        Version 4.2 patchlevel 5
        last modified Mar 2009
        System: Linux 2.6.31.14-0.6-desktop

        Copyright (C) 1986 - 1993, 1998, 2004, 2007 - 2009
        Thomas Williams, Colin Kelley and many others

        Type `help` to access the on-line reference manual.
        The gnuplot FAQ is available from http://www.gnuplot.info/faq/

        Send bug reports and suggestions to <http://sourceforge.net/projects/gnuplot>


Terminal type set to 'x11'
gnuplot>  plot 'myplot', 'innyplot'

Rysunek:

gnuplot2.png

Przyjemną cechą funkcji sklejanych jest możliwość dopasowania bazy. Mniejsza liczba funkcji bazowych oznacza prostszą funkcję, choć zapewne odwzorowującą dane z większym błędem. Popatrzmy na aproksymację z wykorzystaniem nie 10, a tylko 3 funkcji bazowych:

oer:~/tmp/lmp10/gr1> export APPROX_BASE_SIZE=3
oer:~/tmp/lmp10/gr1> ./aprox -s spl -p test/dane.1 -g 3spl
oer:~/tmp/lmp10/gr1> gnuplot

        G N U P L O T
        Version 4.2 patchlevel 5
        last modified Mar 2009
        System: Linux 2.6.31.14-0.6-desktop

        Copyright (C) 1986 - 1993, 1998, 2004, 2007 - 2009
        Thomas Williams, Colin Kelley and many others

        Type `help` to access the on-line reference manual.
        The gnuplot FAQ is available from http://www.gnuplot.info/faq/

        Send bug reports and suggestions to <http://sourceforge.net/projects/gnuplot>


Terminal type set to 'x11'
gnuplot> plot 'test/dane.1', '3spl'

3spl.png

Zadanie na zaliczenie

Zadawane przez prowadzącego, na przykład:


To już prawie wszystko, ale nie wolno nam zapomnieć, że

materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.

wikidyd - IETiSIP, Wydzial Elektryczny Politechniki Warszawskiej: LMP/10 (last edited 2012-12-03 14:21:36 by JacekStarzyński)