AD - Algorithmen FS17
HSLU Informatik - Algorithmen & Datenstrukturen - Teil Algorithmen - FS17
HSLU Informatik - Algorithmen & Datenstrukturen - Teil Algorithmen - FS17
Kartei Details
| Karten | 62 |
|---|---|
| Lernende | 23 |
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 20.06.2017 / 14.06.2023 |
| Weblink |
https://card2brain.ch/box/20170620_ad_algorithmen_fs17
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170620_ad_algorithmen_fs17/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Was ist ein Algorithmus?
Ein Algorithmus ist ein präzise festgelegtes Verfahren zur Lösung eines Problems; genauer gesagt von einer Problem- Klasse beinhaltend (unendlich) viele gleichartige Probleme.
Algorithmus = Lösungsverfahren
Was sind gleichwertige Algorithmen?
Verschiedenen Algorithmen, die alle das problem einer Problemklasse lösen können.
Wie beweist man die Gleichwertigkeit von Algorithmen?
Die Gleichwertigkeit von Algorithmen allgemein zu beweisen ist ein unlösbares Problem. Dies bedeutet, dass es kein Java-Programm geben kann, das den Quellcode von zwei Implementationen einliest und feststellt, ob sie gleichwertige Algorithmen repräsentieren oder nicht!
Weshalb hängen Algorithmen und Datenstrukturen eng zusammen?
Algorithmen operieren auf Datenstrukturen und Datenstrukturen bedingen spezifische Algorithmen.
Definieren Sie Komplexität im Bezug auf Algorithmen.
Wie hängt der Ressourcenbedarf von den Eingabedaten ab?
Ressourcenbedarf = f ( Eingabedaten )
Ressourcenbedarf:
- Rechenzeit → Zeitkomplexität
- Speicherbedarf → Speicherkomplexität
Eingabedaten:
- Grösse der Datenmenge
- Grösse eines Datenwertes
Zählen Sie die Wichtigsten Ordnungsfunktionen in der richtigen Reihenfolge auf.
Konstant O( 1 ) Hashing
Logarithmisch O( ln( n ) ) binäres Suchen
Linear O( n ) Suchen in Texten
n log n O( n · ln( n ) ) schlaues Sortieren
Polynomial O( n m ) einfaches Sortieren
Exponential O( d n ) Optimierungen
Fakultät O( n ! ) Permutationen, TSP
Was sind die Schwächen der Big-O-Notation
- Die Ordnung ignoriert konstante Faktoren. Diese können aber praktisch relevant sein!
- Die Ordnung berücksichtigt das Verhalten bei kleinen n nicht. Langsamere Algorithmen sind aber bei kleinen n oft auch brauchbar oder gar die bessere Wahl!
- Die exakte mathematische Analyse von vielen Algorithmen ist schwierig oder sogar unmöglich!
- Häufig muss man bei der Analyse differenzieren (Best-, Worst-, Average Case). Häufig ist der mittlere Fall ein besseres Mass für die Leistung eines Algorithmus, als der schlimmste.
Was haben Algorithmen und Datenstrukturen mit Selbstähnlichkeit und Selbstbezug zu tun?
Viele Algorithmen und Datenstrukturen sind von Natur aus selbstähnlich bzw. selbstbezüglich:
- Der ggT von (21, 15) ist gleich dem ggT von (21-15, 15).
- Ein Verzeichnis enthält Dateien und andere Verzeichnisse.
- Ein Ausschnitt einer Matrix, einer Liste, eines Baumes, eines Graphen ist wieder eine Matrix, eine Liste, ein Baum, ein Graph.
⇒ Grundlage für Rekursion
Definieren sie im Codebeispiel die Rekursionsbasis und die Rekursionsvorschrift.
Wozu dient der Heap der JVM?
In diesem Speicherbereich werden die Objekte gespeichert, d.h. deren Instanzvariablen bzw. Zustände. Nicht mehr referenzierbare Objekte werden durch den Garbage Collector (GC) automatisch gelöscht.
Wozu dient der Call Stack der JVM?
Bei der Ausführung eines Programms «eine Kette» von Methoden abgearbeitet. Jeder Methodenaufruf bedingt gewissen Speicher, insbesondere für Parameter und lokalen Variablen. Dazu dient der Call Stack. Ein neuer Methodenaufruf bewirkt, dass der Call Stack wächst bzw. darauf ein zusätzlicher Stack Frame angelegt wird.
Was haben Rekursionen und Iterationen gemeinsam?
Sie sind gleich mächtig:
- Die Menge der berechenbaren Problemstellungen bei Verwendung der Rekursion und Verwendung der Iteration ist gleich.
- Eine rekursive Implementation lässt sich grundsätzlich immer in eine gleichwertige iterative Implementation umprogrammieren und umgekehrt.
Was sind die Motivationen für Rekursion?
- mächtiges Lösungskonzept
- häufig einfache und elegante Problemlösungen
- weniger Quellcode
- Korrektheit häufig einfacher zu zeigen
- Gewisse Programmiersprachen (zB Lisp, Prolog) kennen nur Rekursion!
Was sind die Tücken der Rekursion?
- schnell sehr viele Methodenaufrufe
- tendenziell langsamere Programmausführung
- grosser Speicherbedarf auf dem Call Stack
- Gefahr eines Stack Overflow!
⇒ Bei Wahlmöglichkeit eine iterative Implementierung bevorzugen!
Was ist die Motivation fürs Sortieren?
Schneller & Effizienter Zugriff auf gewünschte Daten.
Beispiele:
- Person mit bestimmter ID
- Prozess mit höchster Priorität
- Zugsverbindung mit Abfahrtszeit früher als x
- Taxi, das am nächsten ist
Was sind die Voraussetzungen fürs Sortieren?
Eine Menge an Datenelementen die:
- eine Totale Ordnung haben (x ist kleiner/grösser/gleich y)
- vergleichbar sind (z.B. durch einen Key/Schlüssel)
Welche Java-Interfaces sind die Voraussetzung fürs Sortieren?
- Interface Comparable<T> mit int compareTo(T o)
→ für die natürliche Ordnung - Interface Comparator<T> mit int compare(T o1, T o2)
→ für jede spezielle Ordnung.
Welche Zeitkomplexität besitzen vergleichsbasierte-Sortierverfahren bestenfalls?
O(n * log n)
Welche Zeitkomplexität besitzen Radix-Sortierverfahren bestenfalls?
O(n)
Definiere internes Sortieren.
- Daten liegen im Arbeitsspeicher vor.
- Direktes Vergleichen der Daten möglich.
- Internes Sortieren ist primär von Bedeutung.
- Beispiel: Sortieren von Arrays
Definiere externes Sortieren.
- Daten liegen in einem externen Massenspeicher vor.
- Nur Lesen und Schreiben möglich, kein direktes Vergleichen!
- Interner Speicher ist für alle Daten zu klein!
- Beispiel: Sortieren von sequentiellen Dateien
Was garantiert ein stabiler Sortieralgorithmus?
Der Algorithmus garantiert, dass durch das Sortieren die Reihenfolge unter gleichen Datenelementen nicht ändert.
Beislpiel:
Ausgangssituation vor dem Sortieren:
- Mehrere Datenelemente haben den gleichen Schlüssel bzw. sind gleich, z.B. [D1/22, D2/7, D3/22, D4/5, D5/71, D6/10].
- D1 und D3 haben den gleichen Schlüssel 22 bzw. sind gleich.
Danach:
- [D4/5, D2/7, D6/10, D1/22, D3/22, D5/71].
- Das Datenelement D1 steht nach wie vor links und D3 rechts.
Wie differenziert man Zeitkomplexität häufig praktisch?
Bei der Zeitkomplexität unterscheidet man häufig:
- Average Case (Mittel über alle Permutationen)
- Worst Case
- Best Case (nicht besonders wichtig)
Denn nicht nur die Anzahl der Elemente ist ausschlaggebend für die Geschwindigkeit, sondern auch die Werte. Falls die zu sortierenden Werte z.B. bereits mehrheitlich aufsteigend vorliegen, arbeitet ein Algorithmus vielleicht wesentlich schneller.
Nenne 4 einfache Sortieralgorithmen.
- Direktes Einfügen (Insertion Sort)
- Direktes Auswählen (Selection Sort)
- Direktes Austauschen (Bubble Sort)
- Shellsort
Was sind die Best-, Worst- und Average Case Werte für Insertion Sort?
- Best Case = O(n)
- Worst Case = O(n2)
- Average Case = O(n2)
Ist Insertion Sort stabil?
Ja
Was sind die Best-, Worst- und Average Case Werte für Selection Sort?
- Best Case = O(n2)
- Worst Case = O(n2)
- Average Case = O(n2)
Ist Selection Sort stabil?
Grundsätzlich Nein.
Mann kann den Algorithmus aber mit einer kleinen änderung stabil machen:
Anstatt das kleinste gefundene Element mit dem Ersten zu tauschen, fügt man es an erster Stelle ein und schiebt den Rest um eine Stelle nach rechts.
Was sind die Best-, Worst- und Average Case Werte für Bubble Sort?
- Best Case = O(n)
- Worst Case = O(n2)
- Average Case = O(n2)
Ist Bubble Sort stabil?
Ja
Was sind die Best-, Worst- und Average Case Werte für Shell Sort?
- Best Case = O(n log n)
- Worst Case = O(n2)
- Average Case = O(n2)
Implementiere Insertion Sort in Java.
Implementiere Selection Sort in Java.
Implementiere Bubble Sort in Java.
Implementiere Shell Sort in Java.
Nenne 3 höhere Sortier Algorithmen.
- Quicksort
- Mergesort
- Heapsort
Ist Quicksort stabil?
Nein
Was sind die Best-, Worst- und Average Case Werte für Quicksort?
- Best Case = O(n log n)
- Worst Case = O(n2)
- Average Case = O(n log n)
Implementiere Quicksort in Java.
Nach welchem Lösungsprinzip arbeitet Quicksort?
Teile und Herrsche
