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();
}
}
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:
A worksheet within a workbook shall be deleted via VBA in Excel. Ein Arbeitsblatt soll in einer Arbeitsmappe gelöscht werden.
Approach / Ansatz
Create a new SUB method with the worksheet name as parameter / Definition einer neuen Sub-Methode mit Übergabe des Namen des zu löschenden Arbeitsblattes
Iterate all worksheets / über alle Arbeitsblätter iterieren
Check the name of the current worksheet / Namen der Worksheets prüfen
When the name matches the SUB paramter, the worksheet will get deleted via .Delete method / Wenn der Name des übergebenen Parameters entspricht, wird das worksheet gelöscht mit der .Delete Methode
Solution / Lösung
Sub DeleteWorksheet(worksheetName As String)
Dim ws As Worksheet, wb As Workbook
Set wb = ActiveWorkbook
Application.DisplayAlerts = False
For Each ws In wb.Worksheets
If ws.Name = worksheetName Then
ws.Delete
Exit For
End If
Next
Application.DisplayAlerts = True
End Sub
AutoResetEvent bietet über einen globalen oder übergeordneten Kontext die Möglichkeit durch den Aufruf der WaitOne-Methode innerhalb des Thread-Codes, Threads zu blockieren bis ein Signal aus einem anderem Kontext gesendet wird. Der andere Kontext sollte dabei auch Zugriff auf das steuernde AutoResetEvent-Objekt haben.
Konstruktor-Parameter
AutoResetEvent event_1 = new AutoResetEvent(true);
AutoResetEvent event_2 = new AutoResetEvent(false);
Ein Thread, welcher event_1.WaitOne() aufruft, blockiert nicht da signaled auf TRUE steht.
Ein Thread, welcher event_2.WaitOne() aufruft, blockiert da signaled über den Konstruktor mit FALSE initialisiert wurde.
Ruft ein Thread die Methode „WaitOne“ auf, wird dieser allerdings nur blockiert, wenn AutoResetEvent mit false initialisiert wurde.
Event auf „signaled“ ohne Konstruktor setzen
Um die blockierten Threads nun aus einem anderen Kontext, welcher auch Zugriff auf das AutoResetEvent-Objekt haben muss, zu steuern können die Methoden .Set() und .Reset() des AutoResetEvents aus dem steuerenden Kontext heraus genutzt werden:
// Setzt den Status auf "nicht signalisiert" / "non signaled"
// Threads blockieren nach Aufruf von AutoResetEvent.WaitOne()
event_1.Reset();
// Setzt den Status auf "signalisiert" / "signaled"
// Threads blockieren NICHT nach Aufruf von AutoResetEvent.WaitOne()
event_2.Set();
Nur einer, der wartenden Threads erhält ein Signal wenn Set() aufgerufen wird. Will man alle wartenden Threads befreien, muss man Set() mehrfach aufrufen.
Unterschied zu ManualResetEvent
ManualResetEvent signalisiert allen wartenden Threads, dass diese die WaitOne()-Methode passieren dürfen. Sie ist also wie eine Tür, die sich für alle öffnet. ManualResetEvent.Reset(); schließt, die Tür, ManualResetEvent.Set(); öffnet die Tür.
AutoResetEvent signaliert maximal einem wartendendem Thread, dass er nach Aufruf der AutoResetEvent.WaitOne()-Methode weitermachen darf. Um alle blockierten Threads zu befreien, muss AutoResetEvent .Set() entsprechend der Anzahl wartender Threads aufgerufen werden. Wenn kein AutoResetEvent auf „signaled“ gesetzt wurde, wird auch niemand durchgelassen. Das entspricht der Warteschlange auf Ämtern oder Ärzten, wo man eine Nummer ziehen muss und immer nur einer aufgerufen wird.
