Informatik II - Ãœbung 12

Pascal Schärli

CheapHeap@pascscha.ch

11.12.2020

Nachbesprechung

Pascal Schärli 11.12.2020

Sortieren mit Suchbäumen

aufsteigend vorsortiert

absteigend vorsortiert

gut durchmischt

[1, 2, 3, 4, 5, 6, 7]
[4, 3, 6, 7, 1, 2, 5]
[7, 6, 5, 4, 3, 2, 1]

worst case:

\(O(n^2)\)

worst case:

\(O(n^2)\)

best & average case:

\(O(n \cdot log_2(n))\)

Pascal Schärli 11.12.2020

Komplexitätsanalyse und O-Notation

// Fragment 6
for (int i=0; i<n; i++)
    for (int j=0; j<n*n; j++)
        for (int k=0; k<j; k++)
            a++;

Pascal Schärli 11.12.2020

  • Zeile 2 macht, dass die inneren Loops \(n\)-mal ausgeführt werden.
  • Zeile 3 macht, dass der inneren Loop \(n^2\)-mal ausgeführt wird.
  • Der letzte Loop führt a++ \(j\) mal aus. Da \(j\) von \(0\) bis \(n^2\) geht, hat der innerste Loop auch die Komplexität \(O(n^2)\).
  • Somit hat das gesamte Fragment die Komplexität
    \(O(n*n^2*n^2) = O(n^5)\)

