Skip to main content

· 14 min read

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=log2(n)t = log_2(n) Inkremente1 hth_t2 der Form n2i\lfloor {\frac{n}{2^i}} \rfloor verwendet, um lg(n)lg(n) hh-sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in h1h_1 die Schlüssel mit Abstand=11.

Die Effizienz des Sortierverfahrens ist stark abhängig von hh: So zeigt Knuth, dass O(n32)O(n^{\frac{3}{2}}) gilt, wenn für hh gilt: hs=2s+11h_s = 2^{s+1} - 1 mit 0s<t=lg(n)0 \leq s < t = \lfloor{lg(n)} \rfloor (vgl. [📖Knu97c, p. 91]3. In unserem Fall können wir von O(n2)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)O(n\ lg\ n) und O(n2)O(n^2),

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

Listing 1: Zur Protokollierung der Aufrufe können in dem Code Zählvariablen eingesetzt werden (c1, ... ,c4).
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 c3c3 können randomisierte Felder erzeugt werden, wie es der Test-Code in Listing 2 demonstriert. Dann wird überprüft, in welchen Bereichen sich c3c3 bewegt. Da jeder auf Vergleichsoperationen basierende Sortieralgorithmus zu der Laufzeitklasse Ω(n log n)\Omega(n\ log\ n) gehört, kann im Mittel c3n log nc3 \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 Ω(N log N)\Omega(N\ log\ N) Schlüsselvergleiche.

[📖OW17b, p. 154]

Allerdings wird n1.3n^{1.3} ab n=982n=982 schneller wachsen als n log nn\ 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 nn\ log\ n beträgt.

Listing 2: Code zum Erzeugen randomisierter Felder zum Testen von Shellsort.
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));
}
}
info

Mit einem Wert von 100100 für die Epochen und einer Feldgröße von 2.000.0002.000.000 liefert der Test in Listing 2 folgende Ausgabe:

nlgn<n1.3<x<n2:74nlgn < n^{1.3} < x < n^2: 74
nlgn<x<n1.3:26nlgn < x < n^{1.3}: 26

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

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

  • n log nc3n1.3n\ log\ n \leq c3 \leq n^{1.3}

  • n log nn1.3c3n2n\ log\ n \leq n^{1.3} \leq c3 \leq n^2

Die Ausführung des Tests zeigt, dass die Aufrufanzahl von c3c3 bei großen nn unterhalb n1.3n^{1.3} oder zwischen n1.3n^{1.3} und n2n^2 liegt:

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

Laufzeitanalyse

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

ht=n2,ht1=n4,,h1=1h_t = \frac{n}{2}, h_{t-1} = \frac{n}{4}, \dots, h_1 = 1

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

Listing 3: Implementierung des Shellsort-Algorithmus.
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 c1c1 in Zeile 8, c2c2 in Zeile 12 und c3c3 in Zeile 19.

Für eine erste worst-case-Analyse ist ein Feld der Länge 1616 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)lg(n)-mal aufgerufen wird5. 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 c1c1 der aktuelle Wert von delta 6, und läuft jeweils bis n1n - 1.

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

(n1)delta+1=ndelta(n - 1) - delta + 1 = n - delta

info

Hinweis: Für das Beispiel betrachten wir der Einfachheit halber Feldlängen der Form 2p2^p. Für den allgemeinen Fall gilt für die Anzahl der Aufrufe von c2c2:

i=1lg(n)nn2i=nlg(n)i=1lg(n)n2i\sum_{i=1}^{\lfloor lg(n) \rfloor} n - \lfloor \frac{n}{2^i} \rfloor = n * lg(n) - \sum_{i=1}^{\lfloor lg(n) \rfloor} \lfloor \frac{n}{2^i} \rfloor

Für die Gesamtzahl der Aufrufe von c2c2 ergibt sich somit unter Berücksichtigung von c1c1

i=1lg(n)nn2i1\sum_{i=1}^{lg(n)} n - \frac{n}{2^{i-1}}

was nach Auflösen

nlg(n)n+1n * lg(n) - n + 1

entspricht, und für unser Beispiel

16lg(16)16+1=4916 * lg(16) - 16 + 1 = 49

