Vorlesung 3 Flashcards
Was ist ein Graph im mathematischen Sinn?
Was bedeutet es, wenn ein Graph als ‘planar’ bezeichnet wird?
Ein Graph ist planar, wenn er in der Ebene so gezeichnet werden kann, dass sich die Kanten nur in den Knoten treffen.
Was versteht man unter einem ‘vollständigen Graphen’?
Was bedeutet ‘zusammenhängend’ in Bezug auf Graphen?
Ein Graph heißt zusammenhängend, wenn man von jedem Knoten über die Kanten jeden anderen Knoten erreichen kann.
Was ist ein gerichteter Graph?
Was sind gerichtete Kanten und wie werden parallele Kanten definiert?
Was versteht man unter einem Pfad in einem gerichteten Graphen?
Ein Pfad in einem gerichteten Graphen ist eine durchgehende Folge von Kanten. Ein einfacher Pfad hat keine wiederholten Knoten, und seine Länge wird durch die Anzahl der enthaltenen Kanten bestimmt. Ein Zyklus entsteht, wenn ein Pfad vom Knoten v_i wieder zum gleichen Knoten zurückführt. Eine Schlinge ist ein Zyklus der Länge 1.
Was ist ein Baum in der Graphentheorie?
Ein Baum ist ein gerichteter Graph, bei dem von einem bestimmten Knoten (der Wurzel) zu jedem anderen Knoten genau ein einfacher Pfad existiert. Es gibt keine Zyklen, und alle Knoten sind über Kanten miteinander verbunden.
Wie unterscheiden sich Blätter, Wurzeln und innere Knoten in einem Baum?
Blätter sind Knoten am Ende der Pfade ohne Nachkommen, die Wurzel ist der Ursprungsknoten, von dem aus alle anderen Knoten erreichbar sind, und innere Knoten sind alle anderen Knoten, die weder Blätter noch die Wurzel sind.
Was besagt die Beziehung zwischen der Anzahl der Knoten und Kanten in einem Baum?
Ein Baum mit n Knoten hat immer n−1 Kanten.
Wie wird die Höhe eines Baumes definiert?
Die Höhe eines Baumes entspricht der Länge des längsten Pfades von der Wurzel zu einem Blatt.
Was ist ein binärer Baum?
Ein binärer Baum ist ein Baum, bei dem jeder Knoten entweder genau zwei oder keine gerichteten Kanten abgibt.
Was ist eine Adjazenzmatrix in der Graphentheorie?
Eine Adjazenzmatrix ist eine quadratische Matrix, die verwendet wird, um die Kantenbeziehungen in einem gerichteten Graphen darzustellen. Die Elemente der Matrix zeigen an, ob eine Kante von einem Knoten i zu einem Knoten j existiert (1 für existierend, 0 für nicht existierend).
Wie wird die Adjazenzmatrix für einen gerichteten Graphen definiert?
Was repräsentiert ein Diagonalelement a_ij in der Adjazenzmatrix eines gerichteten Graphen?
Was bedeutet das Transponieren der Adjazenzmatrix eines gerichteten Graphen?
Das Transponieren der Adjazenzmatrix eines gerichteten Graphen entspricht der Umkehrung aller Kantenrichtungen im Graphen.
Wie können parallele Kanten in der Adjazenzmatrix erkannt werden?
Parallele Kanten können in der Adjazenzmatrix nicht erkannt werden, da die Matrix nur die Information über die Existenz mindestens einer Kante zwischen zwei Knoten enthält, nicht jedoch die Anzahl der Kanten.
Beispiel einer Adjaszenz Matrix
Was besagt die Erreichbarkeit von Knoten in Bezug auf die Adjazenzmatrix?
Wie kann die Existenz von Zyklen mit der Adjazenzmatrix festgestellt werden?
2) Wie kann die Existenz von Zyklen mit der Adjazenzmatrix festgestellt werden?
Was ist ein Erreichbarkeitsbaum und wie wird er bestimmt?
Ein Erreichbarkeitsbaum ist eine Darstellung aller Knoten, die von einem Wurzelknoten aus erreichbar sind. Für einen gegebenen Graphen und einen ausgewählten Wurzelknoten zeigt der Erreichbarkeitsbaum alle Knoten, die vom Wurzelknoten aus über Pfade verschiedener Längen erreichbar sind.
Was bedeutet es, wenn zwei Knoten in einem Graphen “stark zusammenhängend” sind?
Was impliziert die Eigenschaft “stark zusammenhängend” für eine Relation auf der Knotenmenge eines Graphen?
Die Eigenschaft “stark zusammenhängend” impliziert, dass die Relation reflexiv, symmetrisch und transitiv ist, und somit eine Äquivalenzrelation darstellt.
Wie wird ein Graph als “stark zusammenhängend” klassifiziert?
Ein Graph wird als stark zusammenhängend klassifiziert, wenn jeder Knoten des Graphen mit jedem anderen Knoten stark zusammenhängend ist, d.h., es gibt einen Weg in beide Richtungen zwischen jedem Paar von Knoten.
Was ist ein kondensierter Graph G_kond?
Ein kondensierter Graph G_kond ist ein Graph, der aus Knoten besteht, die jeweils eine Menge von stark zusammenhängenden Knoten in einem ursprünglichen Graphen repräsentieren.
Was bedeutet es, wenn die Knotenmenge
V eines Graphen in disjunkte Teilmengen V_i partitioniert ist?
Was versteht man unter einem gewichteten Graphen?
In einem gewichteten Graphen ist jeder Kante ein Gewicht zugeordnet, welches eine Zahl (numerisch) oder ein Symbol (symbolisch) sein kann. Das Gewicht kann verschiedene Bedeutungen haben, wie zum Beispiel die Kosten oder die Distanz zwischen zwei Knoten.
Wie wird das Gewicht eines Pfades in einem gewichteten Graphen bestimmt?
Das Gewicht eines Pfades ergibt sich aus der Summe der Gewichte der einzelnen Kanten, die den Pfad bilden. Bei numerischen Gewichten wird oft der Durchschnittswert verwendet, insbesondere bei der Ermittlung des kritischen Pfades in Optimierungsproblemen.
Was ist ein “dump-state” 0_+ in der Theorie der symbolischen Gewichtung?
Ein “dump-state 0_+” ist ein Zustand in einem Erkennungs- oder Akzeptanzsystem, der Wörter oder Symbolfolgen erkennt, die nicht gewünscht sind oder nicht zu der Sprache gehören, die das System erkennen soll.
Was zeigt das Beispiel für symbolische Gewichtung auf der Folie?
Das Beispiel zeigt einen Erkenner für eine Sprache, der alle Wörter oder Symbolfolgen erkennt, die ausschließlich aus dem Symbol a bestehen. Die erkannte Sprache wird als Menge von Zeichenketten dargestellt, die erreicht werden, wenn ein Zielzustand durch die Folge von a’s erreicht wird.
Wie wird mit numerischen Kantengewichten umgegangen?
Was bedeutet die Aussage, dass es eigentlich 25 parallele Kanten gibt?
Diese Aussage deutet darauf hin, dass es in dem Beispiel für symbolische Gewichtung eine Vielzahl von Kanten zwischen zwei Zuständen gibt, die durch das gleiche Symbol
�
a gekennzeichnet sind, was in einer Adjazenzmatrix als einzelne Kante repräsentiert wird.
Was ist ein bipartiter Graph?
Ein bipartiter Graph ist ein Graph, bei dem die Knotenmenge in zwei disjunkte Teilmengen unterteilt werden kann, sodass keine zwei Knoten innerhalb derselben Teilmenge miteinander verbunden sind. Jede Kante verbindet einen Knoten aus der einen mit einem Knoten aus der anderen Teilmenge.
Was ist ein Beispiel für einen bipartiten Graphen?
Wie ist die Inzidenzmatrix eines bipartiten Graphen definiert?
Was beschreibt das Heiratssatz-Beispiel in Bezug auf bipartite Graphen?
Im Heiratssatz-Beispiel geht es darum, ob eine Zuordnung zwischen zwei Gruppen (hier Herren und Damen) so möglich ist, dass jede Person genau eine Person aus der anderen Gruppe wählt, die sie mag (Matchingproblem).
Was repräsentiert ein Petrinetz?
Ein Petrinetz ist ein grafisches Modell zur Darstellung von Prozessen mit mehreren Zuständen und Übergängen. Es wird verwendet, um die Dynamik von Systemen, wie Betriebssystemprozessen, zu modellieren und zu analysieren.
Was zeigt die Netzmatrix
�
N in einem Petrinetz an?
Die Netzmatrix
�
N kodiert die Beziehungen zwischen Stellen und Transitionen in einem Petrinetz. Die Elemente der Matrix geben die Richtung der Kanten zwischen Stellen und Transitionen an und ermöglichen so eine Analyse des Netzes.
Wie wird in Petrinetzen die Erzeugung eines Kindprozesses aus einem Elternprozess modelliert?
Im Petrinetz wird die Erzeugung eines Kindprozesses durch die Transition “fork” modelliert, welche die Stelle für den Elternprozess mit der für den Kindprozess verbindet.
Was ist die Bedeutung der Transitionen “wait” und “exit” in diesem Petrinetz?
“wait” repräsentiert einen Wartezustand, in dem sich ein Prozess befindet, während “exit” das Beenden eines Prozesses darstellt.
Was versteht man unter einem Automaten mit “symbolischer Gewichtung”?
Ein Automat mit symbolischer Gewichtung ist ein Modell, das dazu dient, formale Sprachen zu erkennen, indem es Symbolfolgen anhand ihrer Struktur klassifiziert, wobei die “Gewichtung” auf den Übergängen zwischen den Zuständen basiert.
Was bedeutet es, wenn ein Erkenner eine Sprache
�
L erkennt
Ein Erkenner, der eine Sprache
�
L erkennt, ist in der Lage, alle Wörter oder Symbolfolgen zu identifizieren, die zu dieser Sprache gehören. In diesem Fall erkennt der Erkenner alle möglichen nicht-leeren Sequenzen des Symbols
�
a.
Was ist ein “dump-state” in einem Automaten?
Ein “dump-state” ist ein Zustand in einem Automaten, der dazu dient, alle Eingaben aufzufangen, die nicht zu den akzeptierten Wörtern der Sprache gehören. Er fungiert als eine Art Auffangbecken für unerwünschte Sequenzen.
Was impliziert die Aussage, dass “eigentlich 25 parallele Kanten” vorhanden sind?
Diese Aussage impliziert, dass der Automat viele mögliche Übergänge zwischen zwei Zuständen aufweist, die durch das gleiche Symbol repräsentiert werden, auch wenn sie in der Darstellung möglicherweise als einzelne Kante erscheinen.
Was ist das Ziel bei der Bestimmung eines Erreichbarkeitsbaumes in einem Graphen?
Wie wird die Bestimmung eines Pfades in einem Graphen definiert?
Was versteht man unter blinder Suche (uninformierte Suche) bei Graphensuchalgorithmen?
Blinde Suche, auch uninformierte Suche genannt, ist eine sequenzielle, systematische Untersuchung aller Kanten des Graphen, ohne Vorwissen oder Heuristiken zu nutzen. Die Vorgehensweise ist starr und berücksichtigt nicht die spezifischen Eigenschaften des Graphen.
Was ist der Unterschied zwischen blinder und heuristischer Suche?
Blinde Suche verwendet keine zusätzlichen Informationen über den Graphen, während heuristische Suche (informierte Suche) eine a-priori Bewertung und Sortierung der Alternativen im Suchraum vornimmt. Heuristische Suche nutzt zusätzliche Informationen oder Heuristiken, um die Suche effizienter zu gestalten.
Welche Suchalgorithmen fallen unter die Kategorie der blinden Suche?
Zu den blinden Suchalgorithmen gehören Geradeaussuche, Breite-zuerst und Tiefe-zuerst-Suche.
Welcher bekannte Suchalgorithmus ist ein Beispiel für heuristische Suche?
Der A*-Algorithmus, bekannt durch Dijkstras Algorithmus, ist ein Beispiel für heuristische Suche.
Wie funktioniert die Tiefe-zuerst-Suche in Graphen?
Die Tiefe-zuerst-Suche beginnt an einem Startknoten und erkundet so weit wie möglich entlang jedes Zweiges, bevor sie zurückweicht. Sie verwendet eine LIFO-Datenstruktur, typischerweise einen Stapel, um die Reihenfolge der Knoten zu verwalten.
Wie unterscheidet sich die Breite-zuerst-Suche von der Tiefe-zuerst-Suche?
Die Breite-zuerst-Suche durchsucht den Graphen niveauweise, beginnend beim Startknoten und expandiert dann zu allen Nachbarknoten, bevor sie tiefer geht. Sie verwendet eine FIFO-Datenstruktur, typischerweise eine Warteschlange, um die zu durchsuchenden Knoten zu speichern.
Welche Datenstruktur wird typischerweise für die Tiefe-zuerst-Suche verwendet?
Für die Tiefe-zuerst-Suche wird in der Regel ein Stapel verwendet, der die LIFO-Eigenschaft unterstützt.
Welche Datenstruktur wird in der Breite-zuerst-Suche verwendet?
In der Breite-zuerst-Suche wird eine Warteschlange verwendet, die FIFO-Eigenschaften hat.
Was versteht man unter einem Erreichbarkeitsbaum?
Ein Erreichbarkeitsbaum ist eine Baumstruktur, die während der Suche in einem Graphen erstellt wird. Sie zeigt alle von einem bestimmten Startknoten aus erreichbaren Knoten an. Für DFS zeigt der Baum den Pfad der Tiefe-zuerst-Suche und für BFS den der Breite-zuerst-Suche.
Was ist das Hauptanliegen der Komplexitätstheorie in der Informatik?
Die Komplexitätstheorie beschäftigt sich mit der Untersuchung des Ressourcenverbrauchs von Algorithmen und der algorithmischen Behandelbarkeit von Problemstellungen. Sie analysiert, wie viel Rechenzeit und Speicherplatz Algorithmen benötigen, um bestimmte Probleme zu lösen.
Was ist der Unterschied zwischen statischer und dynamischer Komplexität?
Statische Komplexität bezieht sich auf den notwendigen Speicherplatzbedarf zur Repräsentation von Daten oder Algorithmen, gemessen in der Größe n. Dynamische Komplexität hingegen beschreibt die notwendige Laufzeit (Rechenzeit) zur Lösung eines Problems und wird oft in Form von Laufzeitfunktionen T(n) ausgedrückt.
Von welchen Faktoren ist die Komplexitätstheorie unabhängig?
Die Komplexitätstheorie ist ein abstrakter Bereich der theoretischen Informatik und ist unabhängig von praktischen Implementierungen wie Betriebssystem, Programmiersprache (Software), Prozessorleistung, Rechnerarchitektur und Speicherausstattung (Hardware).
Was ist das Ziel der Laufzeitanalyse eines Algorithmus?
Das Ziel der Laufzeitanalyse ist es, die Anzahl der durchgeführten Elementaroperationen für eine gegebene Eingabegröße n zu ermitteln und eine Laufzeitfunktion T(n) zu definieren, die diese Anzahl in Abhängigkeit von der Kardinalität der Eingabemenge darstellt.
Frage: Was versteht man unter der Laufzeitfunktion T(n) in der Algorithmusanalyse?
Die Laufzeitfunktion T(n) ist eine Funktion, die die Anzahl der Elementaroperationen beschreibt, die ein Algorithmus in Abhängigkeit von der Größe n der Eingabe ausführt. Sie wird verwendet, um die Effizienz und Leistung eines Algorithmus zu bewerten.
Die Betrachtung des “worst case” gibt Aufschluss über die maximal mögliche Laufzeit des Algorithmus für die ungünstigste Eingabe. Sie ist wichtig für die Abschätzung der oberen Grenze der Performance und um sicherzustellen, dass der Algorithmus auch unter den schlechtesten Bedingungen akzeptabel funktioniert.
Wie werden Algorithmen nach der O-Notation eingeordnet?
Algorithmen werden nach der O-Notation basierend auf ihrem Wachstumsverhalten klassifiziert. Die O-Notation beschreibt die obere Grenze für die Laufzeit oder den Platzbedarf eines Algorithmus und dient als abstrakte Darstellung der Komplexität.
Was sind Beispiele für Elementaroperationen und warum sind sie relevant?
Welche Operationen gelten nicht als elementar in der Laufzeitanalyse?
Nicht elementare Operationen sind solche, die eine komplexe Struktur aufweisen, wie Schleifen (z.B. while, for, repeat) und Prozeduraufrufe, insbesondere wenn sie rekursiv sind. Diese Operationen können die Laufzeit exponentiell erhöhen und sind daher in der Analyse gesondert zu betrachten.
Was wird in der Laufzeitanalyse eines Algorithmus gezählt?
In der Laufzeitanalyse werden die durchgeführten Elementaroperationen wie Zuweisungen, Vergleiche und Arrayzugriffe für eine gegebene Eingabe n gezählt.
Wie wird die Laufzeitkomplexität eines Algorithmus dargestellt?
Was versteht man unter dem Abstraktionsschritt in der Laufzeitanalyse?
Der Abstraktionsschritt in der Laufzeitanalyse bezieht sich darauf, dass man nicht zwischen verschiedenen Elementaroperationen unterscheidet und alle als gleich “teuer” annimmt, sowie dass man die Gesamtmenge aller Eingaben in Komplexitätsklassen aufteilt und den worst case innerhalb einer Klasse betrachtet.
Was besagt die O-Notation in der Laufzeitanalyse?
Die O-Notation klassifiziert die Laufzeitfunktion T(n) nach ihrem asymptotischen Verhalten, indem sie die führenden Terme betrachtet und konstante Faktoren sowie niedrigere Ordnungsterme ignoriert, um die grundlegende Wachstumsrate der Laufzeit zu bestimmen.
Was kann aus der O-Notation über die Effizienz eines Algorithmus abgeleitet werden?
Aus der O-Notation kann abgeleitet werden, wie die Laufzeit des Algorithmus mit zunehmender Eingabegröße skaliert. Zum Beispiel bedeutet O(n), dass die Laufzeit linear mit der Größe der Eingabe wächst, während O(n^2 ) auf ein quadratisches Wachstum hinweist.
ie wird der Speicherplatzbedarf des contains Algorithmus bewertet?
Der Speicherplatzbedarf des contains Algorithmus ist proportional zur Größe des Arrays, also O(n), da jeder Wert im Array einmal gespeichert werden muss.
Was ist der Zweck des contains Algorithmus?
Der contains Algorithmus prüft, ob ein bestimmter Wert c in einem Array s von ganzen Zahlen enthalten ist. Die Ausgabe ist true, wenn c in s enthalten ist, andernfalls false.
Wie wird die Laufzeit
�
T des contains Algorithmus berechnet?
Die Laufzeit
�
T des contains Algorithmus wird berechnet, indem die Anzahl der Elementaroperationen wie Zuweisungen, Vergleiche und Arrayzugriffe summiert wird, die während der Ausführung des Algorithmus durchgeführt werden.
Wie viele Operationen benötigt der contains Algorithmus, wenn der gesuchte Wert das letzte Element des Arrays ist?
Wenn der gesuchte Wert das letzte Element des Arrays ist, benötigt der contains Algorithmus
�
n Vergleiche und
�
n Arrayzugriffe, wobei
�
n die Länge des Arrays ist, plus eine anfängliche Zuweisung für die Variable b. Das ergibt insgesamt 2n + 1 Operationen.
Was passiert, wenn der gesuchte Wert nicht im Array enthalten ist?
Wenn der gesuchte Wert nicht im Array enthalten ist, durchläuft der Algorithmus das gesamte Array einmal und führt n Vergleiche und n Arrayzugriffe durch, plus eine Zuweisung für b. In diesem Fall sind es auch 2n+1 Operationen
Was bedeutet der erste Abstraktionsschritt bei der Laufzeitanalyse eines Algorithmus?
Im ersten Abstraktionsschritt der Laufzeitanalyse werden alle Elementaroperationen gleich behandelt, ohne zwischen ihnen zu unterscheiden. Das bedeutet, dass jede Operation als gleich aufwändig oder “teuer” betrachtet wird, unabhängig davon, ob es sich um eine Zuweisung, einen Vergleich oder einen Arrayzugriff handelt.
Wie wird im zweiten Abstraktionsschritt die Laufzeit eines Algorithmus klassifiziert?
Im zweiten Abstraktionsschritt werden die Eingaben in Komplexitätsklassen basierend auf ihrer Größe
�
n eingeteilt. Die Laufzeituntersuchung konzentriert sich dann nur auf die möglichen Komplexitätsklassen, um eine allgemeine Einschätzung der Laufzeiteffizienz zu geben, wobei die Laufzeit oft wesentlich von der Größe
�
n der Eingabe abhängt.
Was versteht man unter dem dritten Abstraktionsschritt in der Laufzeitanalyse?
Der dritte Abstraktionsschritt bezieht sich auf die Vereinfachung innerhalb einer Komplexitätsklasse, indem der “worst case” betrachtet wird. Hierbei wird die höchste Anzahl von Operationen angenommen, die der Algorithmus für die größtmögliche Eingabe innerhalb dieser Klasse benötigen würde.
Wie wird die Laufzeitfunktion eines Algorithmus in der O-Notation ausgedrückt?
