uni/ws2019/ipi/uebungen/ipi11.tex

\documentclass[uebung]{../../../lecture}

\title{IPI: Übungsblatt 11}
\author{Samuel Weidemaier, Christian Merten}

\begin{document}

\begin{tabular}{|c|m{1cm}|m{1cm}|m{1cm}|m{1cm}|@{}m{0cm}@{}}
    \hline
    Aufgabe & \centering A1 & \centering A2 & \centering A3 & \centering $\sum$ & \\[5mm] \hline
    Punkte & & & & & \\[5mm] \hline
\end{tabular}

\begin{aufgabe}
    Polynomschablone. Die vorgegebene Implementation der \lstinline{SimpleArray} Klasse
    ist in \textit{simplearray.cc} zu finden. In \textit{polynomial.cc} befindet
    sich die Implementation der verallgemeinerten \lstinline{Polynomial} Klasse.
    \begin{lstlisting}[language=C++, captionpos=b, title=polynomial.cc]
#include <iostream>
#include <stdio.h>
#include "simplearray.cc"

template <class T>
class Polynomial: public SimpleArray<T> {
    public:
        // konstruiere Polynom vom Grad n
        Polynomial<T> (int n);

        // Default-Destruktor ist ok
        // Default-Copy-Konstruktor ist ok
        // Default-Zuweisung ist ok

        // Grad des Polynoms
        int degree();

        // Auswertung
        T eval (T x);

        // Addition von Polynomen
        Polynomial<T> operator+ (Polynomial<T> q);

        // Multiplikation von Polynomen
        Polynomial<T> operator* (Polynomial<T> q);

        // Gleichheit
        bool operator== (Polynomial q);

        // drucke Polynom
        void print ();
};

// Constructor
template <class T>
Polynomial<T>::Polynomial(int n)
    : SimpleArray<T>::SimpleArray(n+1,0.0) {}

// Grad auswerten
template <class T>
int Polynomial<T>::degree ()
{
    return SimpleArray<T>::maxIndex();
}

// Addition von Polynomen
template <class T>
Polynomial<T> Polynomial<T>::operator+ (Polynomial<T> q) {
    int nr=degree(); // mein grad

    if (q.degree()>nr) nr=q.degree();

    Polynomial r(nr); // Ergebnispolynom

    for (int i=0; i<=nr; i=i+1)
    {
        if (i<=degree())
            r[i] = r[i]+(*this)[i]; // add me to r
        if (i<=q.degree())
            r[i] = r[i]+q[i];       // add q to r
    }

    return r;
}

// Multiplikation von Polynomen
template <class T>
Polynomial<T> Polynomial<T>::operator* (Polynomial<T> q)
{
    Polynomial r(degree()+q.degree()); // Ergebnispolynom

    for (int i=0; i<=degree(); i=i+1)
        for (int j=0; j<=q.degree(); j=j+1)
            r[i+j] = r[i+j] + (*this)[i]*q[j];

    return r;
}

// Drucken
template <class T>
void Polynomial<T>::print ()
{
    if (degree()<0)
        std::cout << 0;
    else
        std::cout << (*this)[0];

    for (int i=1; i<=SimpleArray<T>::maxIndex(); i=i+1) 
        std::cout << " + " << (*this)[i] << "*x^" << i;

    std::cout << std::endl;
}

int main() {
    Polynomial<float> p(2);
    p[0] = 1.0;
    p[1] = 1.0;
    p.print();

    p = p*p;
    p.print();

    Polynomial<double> q(3);
    q[0] = 2.0;
    q[1] = -1.0;
    q[3] = 4.0;
    q.print();
}\end{lstlisting}
\end{aufgabe}

\begin{aufgabe}
    Vektorimplementation
    \begin{lstlisting}[language=C++, captionpos=b, title=vectors.cc]
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// a class implementing a mathematical vector
template <class K, size_t N>
class Vector {
    public:
        // constructor, initializes vector with zeroes of length N
        Vector() : _vector(N, 0) {}
        // initialize by passing vector vec to initialize the vector object with
        Vector(std::vector<K> vec) { _vector = vec; }
        
        // copy constructor, assignment, destructor not needed
        // all handled by std::vector
        
        // reference [] operator, used for assignments
        K& operator[](int i) {
            return _vector[i];
        }

        // const ref [] operator
        K operator[](int i) const {
            return _vector[i];
        }

        // return an iterator pointing to the first element of the underlying std::vector
        typename std::vector<K>::const_iterator begin() const {
            return _vector.begin();
        }
        
        // return an iterator pointing to the last element of the underlying std::vector
        typename std::vector<K>::const_iterator end() const {
            return _vector.end();
        }

        // dot product of two vectors of the same length
        template <class K2>
        K operator*(const Vector<K2,N>& y) {
            std::vector<K> result(N); // new empty std::vector of correct size
            // now multiply one element of the first with one of the second vector
            std::transform(_vector.begin(), _vector.end(), y.begin(), result.begin(), std::multiplies<K>());
            // and sum up the products
            return std::accumulate(result.begin(), result.end(), 0);
        }

