endlich
bzgl. der Beschreibung endlicher Text, endliches Alphabet,
endliche Graph-Knoten
terminierend
kommt zu einem Ende
deterministisch
bei gleicher Eingabe wird die gleiche Ausgabe berechnet/erzeugt
Zeit (Komplexitätsmaß)
Anzahl der elementaren Berechnungen die zur Lösung eines Problems nötig sind
Speicher (Komplexitätsmaß)
Anzahl der Speicherzellen, die bei der Berechnung eines Problems benötigt werden
Beschreibung (Komplexitätsmaß)
Größe des Programms, das ein Problem löst
Laufzeitabschätzung für den BubbleSort
Laufzeitabscäatzung für den QuickSort
BFS
Breitensuche - Breadth First Search traversal method
DFS
Tiefensuche - Depth First Search traversal method
Was braucht man um einen Baum zu rekonstruieren ?
Inorder-Notation
einer Preorder- oder Postorder-Notation
Heap Sort erzeugen
Die Knoten werden in umgekehrter BFS-(LR)-Reihenfolge von unten beginnend auf die Heap-Bedingung geprüft (Blätter können übersprungen werden, da sie automatisch Heaps sind) und lässt diese ”auf dem Pfad des größten Sohns einsickern”, bis der jeweilige Knoten größer als beide Kinder oder gleich groß ist
Heap sortieren
Der Wurzelknoten wird aus dem Baum entfernt und an seiner Stelle wird der nach BFS-LR-Reihenfolge zuletzt eingefügte Knoten gesetzt. Die Heap-Bedingung muss nur in der Wurzel durch ”Einsickern” wieder hergestellt werden. Dann wird dieser Vorgang wiederholt, bis der Baum leer ist
Entscheidungsgehalt des Alphabets
Mit wie vielen Bits wäre ein Text mit den gegebenen Häufigkeiten zu codieren, wenn alle Symbole mit der gleichen Anzahl Bits codiert werden?
Informationsgehalt berechen
Zunächst sind die relativen Häufigkeiten pi der Symbole zu bestimmen.
Anschließend lässt sich über Hi = −ld pi der Informationsgehalt der einzelnen Symbole bestimmen.
Quellenentropie H
Hi : Informationsgehalt
pi : relative Häufigkeit
Entropie HHuff
Fließkommazahl float
127 / 8Bits
23 Bits Mantisse
Fließkommazahl double
52 Bits Mantisse
Wie muss eine Liste sortiert sein, die mit dem Bubblesort aufsteigend sortiert werden sol, damit:
der Worst Case eintritt?
der Average Case eintritt?
der Best CAse eintritt?
absteigend sortiert
unsortiert
aufsteigend sortiert
Welche zeitliche Komplexität besitzt das Bubblesort-Verfahren
OWorstCase(Bubblesort(n)) = n^2
OAverageCase(Bubblesort(n)) = n^2
OBestCase(Bubblesort(n)) = n
Was passiert während der Ausführung des Quicksort-Verfahrens bei der Pivotisierung?
ein Pivotelement wir ausgesucht (zufälli, Mitte, Median)
Die Elemente werden bei aufsteigender Sortierung solange vertauscht, bis alle Elemente größer-gleich) als Pivot rechts davon liegen, der Rest links
Was komplettiert das Qicksort-Verfahren nach dem Pivotisierungs-Schritt?
Die rekursive Fortsetzung der Pivosierung in den Teillisten, bis diese nur noch z.B. einelementig sind
Welche zeitliche Komplexität hat das Quicksort-Verfahren im Worst Case und wie muss die Liste sortiert sein ?
OWorstCase(n) = n^2
Tritt ein, wenn bei jeder Pivotisierung das größte oder kleinste Element der Teilliste als Pivot gewählt wird
Welche zeitliche Komplexität besitzt das Quicksort-Verfahren
OAverageCase(Bubblesort(n)) = n * ld n
OBestCase(Bubblesort(n)) = n * ld n
Eigenschaften von variablen
Name
Typ
Speicheradresse
Wert
Ganzzahldatentypen
Gleitkommadatentypen
Zuletzt geändertvor 9 Monaten
