\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,kontrollflussgraph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {Methode „isPalindrom()“},
  Referenz = 46116-2015-H.T2-TA1-A2,
  RelativerPfad = Examen/46116/2015/09/Thema-2/Teilaufgabe-1/Aufgabe-2.tex,
  ZitatSchluessel = examen:46116:2015:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = korrekt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Kontrollflussgraph, C1-Test Zweigüberdeckung (Branch Coverage), C2b Schleife-Inneres-Pfadüberdeckung (Boundary-Interior Path Coverage), Zyklomatische Komplexität nach Mc-Cabe, C2a Vollständige Pfadüberdeckung (Full Path Coverage), Datenfluss-annotierter Kontrollflussgraph},
  EinzelpruefungsNr = 46116,
  Jahr = 2015,
  Monat = 09,
  ThemaNr = 2,
  TeilaufgabeNr = 1,
  AufgabeNr = 2,
}

% https://github.com/hbschlang/urheberrechtliches-studium-material-privat/blob/main/40%20SOSY/50%20Formale%20Verifikation%20und%20Testen/Pr%C3%A4senz%C3%BCbung%205/Praesenzuebung_5.pdf

% https://github.com/hbschlang/urheberrechtliches-studium-material-privat/blob/main/40%20SOSY/50%20Formale%20Verifikation%20und%20Testen/Pr%C3%A4senz%C3%BCbung%205/L%C3%B6sung%20Aufgabe%203%20palindrom/RS_H15_T2_TA1_A2_Lsg%20(handschriftlich).pdf

% https://github.com/hbschlang/urheberrechtliches-studium-material-privat/blob/main/40%20SOSY/50%20Formale%20Verifikation%20und%20Testen/Pr%C3%A4senz%C3%BCbung%205/L%C3%B6sung%20Aufgabe%203%20palindrom/RS_H15_T2_TA1_A2_Lsg.pdf

\let\c=\bKontrollCode
\let\w=\bBedingungWahr
\let\f=\bBedingungFalsch

Gegeben sei folgende Methode \bJavaCode{isPalindrom} und ihr
Kontrollflussgraph:\footcite{examen:46116:2015:09}
\index{Kontrollflussgraph}

\noindent
\textbf{Abkürzungen:} I = Import, E = Export

\begin{minipage}{9cm}
\bJavaDatei[firstline=5,lastline=17]{aufgaben/sosy/pu_5/Aufgabe2}
\end{minipage}
%
\begin{minipage}{4cm}
\begin{bKontrollflussgraph}[xscale=1,yscale=-1.1]
\node at (0,0) (I) {I};
\node at (0,1) (1) {1};
\node at (0,2) (2) {2};
\node at (0,3) (3) {3};
\node at (-0.5,4) (4) {4};
\node at (0,5) (5) {5};
\node at (0,6) (6) {6};
\node at (0,7) (E) {E};

\path (I) -- (1);
\path (1) -- (2);
\path (2) -- (3) \w{left};
\path (3) -- (4) \w{above left};
\path (4) -- (5);
\path (5) -- (6);
\path (6) -- (E) \f{left};
\path (2) edge[bend right=50] (E) \f{right};
\path (6) edge[bend right=90] (3) \w{left};
\path (3) edge[bend right] (5) \f{right};
\end{bKontrollflussgraph}
\end{minipage}

\begin{enumerate}

%%
% a)
%%

\item Geben Sie je einen Repräsentanten aller Pfadklassen \textbf{im
Kontrollflussgraphen} an, die zum Erzielen einer vollständigen … mit
\textbf{minimaler} Testfallanzahl und \textbf{möglichst kurzen} Pfaden
genügen würden.

\begin{bAntwort}
Bemerkung: In der Aufgabenstellung steht \emph{„Geben Sie je einen
Repräsentanten aller Pfadklassen \textbf{im Kontrollflussgraphen} an,
[...] “.} Das bedeutet, dass es hier erstmal egal ist, ob ein Pfad im
Code möglich ist oder nicht!

\begin{bKontrollflussgraph}[xscale=1,yscale=-1.2]
\node at (0,0) (I) {I};
\node[pin={\c{boolean yesItIs = true;}}] at (0,1) (1) {1};

\node[pin={
  [pin distance=0.5cm]
  äußeres if \c{if (s != null \&\& s.length() > 1)}
}] at (0,2) (2) {2};

