Für das Modul prog¹ im Wintersemester 2023/2024 des Fernstudiengangs Informatik (M.C.Sc.) der Hochschule Trier habe ich hier Lösungshinweise zu ausgewählten Tests zusammengefasst. Diese stehen als PDF zum Download zur Verfügung.

Repetitorium und Lösungshinweise Musterklausur (22.03.2024)​

• Das Repetitorium zu dem Modul PROG im WS 23/24 kann hier heruntergeladen werden
• Lösungsvorschläge, Anmerkungen und Ergänzungen zu der Musterklausur können hier heruntergeladen werden.

Lösungshinweise Test 5 - Such-undSortieralgorithmen (23.01.2024)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Lösungshinweise Test 4 - Dynamische Datenstrukturen und spezifische Algorithmen (09.01.2024)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Lösungshinweise Test 3 - Objektorientierung (05.12.2023)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Die Lösungshinweise beinhalten nicht die Testaufgaben, bei denen eine bestimmte Programmausgabe nachvollzogen werden musste.

Um Konzepte des Lehrmaterials deutlicher von weiterführenden, für den Kurs weniger relevante Themen abzugrenzen, sind diese nun unter Exkurs in den jeweiligen Abschnitten zusammengefasst.

Lösungshinweise Test 1 - Klassenbasierte Programmierung (31.10.2023)​

Lösungshinweise sowie Anmerkungen und Ergänzungen können hier heruntergeladen werden.

Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als Sortieren mit abnehmenden Inkrementen [📖OW17b, p. 88], das Verfahren ist eine Variation von Insertion Sort:

[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, p. 48]

In der vorliegenden Implementierung (siehe Listing 1) werden $t = log_2(n)$ Inkremente¹ $h_t$² der Form $\lfloor {\frac{n}{2^i}} \rfloor$ verwendet, um $lg(n)$ $h$-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in $h_1$ die Schlüssel mit Abstand=$1$.

