Bei der rekursiven Fakultät handelt es sich um einen rekursiven Funktionsaufruf:
package AlgoDat;
public class RekursiveFakultaet {
// Zu sortierendes Array
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static RekursiveFakultaet program;
public long berechneFakultaet(int teilFakultaet)
{
// Abbruchbedingung der Rekursion wenn 1 erreicht ist
if (teilFakultaet == 1) return 1;
// Multipliziere rekursiv f(n) = n * f(n - 1) bis 1
return teilFakultaet * berechneFakultaet(teilFakultaet - 1);
}
// Konstruktor
public RekursiveFakultaet()
{
System.out.println(this.berechneFakultaet(25) + "");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new RekursiveFakultaet();
}
}
Ausgabe
7034535277573963776
Komplexität: O-Notation (Ordnung)
Der rekursive Aufruf dieser Art kann als primitiv rekursiven Klasse gezählt werden und besitzt die lineare Komplexität / O-Notation:
Der MergeSort-Algorithmus ist ein stabiler Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Im ersten Teil wird das Array rekursiv so lange halbiert, bis in jeder Liste nur noch 1 Element vorhanden ist. Bei einer Liste mit einem Element geht man davon aus, dass die Liste automatisch als sortiert gilt. Danach können alle nachfolgenden Operationen von zwei sortierten Listen ausgehen, wodurch weniger Operationen beim Zusammenführen ausreichen um ein neues sortiertes Array zu erhalten.
Im zweiten Teil werden die bereits sortierten Listenhälften verglichen und mit der Komplexität O(n) je rekursiver Iteration verglichen und zusammengeführt (siehe den nachfolgenden JAVA Code).
package AlgoDat;
public class MergeSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static MergeSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
public void mergeSort(int myArray[])
{
// zunächst wird das Array ab der Hälfte in zwei
// Arrays links und rechts geteilt, das passiert
// rekursiv ... und zwar so lange bis jedes Element
// für sich nur noch 1x vorhanden ist (Teile-Herrsche-Prinzip).
// Das Teilen ist damit erledigt und nun sollte da
// Problem dadurch beherrschbarer werden -> nun
// werden die Einzelelemente wieder in Arrays sortiert.
// Die Abbruchbedingung der Rekursion ist, wenn die Liste
// nur noch ein einziges Element hat, wobei die Liste bei
// einem einzigem Element als sortiert gilt.
if (myArray.length == 1) return;
// weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
int indexHaelfte = myArray.length / 2;
int[] linkeHaelfte = new int[indexHaelfte];
// Die abgerundete Ganzzahl kann von der Länge abgezogen werden
// um die Größe des rechten Arrays zu erhalten.
int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
// Befülle die linke Hälfte
for (int i = 0; i < indexHaelfte; i++)
{
linkeHaelfte[i] = myArray[i];
}
// Befülle die rechte Hälfte
for (int i = indexHaelfte; i < myArray.length; i++)
{
rechteHaelfte[i - indexHaelfte] = myArray[i];
}
// Hier ist der rekursive Aufruf, indem die beiden Hälften an
// die mergeSort-Methode selbst übergeben wird.
this.mergeSort(linkeHaelfte);
this.mergeSort(rechteHaelfte);
// Hier werden die beiden Arrays wieder kombiniert (geMerged)
this.merge(myArray, linkeHaelfte, rechteHaelfte);
}
private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
{
System.out.print("Vergleiche linke Hälfte: ");
this.OutputOfIntArray(linkeHaelfte);
System.out.print("mit rechter Hälfte ");
this.OutputOfIntArray(rechteHaelfte);
int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
// Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
// in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
{
if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
}
else
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
}
iteratorMergeArray++;
}
// Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorLinks < linkeHaelfte.length)
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
iteratorMergeArray++;
}
// Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorRechts < rechteHaelfte.length)
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
iteratorMergeArray++;
}
}
// Konstruktor
public MergeSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
// Wir lagern alles weitere in eine eigene Methode aus,
// da MergeSort ein rekursiver Algorithmus ist, dessen
// Funktion aufgerufen werden muss und beeginnen mit dem
// unsortierten Array
this.mergeSort(myArray);
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new MergeSort();
}
}
Ausgabe
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Vergleiche linke Hälfte: 22
mit rechter Hälfte 6
Vergleiche linke Hälfte: 4
mit rechter Hälfte 10
Vergleiche linke Hälfte: 2
mit rechter Hälfte 4;10
Vergleiche linke Hälfte: 6;22
mit rechter Hälfte 2;4;10
Vergleiche linke Hälfte: 9
mit rechter Hälfte 7
Vergleiche linke Hälfte: 3
mit rechter Hälfte 7;9
Vergleiche linke Hälfte: 8
mit rechter Hälfte 1
Vergleiche linke Hälfte: 5
mit rechter Hälfte 1;8
Vergleiche linke Hälfte: 3;7;9
mit rechter Hälfte 1;5;8
Vergleiche linke Hälfte: 2;4;6;10;22
mit rechter Hälfte 1;3;5;7;8;9
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Komplexität: O-Notation (Ordnung)
Der MergeSort besteht aus 3 Teilen, die sich zu der Gesamtkomplexität zusammensetzen.
Teil 1: (Rekursives) Teilen
Wenn wir ein Array der Größe n in zwei Hälften teilen, benötigen wir
Schritte. Hierbei handelt es sich um den Logarithmus dualis, also den Logarithmus zur Basis 2 (wessen Basis für die 2 Hälften spricht, in die aufgeteilt wird). Dies liegt also daran, dass wir die Liste in jeder Rekursionsebene halbieren. Wir fragen hier also mit welcher Zahl man 2 potenzieren muss um n zu erhalten.
Wenn wir in dem unsortierten Array 11 Elemente haben, würden wir also fragen, mit welcher Zahl wir 2 potenzieren müssen um 11 zu erhalten. Den Exponenten den wir hier erhalten wäre 4:
Wir runden die Kommazahl immer auf die nächste volle Zahl auf, da wir keine halben Schritte machen können. Die Zahl 4 entspricht hier auch der Rekursionstiefe, die benötigt wird bis der aktuelle Rekursions-Heap nur noch aus einem Element bekommt, was zu Abbruch der Rekursion führt.
Der erste Teil besitzt somit die Ordnung:
Teil 2 und 3: Sortieren und Mergen
Der Schritt des Zusammenführens (des Mergens) beider Liste ist mit der Sortierung kombiniert. Hier wird vorausgesetzt dass bereits sortierte Listenhälften vorliegen, da man zwei bereits sortierte Arrays mit der Komplexität n vergleichen kann. Beim Zusammenführen der sortierten Teillisten benötigen wir
Zeit. Dieser Schritt ist linear abhängig von der Gesamtanzahl der Elemente.
Beim „Bubble Sort“ markiert die äußere Schleife das erste Element des noch unsortierten Bereichs, während die innere Schleife ab diesem Element immer bis zum Ende des Arrays ein Element zum Vergleich rauspickt. Ist ein Element kleiner/größer (je nachdem wie der Vergleichsoperator „gedreht“ ist) wird getauscht.
Dies führt am Ende zu der Sortierung des Arrays. Im Gegesatz zum Selection Sort, wo nur das Minimum getauscht wird, wird beim Bubble Sort immer getauscht.
package AlgoDat;
public class BubbleSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static BubbleSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Konstruktor
public BubbleSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
// Äußere Schleife: Laufe das zu sortierende Array von Anfang bis Ende durch (Komplexität: n)
for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)
{
// Innere Schleife: Laufe das Array ab dem Index der äußeren Schleife bis Ende durch (Komplexität: n / 2)
for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)
{
// Tausche die Array-Inhalte an den Indizes der inneren und äußeren Schleife
// wenn diese kleiner/größer sind. Anmerkung: Ein Drehen von < zu > ändert die Sortierreihenfolge
if (myArray[idxUnsortierterBereich] < myArray[idxSortierterBereich])
{
// Beim Bubble Sort wird im Gegensatz zum Selection Sort immer getauscht.
// Beim Selection Sort wird nur das gefundene Minimum getauscht.
// Dieser Code tauscht das Element am Index der äußeren Schleife
// mit dem Element am Index der inneren Schleife
int swapVar = myArray[idxUnsortierterBereich];
myArray[idxUnsortierterBereich] = myArray[idxSortierterBereich];
myArray[idxSortierterBereich] = swapVar;
System.out.print("Tausche: ");
this.OutputOfIntArray(myArray);
}
}
}
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new BubbleSort();
}
}
package AlgoDat;
public class SelectionSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static SelectionSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Konstruktor
public SelectionSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
// Laufe das zu sortierende Array von Anfang bis Ende durch
for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)
{
// Starte an der Index-Position der äußersten Schleife - davor ist schon alles sortiert
int indexPivotElement = idxSortierterBereich;
for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)
{
// ... und merke dir das kleinste Element
if (myArray[indexPivotElement] > myArray[idxUnsortierterBereich])
{
indexPivotElement = idxUnsortierterBereich;
}
}
// Dieser Code tauscht das neu gefundene Minimum mit dem Element am aktuellen Index der äußeren Schleife
int swapVar = myArray[indexPivotElement];
myArray[indexPivotElement] = myArray[idxSortierterBereich];
myArray[idxSortierterBereich] = swapVar;
System.out.print("Tausche: ");
this.OutputOfIntArray(myArray);
}
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new SelectionSort();
}
}
Zwei verschaltete Schleifen. Die äußere Schleife läuft von 1 bis n; Die innere Schleife läuft vom Element der äußeren Schleife bis Schluss -> also n/2, da der Bereich immer kleiner wird.
Markant sind die zwei verschachtelten Schleifen, wobei die innere Schleife meistens eine While-Schleife mit 2 Bedingungen ist. Ein Index, welcher die Position der Trennung vom sortierten (links) und vom unsortierten (rechts) Bereich präsentiert, wird runtergezählt und das Array-Element an der Index-Position entspricht nach Ende der Schleife der Array-Position, mit der ein gemerktes Element getauscht werden kann. Während der sortierte Bereich (immer links) mit dem ersten Element des unsortierten Bereichs (immer rechts), welches sich gemerkt wird, verglichen wird, werden alle Elemente bis zu diesem Punkt um eins nach rechts gerückt. Dadurch existiert die zu tauschende Position nach diesem Schritt zwei Mal und wird durch das gemerkte Element ausgetauscht.
Die zweite Bedingung der inneren While-Schleife verhindert, das der runterzählende Index negativ wird.
package AlgoDat;
class InsertionSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse InsertionSort als instanziertes Objekt
@SuppressWarnings("unused")
private static InsertionSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Konstruktor
public InsertionSort()
{
this.OutputOfIntArray(myArray);
// Bei 1 beginnen, da das Element mit dem Index 0 bereits als sortiert gilt
for (int idxSortierterBereich = 1; idxSortierterBereich < myArray.length; idxSortierterBereich++)
{
// Merke dir das erste Element vom unsortierten Bereich
int swapVar = myArray[idxSortierterBereich];
System.out.println("Gemerkt vor dem Aufrücken: " + swapVar);
// Das erste unsortierte Element auf der rechten Seite wird in den bereits sortierten Bereich
// auf der linken Seite eingefügt, womit der unsortierte Bereich immer weiter nach rechts rückt
// und dann verschwindet.
int idxUnsortierterBereich = idxSortierterBereich;
System.out.println("Der unsortierte Bereich beginnt bei Index: " + idxUnsortierterBereich);
// Laufe im Array von rechts nach links, so lange wie vorige Element noch größer wie
// das erste Element vom unsortierten Bereich ist und der Bereich nicht negativ wird
while (idxUnsortierterBereich > 0 && myArray[idxUnsortierterBereich - 1] > swapVar)
{
// Alles eins nach rechts im Array rücken bis zum bereits sortierten Bereich
myArray[idxUnsortierterBereich] = myArray[idxUnsortierterBereich - 1] ;
idxUnsortierterBereich--;
System.out.print("Nach rechts aufrücken: ");
this.OutputOfIntArray(myArray);
}
System.out.println("Tausche Stelle " + (idxUnsortierterBereich + 1) + " (" + myArray[idxUnsortierterBereich] +
") mit gemerkter Stelle " + (idxSortierterBereich + 1) + " (" + swapVar + ")");
myArray[idxUnsortierterBereich] = swapVar;
System.out.print("Getauscht: ");
this.OutputOfIntArray(myArray);
}
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new InsertionSort();
}
}
Ausgabe
22;6;2;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 6
Der unsortierte Bereich beginnt bei Index: 1
Nach rechts aufrücken: 22;22;2;4;10;3;9;7;5;8;1
Tausche Stelle 1 (22) mit gemerkter Stelle 2 (6)
Getauscht: 6;22;2;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 2
Der unsortierte Bereich beginnt bei Index: 2
Nach rechts aufrücken: 6;22;22;4;10;3;9;7;5;8;1
Nach rechts aufrücken: 6;6;22;4;10;3;9;7;5;8;1
Tausche Stelle 1 (6) mit gemerkter Stelle 3 (2)
Getauscht: 2;6;22;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 4
Der unsortierte Bereich beginnt bei Index: 3
Nach rechts aufrücken: 2;6;22;22;10;3;9;7;5;8;1
Nach rechts aufrücken: 2;6;6;22;10;3;9;7;5;8;1
Tausche Stelle 2 (6) mit gemerkter Stelle 4 (4)
Getauscht: 2;4;6;22;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 10
Der unsortierte Bereich beginnt bei Index: 4
Nach rechts aufrücken: 2;4;6;22;22;3;9;7;5;8;1
Tausche Stelle 4 (22) mit gemerkter Stelle 5 (10)
Getauscht: 2;4;6;10;22;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 3
Der unsortierte Bereich beginnt bei Index: 5
Nach rechts aufrücken: 2;4;6;10;22;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;6;10;10;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;6;6;10;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;4;6;10;22;9;7;5;8;1
Tausche Stelle 2 (4) mit gemerkter Stelle 6 (3)
Getauscht: 2;3;4;6;10;22;9;7;5;8;1
Gemerkt vor dem Aufrücken: 9
Der unsortierte Bereich beginnt bei Index: 6
Nach rechts aufrücken: 2;3;4;6;10;22;22;7;5;8;1
Nach rechts aufrücken: 2;3;4;6;10;10;22;7;5;8;1
Tausche Stelle 5 (10) mit gemerkter Stelle 7 (9)
Getauscht: 2;3;4;6;9;10;22;7;5;8;1
Gemerkt vor dem Aufrücken: 7
Der unsortierte Bereich beginnt bei Index: 7
Nach rechts aufrücken: 2;3;4;6;9;10;22;22;5;8;1
Nach rechts aufrücken: 2;3;4;6;9;10;10;22;5;8;1
Nach rechts aufrücken: 2;3;4;6;9;9;10;22;5;8;1
Tausche Stelle 5 (9) mit gemerkter Stelle 8 (7)
Getauscht: 2;3;4;6;7;9;10;22;5;8;1
Gemerkt vor dem Aufrücken: 5
Der unsortierte Bereich beginnt bei Index: 8
Nach rechts aufrücken: 2;3;4;6;7;9;10;22;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;9;10;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;9;9;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;7;9;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;6;7;9;10;22;8;1
Tausche Stelle 4 (6) mit gemerkter Stelle 9 (5)
Getauscht: 2;3;4;5;6;7;9;10;22;8;1
Gemerkt vor dem Aufrücken: 8
Der unsortierte Bereich beginnt bei Index: 9
Nach rechts aufrücken: 2;3;4;5;6;7;9;10;22;22;1
Nach rechts aufrücken: 2;3;4;5;6;7;9;10;10;22;1
Nach rechts aufrücken: 2;3;4;5;6;7;9;9;10;22;1
Tausche Stelle 7 (9) mit gemerkter Stelle 10 (8)
Getauscht: 2;3;4;5;6;7;8;9;10;22;1
Gemerkt vor dem Aufrücken: 1
Der unsortierte Bereich beginnt bei Index: 10
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;10;22;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;10;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;4;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;3;4;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;2;3;4;5;6;7;8;9;10;22
Tausche Stelle 1 (2) mit gemerkter Stelle 11 (1)
Getauscht: 1;2;3;4;5;6;7;8;9;10;22
Komplexität: O-Notation (Ordnung)
O(T(n)) = O(n^2/2+n/2-n) = O(n^2/2) = O (n^2)
Die äußere Schleife läuft von 1 bis n-1, während die innere While-Schleife vom ersten Element des unsortierten Bereichs bis zu der Stelle der richtige Einfügeposition läuft.
Äußere Schleife: Iteriert n-1 mal. Innere Schleife: Iteriert 1x für Element 1, 2x für Element 2, 3x für Element 3, … n mal für Element n, was zu einer Laufzeit von
führt. Daraus folgt:
Additive Bestandteile, Faktoren und Konstanten fallen bei der Bestimmung der Ordnung weg, daher ist die Ordnung O(n²). Die Domäne ist der dominante Teil der Ordnung – sie ist n² .
Zum Auffrischen des eigenen Wissens über künstliche neuronale Netze (KNN) möchte man sich mit Frameworks wie PyTorch oder TensorFlow auseinandersetzen.
Problem
In den ersten Tutorials ist meistens die Rede vom „MNIST-Datensatz“ oder der „MNIST Datenbank“ mit 70.000 handgeschriebenen Ziffern im Format 28×28 mit 256 Grauwerten je Pixel (also je Byte). 60.000 Bilder davon sind zum Trainieren, 10.000 Bilder zum Testen eines neuronalen Netzes. Die Dateiendung der entpackten Dateien lässt sich nicht einfach in *.bmp umbenennen und zum Beispiel mit Paint öffnen. Man weiß erstmal nicht in welchem Format die Dateien sind um sich einzelne Zahlen anzusehen.
Laut „https://yann.lecun.com/exdb/mnist“ (manchmal nur über einen archive.org-Snapshot erreichbar) handelt es sich bei diesem Format nicht um ein Standard-Bildformat. Man muss ein eigenes Programm schreiben um diese Bilder zu interpretieren.
Analyse
train-images-idx3-ubyte, t10k-images-idx3-ubyte
Diese Dateien sind mit GZip (Endung *.gz) gepackt und lassen sich in Windows direkt mit einem Doppelklick öffnen oder mit einem Rechtsklick extrahieren:
Die *-images*-Dateien enthalten Bilder von handgeschriebenen Ziffern zwischen 0 und 9, die von Studenten und Mitarbeitern der Universität von South Carolina Beaufort im Jahre 1994 gesammelt wurden.
Öffnet man die extrahierten Dateien in einem Hexadezimaleditor wie zum Beispiel dem kostenlosen HxD-Editor und stellt die Spaltenanzahl auf 28 um, ist bereits ein Muster der enthaltenen Zahlen erkennbar:
Die ersten 16 Byte haben den folgenden Aufbau:
[offset] [type] [value] [description]
0000 32 bit integer 0x00000803(2051) magic number
0004 32 bit integer 60000 number of images
0008 32 bit integer 28 number of rows
0012 32 bit integer 28 number of columns
0016 unsigned byte ?? pixel
0017 unsigned byte ?? pixel
........
xxxx unsigned byte ?? pixel
Die 0x08 des dritten Bytes in der Magic Number sagt aus, dass es sich hierbei um UByte-Werte anhandelt. Das dritte Byte kann dabei die folgenden Werte annehmen:
The third byte codes the type of the data:
0x08: unsigned byte
0x09: signed byte
0x0B: short (2 bytes)
0x0C: int (4 bytes)
0x0D: float (4 bytes)
0x0E: double (8 bytes)
Das vierte Byte in der Magic Number hat hier den Wert 0x03, was bedeutet das unsere Daten 3 Dimensionen für den Pixel haben (x-Pos, y-Pos, Pixelwert/Grauwert[0-255]).
Entfernt man den markierten Header mit den ersten 16 Bytes (siehe obiges Bild) z.B. im HxD, indem man einfach die Entfernen-Taste drückt, ist das Schriftmuster bereits im HEX-Editor erkennbar:
Wie bereits erwähnt, hat jeder Pixel einen Wert zwischen 0 (weiß) und 255 (schwarz) [Magic Number: 3. Byte], wobei die Zwischenwerte lineare Abstufungen für Grauwerte sind.
Hier noch ein Beispiel der Fashion-MNIST-Datenbank mit Kleidungsstücken (von Zalando):
train-labels-idx1-ubyte, t10k-labels-idx1-ubyte
Der Aufbau der *-labels*-Dateien ist ähnlich. Als Label werden hier die Zahlen mit den Werten zwischen 0 bis 9 in der selben Reihenfolge wie in den *-images*-Dateien aufgeführt. Diese beginnen nach dem Header an Position 8 (hier 5 und 0 / unten wie oben im Screenshot):
Das Format ist also:
[offset] [type] [value] [description] 0000 32 bit integer 0x00000801(2049) magic number 0004 32 bit integer 60000 number of images 0008 byte [0-9] Ziffer zw. 0-9 ……..
QRCoder ermöglicht das Erstellen von QR-Codes mit einer einfachen Bibliothek. Solange keine QR-Code-Version angegeben wird, passt sich die Größe der generierten QR-Codes an den zu codierenden Text an.
Die folgenden Parameter werden unterstützt:
ECC Level: Fehlerkorrekturlevel. Gibt an wieviel Redundanzen eingebaut werden um im Fehlerfalle trotzdem lesbare Q- Codes zu erhalten. Je höher der Level ist, desto weniger Text kann im QR-Code einer bestimmten Größe gespeichert werden. Es gibt 4 ECC-Level={L, M, Q, H}, die in der folgenden ENUM definiert sind: QRCodeGenerator.ECCLevel
Version (optional): Die QR-Code-Version legt eine feste Größe (Modulanzahl) für den generierten QR Code fest. Die QR-Code-Größe definiert sich durch die Anzahl der „Module“ in der Matrix. Ein „Module“ definiert ein Quadrat im QR-Code. Wird keine Version angegeben, vergrößert sich der QR-Code automatisch auf die entsprechende Version. Beispiele: Version 1 hat eine Größe von 21×21 Modulen, also 1(21×21), Version 2(25×25), 3(29×29), 4(33×33), 5(37×37), 6(41×41), 7(45×45), 8(49×49), 9(53×53), 10(57×57), 11(61×61) …
Pixel pro Modul: Die Anzahl der verwendeten Pixel für die Darstellung eines Moduls im QR-Code. Da Module im QR-Code quadratisch sind, gilt der Parameter für Breite und Höhe. Durch die exakte Festlegung der Pixel kann verhindert werden, dass der QR-Code wegen einer Skalierung unscharf oder verschwommen wird (wg. Aliasing).
Text (bzw. Textformat des zu codierenden Textes): Ein codierter Text kann numerische, alphanumerische, binäre oder Kanji-Zeichen enthalten. Die Reihenfolge dieser möglichen Zeichensätze legt von links nach rechts fest, wieviel Text insgesamt im QR-Code enthalten sein kann. Rein numerische Zeichen benötigen wenig Platz im QR-Code, wodurch für eine festgelegte Größe (Version) z.B. viel mehr Text codiert werden kann. Wenn ein Text aber nur ein einziges Kanji-Zeichen beinhaltet, wird der gesamte Textinhalt für Kanji codiert, was dazu führt dass weniger Text für eine Version (festgelegte Anzahl von Modulen) codiert werden kann.
Die folgende Tabelle verdeutlicht anhand der oben genannten Parameter, welche Datenkapazität (Textlänge) nach Version, ECC Level und verwendetem Zeichensatz erwartet werden kann:
Version (Modulzahl)
Numerisch
Alphanumerisch
Binär
Kanji
L
M
Q
H
L
M
Q
H
L
M
Q
H
L
M
Q
H
1(21)
41
34
27
17
25
20
16
10
17
14
11
7
10
8
7
4
2(25)
77
63
48
34
47
38
29
20
32
26
20
14
20
16
12
8
3(29)
127
101
77
58
77
61
47
35
53
42
32
24
32
26
20
15
4(33)
187
149
111
82
114
90
67
50
78
62
46
34
48
38
28
21
5(37)
255
202
144
106
154
122
87
64
106
84
60
44
65
52
37
27
6(41)
322
255
178
139
195
154
108
84
134
106
74
58
82
65
45
36
7(45)
370
293
207
154
224
178
125
93
154
122
86
64
95
75
53
39
8(49)
461
365
259
202
279
221
157
122
192
152
108
84
118
93
66
52
9(53)
552
432
312
235
335
262
189
143
230
180
130
98
141
111
80
60
10(57)
652
513
364
288
395
311
221
174
271
213
151
119
167
131
93
74
11(61)
772
604
427
331
468
366
259
200
321
251
177
137
198
155
109
85
12(65)
883
691
489
374
535
419
296
227
367
287
203
155
226
177
125
96
13(69)
1022
796
580
427
619
483
352
259
425
331
241
177
262
204
149
109
14(73)
1101
871
621
468
667
528
376
283
458
362
258
194
282
223
159
120
15(77)
1250
991
703
530
758
600
426
321
520
412
292
220
320
254
180
136
16(81)
1408
1082
775
602
854
656
470
365
586
450
322
250
361
277
198
154
17(85)
1548
1212
876
674
938
734
531
408
644
504
364
280
397
310
224
173
18(89)
1725
1346
948
746
1046
816
574
452
718
560
394
310
442
345
243
191
19(93)
1903
1500
1063
813
1153
909
644
493
792
624
442
338
488
384
272
208
20(97)
2061
1600
1159
919
1249
970
702
557
858
666
482
382
528
410
297
235
21(101)
2232
1708
1224
969
1352
1035
742
587
929
711
509
403
572
438
314
248
22(105)
2409
1872
1358
1056
1460
1134
823
640
1003
779
565
439
618
480
348
270
Installation von QRCoder.dll
Die Bibliothek „QRCoder“ kann über die gängigen Quellen bezogen werden und muss dann ggfs. als Verweis hinzugefügt werden:
Einige der genannten Quellen tun dies allerdings automatisch
// Install QRCoder as a Cake Addin
#addin nuget:?package=QRCoder&version=1.4.3
// Install QRCoder as a Cake Tool
#tool nuget:?package=QRCoder&version=1.4.3
C# Konsolenanwendung
Die folgende C# Konsolenanwendung erzeugt drei QR-Codes der Version 5 (also 37×37 Module) mit dem Fehlerkorrekturlevel L (niedrigster Korrekturlevel für viel Platz) und 4×4 Pixel pro Modul. Der Text ist binär, da er die Sonderzeichen einer URL aber keine Kanji-Zeichen beinhaltet. Der erste QR-Code beinhaltet nur den Text „d“ und wird deswegen als alphanumerisch klassifziert.
Außerdem wird der „Ruhebereich“ des QR-Codes (weißer Rand) abgeschnitten, was nicht immer zu empfehlen ist, da diese Trennung für einen korrekten Scan benötigt wird.
using QRCoder;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QRCodeTestConsole
{
public class Program
{
public static Program prg;
public const int version5QRCodeSize = 148 + 32;
public const int pixelPerModule = 4;
public const int moduleVersion = 5;
public const int croppedBorderPixels = 16;
public const QRCodeGenerator.ECCLevel eccLevel = QRCodeGenerator.ECCLevel.L;
public Program()
{
string[] content = { "d",
"https://www.youtube.com/playlist?list=PLA4OWG_-fY-JLoj-bHIPiUU1SJquB9X8J",
"https://www.youtube.com/playlist?list=PLA4OWG_-fY-JLoj-bHIPiUU1SJquB9X8J----------------------...........oipipoiopiopipoipiooipo"};
for (int i = 0; i < content.Length; i++)
{
string current = content[i];
string msgResult = this.GenerateQRCode(current, "QRCode" + i + ".bmp");
if (!msgResult.ToLower().Equals("ok"))
{
Console.WriteLine(msgResult);
}
}
Console.ReadLine();
}
public string GenerateQRCode(string content, string fileName)
{
try
{
QRCodeGenerator qrGenerator = new QRCodeGenerator();
QRCodeData qrCodeData = qrGenerator.CreateQrCode(content, eccLevel, false, false, QRCodeGenerator.EciMode.Default, moduleVersion);
QRCode qrCode = new QRCode(qrCodeData);
Bitmap qrCodeImage = new Bitmap(qrCode.GetGraphic(pixelPerModule));
// Ruhezone abschneiden - falls nicht
// gewünscht bei qrCodeImage.Save aufrufen
Bitmap croppedBmp = qrCodeImage.Clone(new Rectangle(croppedBorderPixels, croppedBorderPixels, qrCodeImage.Width - 2 * croppedBorderPixels, qrCodeImage.Height - 2 * croppedBorderPixels), qrCodeImage.PixelFormat);
croppedBmp.Save("CROP_" + fileName);
}
catch (Exception e)
{
return e.ToString();
}
return "ok";
}
public static void Main(string[] args)
{
prg = new Program();
}
}
}
npm init -y // erstellt die package.json und bestätigt alles mit y
npm install typescript --save-dev // Mit Typescript entwickeln - fügt in package.json eine devDependencies hinzu
npx tsc --init // Erzeugt tsconfig.json (enthält z.B. die Ecma-Script-Version)
npx tsc --watch // Schaut nach Änderungen
node src/hello.js // Interpretiert das Javascript damit wir keinen Browser brauchen mit Node kann man aufs Dateisystem zugreifen
npm installiert pakete
npx temporäres Paket
Aufgabe 1: Klassen & Methoden
Baue eine Klasse die etwas zurückgibt bei folgendem Code
let s: Student = new Student();
let label:string = s.getLabel(123457);
console.log(label); // "Student mit Matrikelnummer: 123456"
Lösung 1
class Student {
oldNumber:number = -1;
getLabel(matNr:number):string {
if (matNr == 123456)
{
this.oldNumber = matNr;
let zusammenGebaut = "Die Nr. " + this.oldNumber;
return zusammenGebaut;
}
else
{
return `Student mit Matrikelnummer: ${matNr}`;
}
}
}
Aufgabe 2: Konstrukturen
Sorge dafür, dass diese Ausgabe über einen Konstruktor funktioniert
let s: Student = new Student("Max", 123456);
let label: string = s.getLabel();
console.log(label); // "Student Max mit Matrikelnummer: 123456";
Lagere die Klasse Student in eine andere Datei aus, so dass sie mit den folgenden Kommandos wieder instanziert werden kann
import {Student} from "./student"
let s: Student = new Student("Max", 123456);
let label: string = s.getLabel();
console.log(label); // "Student Max mit Matrikelnummer: 123456";
Lösung 3
Lege die Klasse student.js im gleichen Verzeichnis wie hello.js an und kopiere die Student-Klasse von Lösung 2 rein:
„ADHS in Mexico“ für den Blues Contest No. 1 von Recording.de
Intention
Diesen Song habe ich für den Blues Contest No. 1 von Recording.de geschrieben. Im Text geht es konkret um den Auftritt von Mr. T. im Blues Brothers Film, wie er in diesem Video (bereits zurechtgespult) erläutert. Er hat für diese Rolle 25 Dollar bekommen und war gegen Schluss verschwommen und kurz sichtbar:
Die erste Rolle von Mr. T. im Blues Brothers Film
Hierbei handelte es sich um seine erste Filmrolle, ich hab die in den Kontext von „From dusk till dawn“ gesetzt.
Text
Strophe 1
Ich war mit meiner Truppe auf ’ner Road nach Mexico Ich dachte mir ja nur – ma hier ma dort und so … Doch plötzlich wurd‘ ich durstig, der Staub trocknet‘ mich aus … Ich hielt nach einem Ort … zum Kehle-befeuchten aus … Der Wüsten-Horizont war in der Dämmerung erhellt vom Neonlicht von einer Tabledance-Bar wie bestellt Ein von Staub verschmiertes Tablet streamte den Blues Brothers Film Seht ihr da auch was? Schaut mal genauer hin!
Refrain
Kann das wirklich wahr sein? Macht es wirklich Sinn? Ich sah … Mr. T im Blues Brothers Film … oh yeah
(Riff)
Strophe 2
Wir ereichten die Spelunke … fuhr’n in die Parkbucht ein Ein schreiender Türsteher rief uns in die Tanzbar rein Wir nahmen schließlich Platz und bestellten uns ein Fass jetzt machen wir erstmal … uns’re tock’nen Kehlen nass Umringt von Stripperinnen tranken wir das Fässchen leer und bestellten uns dann noch eins schließlich macht das Lust auf mehr B1ildschirme an der Wand streamten den Blues Brothers Film Seht ihr da auch was? Schaut mal genauer hin!
Refrain
Kann das wirklich wahr sein? Macht es wirklich Sinn? Ich sah … Mr. T im Blues Brothers Film … oh yeah
(Riff)
Strophe 3
Plötzlich und unerwartet … veränderte sich was .. Die Mädels um uns rum war’n auf einmal richtig blass Sie versuchten mich zu beissen … doch das is nich so mein Ding Mit ein paar Kopfschüssen … hielt‘ ich sie schließlich hin So etwas hat mir nämlich noch niemals imponiert denn ich war sehr schwer bewaffnet … Munition war deponiert Mein Handy in der Hand streamte den Blues Brothers Film Seht ihr da auch was? Schaut mal genauer hin!
Refrain
Kann das wirklich wahr sein? Macht es wirklich Sinn? Ich sah … Mr. T im Blues Brothers Film … oh yeah
(Riff)
Zwischenteil
SOLO
Strophe 4
„Geht bloß weg ihr Blutsauger … ich schieß euch in den Kopf“ Ich versteckte mich nun … in einem großem Suppentopf Das Gescheh’n hier zu verfolgen war für mich ein großes Ding Seht ihr da auch was? Schaut mal genauer hin!
Refrain
Kann das wirklich wahr sein? Macht es wirklich Sinn? Ich sah … Mr. T im Blues Brothers Film … oh yeah
Ein internes Audit wird durchgeführt, um die Wirksamkeit, Konformität und Effektivität eines Managementsystems zu bewerten.
Vorbereitung: Erstellen Sie ein Audit-Programm
Ein Auditprogramm ist ein systematischer Ansatz zur Planung, Organisation und Durchführung von Audits in einer Organisation. Es handelt sich um einen Rahmen oder einen Leitfaden, der festlegt, wie interne oder externe Audits durchgeführt werden.
Das Auditprogramm der Organisation sollte in der Regel im Voraus bekannt gegeben werden. Dies ermöglicht den betroffenen Mitarbeitern und Abteilungen, sich auf das Audit vorzubereiten und die erforderlichen Informationen und Dokumente bereitzustellen.
Die genaue Zeitspanne, in der das Auditprogramm angekündigt wird, kann je nach Organisation und Art des Audits variieren. In der Regel wird das Auditprogramm jedoch einige Wochen oder sogar Monate im Voraus angekündigt, um ausreichend Zeit für die Vorbereitung zu gewährleisten.
Die Ankündigung des Auditprogramms sollte die folgenden Informationen enthalten:
Datum und Zeitraum des Audits: Geben Sie den genauen Zeitpunkt oder den Zeitraum an, in dem das Audit stattfinden wird. Dies ermöglicht den betroffenen Mitarbeitern, ihre Verfügbarkeit entsprechend zu planen.
Auditbereich und -ziel: Beschreiben Sie den Bereich des Managementsystems, der auditiert wird, sowie das Ziel des Audits. Dies hilft den betroffenen Mitarbeitern, sich auf die relevanten Prozesse, Verfahren und Dokumente vorzubereiten.
Kontaktpersonen: Nennen Sie die Auditoren und die Kontaktpersonen, an die sich die Mitarbeiter wenden können, wenn sie Fragen oder Bedenken haben oder weitere Informationen benötigen.
Vorbereitungshinweise: Geben Sie Anleitungen und Hinweise zur Vorbereitung auf das Audit. Dies kann beispielsweise die Bereitstellung von Dokumenten, Aufzeichnungen oder Zugang zu bestimmten Räumlichkeiten umfassen.
Die frühzeitige Bekanntgabe des Auditprogramms ermöglicht es der Organisation, einen reibungslosen Ablauf des Audits zu gewährleisten und den betroffenen Mitarbeitern die Möglichkeit zu geben, sich angemessen vorzubereiten. Es fördert auch die Transparenz und Offenheit im Auditprozess.
Schritte für die Durchführung eines internen Audits
Hier sind die grundlegenden Schritte, die bei der Durchführung eines internen Audits üblicherweise befolgt werden:
Vorbereitung:
Festlegung des Auditumfangs und -ziels: Definieren Sie den Bereich des Managementsystems, der geprüft werden soll, sowie das Ziel des Audits.
Auditplanung: Erstellen Sie einen detaillierten Auditplan, der den Zeitplan, die Auditmethoden, die zu prüfenden Dokumente und Verfahren sowie die zugewiesenen Auditoren enthält.
Auswahl des Auditteams: Benennen Sie erfahrene und qualifizierte interne Auditoren, die unabhängig und objektiv das Audit durchführen.
Durchführung des Audits:
Eröffnungsbesprechung: Beginnen Sie das Audit mit einer Eröffnungsbesprechung, um den Zweck des Audits zu erläutern, den Ablauf zu erläutern und Erwartungen zu klären.
Datenerhebung: Sammeln Sie Informationen durch Beobachtungen, Interviews mit Mitarbeitern, Überprüfung von Dokumenten und Aufzeichnungen sowie ggf. technische Prüfungen.
Bewertung und Analyse: Bewerten Sie die erhobenen Daten, um die Konformität mit den Anforderungen des Managementsystems zu beurteilen und potenzielle Schwachstellen oder Verbesserungsmöglichkeiten zu identifizieren.
Dokumentation: Halten Sie Ihre Feststellungen, Abweichungen, Empfehlungen und Verbesserungspotenziale in Auditberichten oder Checklisten fest.
Kommunikation der Ergebnisse:
Abschlussbesprechung: Halten Sie eine Abschlussbesprechung ab, um die Ergebnisse des Audits mit dem geprüften Personal zu teilen und eventuelle Missverständnisse zu klären.
Auditbericht: Erstellen Sie einen schriftlichen Auditbericht, der die Ergebnisse des Audits, die identifizierten Abweichungen und Verbesserungsvorschläge enthält.
Follow-up: Überwachen Sie die Umsetzung von Korrekturmaßnahmen und überprüfen Sie bei Bedarf die Wirksamkeit der getroffenen Maßnahmen.
Nachverfolgung:
Überwachung und Überprüfung: Überwachen Sie die Umsetzung von Korrekturmaßnahmen und überprüfen Sie deren Wirksamkeit im Laufe der Zeit.
Planung weiterer Audits: Basierend auf den Ergebnissen und Erkenntnissen des internen Audits planen Sie weitere Audits, um die kontinuierliche Verbesserung des Managementsystems sicherzustellen.
Die genaue Vorgehensweise kann je nach Organisation und Art des Managementsystems variieren. Wichtig ist jedoch, dass das interne Audit unabhängig, objektiv und systematisch durchgeführt wird, um die Konformität mit den Anforderungen festzustellen und Verbesserungspotenziale zu identifizieren.
Was steht in einem Audit-Programm nach ISO 27007?
Die Norm ISO/IEC 27007:2020 „Information technology – Security techniques – Guidelines for information security management systems auditing“ enthält Leitlinien für das Auditieren von Informationssicherheitsmanagementsystemen (ISMS). Ein Audit-Programm nach ISO 27007 umfasst typischerweise die folgenden Informationen:
Zielsetzung: Das Audit-Programm sollte seine Ziele klar definieren. Diese können beispielsweise die Bewertung der Konformität mit den Anforderungen der ISO/IEC 27001-Norm, die Identifizierung von Schwachstellen oder die Überprüfung der Effektivität des ISMS sein.
Auditbereich und Umfang: Das Audit-Programm legt den Bereich oder die Bereiche des ISMS fest, die auditiert werden sollen. Es definiert den Umfang des Audits, einschließlich der Standorte, Prozesse, Abteilungen oder Systeme, die einbezogen werden sollen.
Auditverfahren und -methoden: Das Audit-Programm beschreibt die spezifischen Verfahren und Methoden, die während des Audits angewendet werden sollen. Dies kann beispielsweise die Durchführung von Interviews, Überprüfung von Dokumenten und Aufzeichnungen, Beobachtung von Prozessen oder technische Prüfungen umfassen.
Audit-Ressourcen: Das Audit-Programm legt die erforderlichen Ressourcen für das Audit fest, einschließlich des Audit-Teams, der Zeitpläne, des Budgets und der technischen Hilfsmittel.
Zeitplan: Das Audit-Programm enthält einen Zeitplan für die Durchführung des Audits. Es legt fest, wann das Audit beginnt und endet, sowie die geplanten Aktivitäten und Meilensteine während des Auditprozesses.
Audit-Ergebnisse und Berichterstattung: Das Audit-Programm beschreibt die Erwartungen und Anforderungen an die Dokumentation der Audit-Ergebnisse. Dies umfasst die Erstellung von Auditberichten, in denen die Feststellungen, Empfehlungen, Verbesserungspotenziale und ggf. Nichtkonformitäten festgehalten werden.
Nachverfolgung und Überprüfung: Das Audit-Programm kann auch Maßnahmen zur Nachverfolgung und Überprüfung der umgesetzten Korrekturmaßnahmen enthalten, um sicherzustellen, dass festgestellte Abweichungen behoben werden und das ISMS kontinuierlich verbessert wird.
Das Audit-Programm nach ISO/IEC 27007 dient als Leitfaden für die Planung und Durchführung von ISMS-Audits. Es stellt sicher, dass das Audit effektiv und systematisch durchgeführt wird, um die Informationssicherheit zu bewerten und die Compliance mit den Anforderungen der ISO/IEC 27001-Norm sicherzustellen.