\node[pin={
  [pin distance=1cm]
  inneres if \c{if (s.charAt(0) != s.charAt(s.length() - 1))}
}] at (0,3) (3) {3};

\node[pin={
  [pin distance=1.5cm]
  \c{yesItIs = false;}
}] at (-0.5,4) (4) {4};

\node[pin={
  [pin distance=1.5cm]
  \c{s = s.substring(1, s.length() - 1);}
}] at (0,5) (5) {5};

\node[pin={
  [pin distance=1cm]
  \c{while (yesItIs \&\& s.length() > 1);}
}] at (0,6) (6) {6};

\node at (0,7) (E) {E};

\path (I) -- (1);
\path (1) -- (2);
\path (2) -- (3) \w{left};
\path (3) -- (4) \w{above left};
\path (4) -- (5);
\path (5) -- (6);
\path (6) -- (E) \f{left};
\path (2) edge[bend right=50] (E) \f{right};
\path (6) edge[bend right=90] (3) \w{left};
\path (3) edge[bend right] (5) \f{right};
\end{bKontrollflussgraph}
\end{bAntwort}

\begin{enumerate}

%%
% i)
%%

\item Verzweigungsüberdeckung (Branch-Coverage, $C_1$)\index{C1-Test
Zweigüberdeckung (Branch Coverage)}

\def\TmpPfadEins{\bKontrollKnotenPfad{I - 1 - 2 - E}}
\def\TmpPfadZwei{\bKontrollKnotenPfad{I - 1 - 2 - 3 - 5 - 6 - 3 - 4 - 5 - 6 - E}}

\begin{bAntwort}
\begin{description}
% Video:
\item[Pfad 1 (p1)]

\TmpPfadEins

(äußere \bJavaCode{if}-Bedingung \bJavaCode{false})

\item[Pfad 2 (p2)]

\TmpPfadZwei

(äußere \bJavaCode{if}-Bedingung \bJavaCode{true}, innere \bJavaCode{if}-Bedingung
\bJavaCode{false}, Wiederholung, innere \bJavaCode{if}-Bedingung \bJavaCode{true}, keine
Wiederholung)
\end{description}

\end{bAntwort}

%%
% ii)
%%

\item Schleife-Inneres-Überdeckung (Boundary-Interior-Coverage,
$C_{\infty,2}$)\index{C2b Schleife-Inneres-Pfadüberdeckung
(Boundary-Interior Path Coverage)}

\begin{bAntwort}
% Video ab 1:10
\begin{description}
\item[ohne Ausführung der Wiederholung (äußere Pfade):]

p1 (siehe oben) \TmpPfadEins

\item[Boundary-Test:]

(alle Pfade, die die Wiederholung betreten, aber nicht wiederholen; innerhalb des
Schleifenrumpfes alle Pfade!)

\item[interior-Test:]

(alle Pfade mit \emph{einer Wiederholung des Schleifenrumpfes};
innerhalb des Schleifenrumpfes wieder alle Pfade!)

\def\TmpWahr{innere \bJavaCode{if}-Bedingung \bJavaCode{true}}
\def\TmpFalsch{innere \bJavaCode{if}-Bedingung \bJavaCode{false}}

\TmpWahr: \bKontrollKnotenPfad{3 - 4 - 5 - 6}

\TmpFalsch: \bKontrollKnotenPfad{3 - 5 - 6}

\begin{description}
\item[p5]

\bKontrollKnotenPfad{I - 1 - 2 - 3 - 4 - 5 - 6 - 3 - 4 - 5 - 6 - E}

(\TmpWahr, \TmpWahr)

\item[p2]

(siehe oben) \TmpPfadZwei

(\TmpFalsch, \TmpWahr)

\item[p6]

\bKontrollKnotenPfad{I - 1 - 2 - 3 - 4 - 5 - 6 - 3 - 4 - 5 - 6 - E}

(\TmpWahr, \TmpFalsch)

\item[p7]

\bKontrollKnotenPfad{I - 1 - 2 - 3 - 5 - 6 - 3 - 5 - 6 - E}

(\TmpFalsch, \TmpFalsch)
\end{description}
\end{description}
\end{bAntwort}
\end{enumerate}

mit \textbf{minimaler} Testfallanzahl und \textbf{möglichst kurzen}
Pfaden genügen würden.

%%
% b)
%%

