c2b_default

GADS 2022

Uni Würzburg Grundlagen der Algorithmen und Datenstrukturen

Uni Würzburg Grundlagen der Algorithmen und Datenstrukturen

20
0.0 (0)

Kartei Details

Karten 20
Sprache Deutsch
Kategorie Technik
Stufe Universität
Erstellt / Aktualisiert 05.02.2022 / 18.09.2023
Weblink
https://card2brain.ch/box/20220205_gads_2022
Einbinden
<iframe src="https://card2brain.ch/box/20220205_gads_2022/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
Lernen

Was bedeutet der Begriff "terminierend"?

Bricht bei jeder erlaubten Eingabe nach endlich vielen Schritten ab.

Was bedeutet der Begriff "Determiniert"?

Was bedeutet der Begriff "terminierend"?

Was bedeutet der Begriff "Deterministich"?

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

Was sind die elementaren Schritte von Algorithmen?

  • Elementare Operationen: + - * 

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

  • Bedingte Ausführung: if-else 

  • Schleife: for-while

  • Unterprogramm: function def my_function()

  • Rekursion

Was sind applikative Algorithmen?

⇒ Definition von zusammengesetzten Funktionen

⇒ Verallgemeinerung der Funktionsauswertung mathematisch notierter Funktionen

⇒ Keine Variablen, sondern Rekursion

Was sind imperative Algorithmen?

⇒ Basiert auf Anweisungen & Variablen

⇒ Kann leicht durch Programmiersprachen realisiert werden

Was ist das Ziel von abstrakten Datentypen?

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

Was bedeutet der Begriff "Kapselung" im Zusammenhang mit abstrakten Datentypen?

ADT darf nur über seine Schnittstelle benutzt werden.

Was bedeutet der Begriff "Geheimnisprinzip" im Zusammenhang mit abstrakten Datentypen.

Interne Implementierung bleibt verborgen.

Bilden somit die grundlage für die OOP.

Was bedeuten die Begriffe "Operatoren" und "Axiome" im Zusammenhang mit abstrakten Datentypen?

Operators: Beschreiben die von der Schnittstelle implementierten Funktionen.

Axioms: Legen Verhalten der Operatoren mit Beispielen fest.

 

Was bedeuten die Begriffe "Konstruktor-Funktionen" und "Selektor-Funktionen" im Zusammenhang mit abstrakten Datentypen?

Konstruktor-Funktionen: Aufbauen von Elementen des ADT

Selektor-Funktionen: return Einzelteile eines Elements zurück

Wie lauten die Regeln für die Schlüssel von Maps/Dictionaries?

  • Darf nicht veränderbar sein

  • Muss eindeutig sein

Was ist TimSort?

Hybrid aus MergeSort & InsertionSort

  • Erst splitten, mit insertion sortieren und danach wieder mergen

Welche Eigenschaften sollten Hashing-Funktionen haben?

  • 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

Welche drei Methoden gibt es für den Umgang mit Kollisionen in Hashing-Algorithmen und welche Eigenschaften haben sie?

  • 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

In welchen drei Schritten wird die Korrektheit eines Algorithmus bewiesen?

  • 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

Welches sind die sechs Prinzipien der Algorithmenentwurf?

  • Schrittweise Verfahren

  • Vollständige Aufzählung

  • Greedy Verfahren

  • Divide and Conquer

  • Backtracking

  • Dynamische Programmierung

     

Wie funktioniert die "schrittweise Verfeinerung"?

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

 

Wie lauten die Regeln für Rot-Schwarz-Bäume?

  • 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

Was sind die Eigenschaften von Heaps?

  • Baum ist komplett

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

Lernen