Metody Programowania - Lista 1

Zadanie 1

Obliczyć dokładnie (jako funkcję n) ilość porównań (tzn. znaleźć wzór) w algorytmie sortowania przez wybór:

void sortuj(int * ll, int n)
{
        int i, mi, tmp;
        for(i = 0; < n - 1; i++) {
                int k;
                mi = i;
                for(k = i + 1; k < n; k++) {
                        if(ll[k] < ll[mi]) mi = k;
                }
                tmp = ll[i];
                ll[i] = ll[mi];
                ll[mi] = tmp;
        }
}

Sprawdzić wynik modyfikując program tak by obliczył i wypisał ilość porównań.

Zadanie 2

a) Obliczyć ilości działań arytmetycznych potrzebnych do obliczenia wartości wielomianu stopnia n różnymi metodami (sumowanie wyrazów z obliczaniem potęg oddzielnie dla każdego wyrazu (przy pomocy oddzielnej funckji), przy iteracyjnym obliczaniu potęg (równocześnie z obliczaniem sumy), itp.). Przedyskutowac wyniki.

b) Obliczyć ilości działań arytmetycznych potrzebnych do pomnożenia dwu macierzy n na n metodą "z definicji".

Zadanie 3

Obliczyć ile wywołań rekursywnych wykonuje się przy rekursywnym obliczaniu liczb Fibonacciego:

int fib(int n)
{
    if (n < 2) {
        return 1;
    } else {
        return fib(n - 1) + fin(n - 2)
    }
}

czy współczynników dwumianowych:

int n_nad_k(int n, int k)
{
    if (k == 0 || k == n) {
        return 1;
    } else {
        return n_nad_k(n - 1, k - 1) + n_nad_k(n - 1, k);
    }
}

Znaleźć dokładny wzór i sprowdzić przy pomocy programu.

Zadanie 4

Nastepujący program kopiuje wejście na wyjście blokami

int
main(void)
{
    char bufor[1024];
    int dlugosc;
    while((dlugosc = read(0,bufor,1024)) > 0) {
                write(1, bufor, dlugosc);
    }
    return 0;
}

Napisać wersję wykonującą kopiowanie znak po znaku (przy użyciu 'getchar' i 'putchar'). Zmierzyć czas wykonania przy pomocy polecenia 'time' do obu wersji i kilku wielkości pliku (np. 1MB, 10MB, 100MB). Każdy pomiar powtarzać kilkakrotnie. Powtórzyć pomiary kompilując programy przy pomocy opcji '-O0', '-O', '-O2' i '-O3' (spróbować na kilku _różnych_ komputerach). Przedyskutować wyniki.

Zadanie 5

Poniższa funkcja oblicza sumę sinusów liczb od 1 do n:

#include 

double
sumuj_sinusy(int n)
{
    int i;
    double suma = 0;
    for(i=1; i <= n; i++) {
        suma += sin(i);
    }
    return suma;
}
Napisać program główny który wywoła tą funkcję w pętli 100000 (chodzi
o to by sztucznie wydłużyć czas wykonania tak, by było go łatwo 
zmierzyć) z argumentem 1000. Następnie zrobić wersję która oblicza
sinusy kolejnych kątów przy pomocy wzorów na sinus i kosinus sumy kątów
korzystając ze wstępnie obliczonych (przy pomocy funkcji bibliotecznej)
wartości 'sin(1)' i 'cos(1)'. Porównać czasy wykonania (dla różnych
opcji kompilatora) i przedyskutować wyniki.

 Zadanie 6

Zapoznać się z programem  rread.c . Przekompilować
go i zmierzyć czas wykonania. Ile razy wykonuje się wewnętrzna pętla
w funkcji 'iter_tab' i jak długo (w taktach zegara procesora) trwa
jedno okrążenie tej pętli. Porównać to z wersją gdzie argument krok 
jest równy 1. Tradycyjnie, powtórzyć to dla różnych opcji kompilatora.
Przedyskutować wyniki.