ist.

info

Die Aufrufzahlen für c2c2 für verschiedene nn. Schlüsselvergleiche finden erst später statt. Mit n>2156n > 2156 wächst O(n43)O(n^\frac{4}{3}) schneller als c2c2 und mit n>=982n >= 982 schneller als O(n log n)O(n\ log\ n).

nc2O(n1.1)O(n^{1.1})O(n1.3)O(n^{1.3})O(n log n)O(n\ log\ n)O(n2)O(n^2)
8179142464
1649213664256
3212945901601024
64321972223844096
12876920754889616.384
25617934451351204865.536
1024921720488192102401.048.576
215621.5654.645,2921.564,6923.875,844.648.336
215721.5764.647,6621.577,7023.888,364.652.649
215821.5864.650,0321.590,7023.900,884.656.964
..................
10.000120.00525.118158.489132.8771.0E8
100.0001.500.006316.2273.162.2771.660.9641.0E10
200.0003.200.006677.8497.786.4403.521.9284.0E10
500.0008.500.0071.857.2352.56..E79.465.7842.5E11
1.000.00018.000.0073.981.0716.30..E71.99..E71.0E12

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

Ist das nicht der Fall, werden die Elemente an den Stellen jj und jdeltaj - delta ausgetauscht, bis die hh-Folge sortiert ist.
Für den ersten Durchgang des Algorithmus an dieser Stelle mit h4=8h_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 h4 = 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 hh: Es sind danach jeweils Schlüssel mit den Abständen 44 (Abbildung 4 und 22 (Abbildung 5) sortiert; im letzten Schritt dann vollständig (Abbildung 6):

Figure 4 Die Sortierung für h3 = 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 c3c3 stellt man fest, das in diesem Fall in jedem Schritt immer 2 Elemente, die eine Distanz von hsh_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 nn ergibt, nämlich n2\frac{n}{2}. Insgesamt finden dadurch für c3c3

lg(n)n2lg(n) * \frac{n}{2}

Aufrufe statt.

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

lg(n)+nlg(n)n+1+lg(n)n2lg(n) + n * lg(n) - n + 1 + lg(n) * \frac{n}{2}

und zusammengefasst

f(n)=32nlg(n)+lg(n)n+1f(n) = \frac{3}{2} * n * lg(n) + lg(n) - n + 1

was nach Einsetzen zu

lg(16)+16lg(16)16+1+lg(16)162=85lg(16) + 16 * lg(16) - 16 + 1 + lg(16) * \frac{16}{2} = 85

Aufrufen für unser Beispiel führt.

Nachweis der Komplexitätsklasse

Um OO zu ermitteln, werden nun alle Konstanten der Funktion

f(n)=32nlg(n)+lg(n)n+1f(n) = \frac{3}{2} * n * lg(n) + lg(n) - n + 1

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

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

fO(n log n):n0N,cR,c>0:nn0:f(n)cnlg(n)f \in O(n\ log\ n): \leftrightarrow \exists n_0 \in \mathbb{N}, c \in \mathbb{R}, c > 0: \forall n \geq n_0: f(n) \leq c * n*lg(n)

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

Zu zeigen ist

32nlg(n)+lg(n)n+1cnlg(n)\frac{3}{2} * n * lg(n) + lg(n) - n + 1 \leq c * n * lg(n)

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

nn0:32nlg(n)32nlg(n)\forall n \geq n_0: \frac{3}{2} * n * lg(n) \leq \frac{3}{2} * n * lg(n).

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

Insgesamt gilt also

n0=1,c=32:nn0:32nlg(n)+lg(n)n+1cnlg(n)n_0 = 1, c = \frac{3}{2}: \forall n \geq n_0: \frac{3}{2} * n * lg(n) + lg(n) - n + 1 \leq c * n * lg(n)

womit f=O(nlog(n))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(n2)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)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 hh-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(n2)O(n^2) bound. [📖Pra72, p. 3]

