Algorithmik Flashcards
Welche Arten von Algorithmen gibt es?
- Such- und
- Sortieralgorithmen
Welche Arten von Vorgehensweisen gibt es bei Algorithmen?
- rekursiv
- iterativ
Was ist ein iterativer Algorithmus?
- läuft nur schrittweise ab
- basiert auf klassischen Schleifen und Vertweigungen
- läuft linear ab
- so lange wiederholt, bis zu Lösung des Problems
Was ist ein rekursiver Algorithmus?
- ruft sich selbst mit neuen Parametern wieder auf
- Problem wird in einzelne Teile aufgeteilt
- Arbeit nur in einzelnen Schritten (Arbeitsteilung)
- Am Ende eird der jeweilige Teil an die nächst höhere Funktion zurückgegeben
- bis die Startfunktion wieder erreicht wurde
- Lösung der Einzelteile ergibt die gesamte Lösung
Was ist der Rekursionsanker?
Verhindert eine Endlosschleife, ist ein Abbruch Statement und beendet die Rekursion
Wann wird Rekursion benutzt?
- Wenn ein Problem in mehrere Einzelteile zerteilbar ist und sich auf einen einfachen Fall reduzieren lässt
- oft für die Suche in nicht-linearen Datenstrukturen (Bäume, Graphen, …)
Wie überprüft man rekursiv ein Palindrom?
Welchem (umgangssprachlichen) Prinzip folgt die Rekursion?
Teilen und Herrschen
Das eigentliche Problem wird so lange rekursiv in kleinere und einfachere Teilprobleme zerlegt, bis es beherrschbar wird. Aus den Teillösung wird dann am Ende eine Lösung für das Gesamtproblem rekonstruiert.
Was ist Backtracking?
- Suchalgorithmus
- Wenn erkannt wird, das eine Teillösung nicht zum Ziel führt, werden die letzten Schritte zurüclgenommen und es werden alternative Wege ausprobiert
- Es werden so lange verschiedeen Wege probiert, bis der Algorithmus zur Lösung kommt oder alle Möglichkeiten ausgeschöpft sind
Welchem Prinzip folgt das Backtracking?
trial and error
Was ist über die Dauer des Backtrackings zu sagen?
Ist durch das zufällige Vorgehen nur schwer einschätzbar.
Wie stellt man in einem Flussdiagramm / PAP eine Aktion/Ausführung dar?
Mit einem Rechteck
Wie stellt man in einem Flussdiagramm / PAP eine Verzweigung dar?
Mit einer Raute
Wie stellt man in einem Flussdiagramm / PAP eine Grenzstelle dar?
Mit einem Rechteck mit runden Ecken
Wie stellt man in einem Flussdiagramm / PAP einen Input/Output dar?
Mit einem Parallelogramm
Wie stellt man in einem Struktogramm eine Anweisung dar?
Mit einem Rechteck
Wie stellt man in einem Struktogramm eine Verzweigung dar?
Wie stellt man in einem Struktogramm eine Mehrfachauswahl dar?
Wie stellt man in einem Struktogramm eine While-Schleife dar?
Wie stellt man in einem Struktogramm eine Do-While-Schleife dar?
Wie stellt man in einem Struktogramm eine For-Schleife dar?
Wie stellt man in einem Struktogramm einen Methodenaufruf dar?
Was muss man unbedingt implementieren, damit man einen binären Suchbaum erstellen kann?
In der Klasse der Objekte, die gespeichert werden sollen, muss comparableContent implementiert werden
public class kName implements comparableContent {
[…]
}
Wann kann man beim Djkstra Algorithmus sicher sein, dass kein kürzere Weg zu einen Knoten G vorhanden ist?
Wenn dieser Knoten G aus der Warteschlange gelöscht wurde.
Wie läuft der Djkstra Algorithmus ab?
- Falls die Kantengewichte plus das eigene summierte Kantengewicht kleiner zu einem bestimmten Knoten, als das bereits vorhanden angegebene ist, wird es zu dem Knoten mit “Kantengewicht plus das eigene summierte Kantengewicht” aktualisiert
- Die Nachbarknoten werden aufsteigend sortiert in die Warteschlange eingefügt
- Ersten Knoten aus der Wartschlange nehmen und Schritt 1 wiederholen, bis die Warteschlange leer ist
Erkläre die Methodik des Bubble Sorts
- Es werden zwei Zahlen miteinander verglichen, wenn die hintere kleiner ist, wenn die beiden Zahlen ausgtauscht, wenn nicht, passiert nichts
- es wird ein weiter gegangen und Schrit 1 wiederholt, bis man am Ende der Liste angekommen ist
Nenne Best, Average und Worst Case des Bubblesortst
Best Case: n
Average Case: n2
Worst Case: n2
Nenne Best, Average und Worst Case des Selectionsorts
Best Case: n2
Average Case: n2
Worst Case: n2
Erkläre die Methodik des Selectionsorts
- Man sucht die kleinste Zahl aus der Datenmenge und tauscht sie mit der Zahl, an der ersten Stelle
- Schritt 1 wiederholt man mit dem Rest der Liste
Nenne Best, Average und Worst Case des Insertionsort
Best Case: n
Average Case: n2
Worst Case: n2
Erkläre die Methodik des Insertionsorts
Man nimmt einzeln die Elemente aus der Liste und verlegt sie nach vorne: So lange sie größer sind, als der vorderste Wert und die darauf folgenden Werte, geht man einen Schritt weiter, bis man den Plaz gefunden hat, an dem der Wert eingefügt werden soll.
Erkläre die Methodik des Quicksorts
Nenne Best, Average und Worst Case des Quicksorts
Best Case: n*log(n)
Average Case: n*log(n)
Worst Case: n2
Erkläre die Methodik des Quicksorts
- Man nimmt sich ein Pivot-Element
- Man packt alle kleineren Werte auf die linke Seite des P-Elements und alle größeren auf die rechte
- mit den Teillisten (l und r) fängt man wieder bei Schritt 1 an
Nenne Best, Average und Worst Case der linearen Suche
Best: 1
Average: n/2
Worst: n
Erkläre die Methodik der binären Suche
- Man vergleicht den Wert mit dem Wert aus der Mitte der Liste
- Wenn eigener Wert größer, macht man mit der Mitte der rechten Liste weiter, sonst links
- man wiederholt Schritt 2
Was ist Hashing?
Ein Prinzip zum Speichern von Daten, durch eine Formel wird entschieden, an welche Stelle ein Wert in einem Array gespeichert werden soll.
Was sind Vorteile und Nachteile des Hashing?
Vorteile
- prinzipiell schnelle Suche
- möglicherweise hohe Suchaufwand, bei Kollisionen
- schlechte Hshingformel
Nachteile
- meist 20-30% mehr Speicher nötig
- möglicherweise hohe Speicheraufwand, bei Kollisionen
- schlechte Hshingformel
Was macht eine gute Hashfunktion aus?
Am Ende modulo n wobei n mindestens die Anzahl der benötigten Speicherstellen beträgt
(zweite Funktion beim doppelten Hashing ausgenommen)
Was ist das geschlossene Hashing mit offener Adressierung?
Bei einer Kollision wird zwangsweise ein neuer Speicherplatz für den Wert gesucht
Erläutere das linerare Sondieren und wieso es schlecht ist
Bei einer Kollision, wird der Wert in das nächstmögliche Feld geschrieben
- kann zu hohen (überdurchschnittlichen) Suchzeiten führen
- es bilden sich schnell Cluster
Erläutere das quadratische Sondierenn und ihre Nachteile
Ein quadratische Funktion berechnet bei einer Kollision eine neue Speicherzelle
- führt bei einer schlechten Hashfunktion auch zu langen Suchezeiten
- es bilden sog. sekundäre cluster
Was sind primäre und sekundäre Cluster
- Primäre bilden sich eng um den Hashwert und bei ihnen gilt, je größer sie werden, desto extrem wahrscheinlicher ist die weitere Clusterbildung
- Sekundäre Cluster, dessen Werte entfernen sich immer weiter (quadratisch) von dem Hashwert weg und sind deswegen akzeptabler, als primäre Cluster, da keine wirklich großen Cluster enstehen
Erläutere das Sondieren durch doppeltes Hashen und dessen Vorteile
Man hasht pro Kollision noch einmal, undzwar beim zweiten mal mit einer neuen Hashfunktion
- kaum Clusterbildung
Was ist das offen Hashing mit geschlossener Sondierung?
Bei eine Kollision wird ein Array mit den dort hingehörenden Werten erstellt -> 2D-Array
Nenne Vor- und Nachteile des Sondierens durch Verkettung
- gute ertwartbare Suchzeit
- Listenoperationen sind langsam
Erkläre das Prinzip der Nebenläufigkeit
- Mehrere Aufgaben werden parallel ausgeführt
Was ist ein Thread?
eine Reihe von Aufgaben, die parallel zu anderen Aufträgen abgearbeitet werden
Was ist eine echte Nebenläufigkeit?
- Zwei oder mehrere Aufträge können unabhängig voneinander bearbeitet werden -> Mehrkernprozessoren
- oft genutzt bei Netzwerken mehrerer Rechner
Was ist die scheinbare Nebenläufigkeit?
Nach einer Zeit wird der eine Prozess schlafen gelegt und ein anderer fortgeführt
Es sieht so aus, als wenn die Prozesse nebenher laufen, obwohl in Realität in Bruchteilen einer Sekunde zwischen den einzelnen Threads gewechselt wird, sodass kurz an einem Auftrag gearbeitet wird und dann zum nächsten gegangen wird.