Komplexität

  • \(M_i' = f_i^{-1}(k \cdot f_i(M_i))\)
     
  • \(M_3' = log_2(3 \cdot 2^{M_3}) = log_2(3) + M_3 \neq log_2(3) \cdot M_3\)
     
  • \(M_4' = 2^{3 \cdot log_2(M_4)} = M_4^3  \neq 2^3 \cdot M_4\)

Pascal Schärli 11.12.2020

Vorlesung

Pascal Schärli 11.12.2020

Heaps

  • Wie in der letzten Serie gesehen hat man bei Suchbäumen das Problem, dass diese entarten könnten.
    • \(\Rightarrow\) Heaps
       
  • Ein Heap ist ein Binärbaum mit den folgenden Eigenschaften:
    1. Alle bis auf die letzte Ebene sind vollständig besetzt
    2. Die letzte Ebene wird von rechts nach links aufgefüllt
    3. Die Elemente sind niveauweise sortier:
      • Max-Heap: Alle Kinder sind kleiner als die Wurzel
      • Min-Heap: Alle Kinder sind grösser als die Wurzel

2

3

5

11

6

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

Element einfügen

  • Um ein Element einzufügen, fügt man es in der Untersten Ebene beim ersten freien Platz ein.
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird das Element so lange mit seinem Vorgänger getauscht, bis es grösser als sein Vorgänger ist.

2

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

2

Element einfügen

  • Um ein Element einzufügen, fügt man es in der Untersten Ebene beim ersten freien Platz ein.
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird das Element so lange mit seinem Vorgänger getauscht, bis es grösser als sein Vorgänger ist.

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

2

Element einfügen

  • Um ein Element einzufügen, fügt man es in der Untersten Ebene beim ersten freien Platz ein.
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird das Element so lange mit seinem Vorgänger getauscht, bis es grösser als sein Vorgänger ist.

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

2

Element einfügen

  • Um ein Element einzufügen, fügt man es in der Untersten Ebene beim ersten freien Platz ein.
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird das Element so lange mit seinem Vorgänger getauscht, bis es grösser als sein Vorgänger ist.

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

2

Wurzel entfernen

  • Um die Wurzel zu entfernen ersetzt man die Wurzel mit dem Letzten Element im Stack
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird die neue Wurzel so lange mit seinem kleinsten Kind getauscht, bis es kleiner als alle Kinder ist.

1

4

Pascal Schärli 11.12.2020

Heaps

1

4

5

7

11

6

12

9

3

4

8

5

2

Wurzel entfernen

  • Um die Wurzel zu entfernen ersetzt man die Wurzel mit dem Letzten Element im Stack
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird die neue Wurzel so lange mit seinem kleinsten Kind getauscht, bis es kleiner als alle Kinder ist.

1

4

Pascal Schärli 11.12.2020

Heaps

2

4

5

7

11

6

12

9

3

4

8

5

2

Wurzel entfernen

  • Um die Wurzel zu entfernen ersetzt man die Wurzel mit dem Letzten Element im Stack
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird die neue Wurzel so lange mit seinem kleinsten Kind getauscht, bis es kleiner als alle Kinder ist.

1

4

Pascal Schärli 11.12.2020

Heaps

2

4

5

7

11

6

12

9

3

4

8

5

3

Wurzel entfernen

  • Um die Wurzel zu entfernen ersetzt man die Wurzel mit dem Letzten Element im Stack
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird die neue Wurzel so lange mit seinem kleinsten Kind getauscht, bis es kleiner als alle Kinder ist.

1

4

Pascal Schärli 11.12.2020

2

4

5

7

11

6

12

9

4

8

5

3

Wurzel entfernen

  • Um die Wurzel zu entfernen ersetzt man die Wurzel mit dem Letzten Element im Stack
     
  • Dies könnte in einem ungültigen Heap resultieren
     
  • Deshalb wird die neue Wurzel so lange mit seinem kleinsten Kind getauscht, bis es kleiner als alle Kinder ist.

1

Heaps

Pascal Schärli 11.12.2020

Heap Sort ♥

Pascal Schärli 11.12.2020

Heap Sort ♥

  • Wie schon in der Ãœbung 2 gelernt haben, lässt sich ein Binärbaum in einem Array darstellen.
     

  • Somit kann man einen Array ohne zusätzlichen Speicherplatz sortieren:

    • Zuerst erstellen wir eine Heapstruktur im Array

    • Danach können wir immer das grösste bzw kleinste Element aus dem Heap entfernen

Pascal Schärli 11.12.2020

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

9

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

unstrukturiert

im heap

sortiert

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

1

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

1

Heap Sort ♥

7

3

9

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

2

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

3

9

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

9

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

7

9

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Heap Sort ♥

9

Pascal Schärli 11.12.2020

7

3

9

1

2

min heap (nur als visualisierung vom Array)

unstrukturiert

im heap

sortiert

Parallel processing

  • Wenn man verschiedene Tasks parallel Ausführt, kann die Laufzeit von Programmen reduziert werden.
     
  • Um dies zu ermöglichen gibt es zwei Varianten:
    • parallele Prozesse
    • parallele Threads

Pascal Schärli 11.12.2020

Parallel processing

  • Parallele Prozesse:
    • Laufen in einem anderen Kontext
    • Keinen Zugriff auf Variablen von anderen Prozessen
       
  • Parallele Threads:
    • Laufen im selben Kontext
    • Können auf Variablen von anderen Threads im selben Kontext zugreifen
    • Schnelleres Task-Switching
    • Daten können geteilt werden
    • Kann aber zu Problemen in der Synchronisation geben, wenn man Daten mit anderen Threads teilt

Pascal Schärli 11.12.2020

Multithreading - start

 public class Main {
     public static void main(String[] args) {
         for (int i = 0; i < 5; i++){
             new Worker().start();
         }
         System.out.println("Done!");
     }
 }
public class Worker extends Thread {
    static int j = 0;
    int k;
    
    @Override
    public void run() {
        for (int i = 0; i < 4000000; i++) {
            j++;
            k++;
        }
        System.out.println("k: " + k + " j:" + j);
    }
}
Done!
k: 4‘000‘000, j: 3‘752‘884
k: 4‘000‘000, j: 10‘806‘936
k: 4‘000‘000, j: 7‘307‘897
k: 4‘000‘000, j: 5‘322‘116
k: 4‘000‘000, j: 4‘366‘084
  • Mit ".start()" Kann man einen Thread starten. Dieser wird dann im Hintergrund ausgeführt, das heisst es wird nicht gewartet bis die Funktion fertig ist, sondern das Programm geht direkt weiter.
  • Die "run" Funktion vom Thread wird ausgeführt wenn ".start()" aufgerufen wird.

Pascal Schärli 11.12.2020

Multithreading - synchronized

 public class Main {
     public static void main(String[] args) {
         for (int i = 0; i < 5; i++){
             new Worker().start();
         }
         System.out.println("Done!");
     }
 }
public class Worker extends Thread {
    static int j = 0;
    int k;
    static Object lock = new Object();
    
    @Override
    public void run() {
        for (int i = 0; i < 4000000; i++) {
            synchronized(lock){
              j++;
              k++;            
            }
        }
        System.out.println("k: " + k + " j:" + j);
    }
}
Done!
k: 4‘000‘000, j: 15‘786‘100
k: 4‘000‘000, j: 18‘432‘690
k: 4‘000‘000, j: 19‘344‘207
k: 4‘000‘000, j: 19‘408‘717
k: 4‘000‘000, j: 20‘000‘000
  • Mit "synchronized" kann man gewisse Programmabschnitte synchronisieren
     
  • Man braucht ein geteiltes Objekt (hier "lock") als Schloss
     
  • Es kann immer nur ein Thread gleichzeitig im synchronisierten Bereich sein.

Pascal Schärli 11.12.2020

Multithreading - join

public static void main(String[] args) {
    Worker workers[] = new Worker[5];
    for (int i = 0; i < 5; i++) {
        workers[i] = new Worker();
        workers[i].start();
    }
    for (int i = 0; i < 5; i++) {
        try {
            workers[i].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    System.out.println("Done!");
}
k: 4‘000‘000, j: 15‘786‘100
k: 4‘000‘000, j: 18‘432‘690
k: 4‘000‘000, j: 19‘344‘207
k: 4‘000‘000, j: 19‘408‘717
k: 4‘000‘000, j: 20‘000‘000
Done!
  • Mit "join" kann man warten bis ein Thread fertig ist.
     
  • So ist es mehrere Threads zu starten und dann zu warten bis alle fertig sind.

Pascal Schärli 11.12.2020

Pascal Schärli 11.12.2020

Vorbesprechung

Pascal Schärli 11.12.2020

Heapsort Textaufgaben

  1. Wie viel Elemente sind in einem Heap der Höhe h mindestens/maximal?
     
  2. Repräsentiert ein sortiertes Array einen gültigen Heap?
    Ist die Array Repräsentation eines Heaps immer sortiert?
     
  3. Heapsort von Hand

Pascal Schärli 11.12.2020

Heapsort Programmieren

  • Implementiert Heapsort (min Max-Heap)
  • Teilt den Algorithmus in Teilprobleme auf:
    1. Heap aufbau
    2. Heap abbau
  • Verwendet dazu Hilfsfunktionen um beim einfügen/entfernen von Elementen zu helfen:
    1. raise: Element so weit wie nötig nach oben wandern lassen
      • Ist Element schon am richtigen Platz?
      • sonst swap mit parent und raise an der neuen Position rekursiv ausführen
    2. sink:Element so weit wie nötig nach unten wandern lassen
      • Ist Element schon am richtigen Platz?
      • Sonst swap mit dem grösseren Kind und sink an der neuen Position rekursiv ausführen
    3. swap, father, leftChild, rightChild

Pascal Schärli 11.12.2020

Parallelisiertes Mergesort

  public Worker(MergeSort sort, int[] items, int threadCount, int begin, int end) {
    this.sort = sort;
    this.items = items;
    this.threadCount = threadCount;
    this.begin = begin;
    this.end = end;
  }

  @Override
  public void run() {
    if(threadCount <= 1)
      // Call Mergesort function from Exercise 10
    else {
      // 1. Divde array into two parts
      // 2. Create a new worker for left half
      // 3. Create a new worker for right half
      // 4. Wait for both workers to finish
      // 5. Merge results of both workers and store it in sortedItems
    }
  }
  
  public int[] getResult() {
    return sortedItems;
  }

Pascal Schärli 11.12.2020

Rekursives Problemlösen

  • Findet eine rekursive Formel: \(f(n) = g(f(n-1))\)
     
  • Gute Ãœbung für Rekursives Problemlösen, jedoch nicht so relevant wie die ersten Aufgaben.
  • Wir haben n Rechtecke gegeben. Wie viele Rechtecke kann man mit diesen n Rechtecken als Bauklötze bauen?
  • Beispiel \(n = 4\): 8

Pascal Schärli 11.12.2020

Reversi

Pascal Schärli 11.12.2020

Viel Spass, schöne Weinachten, gute Lernphase, bleibt gesund!

Ich freue mich euch am Reversi Tournier und am PVK nochmals zu treffen.

Pascal Schärli 11.12.2020