Es gilt also, die Vorsortierung auszuhebeln.
Für Insertion-Sort ist die Laufzeit im worst-case O(n2)O(n^2) (vgl. [📖OW17b, p. 87]). Da Shellsort mindestens im letzten Schritt diese Sortiermethode auf Distanzfolgen der Länge 11 anwendet, muss der Algorithmus eine Folge als Eingabe erhalten, die durch die ersten lg(n)1lg(n) - 1-Durchgänge (mit hs=2s1,1s<lg(n)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 n2\frac{n}{2} Inversionen8 bedeutet, und damit ebenso viele Vertauschungen (zuzüglich der benötigten Verschiebe-Operationen).
Hierzu kann wie im vorherigen Beispiel für n=16n=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 AA:

i,jN[0,n1],2i,2j:A[i]<A[j]A[i]<A[i+1]A[j]<A[j+1]\forall i, j \in \mathbb{N}_{[0, n - 1]}, 2 \mid i, 2 \nmid j: A[i] < A[j] \land A[i] < A[i + 1] \land A[j] < A[j +1]

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 hs>1h_s > 1 - findet der Algorithmus jeweils Schlüssel in korrekter Sortierreihenfolge vor.

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

Auch im darauffolgenden Durchgang (h3=4,ji=4h_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 c3c3 insgesamt 3232 mal aufgerufen.

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

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

i=1n21i=n2(n21)2=n22n8\sum_{i=1}^{\frac{n}{2} - 1} i = \frac{\frac{n}{2}(\frac{n}{2} - 1)}{2} = \frac{n^2 - 2n}{8}

und unter Berücksichtigung der Terme für c1c1, c2c2, c3c3 die Funktion

f(n)=lg(n)+nlg(n)n+1+n22n8f(n) = lg(n) + n * lg(n) - n + 1 + \frac{n^2 - 2n}{8}

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


  1. mit n=n = Länge des zu sortierenden Feldes. Im folgenden lglg für log2log_2.
  2. vgl. [📖Knu97c, p. 84]
  3. Knuth bezieht sich hier auf die Arbeit von Papernov und Stasevich ([📖PS65]). Weitere Verweise auf Laufzeiten in Abhängigkeit von nn und hh fasst übersichtlich der Wikipedia-Artikel zusammen: https://en.wikipedia.org/wiki/Shellsort (abgerufen 23.01.2024).
  4. Shell führt in seinem Paper keinen Beweis auf. Er stützt seine Behauptung auf Messungen, die er selber in Tests durchgeführt hat: "[...] an analytical determination of the expected speed has eluded the writer. However, experimental use has established its speed characteristics." (ebenda)
  5. hier wie im folgenden ohne Betrachtung der Schleifenbedingung, die an dieser Stelle insgesamt lg(n)+1lg(n) + 1-mal aufgerufen wird
  6. 8,4,2,1{8, 4, 2, 1} für das gegebene Beispiel
  7. mit O(log n)O(log\ n) bzw O(n log n)O(n\ log\ n) nehmen wir für die OO-Notation wieder die in der Fachliteratur gebräuchlichere Schreibweise auf. Sowohl Güting und Dieker als auch Ottmann und Widmayer weisen in [📖GD18a, p. 15] bzw. [📖OW17a, p. 5] darauf hin, dass die Angabe der Basis keine Rolle spielt, da sich Logarithmen mit verschiedenen Basen ohnehin nur durch einen konstanten Faktor unterscheiden (es gilt loga(x)=logb(x)logb(a)log_a(x) = \frac{log_b(x)}{log_b(a)}).
  8. in diesem Zusammenhang bedeutet Inversion: Fehlstellung (vgl. [📖OW17b, p. 87])

· One min read

Für das Modul prog1 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.

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.


  1. Modulbegleitende Diskussions- und Lerngruppen sind auch auf unserem Discord-Server zu finden.

· 6 min read

info

Man darf behaupten, dass im Jahr 2023 das Thema Künstliche Intelligenz endgültig in der Gesellschaft angekommen ist. Mit der Veröffentlichung von ChatGPT Ende 2022 ist "KI" plötzlich für jeden begreifbar. Einmal mehr rutschen defätistische Prophezeiungen auf die Titelseiten der Boulevard-Presse.

Als Software Entwickler mit Schwerpunkt Design und Architektur hatte ich Künstliche Intelligenz bis dahin weitestgehend in den akademischen Bereich verortet.

Dann hatte ich das Glück, mich ausgiebig mit Künstlicher Intelligenz im Rahmen meiner Zulassungsarbeit für den Fernstudiengang Informatik (M.C.Sc.) an der FH Trier beschäftigen zu dürfen.

Entstanden ist eine Arbeit, in dem ich mathematische Modelle künstlicher Neuronen vorstelle. Auf dem Weg dorthin bin ich in die frühen Anfänge der Neurowissenschaft, der Kybernetik und Rechnerarchitektur eingetaucht. Es hat meine Sichtweise auf vieles, was mir bis dahin (un)verständlich gewesen ist, geändert.

Für meine Kommilitonen, die die Eignungsprüfung noch vor sich haben, habe ich in diesem Post meine Erfahrungen zum Thema Wissenschaftliches Arbeiten zusammengefaßt.

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).

· 3 min read

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.

AABBABA \land B
111
100
010
000
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.

AABBABA \lor B
111
101
011
000
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.

AABBABA \oplus B
110
101
011
000
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

· 9 min read

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

info

Stand 21.06.2023. Meine gesammelten Notizen habe ich komplett überführt. Das Kapitel "D Tipps zu den Übungen" wurde von mir nicht bearbeitet.

Lieber Google-Nutzer, das offizielle Errata findet sich unter https://www.math.uni-konstanz.de/mmath/de/book/material/errata (abgerufen 21.06.2023).

Vergleichslösungen

SeiteFehlerstelleKorrekturvorschlagBemerkung
326 (ML261)0=distd(x,A)infDx,A0 = dist_d(x, A)inf D_{x,A}0=distd(x,A)=infDx,A0 = dist_d(x, A) = inf D_{x,A}
"a<infDx,A+ϵa < inf D_{x,A} + \epsilonu<infDx,A+ϵu < inf D_{x,A} + \epsilon
321 (ML240)und bMin(b)b \in Min(b) gegebenund bMin(B)b \in Min(B) gegeben
318 (ML230)Zu zeigen ist DR:y,zA:d(x,y)D\exists D \in \R: \forall y,z \in A : d(x,y) \le DZu zeigen ist DR:y,zA:d(y,z)D\exists D \in \R: \forall y,z \in A : d(y, z) \le DIn der ML wird weiter d(x,y)d(x,y) genutzt, obwohl sich der Allquantor auf y,zy,z bezieht. Das wäre im Weiteren zu überprüfen, da wir mit der Def. von Brd(x)B_r^d(x) auch d(x,y)<rd(x, y) < r verstehen.
316 (ML226)Wir definieren g:NNR,g: \N_{\le N} \rarr \R,...Wir definieren g:NnR,g: \N_{\le n} \rarr \R,...
315 (ML224)d2(ru,s)=d_2(r \cdot u, s \cdot) =...d2(ru,su)=d_2(r \cdot u, s \cdot u) =...
312 (ML214)Ly={α3β,3α+2β,0)/11+t(0,2,1)tR}L_y = \{\alpha - 3\beta, 3\alpha + 2\beta, 0)/11 + t \cdot (0,2,1)\vert t \in \R\}Ly={3α+2β,α3β,0)/11+t(0,2,1)tR}L_y = \{3\alpha + 2\beta, \alpha - 3\beta, 0)/11 + t \cdot (0,2,1)\vert t \in \R\}u,vu, v vertauscht
308 (ML194, Ende)Da r[u]~r \in [u]_\text{\textasciitilde} auf uXu \in X und u~xu \text{\textasciitilde} x...Da r[u]~r \in [u]_\text{\textasciitilde} auf uXu \in X und u~ru \text{\textasciitilde} r...
302 (ML178 unten)p(f(b),z)Pf,n1(X{a})p(f(b), z) \in P_{f, n-1}(X \setminus \{a\})p(f(b),z)Pf,n(X{a})p(f(b), z) \in P_{f, n}(X \setminus \{a\})
302 (ML178 mittig)[Wegen Aufgabe 153 gilt] xU:Pf,n(X{x})\exists x \in U: P_{f, n}(X \setminus \{x\})xU:Pf,n(X{a})\exists x \in U: P_{f, n}(X \setminus \{a\})Die Menge, auf die Bezug genommen wird, ist hier X{a}X \setminus \{a\}
299 (ML172)zeigt Aufgabe 163zeigt Aufgabe 171
297 (ML168)sei dazu ADαf,n+1A \in D_{\alpha \cdot f, n + 1}sei dazu ADf,n+1A \in D_{f, n + 1}
295 (unten)z+f(b)Sn1(X{a})z + f(b) \in S_{n-1}(X \setminus \{a\})z+f(b)Sn(X{a})z + f(b) \in S_{n}(X \setminus \{a\})
288, 289 (ML147)Es wird auf (3.16) Bezug genommen, aber nN>1:n1N\forall n \in \N_{>1}: n - 1 \in \N ist Axiom (3.18)
277 (ML106)für "    \impliedby" müsste noch yUy \in U gezeigt werden
272 (ML89)Es wird auf eine Symmetrie von \le Bezug genommen, aber in dem Kontext ist \le Antisymmetrisch (Satz 3.11 und Ü89)
269 (ML78)was auf den Widerspruch 010 \ge 1 führtwas auf den Widerspruch 121 \ge 2 führtxNx \in \N, also x0x \ne 0. Im indirekten Beweis wird xx+1x \ge x + 1 mit x=0x=0 verwendet
258 (ML44)mit AA anstelle von AA und BB anstelle von BBmit AA anstelle von EE und BB anstelle von FF

