Algorithmen und Datenstrukturen: O-Notation / Komplexität der rekursiven Fakultät

Der Algorithmus

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:

Algorithmen und Datenstrukturen: Der Merge Sort in Java

Der Algorithmus

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.

Gesamt-Komplexität

Somit ergibt sich die Gesamtkomplexität:

im Worst-, Normal- und Best-Case.

Algorithmen und Datenstrukturen: Der Bubble Sort in Java

Der Algorithmus

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

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Tausche: 6;22;2;4;10;3;9;7;5;8;1
Tausche: 2;22;6;4;10;3;9;7;5;8;1
Tausche: 1;22;6;4;10;3;9;7;5;8;2
Tausche: 1;6;22;4;10;3;9;7;5;8;2
Tausche: 1;4;22;6;10;3;9;7;5;8;2
Tausche: 1;3;22;6;10;4;9;7;5;8;2
Tausche: 1;2;22;6;10;4;9;7;5;8;3
Tausche: 1;2;6;22;10;4;9;7;5;8;3
Tausche: 1;2;4;22;10;6;9;7;5;8;3
Tausche: 1;2;3;22;10;6;9;7;5;8;4
Tausche: 1;2;3;10;22;6;9;7;5;8;4
Tausche: 1;2;3;6;22;10;9;7;5;8;4
Tausche: 1;2;3;5;22;10;9;7;6;8;4
Tausche: 1;2;3;4;22;10;9;7;6;8;5
Tausche: 1;2;3;4;10;22;9;7;6;8;5
Tausche: 1;2;3;4;9;22;10;7;6;8;5
Tausche: 1;2;3;4;7;22;10;9;6;8;5
Tausche: 1;2;3;4;6;22;10;9;7;8;5
Tausche: 1;2;3;4;5;22;10;9;7;8;6
Tausche: 1;2;3;4;5;10;22;9;7;8;6
Tausche: 1;2;3;4;5;9;22;10;7;8;6
Tausche: 1;2;3;4;5;7;22;10;9;8;6
Tausche: 1;2;3;4;5;6;22;10;9;8;7
Tausche: 1;2;3;4;5;6;10;22;9;8;7
Tausche: 1;2;3;4;5;6;9;22;10;8;7
Tausche: 1;2;3;4;5;6;8;22;10;9;7
Tausche: 1;2;3;4;5;6;7;22;10;9;8
Tausche: 1;2;3;4;5;6;7;10;22;9;8
Tausche: 1;2;3;4;5;6;7;9;22;10;8
Tausche: 1;2;3;4;5;6;7;8;22;10;9
Tausche: 1;2;3;4;5;6;7;8;10;22;9
Tausche: 1;2;3;4;5;6;7;8;9;22;10
Tausche: 1;2;3;4;5;6;7;8;9;10;22
Nachher: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

O(T(n)) = O(n²)

Algorithmen und Datenstrukturen: Der Selection Sort in Java

Der Algorithmus

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

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Tausche: 1;6;2;4;10;3;9;7;5;8;22
Tausche: 1;2;6;4;10;3;9;7;5;8;22
Tausche: 1;2;3;4;10;6;9;7;5;8;22
Tausche: 1;2;3;4;10;6;9;7;5;8;22
Tausche: 1;2;3;4;5;6;9;7;10;8;22
Tausche: 1;2;3;4;5;6;9;7;10;8;22
Tausche: 1;2;3;4;5;6;7;9;10;8;22
Tausche: 1;2;3;4;5;6;7;8;10;9;22
Tausche: 1;2;3;4;5;6;7;8;9;10;22
Tausche: 1;2;3;4;5;6;7;8;9;10;22
Nachher: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

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.

O(T(n)) = O(n²)

Algorithmen und Datenstrukturen: Der Insertion Sort in Java

Der Algorithmus

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

