\documentclass[11pt,a4paper]{article}

\usepackage{ngerman}
%\usepackage{amstext}
%\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{stmaryrd}
\usepackage{enumerate}
%\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}
\usepackage{arcs}
%\usepackage{fuzz}

\thispagestyle{empty}

\title{Softwaretechnik (WS 2005/2006) - Übungsblatt 13}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Übungsgruppe Mi, 8-10 Uhr \\
		Dirk Heine - Matrikelnummer 2030941 \\
		Übungsgruppe Di, 14-16 Uhr \\\\
		Rückgabe: Übungsgruppe Di, 14-16 Uhr
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
\subsubsection*{(a)}
\bild{7.2}{a1a}{Aufgabe 1a}{}

\subsubsection*{(b)}
Anweisungsüberdeckung bedeutet, dass jeder Knoten im Kontrollflussgraphen einmal durchlaufen werden muss.
\begin{enumerate}
	\item Testfall: \texttt{ggt(0,0)} \\
		Es wird die erste \texttt{if}-Schleife einmal durchlaufen. Es werden die Knoten (0), (1), (2), (13) erreicht.
	\item Testfall: \texttt{ggt(7,8)}
		\begin{enumerate}
			\item Es wird die zweite \texttt{if}-Schleife durchlaufen.
			\item Es wird einmal die \texttt{while}-Schleife durchlaufen bis 1 zurückgegeben wird.
		\end{enumerate}
		Es werden die Knoten (0), (1), (3), (4), (5), (6), (7), (8), (9), (10), (11), (12), (13) abgedeckt.
\end{enumerate}
Somit wurden alle Knoten mindestens einmal durchlaufen.

\subsubsection*{(c)}
Um Zweigüberdeckung zu erreichen, muss jede Kante im Kontrollflussgraphen einmal ausgeführt werden. Die Zweigüberdeckung schließt die Anweisungsüberdeckung mit ein. Um im vorliegenden Beispiel Zweigüberdeckung zu erreichen, muss ein Testfall eingeführt werden, der die Transition von Knoten (3) nach Knoten (7) abdeckt. Dazu kann man z.B. einen dritten Testfall \texttt{ggt(5,3)} einführen.

\subsubsection*{(d)}
Ein Problem bei der Pfadüberdeckung stellt sich dadurch, dass sie eigentlich keinen praktischen Nutzen hat. Die meisten Programme haben so viele mögliche Pfade, dass man unmöglich alle testen kann. Man beschränkt sich daher in der Regel auf den Boundary Interior-Pfadtest oder den strukturierten Pfadtest, die beide die Anzahl der zu testenden Pfade einschränken.

\subsubsection*{(e)}
Die Idee besteht darin, die Anzahl der zu überprüfenden Pfade zu reduzieren, indem keine Pfade geprüft werden, bei denen Schleifen mehr als zweimal durchlaufen werden. Bei der Pfadüberdeckung muss sichergestellt sein, dass alle Pfade mindestens einmal durchlaufen werden. Für den Boundary Interior-Test fehlt noch der Pfad außerhalb aller Schleifen. Dazu kann man z.B. den Testfall \texttt{ggt(1,1)} einführen, in dem keine Schleife betreten wird.

\newpage
\subsubsection*{(f)}
\begin{verbatim}
$ gcov ggt
File 'ggt.c'
Lines executed: 93.75% of 16
ggt.c:creating 'ggt.c.gcov'
\end{verbatim}
\texttt{ggt.c.gcov}:
\begin{verbatim}
        -:    0:Source:ggt.c
        -:    0:Graph:ggt.gcno
        -:    0:Data:ggt.gcda
        -:    0:Runs:1
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:
function ggt called 1 returned 100% blocks executed 91%
        1:    3:int ggt(int a, int b) {
        1:    4:    int tmp, remainder;
        1:    5:    if((a<=0) || (b<=0)) {
    #####:    6:        return -1;
        -:    7:    }
        1:    8:    if (a < b) {
        1:    9:        tmp = a;
        1:   10:        a = b;
        1:   11:        b = tmp;
        -:   12:    }
        1:   13:    remainder = a % b;
        7:   14:    while (remainder != 0) {
        6:   15:        a = b;
        6:   16:        b = remainder;
        6:   17:        remainder = a % b;
        -:   18:    }
        1:   19:    return b;
        -:   20:}
        -:   21:
function main called 1 returned 100% blocks executed 100%
        1:   22:int main() {
        1:   23:    printf("ggt(11324,23443)=%d\n",ggt(11324,23443));
        -:   24:}
        -:   25:
\end{verbatim}

\newpage
\section*{Aufgabe 2}
\subsubsection*{(a)}
Angenommen, eine Methode nimmt als Argumente Parameter die aktuelle Außentemperatur.
\begin{verbatim}
bool OutOfRangeTemp(float a) {
  if((a < -10) || (a > 40)) return true;
}
\end{verbatim}
Da die Temperatur aber entweder $< -10$ Grad oder $> 40$ Grad sein kann, gibt es keinen Fall, in dem beide atomaren Bedingungen wahr werden können. Somit ist eine Mehrfach-Bedingungsüberdeckung nicht zu realisieren.

\subsubsection*{(b)}
\begin{enumerate}[A:]
	\item \texttt{!isAlreadyLoggedIn(user)}
	\item \texttt{user.hasNeededCash()}
	\item \texttt{user.isSuperUser()}
\end{enumerate}

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
Testfall & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
A & T & F & F & T & T & F & T \\
B & F & T & F & T & F & T & T \\
A \AND\ B & F & F & F & T & F & F & T \\ \hline
C & F & F & T & F & T & T & T \\
A \AND\ B \OR\ C & F & F & T & T & T & T & T \\ \hline
\end{tabular}
\end{center}

\newpage
\section*{Aufgabe 3}
\subsubsection*{(a)}
Beim Mutationstesten werden absichtlich Fehler in ein Programm eingebaut, um die Güte und Vollständigkeit der Testfälle zu überprüfen.

\subsubsection*{(b)}
Es werden lediglich 50 \% der Fehler gefunden. Dies ist zu wenig. Die Testsuite muss insofern erweitert werden, dass entweder mehr Tests eingefügt werden oder Tests korrigiert werden, die bisher \glqq falsch\grqq\ geprüft haben. Es sollte eine Mutanten-Kill-Quote von mindestens 90 \% erreicht werden.

\subsubsection*{(c)}
Die Restfehleranzahl $E$ kann man wie folgt schätzen:
$$E = (M - X) \cdot \frac{N}{X}$$
Dabei sind:
\begin{itemize}
	\item $N$ die Gesamtanzahl der Mutationen
	\item $M$ die Anzahl der gefundenen Fehler (incl. Mutanten)
	\item $X$ die Anzahl der gefundenen Mutanten
\end{itemize}
Also folgt für $E$:
\begin{align*}
	E &= (M - X) \cdot \frac{N}{X} \\
	&= (1958 - 1950) \cdot \frac{2000}{1950} \\
	&= 8,\overline{205128} \\
	&\approx 8
\end{align*}
Die Anzahl der Restfehler liegt bei ungefähr 8 (bzw. nicht mathematisch, sondern sinnvoll gerundet bei 9) Fehlern.


\end{document}