Ideen: Metrische Räume

SeiteFehlerstelleKorrekturvorschlagBemerkung
166 (Ü274)Br(A)B_r(A)Brd(A)B_r^d(A)
167Br(u)B_r(u)Brd(u)B_r^d(u)Mehrfachnennung auf dieser Seite, ohne auf die Metrik Bezug zu nehmen
156 (Ü248)s<supMs < sup MuM:u<supMu \in M: u < sup Mss ist vorgegeben mit sOMs \in O_M, damit gilt ja bereits ssupMs \ge sup M und damit auch sms \ge m
154 (Ü240)Min(b)Min(b)Min(B)Min(B)
147 (Ü226)D:Xn×XnD: X^n \times X^n, ...D:Xn×XnRD: X^n \times X^n \rarr \R, ...

Ideen: Äquivalenzklassen

SeiteFehlerstelleKorrekturvorschlagBemerkung
132 (unten)R([au]~)=R([au]~)R([a \cdot u]_\text{\textasciitilde}) = R([a \cdot u]_\text{\textasciitilde})R(a[u]~)=R([au]~)R(a \boxdot [u]_\text{\textasciitilde}) = R([a \cdot u]_\text{\textasciitilde})

Training

SeiteFehlerstelleKorrekturvorschlagBemerkung
94{tU3:((t1A)(t2B))(t3C)}\{t \in U^3: ((t_1 \in A) \land (t_2 \in B)) \land (t_3 \in C)\}{tU3:(t1A)(t2B)(t3C)}\{t \in U^3: (t_1 \in A) \land (t_2 \in B) \land (t_3 \in C)\}
83 (oben)führt zur Langform U={yZ:xZ:y=g(z)}U = \{y \in \Z: \exists x \in \Z : y = g(z)\}führt zur Langform U={yZ:xZ:y=g(x)}U = \{y \in \Z: \exists x \in \Z : y = g(x)\}in (3.10) wird für die Gleichung ebenfalls die falsche Variable genutzt
82 (Ü102)Zeige aR:g[R0]=Ra\exists a \in \R : g [R_{\ge 0}] = \R_{\ge a}.Zeige aR:g[R0]=Ra\exists a \in \R : g [\R_{\ge 0}] = \R_{\ge a}.