Die Effizienz des Sortierverfahrens ist stark abhängig von $h$: So zeigt Knuth, dass $O(n^{\frac{3}{2}})$ gilt, wenn für $h$ gilt: $h_s = 2^{s+1} - 1$ mit $0 \leq s < t = \lfloor{lg(n)} \rfloor$ (vgl. [📖Knu97c, p. 91]³. In unserem Fall können wir von $O(n^2)$ ausgehen.

Anzahl der Aufrufe für Feldvergleiche​

Gesucht ist die Anzahl der zwischen zwei Feldelementen gemachte Vergleiche für große randomisierte Felder. Wir vermuten hierfür einen Wert zwischen $O(n\ lg\ n)$ und $O(n^2)$,

Um die Aufrufe der Feldvergleiche zu zählen, kann wie in Listing 1 eine Zählvariable $c3$ eingesetzt wird, die jeden Aufruf über ein increment protokolliert.

while (distanz > 0) {
    c1++;
    for (i = distanz; i < feld.length; i++) {
        j = i - distanz;
        c2++;
        while (j >= 0) {
            c3++;
            if (feld[j] > feld[j + distanz]) {
                c4++;
                swap(feld, j, j+distanz);
                j = j - distanz;
            } else {
                j =-1;
            }
        }
    }
    distanz = distanz / 2;
}

Zur Bestimmung von $c3$ können randomisierte Felder erzeugt werden, wie es der Test-Code in Listing 2 demonstriert. Dann wird überprüft, in welchen Bereichen sich $c3$ bewegt. Da jeder auf Vergleichsoperationen basierende Sortieralgorithmus zu der Laufzeitklasse $\Omega(n\ log\ n)$ gehört, kann im Mittel $c3 \geq n\ log\ n$ angenommen werden:

Jedes allgemeine Sortierverfahren benötigt zum Sortieren von N verschiedenen Schlüsseln sowohl im schlechtesten Fall als auch im Mittel wenigstens $\Omega(N\ log\ N)$ Schlüsselvergleiche.

[📖OW17b, p. 154]

Allerdings wird $n^{1.3}$ ab $n=982$ schneller wachsen als $n\ log\ n$ (siehe Abbildung 1), was in der Auswertung berücksichtigt werden muss. Sonst könnte man fälschlicherweise folgern, das in dem geg. Fall die Laufzeit im Durchschnitt $n\ log\ n$ beträgt.

int epochs = 2000;
while(epochs-- >= 0) {
    int[] tests = new int[]{10, 100, 1000, 100_000, 1_000_000};
    java.util.Random r = new java.util.Random();
    for (int i = 0; i < tests.length; i++) {
        int l = tests[i];
        int[] arr = new int[l];

        for (int j = l; j > 0; j--) {
            arr[l - j] = r.nextInt(l + 1);
        }

        ShellSort.sort(Arrays.copyOfRange(arr, 0, arr.length));
    }
}

^{Figure 1 Ab n=982 wächst n(4/3) schneller al n log n.}

Wegen $\Omega(n\ log\ n)$ interessieren wir uns für die Intervalle:

• $n\ log\ n \leq c3 \leq n^{1.3}$

• $n\ log\ n \leq n^{1.3} \leq c3 \leq n^2$

Die Ausführung des Tests zeigt, dass die Aufrufanzahl von $c3$ bei großen $n$ unterhalb $n^{1.3}$ oder zwischen $n^{1.3}$ und $n^2$ liegt:

It appears that the time required to sort $n$ elements is proportional to $n^{1.226}$.⁴ [📖She59, p. 31]

Laufzeitanalyse​

Für die nachfolgenden Betrachtungen sei eine Eingabegröße $n = 2^p$ gegeben. Die Inkremente $h$ entsprechen der über die Implementierung vorgegebenen Folge $h$ mit

Für die Analyse ist die Shellsort-Implementierung in Listing 3 gegeben.

public static int[] sort(int[] arr) {

    int n = arr.length;
    int delta = n/2;
    int min;
    int j;

    while (delta > 0) { // c1

        for (int i = delta; i < arr.length; i++) {

            // c2

            min = arr[i];
            j = i;

            while (j - delta >= 0 && min < arr[j - delta]) {

                // c3;

                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = min;
        }

        delta = delta / 2;

    }
    return arr;
}

Im Folgenden betrachten wir die Anzahl für die im Code durch Kommentare markierten Stellen $c1$ in Zeile 8, $c2$ in Zeile 12 und $c3$ in Zeile 19.

Für eine erste worst-case-Analyse ist ein Feld der Länge $16$ gegeben, in absteigender Reihenfolge sortiert (s. Abbildung 2):

^{Figure 2 Die für die Laufzeitabschätzung verwendete Eingabefolge 16..1.}

Ganz offensichtlich gilt für c3, dass es $lg(n)$-mal aufgerufen wird⁵. c2 befindet sich im Block der durch die in Zeile 11 definierten Zählschleife.

Der Startwert für i ist in jedem Durchgang des Blocks $c1$ der aktuelle Wert von delta ⁶, und läuft jeweils bis $n - 1$.

In einem kompletten Durchlauf der Schleife entspricht die Anzahl der Aufrufe von $c2$ also

Für die Gesamtzahl der Aufrufe von $c2$ ergibt sich somit unter Berücksichtigung von $c1$

entspricht, und für unser Beispiel

ist.

In der while-Schleife in Zeile 17 findet die eigentliche Arbeit des Algorithmus statt: Es wird überprüft, ob $delta$-entfernte Elemente in aufsteigender Reihenfolge sortiert angeordnet sind.

Ist das nicht der Fall, werden die Elemente an den Stellen $j$ und $j - delta$ ausgetauscht, bis die $h$-Folge sortiert ist.
Für den ersten Durchgang des Algorithmus an dieser Stelle mit $h_4 = 8$ ergibt sich somit die in Abbildung 3 dargestellte Reihenfolge der Schlüssel:

^{Figure 3 Nach dem ersten Durchgang sind die Schlüssel in den Abständen h₄ = 8 sortiert, es ergeben sich zwei sortierte Teilfolgen der Länge 8.}

Die weiteren Durchgänge des Algorithmus sortieren das Feld entsprechend der Größe $h$: Es sind danach jeweils Schlüssel mit den Abständen $4$ (Abbildung 4 und $2$ (Abbildung 5) sortiert; im letzten Schritt dann vollständig (Abbildung 6):

^{Figure 4 Die Sortierung für h₃ = 4, es sind 4 Folgen deren Schlüssel jeweils den Abstand 4 zueinander haben.}

^{Figure 5 Im vorletzten Sortierschritt sind 8 Folgen der Länge 2 sortiert.}

^{Figure 6 Der letzte Durchgang des Algorithmus vergleicht Schlüssel mit Distanzfolgen der Länge 1, also direkt benachbarte Schlüssel.}

Für die Berechnung der Anzahl der Aufrufe von $c3$ stellt man fest, das in diesem Fall in jedem Schritt immer 2 Elemente, die eine Distanz von $h_s$ aufweisen, falsch sortiert sind.

Der Algorithmus tauscht daraufhin in jedem Durchgang alle Schlüssel untereinander aus, die er über min < arr[j-delta] miteinander vergleicht, was folglich die maximale Anzahl von Schlüsselvertauschungen in dieser vergleichsbasierten Implementierung für ein Feld der Größe $n$ ergibt, nämlich $\frac{n}{2}$. Insgesamt finden dadurch für $c3$

Aufrufe statt.

Mit der Anzahl der berechneten Aufrufe $c1, c2, c3$ ergibt sich somit für die Laufzeit $T(n)$ für diesen Fall

und zusammengefasst

was nach Einsetzen zu

Aufrufen für unser Beispiel führt.

Nachweis der Komplexitätsklasse​

Um $O$ zu ermitteln, werden nun alle Konstanten der Funktion

eliminiert, und der "dominante" Summand in Abhängigkeit von $n$ betrachtet, der in diesem Fall $lg(n) * n$ ist.

Wir vermuten ein $N-log-N$-Wachstum⁷ (vgl. [📖OW17a, p. 5]), und wollen nun zeigen, dass $T(n)$ in $O(n\ log\ n)$ liegt.
Hierfür müssen wir ein geeignetes $c$ und ein $n_0$ finden, so dass gilt:

(vgl. [📖GD18a, p. 11]).

Zu zeigen ist

Wir wählen für $n_0 = 1$ und $c = \frac{3}{2}$, denn es gilt sicher

Ausserdem gilt stets $\forall n \in \mathbb{N}: lg(n) < n$, woraus $lg(n) - n < 0$ folgt, und damit auch $lg(n) - n + 1 \leq 0$.

Insgesamt gilt also

womit $f = O(n * log(n))$ gezeigt ist. ◻

Worst-Case-Analyse​

Unter der Annahme, dass ein in umgekehrter Reihenfolge sortiertes Feld zu einer Laufzeit von $O(n^2)$ bei dem Shellsort-Algorithmus führt, konnten wir mit dem in dem vorherigen Abschnitt gewählten Parametern nur eine Laufzeit von $O(n\ log\ n)$ nachweisen.
Tatsächlich stellt der Anwendungsfall nicht den worst-case für den Algorithmus dar, da ja gerade diese Form von Sortierreihenfolge dem Algorithmus die Vorsortierung der $h$-Folgen ermöglicht:

The idea underlying Shellsort is that moving elements of A long distances at each swap in the early stages, then shorter distances later, may reduce this $O(n^2)$ bound. [📖Pra72, p. 3]

Es gilt also, die Vorsortierung auszuhebeln.
Für Insertion-Sort ist die Laufzeit im worst-case $O(n^2)$ (vgl. [📖OW17b, p. 87]). Da Shellsort mindestens im letzten Schritt diese Sortiermethode auf Distanzfolgen der Länge $1$ anwendet, muss der Algorithmus eine Folge als Eingabe erhalten, die durch die ersten $lg(n) - 1$-Durchgänge (mit $h_s = 2^{s - 1}, 1 \leq s < lg(n)$) keine Änderungen erfährt, um dann im allerletzten Schritt auf einen Schlag sortiert wird, was maximal $\frac{n}{2}$ Inversionen⁸ bedeutet, und damit ebenso viele Vertauschungen (zuzüglich der benötigten Verschiebe-Operationen).
Hierzu kann wie im vorherigen Beispiel für $n=16$ ein Feld mit folgender Schlüsselanordnung verwendet werden: Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index. Hier gilt für alle Elemente aus dem Feld $A$:

Abbildung 7 veranschaulicht die Anordnung.

^{Figure 7 Eine worst-case Schlüsselfolge für Shellsort. Felder mit geradem Index enthalten kleinere Schlüssel als Felder mit ungeradem Index.}

Markiert sind die direkt benachbarten Felder, die eine Inversion aufweisen, die im letzten Schritt des Algorithmus eine bzw. mehrere Verschiebungen bedingen.
In den vorherigen Schritten - also bei den Durchgängen mit Distanzfolgen $h_s > 1$ - findet der Algorithmus jeweils Schlüssel in korrekter Sortierreihenfolge vor.

Mit $h_4 = 8$ werden die Felder $A[0..7]$ mit den Feldern $A[8..15]$ verglichen - hier gilt in jedem Fall, dass die Schlüssel $A[i] < A[j] (\forall i < j, j - i = 8)$ sind.

Auch im darauffolgenden Durchgang ($h_3 = 4, j - i = 4$) finden keine Verschiebungen statt, da keine Inversion gefunden wird. Erst im letzten Schritt, in dem direkt benachbarte Elemente miteinander verglichen werden, werden die Inversionen ermittelt und die Verschiebung der Elemente findet statt (s. Abbildung 8.

^{Figure 8 Für die worst-case Schlüsselfolge werden im letzten Schritt 7 Inversionen festgestellt. Jede dieser Fehlstellung bedingt eine Verschiebung um die angegebene Anzahl von Positionen.}

In diesem Fall wird $c3$ insgesamt $32$ mal aufgerufen.

Da jeweils zwei Schlüssel bereits korrekt sortiert sind ($A[0]$ und $A[n-1]$) existieren noch $\frac{n}{2} - 1$ Inversionen. Jede Inversion erzwingt eine Verschiebung des größten Elements um $\frac{i}{2}$ Positionen nach links.

Für die Berechnung der Laufzeitkomplexität ergibt sich somit der Term

und unter Berücksichtigung der Terme für $c1$, $c2$, $c3$ die Funktion

was zu einer Laufzeitabschätzung von $O(n^2)$ führt.

Thema​

Für 2023 stand die Zulassungsarbeit zum Master-Fernstudiengang Informatik an der FH Trier unter dem Thema Funktionsprinzipien und Anwendung künstlicher Intelligenz (KI) in der Medizin.

Das Thema wurde Ende Mai 2023 bekannt gegeben, als Bearbeitungszeitraum wurde der 01.07. - 02.10.2023 vorgegeben.

Vorbereitung​

Zur Einarbeitung in das Thema hat mir Grundkurs Künstliche Intelligenz [📖Ert21] von Prof. Dr. Wolfgang Ertel (Hochschule Ravensburg-Weingarten) geholfen. Das Buch hat mich auf die (formalen) Grundlagen der Aussagenlogik und Prädikatenlogik vorbereitet sowie einführend maschinelles Lernen und Neuronale Netze erklärt, was mir die anschliessende Arbeit mit Russel & Norvig's [📖RN12] erleichterte. Das Standardwerk zum Thema Künstliche Intelligenz geht detailliert (in Teilen auch sehr formal) auf Agentenmodelle, Problemlösungen, Logik, Entscheiden und Lernen ein.

Da nicht nur Künstliche Intelligenz als Thema vorgeben gewesen ist, sondern auch Medizin, habe ich darüber hinaus [📖Pfa22] (quer)gelesen, um mir einen Überblick über die verschiedenen Anwendungsgebiete von KI im Gesundheitswesen zu verschaffen. Ergänzend dazu habe ich mit großem Interesse den Podcast Dr. med. KI von Prof. Dr. Kerstin Ritter (Charité Berlin) und Mike Bernd (Stifterverband für die Deutsche Wissenschaft e.V.) verfolgt, in dem Themen aus den Bereichen Medizin, Informatik und Ethik zusammengefasst und Hintergründe, Problematiken und Ausblicke in Zusammenhang mit KI diskutiert werden.

Eingrenzung des Themas und Ausarbeitung​

Im Juli des gleichen Jahres habe ich dann mit der Ausarbeitung begonnen, das Thema hatte ich - noch etwas unscharf - auf den Einsatz von KI bei bildgebenden Verfahren in der Medizin eingegrenzt. Da hier KI überwiegend in Form neuronaler Netze stattfindet, musste ich mich also noch in dieses Thema einarbeiten: Während die Vorbereitung im Juni also das Verständnis um Künstliche Intelligenz geschärft hatte, wurde mir schnell klar, dass das ein bloßes Kratzen an der Oberfläche gewesen ist. Um Modelle neuronaler Netze nachvollziehen zu können, musste ich zunächst das biologische Vorbild verstehen, was mich zu den Neurowissenschaften führte.

Die Literatur, die ich bis zu diesem Zeitpunkt durchgearbeitet habe, hatte meinem Empfinden nach die tierische Nervenzelle als Mittel zum Zweck gesehen: Signalweiterleitung und verrechnende Einheiten in einem neuronalen Netze wurde zwar als Abstraktion biochemischer Vorgänge im Gehirn verstanden, aber das Warum und Wie wurde wenig ausführlich erklärt.

Es war mir also ein großes Anliegen,die komplexen biochemischen Vorgänge im Nervensystem zu verstehen und als fachlichen Hintergrund der Arbeit voranzustellen, um die großen Erfolge, die der Einsatz Künstlicher Intelligenz in den letzten Jahren in der Medizin vorweisen konnte, dem Leser besser verständlich zu machen.

Folglich legte ich das Thema meiner Arbeit fest:

Eine Einführung in mathematische Modelle der biologischen Nervenzelle als Bausteine künstlicher neuronaler Netze und deren Anwendung im Gesundheitswesen.

Es sollte die Signalweiterleitung im biologischen Neuron erklären, erste, frühe Modelle künstlicher Neuronen vorstellen, den Bogen zu künstlichen neuronalen Netzen spannen und dann Anwendungsbeispiele aus dem Gesundheitswesen aufführen.

Abgabe und Bewertung​

Ich hatte damit begonnen, erste Entwürfe in Markdown zu schreiben, damit mir eine spätere Überführung der Arbeit in eine lesbare Form auf meine Webseite erleichtert wird. Die Hochschule stellt Word- und Latex-Vorlagen zur Verfügung - die ich im Anschluss für eine Portierung nutzen wollte.

Als ich mit dem ersten Entwurf meiner Arbeit - ca. Mitte September - fertig war, hatte ich nach Korrektur und meiner (bescheidenen) Zählweise nach gut und gerne 20 - 30 DIN A4 Seiten Text (ohne Illustrationen und Tabellen) - an der Stelle war mir aber schon klar, dass ich den ein oder anderen Abschnitt eher ausführlich als kompakt beschrieben habe, weshalb ich noch eine Woche Lektorat eingeplant hatte.

Nach der Überführung in Latex, die ca. eine Woche gedauert hat, zählte ich - unter Verwendung der Vorlage, die Trier zur Verfügung gestellt hat, ca. 80 Seiten - ohne Inhalts-, Literatur- und Abbildungsverzeichnis. Das Lektorat umfasste also nicht nur inhaltliche und formale Korrekturen, sondern teilweise auch das komplette Umschreiben des ein oder anderen Kapitels, weil viel Stoff in den Anhang wechseln musste: Vor allem Biografien von Persönlichkeiten, die sich in Forschung und Wissenschaft um das Thema verdient gemacht haben, sowie Begriffe und Ergänzungen rund um das Thema Neurobiologie.

Die korrigierte Fassung, die als Vorlage der finalen Abgabeversion diente, umfasste dann knapp 45 Seiten, mit ungefähr 50 Seiten Anhang.

Für die Abgabeversion wurde also noch einmal inhaltlich soweit gekürzt, dass die Intention einer "Einführung" weitestgehend erhalten blieb - mir war aber auch klar, dass eine Arbeit, die Neurobiologie, Neurowissenschaften, Informatik, Mathematik und Medizin unter dem Thema "Künstliche Intelligenz" auf 20 (Vorgabe Prüfungsausschuss) Seiten zusammenfasst, keine Einführung mehr sein kann. Die Abgabeversion wurde kurzum umbenannt in

Mathematische Modelle der biologischen Nervenzelle als Bausteine künstlicher neuronale Netze und deren Anwendung im Gesundheitswesen

und umfasst 30 Seiten, inkl. Tabellen und Illustrationen. Der Anhang ist komplett entfallen, Fußnoten, die in der Ursprungsversion zahlreich vorhanden sind und viele Ergänzungen bieten, rausgekürzt.

Die Abgabeversion entsprach somit den formalen Vorgaben, was sich auch in der Bewertung der Arbeit widerspiegelte.

Download​

Die Arbeit liegt in zwei Versionen vor: Eine ausführliche Ausarbeitung der wichtigen Themen, die einen einführenden Charakter besitzt, sowie die gekürzte Fassung, die den formalen Vorgaben entspricht.

In beide Versionen wurden bereits Anmerkungen und Korrekturen aus dem Errata übernommen. Glücklicherweise beschränkten sich diese weitestgehend auf wenige Fehler in der Orthographie und einen Fehler in der formalen Herleitung des McCulloch-Pitts-Netzes als Graph in Abschnitt 3.1.4 (ungekürzte Version, entfallen in der Abgabeversion).

• Download ungekürzte Version (pdf)
• Download gekürzte Abgabeversion (pdf)

I have updated my Perceptron-implementation with a plotting function that allows for visualizing the adjustments of the Perceptron's weight-vector through the epochs.

The source-code can be found at https://github.com/ThorstenSuckow/pylabs.

Usage​

Create input data and the associated output values. As an example, the following represents the logical AND-function:

import numpy as np
from Perceptron import Perceptron

# input
X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

# output
y = np.array([0, 0, 0, 1])

In the next step, the Perceptron is created.

p = Perceptron(50, 0.3)

Once a Perceptron-instance is available, you can pass the input- and output-values to learn():

p.learn(X, y)

and test data with

result = p.test([0, 0])

result holds the computed weight vector if the training data could be separated within the epochs. If that failed, None is returned.

Note: The bias is available with p.bias

A log is available for all steps processed by learn():

for step in p.log:
    print(step)

You can pass the log to the PerceptronPlotter which will recreate the computation visually.

Examples​

and​

The and-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"AND\""
y = np.array([0, 0, 0, 1])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

or​

The or-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"OR\""
y = np.array([0, 1, 1, 1])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

xor​

The xor-function with a Perceptron.

X = np.array([
    [0, 0], [0, 1], [1, 0], [1, 1]
])

title= "\"OR\""
y = np.array([0, 1, 1, 0])

p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)
anim = plotter.animate(500)

With the Perceptron as a linear discriminant function, the algorithm can not properly create a separator for XOR [📖MIN69]. The Plotter shows the Epoch-label marked as red, which tells that the algorithm was not able to find a separator in 50 epochs.

Cluster Example​

The following uses isotropic Gaussian blobs generated by sklearn.datasets.make_blobs. The animate-method is called with an interval of 100 to speed up epoch-runs. The interplay of a larger set of data and the re-adjusting of the separator if accuracy does not reach 1 for a full epoch can be observed nicely.

title = "Clusters"
X, y = make_blobs(n_samples=50, n_features=2, centers=2, cluster_std=2.5)


p = Perceptron(50)
p.learn(X, y)

plotter = PerceptronPlotter(p.log, X, y, title)

anim = plotter.animate(100)

Resources

• https://github.com/ThorstenSuckow/pylabs

Errata für Beweisen lernen (Springer Verlag 2020) von Junk und Treude. Ich hoffe, dass meine Notizen dem Autorenteam zur Überprüfung und ggf. Korrektur nützlich sind.

Zum Hintergrund dieses Blog-Posts gibt es weiter unten mehr Informationen.

Errata​

Vergleichslösungen​

Ideen: Metrische Räume​

Ideen: Äquivalenzklassen​

Training​

Rechtschreibung / Grammatik / Druckfehler​

Anmerkungen​

Hintergrund: Aufgabe 178 und das kleine Manöver, das kostete​

In der Lösung zu Aufgabe 178 aus Beweisen lernen - und der hierzu vorbereitenden Aufgabe 158 - bin ich bei der Nachbereitung des Lösungsvorschlages nicht zu dem gleichen Ergebnis gekommen - der Definitionsbereich einer Funktion wurde falsch angegeben. Den Versuch, die Falschaussage nachzuweisen, habe ich hier in diesem Post dokumentiert.

Weitere Notizen bzgl. eventueller Fehler hinsichtlich Logik- und Druck fasse ich in dem o.a. Errata zusammen.

Aufgabe 158​

Notation​

$U$: Elementuniversum

$\Epsilon_n$: Menge aller endlichen Mengen mit der Mächtigkeit $n$

$P(K)$: Potenzmenge von $K$ mit $K \subset U$

Aufgabenstellung​

Es ist per Induktion zu beweisen, das

$\forall n \in \N_0: \forall k \in (N_0)_{\le n}: \forall X \in D_k: | S_k(X)| = 1$

Folgendes steht mit den Voraussetzungen zur Verfügung:

$f: X \mapsto R$

$D_n:=\{X \in \Epsilon_n : X \subset Def(f) \}$

$S_0: D_0 \to P(\R),\space X \mapsto \{0\}$

$S_{n+1}: D_{n+1} \to P(\R),\space X \mapsto \{f(x) + s \space | \space (x, s) \in X \times S_{n}(X \setminus \{x\})\}$

Induktionsschritt​

Die Autoren wollen die Eindeutigkeit des Elementes $x \in U: x \in S_{n+1}(X)$ über

$\exists! x \in U: x \in S_{n+1}(X)$

zeigen. Hierzu muss die Existenz und die Eindeutigkeit des Elementes gezeigt werden, so dass wegen $\forall u,v \in S_{n+1}(X): u = v$ auch $|S_{n+1}(X)| = 1$ folgt (u.a. wegen Aufgabe 99 und Aufgabe 153).

Argumentation​

Hierzu sei

$u:= f(a)+s, v:= f(b)+t$

Die Autoren zeigen einige Schritte weiter, dass mit der Induktionsvoraussetzung für $s$ folgt:

Da $f(a) + s \in S_{n+1}(X)$, ist $s \in S_n(X \setminus \{a\})$.

Mit $b \in X \setminus \{a\}$ soll dann $s = f(b) + z$ gezeigt werden, wobei wieder die Induktionsvoraussetzung angewendet wird und $z \in S_{n-1}(X \setminus \{a\} \setminus \{b\})$ gefunden wird.

Fehlerstelle​

In einem weiteren Schritt wird dann behauptet, dass $f(b) + z \in S_{n-1}(X \setminus\{a\})$ ist, und deswegen $f(b)+z \in \{s\}$ und folglich $f(b) + z = s$. Das scheint der Fehler zu sein, denn für $s$ wurde gezeigt: $s \in S_n(X \setminus \{a\})$:

Wenn $s \in S_n(X \setminus \{a\})$ und $s \in S_{n-1}(X \setminus\{a\})$ gelten würde, dann würde für

$f(c)+s \in S_n(X \setminus \{a\})$ und $f(b)+t \in S_{n-1}(X \setminus \{a\})$ auch $f(c)+s = f(b)+t$ gelten (für $c, b \in X \setminus \{a\}$).

Da $s = f(b) + t$ wegen $f(b) + t \in S_{n-1}(X \setminus \{a\})$ und $s \in S_{n-1}(X \setminus\{a\})$ folgt dann auch $f(c) + s = s$, was im Widerspruch zu $f(c) + s = f(c) + s$ steht und offensichtlich nicht $\forall c \in X \setminus \{a\}$ gilt.

Verfällt ein Big Ball of Mud?​

Durch den Fortschritt der Technologie und der Arbeit von Leuten wie Brooks, Buschmann und Booch wurde uns Entwicklern der Weg vom mikroskopischen ins makroskopische geebnet. Lang vorbei sind die Zeiten, in denen schrankhohe Rechnersysteme nah an der Infrastruktur programmiert werden mußten.
Jedoch, wer heute den Mythischen Mann-Monat [📖MMM] liest und über die damals zur Verfügung stehende Technik schmunzelt, der wird spätestens bei der Aktualität der anderen erwähnten Probleme betreffs Organisation und Planung von Projekten rasch in die Gegenwart zurückgeworfen. Aus Eskapismus wird ein erhobener Finger: Das Lesevergnügen mahnt plötzlich zur Reflektion. Die Probleme von damals sind heute immer noch aktuell, und die Entwicklung der Technik verlief bis dato offensichtlich ungleich schneller als die von Planung und Organisation.

Die Motivation und das Wissen darum, wie man heutzutage Schablonen für die Erstellung von Objekten und Klassen nutzt und all seine Erfahrung in das Schneiden und Zusammenstecken derselben zur Abstraktion einer Fachlichkeit einfliessen lässt, ist dann nicht zuletzt auch der Gang of Four [📖Gof] zu verdanken, die Entwurfsmuster en vogue gemacht haben und in einer ganzen Generation von Programmierern das Interesse an Software Design zu wecken wussten. Aber: Der Schreiner mag in der Lage sein, einen Satz Fensterrahmen passend zu dem äusseren Erscheinungsbild des Hauses zu zimmern. Das hübscheste Fenster hilft aber nichts, wenn niemand weiss wie man es einbaut, geschweige denn öffnet und wieder schliesst.

Wir machen den gedanklichen Sprung zurück in unsere Domäne und wissen: Solche Elemente werden dann in Menge problematisch, wenn ihre Vereinigung in einem System funktional sein und natürlich ein möglichst wartbares Gesamtgebilde ergeben soll. Auch hier helfen Erfahrung und bewährte Blaupausen, damit sich Entwickler*in nicht in einem undurchdringlichen Dickicht von Verantwortlichkeiten und Assoziationen verliert.
Leider gelingt das nicht ganz so oft so gut. Wenn wir nach einem frischen Pull über das Sein des Spaghetti-Codes eines Kollegen sinnieren, oder wir uns selbst dabei ertappen, Schichten durch das freitag-mittagliche Voranstellen eines new vor einer low-level-Klasse in einer high-level-Klasse zu durchbrechen, dann ist man ihm schon einen Schritt näher, dem berüchtigten Big Ball of Mud (BBOM), den Eberhard Wolff in der Folge 159 seiner Reihe Softwarearchitektur im Stream mit gewohnter Präzision vorgestellt und in Ursache und Wirkung analysiert hat.

In der Folge beruft er sich auf das Paper von Foote und Yoder, in dem - vor über 20 Jahren - die Frage gestellt wurde, inwieweit denn so ein Big Ball of Mud überhaupt ein Anti-Pattern sei: Das man diese quellcodegewordene Negation einer Struktur so häufig in Systemen vorfindet sollte doch eigentlich den Schluss zulassen, dass es sich hierbei gar nicht um ein Anti-Pattern, sondern gegebenenfalls um ein erprobtes und bewährtes Konzept in der Software-Entwicklung handelt, nämlich das des geringsten Widerstandes. Dieser kennzeichnet sich hier durch die Vermeidung von Up-Front Architektur. Stattdessen richtet sich der Fokus direkt auf die Umsetzung von Features und Funktionalität, auch, aber nicht ausschließlich, wenn Architektur als zu vermeidender Kostenfaktor verstanden wird:

"Therefore, focus first on features and functionality, then focus on architecture and performance." ^[1]

Man könnte daraus schließen, man solle mehr Verständnis für den Entwickler zeigen, der diesen Weg wählt oder wählen muß. Auch, wenn infolgedessen der Ansatz eines durch die Zuarbeit verschiedener Teams entstehenden Software-Fundamentes über das Fehlen von allgemein als geschäftswertig erachteter Best Practices mit jedem Commit ein bisschen mehr verhindert oder aufgelöst wird. Die Frage hat wohl auch Foote und Yoder beschäftigt:

"[…] we seek not to cast blame upon those who must wallow in these mires. In part, our attitude is to ‘hate the sin, but love the sinner‘". ^[1]

Wenn der Big Ball of Mud als Konsequenz dieses Konzeptes als Struktur eines Systems erkannt wird, das keine Struktur beinhaltet, dann können wir ex falso quodlibet auch jede beliebige Aussage als gültig annehmen, wenn wir uns bei der Beschreibung dieses Systems darauf berufen, dass diesem System eben eine Struktur innewohnt: Und also ist ein Big Ball of Mud eben ein Entwurfsmuster. Aber! So ein Gebilde bekommt man ganz gut beliebig hin, so wie ein Zimmermann sicher auch ohne Kenntnis darüber, wie man Mörtel anrührt, irgendwie in der Lage sein wird, Ziegelsteine um seine Fenster herum zu stapeln.

Unter gewissen Umständen kann das bewusste Zulassen zunehmender Entropie in einem Software System dabei helfen, Kontexte zu identifizieren und die Fachlichkeit zu verstehen, um Schichten herauszumeisseln und Grenzen zu schneiden. Evans, Fowler und auch Foote und Yoder sind sich in jedem Fall einer Sache sicher: Refactoring muss ständig erfolgen, um nicht die Kontrolle zu verlieren.

"The way to arrest entropy in software is to refactor it." ^[1]

Dabei ist man sich aber auch des zweiten Hauptsatzes der Thermodynamik bewusst: Die Entropie kann nicht abnehmen, sie kann gleich bleiben, oder sie kann zunehmen. Will man letzteres verhindern, rät Evans dazu, den BBOM zu demarkieren:

"Draw a boundary around the entire mess and designate it a big ball of mud. Do not try to apply sophisticated modeling within this context. Be alert to the tendency for such systems to sprawl into other contexts." [📖DDDR, p. 38]

Foote und Yoder haben eine ähnliche Empfehlung, die sie in dem Paper etwas schwungvoller mit "Sweeping it under the rug" bezeichnen:

"Therefore, if you can’t easily make a mess go away, at least cordon it off. This restricts the disorder to a fixed area, keeps it out of sight, and can set the stage for additional refactoring." ^[1]

Egal ob Grenzen gezogen werden oder man den BBOM unter den Teppich schaufelt: Eben so kommen wir über grobgranulare Schnittstellen an ausgewählte Funktionalität, und wir lassen gleichzeitig nicht zu, dass die zähe Masse aus dem BBOM in unser System tropft und dort Gestalt annimmt (oder eben auch nicht). Konsequent katalogisiert Robert C. Martin dann auch Viscosity in die Kategorie Design Smell ein [📖ASD, p. 88].

Mein Kommentar während der Folge lautete, dass es in Anbetracht all dessen ohnehin erschwerend hinzukommen kann, dem Management die Sinnhaftigkeit von Tests zu vermitteln. Der Antwort von Eberhard Wolff darauf entnahmen ich, dass in den von ihm beschriebenen Szenarien Tests a priori als sinnvoll verstanden werden und damit Teil der Entwicklung sind (zumindest aber Tests durch entsprechende Fachkräfte): Umso wichtiger sind diese Tests, wenn sich schon zu Beginn des Projektes zeigt, dass wegen fehlender Architekturplanung und wahrscheinlich diffuser Funktions- und Modulgrenzen Funktionalität sichergestellt werden muss.

Von dieser Implikation bin ich in meinem Kommentar nicht ausgegangen. Was ich meinte, war: Wenn Architektur keinen Geschäftswert hat, und dies zu einem BBOM führt, dann kann das auch zu dem Broken Window Effekt führen. Hunt und Thomas raten dazu: "Dont live with broken Windows." [📖PP, p. 7], und Foote und Yoder beziehen aus ähnlichen Erfahrungen die Ensicht:

"If such sprawl continues unabated, the structure of the system can become so badly compromised that it must be abandoned. As with a decaying neighborhood, a downward spiral ensues." ^[1]

Wenn Geld und Zeit in einem Projekt knapp sind, und Architektur damit einhergehend als nicht zielführend verstanden wird, dann ist die Wahrscheinlichkeit eher nicht gering, dass auch das Testing der Software – ich meine hiermit die Art von Tests, die der Entwickler selber schreibt, um sein System zu verifizieren - ebenfalls als negativer Kostenfaktor geführt wird. Sollte das Gegenteil der Fall sein, dann könnte die fehlende Architektur und der entstehende BBOM das eingeworfene Fenster in der Nachbarschaft sein, das dazu führt, dass noch mehr Fenster eingeworfen werden. Der Entwickler, der sich bewusst nicht innerhalb der Schichten bewegt, sondern vor allem dazwischen, sieht sich dazu veranlasst, seinen Code nicht durch Tests zu dokumentieren, weil er dem System die Sinnhaftigkeit ob der fehlenden Struktur aberkennt. Die Projektbeteiligten akzeptieren ein eingeworfenes Fenster wahrscheinlich eher, wenn daneben schon eins existiert.

Wenn alle Projektbeteiligten sich darauf verständigen, dass Grenzen und Fachlichkeiten auch durch unstrukturiertes, organisches Wachstum erkannt werden können, und das System erst später "ent-steht", können Strukturen also später nachgezogen werden: Letztendlich ist eine zähe Masse etwas Formbaren ähnlich, und die Dynamik unserer Handwerkskunst steckt in dem Namen Software. Besteht das Fundament möglichst nicht aus einem Throw Away, dann sollte auch allen Projektbeteiligten die Notwendigkeit von Tests klar sein: Die Räson aller Verantwortlichen verhindern somit ein erstes eingeworfenes Fenster, und es ist an Fachexperten und Programmierern, dass es nicht zu weiteren kommt.

References

• ^[1] Foote, Yoder: "Big Ball of Mud"; University of Illinois, 1999
• Eberhard Wolff: "Software-Architektur im Stream, Folge 159: Big Ball of Mud"

While the pioneers of computer science had to program computer systems close to the infrastructure, as technology progressed and thanks to the tireless work of people like Brooks, Buschmann and Booch, we found the way from the microscopic to the macroscopic.
However, if you read the Mythical Man Month [📖MMM] today and smile about the technology that was available at the time, you will quickly be thrown back to our present time, where problems regarding the organization and planning of projects persist. A raised finger suddenly calls for reflection: The problems of that time are still relevant today. Obviously, the development of technology has been much faster than that of planning, organization and realization of projects.

The motivation and knowledge of how to use templates to create objects and classes, and how to use all of our experience for cutting and assembling them into abstractions of a technicality, has gained momentum since the Gang of Four [📖Gof] sparked an interest in software design in a generation of programmers. But although the carpenter may be able to carve a set of window frames to match the exterior of the house, the prettiest window is of no use if nobody knows how to install it, let alone open and close it.

In our domain, such elements become problematic when their combination is supposed to be functional, and if it should resemble a maintainable structure as a whole. Experience and proven blueprints help to ensure that developers do not lose themselves in a jungle of tangled responsibilities and associations when integrating such elements.

Unfortunately, that doesn't always work out so well. When we catch ourselves breaking layers by adding a new in front of a lower-level class in a high-level class, we are one step closer to the notorious Big Ball of Mud (BBOM), which Eberhard Wolff presented and analyzed in episode 159 of his series "Software Architecture im Stream" with his usual precision.

In this episode, he also refers to the paper of Foote and Yoder, in which - more than 20 years ago - the question was asked to what extent such a Big Ball of Mud is an anti-pattern: That this negation of a structure is so often found in systems should actually lead to the conclusion that this is not an anti-pattern at all, but rather a tried and tested concept in software development, namely that of least resistance. This is characterized here by the avoidance of up-front architecture. Instead, the focus is directly on the implementation of features and functionality, also, but not exclusively, if architecture is understood as a cost factor to be avoided:

"Therefore, focus first on features and functionality, then focus on architecture and performance." ^[1]

A conclusion could be that we should show more understanding for the developer who chooses or must choose to develop like this. Even if such an approach prevents or dissolves a solid fundament for a software system due to the lack of best practices that are generally considered to be valuable for business. Foote and Yoder were probably also concerned with the question:

"[…] we seek not to cast blame upon those who must wallow in these mires. In part, our attitude is to ‘hate the sin, but love the sinner‘". ^[1]

If the Big Ball of Mud is ultimately itself a structure that contains no structure, similar to how the empty set is itself a set, then we can ex falso quodlibet accept any statement as valid if we assume that such a system has an inherent structure: And so a Big Ball of Mud is a design pattern.

But! A structure like this can be done quite easily with no experience, just as a carpenter will probably be able to stack bricks around his window without any knowledge of how to mix mortar.

Under certain circumstances, however, consciously allowing entropy to take over in a software system can also help to identify contexts and understand the technicalities in order to carve out layers and cut boundaries. In any case, Evans, Fowler and also Foote and Yoder are sure of one thing: refactoring must be done constantly in order not to lose control.

"The way to arrest entropy in software is to refactor it." ^[1]

However, one is also aware of the second law of thermodynamics: entropy cannot decrease, it can remain the same, or it can increase. If you want to prevent the latter, Evans advises to create a boundary around the BBOM:

"Draw a boundary around the entire mess and designate it a big ball of mud. Do not try to apply sophisticated modeling within this context. Be alert to the tendency for such systems to sprawl into other contexts." [📖DDDR, p. 38]

Foote and Yoder have a similar recommendation, which they more eloquently call "Sweeping it under the rug" in their paper:

"Therefore, if you can’t easily make a mess go away, at least cordon it off. This restricts the disorder to a fixed area, keeps it out of sight, and can set the stage for additional refactoring." ^[1]

It doesn't matter whether the BBOM is shoveled under the carpet or safe boundaries are created: It allows us to get selected functionality via coarse-grained interfaces out of the BBOM, and at the same time we don't allow the viscous mass to drip into our system.

Consequently, Robert C. Martin also cataloged Viscosity in the category Design Smell [📖ASD, p. 88].

My comment during the episode was that, given all of this, communicating the value of testing to management can be an added complication. I gathered from Eberhard Wolff's answer that in the scenarios he described, tests are understood to be useful a priori and are therefore part of the development process: It is mandatory to verify functionality due to the lack of architectural planning, resulting in diffuse modular boundaries.

I did not assume this implication in my comment. What I meant was: If architecture is seen as a cost factor or other conditions prevail that prevent architecture, and thus leads to a BBOM, then this can also lead to the Broken Window Effect. Hunt and Thomas have already advised: "Don't live with broken Windows." [📖PP, p. 7], and Foote and Yoder conclude from similar experiences:

"If such sprawl continues unabated, the structure of the system can become so badly compromised that it must be abandoned. As with a decaying neighborhood, a downward spiral ensues." ^[1]

If money and time are tight in a project and the architecture is not understood to be of value, then there is a probability that testing the software - I understand this as the kind of tests that the developer writes for verifying his code - is also seen as a negative cost factor. If the opposite is true, then the missing architecture and the resulting BBOM could be the broken window in the neighborhood, causing even more windows to be smashed. The developer who consciously does not move within the layers, but in between, feels compelled not to document his code through tests because he may fail to see any value of his work in the end. Those involved in the project are more likely to accept a broken window if there is already one next to it.

If everyone involved in the project agrees that limits and technicalities can also be recognized through unstructured, organic growth, and the system only emerges later, structures can added later: Ultimately, mud is a mass that is malleable, and the dynamic of our craftsmanship is in the name software. If the foundation does not consist of a Throw Away, then all those involved in the project should be aware that testing is required: the rationale of all those responsible prevents the first window being thrown in, and it is up to the technical experts and programmers to ensure that there won't ever be any.

References

• ^[1] Foote, Yoder: "Big Ball of Mud"; University of Illinois, 1999
• Eberhard Wolff: "Software-Architektur im Stream, Folge 159: Big Ball of Mud"

bcc-header issues with Horde_Mime_Mail​

This issue caused some uncertainty since I was not sure if the headers were broken due to missing quotes. See https://github.com/conjoon/php-lib-conjoon/issues/17.

Turns out that the way I assembled an email from a full text and converting it back to an instance of Horde_Mime_Mail does not consider the type of the internal representation of the bcc-field properly. It's related to Horde_Mail_Rfc822_List::_normalize and how values passed from Horde_Mime_Mail::send() are processed by it.

Here's a code snippet that shows how I use a full text message as input, then converting it back to an instance of Horde_Mime_Mail with headers processed by Horde_Mime_Headers::parseHeaders(). The original message has a bcc header-field:

(Original code can be found here).

         $target = $item->getFullMsg(false);
         // ... 
         $headers = Horde_Mime_Headers::parseHeaders($target);

         $mail = new Horde_Mime_Mail($headers);
         $part = Horde_Mime_Part::parseMessage($target);
         $mail->setBasePart($part);

         $mailer = $this->getMailer($account);
         $mail->send($mailer);   

Horde_Mime_Mail temporarily removes the bcc header and stores it in a property named _bcc, then uses this value to add it to the recipients' addresses later on in send(). This is so the bcc-header is not appearing in the source of the message the recipients receive (see https://www.ietf.org/rfc/rfc2822.txt, Section 3.6.3 and 5):

"The "Bcc:" field (where the "Bcc" means "Blind Carbon Copy") contains addresses of recipients of the message whose addresses are not to be revealed to other recipients of the message." https://www.ietf.org/rfc/rfc2822.txt, Section 3.6.3

This is a part of Horde_mime_Mail::send():

        /* Build recipients. */
        $recipients = clone $this->_recipients;
        foreach (array('to', 'cc') as $header) {
            if ($h = $this->_headers[$header]) {
                $recipients->add($h->getAddressList());
            }
        }
        if ($this->_bcc) {
            $recipients->add($this->_bcc);
        }

The source above shows that for to / cc the method getAddressList() is being called, while the value of _bcc gets passed to the add() method. However, _bcc holds in this case an instance of Horde_Mime_Headers_Addresses, which Horde_Mail_Rfc822_List::_normalize() does not consider. The value is ultimately ignored, Emails are not being sent to the addresses mentioned in the bcc header.

Here's the implementation of normalize():

    protected function _normalize($obs)
    {
        $add = array();

        if (!($obs instanceof Horde_Mail_Rfc822_List) &&
            !is_array($obs)) {
            $obs = array($obs);
        }

        foreach ($obs as $val) {
            if (is_string($val)) {
                $rfc822 = new Horde_Mail_Rfc822();
                $val = $rfc822->parseAddressList($val);
            }

            if ($val instanceof Horde_Mail_Rfc822_List) {
                $val->setIteratorFilter(self::BASE_ELEMENTS);
                foreach ($val as $val2) {
                    $add[] = $val2;
                }
            } elseif ($val instanceof Horde_Mail_Rfc822_Object) {
                $add[] = $val;
            }
        }

        return $add;
    }