GADS 2022

Was bedeutet der Begriff "terminierend"?

Determiniert + Der als nächstes auszuführende Schritt ist immer klar.

• Elementare Operationen: + - * 

• Sequentielle/Parallele Ausführung (Ein/Mehrere Prozessoren)

• Bedingte Ausführung: if-else 

• Schleife: for-while

• Unterprogramm: function def my_function()

• Rekursion

⇒ Definition von zusammengesetzten Funktionen

⇒ Verallgemeinerung der Funktionsauswertung mathematisch notierter Funktionen

⇒ Keine Variablen, sondern Rekursion

⇒ Basiert auf Anweisungen & Variablen

⇒ Kann leicht durch Programmiersprachen realisiert werden

Beschreibung von Datenstrukturen unabhängig von ihrer späteren Implementierung

ADT darf nur über seine Schnittstelle benutzt werden.

Interne Implementierung bleibt verborgen.

Bilden somit die grundlage für die OOP.

Operators: Beschreiben die von der Schnittstelle implementierten Funktionen.

Axioms: Legen Verhalten der Operatoren mit Beispielen fest.

Konstruktor-Funktionen: Aufbauen von Elementen des ADT

Selektor-Funktionen: return Einzelteile eines Elements zurück

• Darf nicht veränderbar sein

• Muss eindeutig sein

Hybrid aus MergeSort & InsertionSort

• Erst splitten, mit insertion sortieren und danach wieder mergen

• Muss determiniert sein

• Soll eine Gleichverteilung schaffen

• Soll effizient berechenbar sein

• Kollisionsvermeidung wichtig

• Abhängig vom Datentyp der einzufügenden Elemente

• Für Integer oft h(i) = i mod N

  • N soll eine große Primzahl sein

• Für andere Datentypen: Rückführung auf Integer

• Verkettung

  • Elemente an der berechneten Stelle in einer verketteten Liste speichern

  • Kann bei ungünstiger Hashfunktion zu linearer Liste entarten.

  • Alternativ: Suchbaum statt liste

• Lineares Sondieren

  • Wenn T[h(e)] bereits besetzt ist, versuche die nächste freie Stelle in der Liste zu finden. 

• Quadratisches Sondieren

  • Wie lineares sondieren, aber statt +1, +2, +3, versuche +1, +4, +9

  • N soll ein Primzahl werden

• Spezifikation:

  • Eindeutige Festlegung der berechneten Funktion bzw. des Terminierungsverhaltens

• Verifikation:

  • Formaler Beweis der Korrektheit bezüglich einer formalen Spezifikation - innere Sicht

• Validation:

  • (nicht-formaler) Nachweis der Korrektheit bezüglich einer informellen oder formalen Spezifikation (etwa systematisches Testen) - äußere Sicht

• Schrittweise Verfahren

• Vollständige Aufzählung

• Greedy Verfahren

• Divide and Conquer

• Backtracking

• Dynamische Programmierung

   

• Definition in Pseudo-Code

• Schrittweise Verfeinerung des pseudo-Codes durch genauere Spezifikation

• Ersetzen von Pseudo-Code durch verfeinerten Pseudo-Code oder Code

Für alle Probleme anwendbar, um die Vorgehensweise zu verstehen und zu spezifizieren.

• Wurzel ist immer Schwarz

• Jeder Knoten ist entweder rot oder schwarz

• None(blatt) Knoten sind Schwarz

• Zwei rote Knoten hintereinander sind nicht erlaubt

• Jeder Pfad von jeder Knoten zu einem Blatt hat die gleiche Anzahl schwarzer Knoten

• Baum ist komplett

• Schlüssel jedes knotens ist kleiner/gleich die Schlüssel seiner Kinder