Rechtschreibung / Grammatik / Druckfehler

SeiteFehlerstelleKorrekturvorschlag
325 (ML259)Insebsondere ist distd(x,A)=0dist_d(x,A) = 0Insebsondere Insbesondere ist distd(x,A)=0dist_d(x,A) = 0
295 (ML160)die Argumentation wurde ist dir eventuelldie Argumentation wurde ist dir eventuell
294zu zeigen ist P(A)=2AP(A)\mid = 2^{\mid A \mid}zu zeigen ist P(A)=2A\mid P(A)\mid = 2^{\mid A \mid}
290ergibt m=nANm = \mid n \mid - \mid A \mid \in \Nergibt m=nANm = n - \mid A \mid \in \N
284 (ML132)und mit Aufgabe 132 ergibt sich schliesslichund mit Aufgabe 131 ergibt sich schliesslich
166 (unten)dass sie sich garnicht scheidendass sie sich garnicht scheiden schneiden
149In einer Kugel mit em RadiusIn einer Kugel mit em dem Radius
125 (unten)und mit Aufgabe 179 dannund mit Aufgabe 179 180 dann
120 (oben)Mit Teil (b) von Aufgabe 179 folgt hierausMit Teil (b) von Aufgabe 179 180 folgt hieraus
117Ausgangspizza in a2b2a_2 \cdot b_2 Teile auftrittAusgangspizza in a1b2a_1 \cdot b_2 Teile auftritt
104 (unten)in Für-Alle-Aussage über N0\N_0 zu verwandelnin Für-Alle-AussageAussagen über N0\N_0 zu verwandeln
102 (oben)auf \emptyset gibt es nur ein einzige Funktionauf \emptyset gibt es nur ein eine einzige Funktion
37 (unten)Dies folgt durch Anwendung von Satz 2.11 bei Ersetzung von AA durch EEDies folgt durch Anwendung von Satz 2.11 2.9 bei Ersetzung von AA durch EE
37 (unten, folgt der vorher erwähnten Fehlerstelle)Dies folgt durch Anwendung von Satz 2.9 bei ErsetzungDies folgt durch Anwendung von Satz 2.9 2.11 bei Ersetzung