        // vector addition
        template <class K2>
        Vector<K, N> operator+(const Vector<K2, N>& y) {
            std::vector<K> result(N); // new empty std::vector of correct size
            // add elements by adding one element of the first to one of the second vector
            std::transform(_vector.begin(), _vector.end(), y.begin(), result.begin(), std::plus<K>());
            return Vector(result);
        }

        // return the maximum value in the vector
        K max() {
            return *std::max_element(_vector.begin(), _vector.end());
        }

        // return the minimum value in the vector
        K min() {
            return *std::min_element(_vector.begin(), _vector.end());
        }

        // return the average value of the vector
        K average() {
            // sum up all elements
            K sum = std::accumulate(_vector.begin(), _vector.end(), 0);
            return sum / N; // and divide by length
        }

        // run the specified function on each vector element
        template <class F>
        Vector<K,N> map(F op) const {
            std::vector<K> result(N); // initialize new std::vector of correct size
            // run op on each element
            std::transform(_vector.begin(), _vector.end(), result.begin(), op);
            return Vector(result);
        }
    private:
        std::vector<K> _vector; // the private std::vector container
};

// print vector
template <class K, size_t N>
std::ostream& operator<<(std::ostream& os, const Vector<K,N>& v) {
    os << "["; // opening brackets
    for (size_t i = 0; i < N; i++) {
        os << v[i]; // print element
        if(i < N-1) {
            os << ", "; // if not the last one, add comma
        }
    }
    os << "]"; // closing brackets
    return os;
}

// scalar multiplication for vector * scalar
template <class K, size_t N, class K2>
Vector<K, N> operator*(const Vector<K,N>& v, const K2 k) {
    // multiply a scalar value using the generic map function
    return v.map(std::bind1st(std::multiplies<K>(), k));
}

// scalar multiplication for scalar * vector
template <class K, size_t N, class K2>
Vector<K, N> operator*(const K2 k, const Vector<K,N>& v) {
    return v * k;
}


// example function
double foo(double val) {
    return val*2+3;
}

// testing out functionalities
int main() {
    Vector<double, 3> a;
    Vector<float, 3> b;
    a[0] = 0;
    a[1] = 0;
    a[2] = 4;

    b[0] = 42;
    b[1] = -20;
    b[2] = 3;

    std::cout << "Vektor a: " << a << ", Vektor b: " << b << std::endl;
    std::cout << "a+b: " << a+b << std::endl;
    std::cout << "a*b: " << a*b << std::endl;
    std::cout << "42*b: " << 42*b << std::endl;
    std::cout << "b*42: " << b*42 << std::endl;
    std::cout << "max(a): " << a.max() << std::endl;
    std::cout << "min(a): " << a.min() << std::endl;
    std::cout << "mean(a): " << a.average() << std::endl;
    std::cout << "foo angewendet auf b: " << b.map(foo) << std::endl;
}\end{lstlisting}
\end{aufgabe}

\begin{aufgabe}[Funktoren und statischer Polymorphismus] 
    \begin{enumerate}[(a)]
        \item Integration mittels Trapezregel
            für $n = 10$, $n = 100$ und $n = 1000$ beispielsweise ausgerechnet.
\begin{lstlisting}[language=C++, captionpos=b, title=integration.cc]
#include <iostream>
#include <cmath>

// Implementiert die Trapezregel mit der Intervallanzahl n
// der unteren Integrationsgrenze a, der oberen Integrationsgrenze b
// und ueber die Funktion f
template <class Function>
double trapezregel(int n, double a, double b, Function f) {
    double h = (b-a)/n; // berechne intervalllaenge
    double accum = 0;
    for (int i = 1; i < n; i++) {
        accum += f(a + i*h); // fuehre die summe aus
    }
    return h/2 * (f(a) + 2*accum + f(b)); // wende formel an
}

// beispiel fuer funktor
class Wurzel {
    public:
        double operator()(double x) {
            return std::sqrt(x);
        }
};

int main() {
    Wurzel f;    
    // fuehre integration fuer verschiedene Intervallanzahlen n aus
    double integ10 = trapezregel(10, 0, 1.5, f);
    double integ100 = trapezregel(100, 0, 1.5, f);
    double integ1000 = trapezregel(1000, 0, 1.5, f);
    std::cout << "Integral ueber sqrt(x) von 0 bis 1.5" << std::endl;
    std::cout << "n = 10: " << integ10 << std::endl;
    std::cout << "n = 100: " << integ100 << std::endl;
    std::cout << "n = 1000: " << integ1000 << std::endl;
}\end{lstlisting}

        \item Vorteile der Verwendung von statischem Polymorphismus gegenüber dynamischem Polymorphismus:
            \begin{itemize}
                \item Auswertung zum Zeitpunkt des Kompilierens führt zu besserer Optimierung und
                    Fehlererkennung durch den Compiler.
                \item Weniger Overhead durch VTABLE's, etc.
                \item Deshalb effizienter und schneller
            \end{itemize}
            Nachteile:
            \begin{itemize}
                \item Potentiell unübersichtlicher
                \item Größe der Programme als kompilierte Binärdatei ist größer
            \end{itemize}

    \end{enumerate}
\end{aufgabe}

\end{document}