\item Welche der vorangehend ermittelten Pfade für die
$C_{\infty,2}$-Überdeckung sind mittels Testfällen tatsächlich
überdeckbar (\emph{„feasible“})? Falls der Pfad ausführbar ist, geben
Sie den zugehörigen Testfall an - andernfalls begründen Sie kurz,
weshalb der Pfad nicht überdeckbar ist.

\begin{bAntwort}
\begin{description}
\item[p1] \bJavaCode{s = "a";}

\item[p2] \bJavaCode{s = "abaa";}

\item[p3] \bJavaCode{s = "ab";}

\item[p4] \bJavaCode{s = "aa";}

\item[p5]
nicht überdeckbar, da \bJavaCode{yesItIs = false}, wenn innere
\bJavaCode{if}-Bedingung \bJavaCode{true}) keine Wiederholung!

\item[p6]
nicht überdeckbar, da \bJavaCode{yesItIs = false}, wenn innere
\bJavaCode{if}-Bedingung \bJavaCode{true}) keine Wiederholung!

\item[p7] \bJavaCode{s = "abba";}
\end{description}
\end{bAntwort}

%%
% c)
%%

\item Bestimmen Sie anhand des Kontrollflussgraphen des obigen
Code-Fragments die maximale Anzahl linear unabhängiger Programmpfade,
also die zyklomatische Komplexität nach McCabe\index{Zyklomatische
Komplexität nach Mc-Cabe}.

\begin{bAntwort}
$M = b + p = 3 + 1 = 4$

($b$: Anzahl Binärverzweigungen, $p$: Anzahl Zusammenhangskomponenten)

\bPseudoUeberschrift{Alternativ}

$M = e - n + 2p = 10 - 8 + 2 = 4$

($e$: Anzahl Kanten, $n$: Anzahl Knoten, $p$: Anzahl
Zusammenhangskomponenten)
\end{bAntwort}

%%
% d)
%%

\item Kann für dieses Modul eine 100\%-ige Pfadüberdeckung\index{C2a
Vollständige Pfadüberdeckung (Full Path Coverage)} erzielt werden?
Begründen Sie kurz Ihre Antwort.

\begin{bAntwort}
Eine 100\%-ige Pfadüberdeckung kann nicht erzielt werden, da es zum
einen unüberdeckbare Pfade gibt (vgl. Teilaufgabe b). Zum anderen ist
das Testen aller Testfälle nicht möglich, da die Anzahl an Zeichen des
übergebenen Wortes nicht begrenzt ist und es somit eine unendliche
Anzahl an Testfällen gibt.
\end{bAntwort}

%%
% e)
%%

\item Übernehmen Sie den vorgegebenen Kontrollflussgraphen und
annotieren Sie ihn mit allen relevanten
Datenflussereignissen\index{Datenfluss-annotierter Kontrollflussgraph}.
Geben Sie jeweils an, ob die Verwendungen berechnend (\texttt{c-use})
oder prädikativ (\texttt{p-use}) sind.

\begin{bAntwort}
\begin{tikzpicture}[li kontrollfluss,xscale=1,yscale=-1.2]
\node at (0,0) (I) {I};
\node at (0,1) (1) {1};
\node at (0,2) (2) {2};
\node at (0,3) (3) {3};
\node at (-0.5,4) (4) {4};
\node at (0,5) (5) {5};
\node at (0,6) (6) {6};
\node at (0,7) (E) {E};

\path (I) -- (1);
\path (1) -- (2);
\path (2) -- (3) \bBedingung{left}{true};
\path (3) -- (4) \bBedingung{right}{true};
\path (4) -- (5);
\path (5) -- (6);
\path (6) -- (E) \bBedingung{left}{false};
\path (2) edge[bend right=90] (E);
\path (6) edge[bend right=90] (3);
\path (3) edge[bend right] (5);

\node[usebox] at (4,0) {def(s)} edge[dotted] (I);
\node[usebox] at (4,1) {def(yesItIs)} edge[dotted] (1);
\node[usebox,anchor=east] at (-3,4) {def(yesItIs)} edge[dotted] (4);
\node[usebox] at (4,5) {def(s), c-use(s)} edge[dotted] (5);
\node[usebox] at (4,7) {c-use(yesItIs)} edge[dotted] (E);
\end{tikzpicture}
\end{bAntwort}

\end{enumerate}
\end{document}