Anmerkungen

SeiteBemerkung
148 Definition 5.9vielleicht bietet es sich hier bereits an, in der Definition den Begriff "offene Kugel" zu verwenden
118 Definition 4.1Sei ~\text{\textasciitilde} eine Äquivalenzrelation auf einer nicht leeren Menge XX
91 Definition 3.24Informatiker würden sich hier über die Erwähnung "partielle Funktion" freuen
*ML = Musterlösung*Ü = Übung

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

UU: Elementuniversum

En\Epsilon_n: Menge aller endlichen Mengen mit der Mächtigkeit nn

P(K)P(K): Potenzmenge von KK mit KUK \subset U

Aufgabenstellung

Es ist per Induktion zu beweisen, das

nN0:k(N0)n:XDk:Sk(X)=1\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:XRf: X \mapsto R

Dn:={XEn:XDef(f)}D_n:=\{X \in \Epsilon_n : X \subset Def(f) \}

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

Sn+1:Dn+1P(R), X{f(x)+s  (x,s)X×Sn(X{x})}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 xU:xSn+1(X)x \in U: x \in S_{n+1}(X) über

!xU:xSn+1(X)\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 u,vSn+1(X):u=v\forall u,v \in S_{n+1}(X): u = v auch Sn+1(X)=1|S_{n+1}(X)| = 1 folgt (u.a. wegen Aufgabe 99 und Aufgabe 153).

Argumentation

Hierzu sei

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

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

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

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

Fehlerstelle

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

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

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

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

· 8 min read
info

Ein Kommentar zu einem Kommentar zu Eberhard Wolff's Episode 159 - Big Ball of Mud als Teil von Software-Architektur im Stream. Eine englische Übersetzung findet sich hier.

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

· 8 min read
info

A comment on a comment to Eberhard Wolff's recent episode 159 of Software-Architektur im Stream - Big Ball of Mud. This is a translation of this article, which was originally published in german language.

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

· 3 min read

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).

HordeClient.php
         $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():

Horde/Mime/Mail.php