Neuronale Netze (KNN) / KI-Training: Das Format / der Aufbau vom MNIST-Datensatz (MNIST Datenbank) der Dateien t10k-images-idx3-ubyte, t10k-labels-idx1-ubyte, train-images-idx3-ubyte, train-labels-idx1-ubyte

Intention

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

C#.NET: QR Code erzeugen mit QRCoder.dll / QR-Codes mit C# oder VB.NET erstellen / generieren

Beispiel: Kostenloser QR Code Generator

Hier ein kostenloser QR Code Generator, welcher in ASP.NET mit C# als Backend realisiert wurde:

https://www.my-asp-experiments.com/QRCode

Beschreibung

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)NumerischAlphanumerischBinärKanji
LMQHLMQHLMQHLMQH
1(21)4134271725201610171411710874
2(25)7763483447382920322620142016128
3(29)1271017758776147355342322432262015
4(33)187149111821149067507862463448382821
5(37)255202144106154122876410684604465523727
6(41)32225517813919515410884134106745882654536
7(45)37029320715422417812593154122866495755339
8(49)46136525920227922115712219215210884118936652
9(53)552432312235335262189143230180130981411118060
10(57)6525133642883953112211742712131511191671319374
11(61)77260442733146836625920032125117713719815510985
12(65)88369148937453541929622736728720315522617712596
13(69)1022796580427619483352259425331241177262204149109
14(73)1101871621468667528376283458362258194282223159120
15(77)1250991703530758600426321520412292220320254180136
16(81)14081082775602854656470365586450322250361277198154
17(85)15481212876674938734531408644504364280397310224173
18(89)172513469487461046816574452718560394310442345243191
19(93)1903150010638131153909644493792624442338488384272208
20(97)2061160011599191249970702557858666482382528410297235
21(101)22321708122496913521035742587929711509403572438314248
22(105)2409187213581056146011348236401003779565439618480348270

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

GitHub

https://github.com/codebude/QRCoder

.NET CLI

dotnet add package QRCoder --version 1.4.3

Package Manager

NuGet\Install-Package QRCoder -Version 1.4.3

Package Reference

<PackageReference Include="QRCoder" Version="1.4.3" />

Paket CLI

paket add QRCoder --version 1.4.3

Script & Interactive

#r "nuget: QRCoder, 1.4.3"

Cake

// 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();
        }
    }
}

AngularJS + NodeJS Schulung

Vorraussetzung

Installation der folgenden Komponenten:

NodeJS

Konsolenbefehle

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

Lösung 2

class Student {
    name: string;
    mNr: number;

    constructor(_name: string, _mNr: number) {
      this.name = _name;
      this.mNr = _mNr;
    }

    getLabel() {
        return `Student ${this.name} mit Matrikelnummer ${this.mNr}`;
    }
  }

Aufgabe 3: Auslagern in andere Dateien

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:

export class Student {
    oldNumber:number = -1;
    name: string;
    mNr: number;

    constructor(_name: string, _mNr: number) {
      this.name = _name;
      this.mNr = _mNr;
    }

    getLabel() {
        return `Student ${this.name} mit Matrikelnummer ${this.mNr}`;
    }
  }

Aufgabe 4: ESLint für sauberen Code

Säubere den Code mit ESLint

Ansatz 4

Führe die folgenden Konsolenbefehle aus um ESLint zu verwenden:

npm init @eslint/config
npx eslint src/hello.ts

Beobachtung 4

ESLint meckert:

Lösung 4

Ändere den Code so, dass aus den Variablen aus Lösung 3 anstelle von let das Keyword const verwendet wird:

import {Student} from "./student"

const s: Student = new Student("Max", 123456);
const label: string = s.getLabel();
console.log(label); // "Student Max mit Matrikelnummer: 123456";

ADHS in Mexico (feat. Blues Brothers, George Clooney, Mr. T, Santanico Pandemonium) | From dusk till dawn @ Titty Twister

YouTube

„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

Ergebnisse des Blues Contests

ISO 27001: Interne Audits planen und durchführen

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.

by Björn Karpenstein