Wachstum von Funktionen Flashcards
Was ist das asymptotische Verhalten und wie analysiert man es?
Das asymptotische Verhalten beschreibt, wie die Laufzeit sich bei steigender Größe von Eingabewerten verhält.
Man abstrahiert den Term, der den höchsten Exponenten bzw. das höchste Wachstum hat und schreibt es als O(f(n)).
Welche Grenzen gibt es und wie sind ihre Definitionen?
Welche Strategie steckt hinter dem Stack und welche Methoden hat er?
last-in, first-out Strategie
Operationen sind alle in O(1)
Operation INSERT -> PUSH (S,e)
Operation DELETE -> POP(e) (gibt ebenfalls oberstes Objekt zurück)
Operation STACK-EMPTY() (gibt boolean zurück)
Wie heißt das Attribut beim Stack und wann kommt es zu fehlern beim Stack?
- Attribut S.top gibt das zuletzt abgelegte Element zurück und ist immer das oberste Element des Stapels
- Wenn S[S.top] = 0 -> Stapel leer
- Wenn Stapel leer ist und Element entfernt wird -> stack underflow
- Wenn S.top > n und möchten Element anhängen -> stack overflow (n ist maximale Anzahl an Objekten im Stack)
Welche Strategie verfolgt die Warteschlange und welche Operationen hat sie?
Strategie: First-in, First-out
Operationen sind alle in O(1)
Operation: INSERT -> ENQUEUE(Q,e)
Operation DELETE -> DEQUEUE(Q,e) (gibt ebenfalls das Element zurück)
Besitzt zwei Attribute head und tail
Welche Attribute hat die Warteschlange und wann kommt es zu fehlern?
- Q.kopf -> gibt den Anfang der Schlange zurück
- Q.ende -> gibt nächst mögliche Stelle für ein Element zurück (einen hinter dem letzten Element)
- Wenn Q.kopf = Q.ende -> Schlange leer
- Wenn Q.kopf = Q.ende = 1 und Element wird entfernt -> stack underflow
- Wenn Q.kopf = Q.länge und möchtest Element anhängen -> stack overflow
- maximal n-1 Elemente
Was ist eine verkette Liste und welche eigenschaften kann sie haben?
- Bei einer verketteten Liste liegen Elemente in linearer Reihenfolge da
- Anordnung wird durch Zeiger festgelegt
- Einfach verkette Liste nutzt einen Nachfolger
- doppelt verkette Liste benutzt Nachfolger und Vorgänger
- Kann sortiert oder unsortiert sein
- Kann zyklisch oder nicht zyklisch sein
Was sind die Attribute einer verketteten Liste und welche besonderen Werte können sie haben?
- schlüssel -> Wert/Inhalt des Elements
- nachf -> zeigt auf den Schlüssel des Nachfolgers Attribut
- vorg -> zeigt auf den Schlüssel des Vorgängers
- L.Kopf -> zeigt auf das erste Element der Liste
- Wenn x.vorg = NIL -> Besitzt keinen Vorgänger -> erstes Element
- Wenn x.nachf = NIL -> Besitz kein Nachfolger -> letztes Element
- Wenn L.kopf = NIL -> leere Liste
Wie wird eine zyklische doppelt verkettete Liste umgesetzt?
- Über ein Wächterobjekt
- Wächter befindet sich zwischen Kopf und Ende der Liste
- Verweise auf NIL ersetzt man durch den Wächter L.nil
- Somit zeigt L.nil.nachf auf den Kopf der Liste und L.nil.vorg auf das Ende der Liste
- Nachf des letzten Elements und vorg des ersten Elements zeigen auf L.nil
- L.kopf überflüssig, da L.nil.nachf auf das erste Element zeigt
Welche Operationen hat die verkettete Liste?
ListInsert(L,x) -> O(1)
ListSearch(L,x) -> Θ(n)
ListDelete(L,x) -> Θ(n) (weil vorher ListSearch aufgerufen wird sonst O(1))
Was sind vor und nachteile der zyklischen Liste?
Vorteile:
* Können zu kleineren konstanten Faktoren führen
* Vorteil liegt eher in der Klarheit des Codes als in der Perfomanz
Nachteile:
* Reduzieren selten die asymptotische Zeitschranke von Operationen
* Gesparte Laufzeit bei ListInsert und ListDelete ist konstant
* Bei vielen kleinen Listen verschwendet es Arbeitsspeicher
* Verwendung nur Ratsam um Programmcode zu vereinfachen
Wie stellt man einen Graphen dar?
Ein Graph besteht aus zwei Mengen, einmal die Menge der “Knoten” und die Menge der “Kanten”. Diese kann man nun als Diagram oder als Tabelle darstellen. Im Diagram zeigt ein Pfeil die Richtung an, wenn es gerichtet ist und in der Tabelle bedeutet (A,B) dass es von A nach B geht {A,B} bedeutet ungerichtet.
Was ist eine Adjazentliste?
Eine Liste aller Verbindungen im Graphen. Dabei hat jedes Element aus der Menge der Knoten eine eigene Liste, mit allen Verbindungen die Sie hat. Erforderlicher Speicherplatz ist die Menge der Knoten + Menge der Kanten
Was ist eine Adjazentmatrix?
Eine Matrix, die alle Verbindungen des Graphen mit einer Zahl repräsentiert. Die Zahl entspricht der Gewichtung des Graphen. Speicherplatz ist die Anzahl der Knoten Quadriert
In der Abbildung unter c) zu sehen
Wann benutzt man eine Adjazenzliste und wann eine Adjazenzmatrix?
Für dünn besetzte Graphen Liste und für dichte Graphen matrizen. Dabei gilt, dass ein Graph dünn besetzt ist, wenn die Anzahl der Kanten kleiner ist als die Menge der Zustände Quadriert
Was ist BFS?
BFS - Breadth-first search (Breitensuche)
* Die Breitensuche erforscht Systematisch alle Kanten und entdeckt die Knoten des Graphen, die vom vorgegebenen Startknoten erreichbar sind.
* Berechnet die Distanz des Startknoten zu jedem erreichbaren
* BFS nutzt eine Queue
* “Färbt” die bereits besuchten Knoten um sie nicht nochmal zu besuchen
Was ist DFS?
DFS - Depth-First Search (Tiefensuche)
* Man geht erst soweit es geht und wenn man nicht mehr zu einem unbesuchten Knoten kann, markiert man diesen
* Hat man einen Knoten markiert, geht man zum letzten besuchten Knoten und wiederholt den Algorithmus
* Wenn alle erreichbaren knoten markiert sind ist es vorbei