/* 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():

Horde/Mail/Rfc822/List.php

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;
}

A possible fix is to call getAddressList() on _bcc in Horde_Mime_Mail::send() or check for this type in the normalize()-method of Horde_Mail_Rfc822_List:

Horde/Mail/Rfc822/List.php.diff

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


+ if ($obs instanceof Horde_Mime_Headers_Addresses) {
+ $obs = $obs->getAddressList();
+ }

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

Fixing this in Horde/Mime/Mail.php is also possible, although I do not know if that would cause any side effect since I could not find the expected type of _bcc. It gets checked in '_normalize()' (see above) so I guess this would be the better place to apply the fix, instead of doing this:

Horde/Mime/Mail.php.diff

/* 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);
+ $recipients->add($this->_bcc->getAddressList());
}

Update 21.03.2023: PR available here

· 3 min read

Fix: Missing favicon.ico in Sencha ExtJS production builds

Fixing missing favicon.ico in Ext JS applications.

The original issue is tracked here: https://github.com/conjoon/conjoon/issues/24

The issue

I’m not quite sure when and why it broke, but it looks like production builds of Sencha Ext JS applications do not contain any favicon.ico originally existing in the development build (anymore).

While everything seems to be okay with development builds (that’s easy, they refer to the development’s root folder in most cases and do not copy and move files around like the production build does), deploying to production will show the default icon coming with your vendor’s browser for any Sencha ExtJS application, at least when your environment is using the following package versions:

    webpack v4.39.3n/a
ext-webpack-plugin v7.6.0
Ext JS v7.6.0.41
Sencha Cmd v7.6.0.87
``

A call to

```bash
$ cross-env webpack
--env.profile=desktop
--env.environment=production
--env.treeshake=yes
--env.cmdopts=--uses

will produce the production build, but the production build will not contain the favicon.ico. Here’s proof (… sort of):

The fix

I did not invest too much investigating the reason why this file is omitted. Instead, I added the copy-webpack-plugin to the project and made sure the the favicon is copied over when running npm run build.

If you’re reading this post, you most likely stumbled across the same issue. Here’s how to fix it.

  1. Add copy-webpack-plugin to your project

I’m still sporting webpack v4.39.3 so I had to fall back to an older version of the plugin. I’m using copy-webpack-plugin@6.4.1 in this case:

    $ npm i -D copy-webpack-plugin@6.4.1
  1. Add a few more modules to your project’s webpack.config.js

Add the following two lines to the head of the file:

    // ....
const CopyWebpackPlugin = require("copy-webpack-plugin");
const fs = require("fs");
//...

Why fs? I couldn’t find an easy way to access the application’s name at this point of the build step through the variables available, so I’m using fs to parse the project's app.json. The value of its name-property is then used for computing the destination folder for the copy-operation.

  1. Add the copy-webpack-plugin to the list of plugins in the script

You’ll easily find the location that has to be edited when looking for the @sencha/ext-webpack-plugin-configuration:

    const plugins = [
new ExtWebpackPlugin({
// ...
}),
new CopyWebpackPlugin({
patterns: [{
from: path.resolve(__dirname, './favicon.ico'),
to: path.join(
__dirname,
"build",
environment,
JSON.parse(
fs.readFileSync(
path.resolve(__dirname, './app.json')
)
).name
)
}]
})
]

Subsequent builds will now contain the favicon.ico.

· 2 min read

Releasing conjoon V1.0

I’m happy to announce conjoon 1.0, the very first major release of the Open Source JavaScript Email client.

For updating to the latest version, simply use our installer. It will let you select the latest release when opting for the version to install.

Highlights

v1.0.0 marks the first major release for our JavaScript Email frontend, over 100 tickets related to bugfixes, optimizations and minor features across all projects where closed.

This release focuses on providing a stable frontend in conjunction with lumen-app-email.

Besides the features already introduced with the release candidates, the following features have been added:

Plugins

Installer and CLI actions for lumen-app-email

The installation for lumen-app-email has been simplified with the help of Artisan and CLI commands. To get an instance of lumen-app-email running, use

$ composer create-project conjoon/lumen-app-email {targetDir} {version}

which will start the installation process. For more information, refer to the official guide.

Docker Container

ddev-ms-email has been updated to utilize the installer of lumen-app-email and additionally provides integration options for conjoon so that the container can be used for serving both the backend and the frontend.

$ ddev create-conjoon

will start the installation of conjoon. For more information, refer to the official guide.

Happy coding! 🎈