CoboCards App FAQ & Wishes Feedback
Language: English Language
Sign up for free  Login

Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Enter your e-mail address and import flashcard set for free.  
Go!
All main topics / Informatik / Algorithmen und Datenstrukturen

Algorithmen und Datenstrukturen II (67 Cards)

Say thanks
1
Cardlink
1
Was ist ein ungerichteter Graph?
Ein Tupel (V, E) heißt ungerichteter Graph, wenn V eine endliche Menge und E eine Menge ungeordneter Paare von Elementen in V ist.

V heißt Knotenmenge, die Elemente von V heißen Knoten.
E heißt Kantenmenge, die Elemente von E heißen Kanten.
Tags: Graphenalgorithmen
Source:
2
Cardlink
0
Wann ist H(W, F) ein Teilgraphen von G(V, E)?
- Teilgraph, wenn W ⊆ V und F ⊆ E

- spannender Teilgraph, wenn W = V
   (H und G enthalten dieselben Knoten)

- indizierter Teilgraph, wenn für alle e ∈ E gilt: e ⊆ W ⇒ e ∈ F
   (Alle Kanten aus G, deren zwei Knoten in H liegen, sind auch
   in H enthalten)
Tags: Graphenalgorithmen
Source:
3
Cardlink
0
Was sind Wälder und Bäume?
- G(V, E) heißt Wald oder zyklenfrei, wenn kein Weg in G ein 
   Zyklus ist

- G heißt Baum, wenn G ein Wald und zusammenhängend ist
→ G hat genau |V| - 1 Kanten.
Tags: Graphenalgorithmen
Source:
4
Cardlink
0
Was ist ein gewichteter Graph?
Jeder Kante des Graphen wird ein Gewicht bzw. eine Länge w(e) zugewiesen, sodass gilt: G = (V, E, w)

- auch negative Gewichte möglich.
Tags: Graphenalgorithmen
Source:
5
Cardlink
0
Was ist ein (minimaler) Spannbaum?
Ein Spannbaum T ist ein Teilgraph eines zusammenhängenden ungerichteten Graphen G, der alle Knoten von G enthält.

T ist minimal, wenn die Summe der verwendeten Kantengewichte minimal ist. Bestimmung: Kruskal- Algorithmus
Tags: Graphenalgorithmen
Source:
6
Cardlink
0
Wie funktioniert der Kruskal- Algorithmus?
G (V, E) … Graph
T (V, F) … Minimaler Spannbaum
F … Kantenliste des Spannbaumes
Q … Queue


(1) Alle Kanten aus E nach Gewicht aufsteigend sortiert in Q 
      schreiben
(2) erste Kante (u, v) aus Q entfernen
(3) Falls T bisher keine Verbindung zwischen u und v enthält,
      Kante (u, v) in F aufnehmen
(4) Gehe zu (2), bis Q leer ist
(5) F ausgeben

- findet immer einen minimaler Spannbaum
- analog: maximaler Spannbaum bei umgekehrter Sortierung
- Komplexität: O(|E| log |V|)
Tags: Graphenalgorithmen
Source:
7
Cardlink
0
Was ist ein gerichteter Graph?
= Digraph
- Graph (V, E), bei dem E eine Menge geordneter Paare von
   Elementen in V ist.
- Schleife: (v, v)
Tags: Graphenalgorithmen
Source:
8
Cardlink
0
Was sind Vorgänger, Nachfolger und Grad eines Knotens?
Vorgänger
- u heißt Vorgänger von v, wenn (u, v) ∈ E
- Menge aller Vorgänger von v: pred(v ) = {u ∈ V |(u, v ) ∈ E }

Nachfolger
- w heißt Nachfolger von v, wenn (v, w)  ∈  E
- Menge aller Nachfolger von v: succ(v) = {w ∈ V |(v, w) ∈ E }

Grad
- Eingangsgrad: eg(v) = |pred(v)| = "Anzahl der Vorgänger"
- Ausgangsgrad: ag(v) = |succ(v)| = "Anzahl der Nachfolger"
Tags: Graphenalgorithmen
Source:
9
Cardlink
0
Was ist eine Adjazenmatrix?
- Speicherung von Graphen in einer Boole'schen |V| * |V| Matrix
- 1, wenn Kante existiert, sonst 0
- gerichtete Kante von u nach v: Zeile u, Spalte v
- symmetrische Belegung bei ungerichteten Graphen
Tags: Graphenalgorithmen
Source:
10
Cardlink
0
Was für Listen gibt es, um Graphen zu speichern?
Kantenliste
- Liste: Knotenzahl, Kantenzahl, Liste von Kanten (je 2 Knoten)
- Speicherbedarf: 2+2 |E|

Knotenliste
- Liste: Knotenanzahl, Kantenanzahl, Liste von
   Knoteninformationen
- Knoteninformationen: Ausgangsgrad und alle Nachfolger
- Speicherbedarf: 2 + |V| + |E|

Adjazenliste
- pro Knoten eine eigene Zeile, durch ↓ verbunden
- in einer Zeile stehen alle Nachfolger des ersten Knotens der
   Zeile in einer verketten Liste (→)
- Speicherbedarf: |V| + |E|
Tags: Graphenalgorithmen
Source:
11
Cardlink
0
Was ist eine Kantenfolge?
= Weg
- gültige Abfolge von Kanten für einen Graph G, d.h. alle Kanten
   sind ∈ E
- geschlossene Kantenfolge, wenn
Tags: Graphenalgorithmen
Source:
12
Cardlink
0
Was ist ein Kantenzug?
- eine Kantenfolge, in der keine Kante doppelt vorkommt
- Knoten dürfen mehrmals vorkommen
Tags: Graphenalgorithmen
Source:
13
Cardlink
0
Was ist ein Pfad?
- Kantenfolge, in der kein Knoten doppelt vorkommt.
Tags: Graphenalgorithmen
Source:
14
Cardlink
0
Was ist die topologische Sortierung?
- nur auf azyklische Graphen anwendbar
- gibt zeitliche Abfolge des Graphen vor: Kante (u, v) → u vor v

Tags: Graphenalgorithmen
Source:
15
Cardlink
0
Was ist eine reflexive transitive Hülle?
- Bestimmung: Warshall- Algorithmus
- Ein Digraph G* = (V, E*) heißt reflexive, transitive Hülle eines
   Digraphen G = (V, E), wenn für alle u, v ∈ V gilt:
          (u, v ) ∈ E*  ⇔ Es gibt einen Pfad von u nach v in G
= wenn v von u aus erreichbar ist, gibt es eine Kante (u, v)
- reflexiv: Es gibt eine Kante (u,u) für jeden Knoten
Tags: Graphenalgorithmen
Source:
16
Cardlink
0
Was ist Traversierung?
Durchlaufen eines Graphen, bei dem jeder erreichbare Knoten bzw. Kante exakt einmal durchlaufen wird
Tags: Graphenalgorithmen
Source:
17
Cardlink
0
Was ist ein Breitendurchlauf?
- Breadth First Search (BFS)

- ausgehend vom Startknoten werden alle direkt erreichbaren
   Knoten bearbeitet
- dann alle über 2 Kanten erreichbaren Knoten
- Prinzip: erst alle Nachbarn, dann Söhne
- bei mehreren Söhnen / Nachbarn Auswahl des nächsten
   Knotens aufgrund vorgeschriebener Regel
   (bspw.: kleinster zuerst)
Tags: Graphenalgorithmen
Source:
18
Cardlink
0
Was ist ein Tiefendurchlauf?
- Depth First Search (DFS)

- rekursiv alle Nachfolger eines Knoten bearbeitet, dann die
   Nachbarn
- bei mehreren Söhnen / Nachbarn Auswahl des nächsten
   Knotens aufgrund vorgeschriebener Regel
   (bspw.: kleinster zuerst)
Tags: Graphenalgorithmen
Source:
19
Cardlink
0
Was ist eine Äquivalenzreaktion?
- sind die Knoten u, v ∈ V eines gerichteten Graphen
  gegenseitig erreichbar, schreibt man u ~ v, also eine
  symmetrische, transitive und reflexive Äquivalenzrelation

- die Knotenmengen der starken Zusammenhangskomponenten
  von G sind die Äquivalenzklassen von ~
Tags: Graphenalgorithmen
Source:
20
Cardlink
0
Was ist eine starke Zusammenhangskomponente?
- ein gerichteter Graph G (V, E) heißt stark zusammenhängend,
  wenn für alle u,v ∈ V gilt: Es gibt einen Pfad von u nach v
- eine starke Zusammenhangskomponente von G ist ein
  maximaler stark zusammenhängender Teilgraph von G
- jeder Knoten eines Graphen ist in genau einer starken
  Zusammenhangskomponente enthalten.
Tags: Graphenalgorithmen
Source:
21
Cardlink
0
Was ist ein Komponentengraph?
- fasst alle Knoten jeweils einer starken
   Zusammenhangskomponente zu einem Knoten zusammen
- erlaubt schnellere Berechnung der transitiven Hülle des Graphen
Tags: Graphenalgorithmen
Source:
22
Cardlink
0
Was ist der Dijkstra- Algorithmus?
- Bestimmung der von einem Knoten ausgehenden kürzesten
  Wege
- funktioniert nur bei nicht- negativen Gewichten
- Basis: Breitensuche
- Komplexität: O(|V|²)

(1) Priorityqueue, die alle Knoten und ihre Entfernung enthält
      Distanz zu Ausgangsknoten: 0
      Anfangsdistanz zu allen anderen Knoten: ∞
(2) Breitensuche auf Graph, dabei ständige Aktualisierung der   
      errechneten Distanz
Tags: Graphenalgorithmen
Source:
23
Cardlink
0
Was ist der Bellmann- Ford- Algorithmus
- Bestimmung der von einem Knoten ausgehenden kürzesten  
  Wege
- funktioniert auch bei negativen Gewichten, aber nicht bei
   negativen Zyklen
- Komplexität: O(|V| * |E|)

(1) Priorityqueue, die alle Knoten und ihre Entfernung enthält
      Distanz zu Ausgangsknoten: 0
      Anfangsdistanz zu allen anderen Knoten: ∞
(2) Kanten werden in lexikographischer Reihenfolge
     durchlaufen, dabei ständige Aktualisierung der errechneten
     Distanz
Tags: Graphenalgorithmen
Source:
24
Cardlink
0
Was ist ein Fluss- Netzwerk?
- ein gerichteter Graph G, mit ausgezeichneten Knoten q  
  (Quelle) und s (Senke) sowie einer Kapazitätsfunktion c (Fluss
  von q nach s)
Tags: Graphenalgorithmen
Source:
25
Cardlink
0
Was ist ein Schnitt durch ein Flussnetzwerk?
- Zerlegung von V in zwei disjunkte Teilmengen A und B,
   so dass q ∈ A und s ∈ B
- alle Kanten zwischen den beiden Teilmengen müssen von A
  nach B führen
- Kapazität des Schnittes ist die Summe der Kapazität aller 
  Kanten, die von A nach B führen
Tags: Graphenalgorithmen
Source:
26
Cardlink
0
Was ist ein Restgraph?
- ausnutzen ungenutzter Restkapazitäten eines
  Flussnetzwerkes

rest((v , w )) = c((v , w )) − f ((v , w )) falls (v , w ) ∈ E
rest((v , w )) = +f ((w , v )) falls (w , v ) ∈ E




→ Optimierung des Flusses für G entlang des zunehmenden
    Weges um Flusskapazität des Weges
Tags: Graphenalgorithmen
Source:
27
Cardlink
0
Was ist ein zunehmender Weg?
- jeder gerichtete Pfad von q nach s in einem Restgraph
Tags: Graphenalgorithmen
Source:
28
Cardlink
0
Was besagt das Min- Cut- Max- Flow- Theorem?
Sei f ein zulässiger Fluss für G, dann sind folgende Aussagen äquivalent:

    - f ist ein maximaler Fluss in G
    - Der Restgraph von f enthält keinen zunehmenden Weg
    - w(f) = c (A, B) für einen Schnitt (A, B) von G
Tags: Graphenalgorithmen
Source:
29
Cardlink
0
Was ist der Ford- Fulkerson- Algorithmus?
(1) Füge solange zunehmende Wege zum Gesamtfluss hinzu
      wie möglich
(2) Kapazität erhöht sich jeweils um Minimum der verfügbaren
     Restkapazitäten der einzelnen Kanten des zunehmenden
     Weges
Tags: Graphenalgorithmen
Source:
30
Cardlink
0
Was bedeutet Matching?
= Zuordnung
- Teilmenge der Kanten, sodass jeder Knoten in V in höchstens
   einer Kante vorkommt
- Perfektes Matching: kein Knoten bleibt alleine ("unmatched")
- Maximales Matching, wenn es kein Matching M' gibt,
  mit |M| < |M'|

|M| … Größe der Zuordnung
Tags: Graphenalgorithmen
Source:
31
Cardlink
0
Was ist ein bipartiter Graph?
- Knotenmenge V in zwei disjunkte Teilmengen und
  aufgeteilt
- alle Kanten verbinden jeweils einen Knoten aus mit
   einem Knoten aus
Tags: Graphenalgorithmen
Source:
32
Cardlink
0
Was ist Lauflängencodierung?
- zur Komprimierung langer Folgen sich wiederholender Zeichen
  (runs)
- einmalige Angabe des sich wiederholenden Zeichens und
  Anzahl der Wiederholungen (Zähler)
- Zähler: Buchstabe statt Ziffer (A = 1, B = 2, … )
- Escape- Zeichen um Paare (Zähler, Zeichen) zu kennzeichnen
          - sollte möglichst selten im Text auftauchen
          - Sonderbehandlung notwendig, wenn Escape- Zeichen im
             Input enthalten ist

Tags: Datenkomprimierung
Source:
33
Cardlink
0
Was ist die Huffmann- Codierung?
- Lauflängencodierung mit variabler Länge
- jedes Zeichen stellt ein Blatt in einem Binärbaum dar
- statt einzelnen Zeichen kann eine Codierungseinheit z.B. auch
  ein Wort sein
Tags: Datenkomprimierung
Source:
34
Cardlink
0
Wie funktioniert die Huffmann- Codierung?
(1) Häufigkeit jedes einzelnen Zeichens bestimmen
(2) Erzeugung eines neuen Knotens, mit den beiden Zeichen
      mit der geringsten Häufigkeit als Blätter
(3) Gehe zu (2), bis der Baum alle Zeichen enthält
(4) Ermittlung des Codes für ein Zeichen:
                  - Pfad zu einem Zeichen entlang gehen
                  - geht man nach links → 0
                  - geht man nach rechts → 1
Tags: Datenkomprimierung
Source:
35
Cardlink
0
Was ist LZW?
- Lempel- Ziv- Welch
- erlaubt Kompression ohne die Initialisierungsdaten zu
  übertragen
- arbeitet mit Zeichensatz variabler Länge
- Zeichen bestehen aus einem oder mehreren Buchstaben
- gute Anpassung an Kontextwechsel im Eingabestrom
Tags: Datenkomprimierung
Source:
36
Cardlink
0
Wie funktioniert der LZW- Algorithmus?
(1) Zeichensatz mit 256 Byte- Zeichen und einem Ende-  
     Zeichen initialisieren
(2) In der Codierungsschleife wird das längste Zeichen des 
     Zeichensatzes ermittelt, welches mit der Buchstabenfolge
     aus dem Input übereinstimmt
(3) Die Nummer dieses Zeichens wird in die Ausgabe geschrieben
(4) Zusätzlich wird ein neues Zeichen definiert: Die
      Verlängerung der eben gefundenen Buchstabenfolge um den
      nächsten Buchstaben
(5) Bei maximaler Größe des Zeichensatzes wird er wieder auf
     257 Zeichen reduziert und der Vorgang beginnt erneut
Tags: Datenkomprimierung
Source:
37
Cardlink
0
Wie funktioniert LZ77 Sliding Window?
p = relative Position des longest match im Dictionary
l = Länge des longest match
c = nächstes Zeichen rechts vom Cursor

- Dictionary und Buffer- Window haben feste Größe und
  verschieben sich mit dem Cursor
- Ausgabe an jeder Cursor- Position (p, l, c)

Decoding pro Triple (p,l,c):
   - p Schritte zurück
   - lese l Zeichen und füge diese hinten ein
   - füge c an
Tags: Datenkomprimierung
Source:
38
Cardlink
0
Was ist die Burrows- Wheeler- Transformation?
- gut geeignet für Text, da Kontext berücksichtigt wird
- vorgelagerte Umordnung von Textblöcken
- Vorbereitung für Move- to- Front- und Huffmann- Codierung
Tags: Datenkomprimierung
Source:
39
Cardlink
0
Wie funktioniert die Burrows- Wheeler- Transformation?
- Eingabe der Länge n wird als n x n Matrix dargestellt
- Zeilen werden alphabetisch sortiert
- Ausgabe: letzte Spalte und Zeilennummer des Originalblocks
→ lange Runs gleicher Buchstaben
- Rekonstruierung des Originals möglich
40
Cardlink
0
Wie funktioniert Move- to- Front- Codierung?
- Lesen des Eingabestroms
- Für gelesenes Zeichen wird Codenummer (ASCII, … )
  ausgegeben
- folgen zwei identische Zeichen aufeinander, wird nach dem
  ersten nur 0  zurückgegeben

Eingabe:       A   A   B   B   C   B   A   A   C   C
Ausgabe:    65   0  66   0  67 66  65  0   67  0
Tags: Datenkomprimierung
Source:
41
Cardlink
0
Was ist ein m-ärer Trie?
- spezielle m-Wege- Bäume, wobei Kardinalität des Alphabets
  und Länge k der Schlüsselteile den Grad m festlegen
          - bei Ziffern:              m = 10 (k = 1)
          - bei Alphazeichen:    m = 26 (k = 1)
- Grad:
Tags: Suffixbäume
Source:
42
Cardlink
0
Welche Operationen sind auf Tries möglich?
Direkte Suche
- Vergleich des 1. Zeichens des Suchschlüssels in der Wurzel
- Bei Erfolg wird Zeiger verfolgt
→ effiziente Bestimmung der Abwesenheit eines Schlüssels

Einfügen
- wenn Suchpfad vorhanden, vorhandenen NULL- Zeiger in
  Verweis auf Datensatz umwandeln
- ansonsten neuen Datensatz einfügen

Löschen
- Datensatz- Zeiger auf NULL setzen
- besteht ein Knoten nur aus NULL- Zeigern wird der Knoten
  entfernt
Tags: Suffixbäume
Source:
43
Cardlink
0
Was ist ein PATRICIA- Tree?
- binärer Digitalbaum
- Speicherung des ganzen Schlüssels in einem Blatt
- innere Knoten speichern, Anzahl der übersprungenen Zeichen
→ Vermeidung von Einwegverzweigungen
→ speichereffizient

"3" → ersten 3 Zeichen werden nicht vergleichen, da stets "Dat"
Tags: Suffixbäume
Source:
44
Cardlink
0
Wie ist ein Suffix?
- Wortende eines Strings
- beliebige Länge
- echtes Suffix: Suffix, welches nicht identisch mit String ist

String: Southpark
Suffixe: k, rk, ark, park, hpark, … , Southpark
Tags: Suffixbäume
Source:
45
Cardlink
0
Was ist ein Präfix?
- Wortanfang eines Strings
- beliebige Länge
- echtes Präfix: Präfix, welches nicht identisch mit String ist

String: Southpark
Präfixe: S, So, Sou, Sout, …, Southpark
Tags: Suffixbäume
Source:
46
Cardlink
0
Was ist ein Infix?
- jeder Substring beliebiger Länge eines Strings
- inklusive aller Präfixe und Suffixe
- echtes Infix: weder Präfix noch Suffix

String: Southpark
Infix: Sou, ou, th, par, park, r, …
Tags: Suffixbäume
Source:
47
Cardlink
0
Was ist ein Suffix- Baum?
- PATRICIA- Baum, welcher alle Suffixe enthält
- $ als Endezeichen eines Suffixes
Tags: Suffixbäume
Source:
48
Cardlink
0
Wie funktioniert die Textsuche nach Knuth- Morris- Pratt?
- zeichenweiser Vergleich zwischen Text und Suchmuster
- Mismatch tritt auf → Nutzen der bereits erfolgreichen
   Vergleiche um Suchmuster möglichst weit nach rechts zu
   verschieben
- Suchmuster wird zu Beginn des Präfixes verschoben, welches
   bis zum zuletzt durchgeführten Vergleich keinen Mismatch
   liefert
next- Tabelle
- gibt es mehrere Präfixe, wird das längste gewählt
- gibt es kein Präfix, wird das Suchmuster zur Stelle des letzten
   Vergleiches weitergeschoben
- vorteilhaft vor allen bei Wiederholung der Teilmuster
49
Cardlink
0
Was ist eine next- Tabelle?
- vereinfacht Textsuche nach Knuth- Morris- Pratt
- wird für das Muster erstellt und ist unabhängig vom zu
  durchsuchenden Text
- gibt an, an welche Stelle das Muster bei
  einem Mismatch an Stelle i geschoben wird
- Zählung beginnt bei 1

Muster: A N A N A S
next[j]:  0 1  1 2  2 1
Tags: Textsuche
Source:
50
Cardlink
0
Wie funktioniert der Boyer- Moore- Algorithmus?
- Auswertung des Musters von rechts nach links um bei einem
   Mismatch das Muster möglichst weit verschieben zu können
- kommt das aktuell gelesene Zeichen nicht im Muster vor, kann
   das Muster hinter t geschoben werden
- wenn das aktuell gelesene Zeichen im Muster vorkommt, kann
   Muster um einen Betrag verschoben werden, der der Position
   des letzten Vorkommens des Zeichens im Muster entspricht
   (j - last[t] - 1 ) - also so, dass das letzte Auftreten im Muster 
   deckungsgleich mit dem gelesenen Zeichen ist
- last- Tabelle speichert Verschiebeumfang für jeden Buchstaben
- für große Alphabete mit kleinen Suchmustern geeignet
→ O (n / m)
51
Cardlink
0
Was ist eine last- Tabelle?
- vereinfacht Textsuche nach Boyer- Moore
- enthält das letzte Vorkommen eines Zeichens im Suchmuster,
  oder -1, wenn es gar kein Vorkommen gibt
- Zählung beginnt bei 0
Tags: Textsuche
Source:
52
Cardlink
0
Wie funktioniert die Textsuche über Signaturen?
- Berechnung einer Signatur s für das Suchmuster (zB Hashing)
- für jedes Textfenster der Länge m wird ebenfalls eine Signatur
   erstellt
- wenn s = → potentieller Match → genaue Prüfung

Beispiel: Ziffern → Quersumme als Signatur
Tags: Textsuche
Source:
53
Cardlink
0
Wodurch unterscheiden sich optimistische und pessimistische Suche?
Optimistische Suche
- erwartet Erfolg
→ führt viele Vergleiche durch um Muster zu finden

Pessimistische Suche
- erwartet Misserfolg
- möglichst viele Stellen im Text werden ausgeschlossen und nur
  wenige exakt geprüft
- z.B.: Signaturen
Tags: Textsuche
Source:
54
Cardlink
0
Was ist die approximative Suche?
- gesucht werden alle Vorkommen von Mustern, sodass an
  höchstens k Stellen ein Missmatch mit dem original
  Suchmuster vorliegt
- erfordert Maß für die Ähnlichkeit zwischen Zeichenketten
          - Hamming- Distanz
          - Editierdistanz
Tags: Textsuche
Source:
55
Cardlink
0
Was ist die Hamming- Distanz?
= Anzahl der Mismatches zwischen und
- nur sinnvoll, wenn und die gleiche Länge haben
Tags: Textsuche
Source:
56
Cardlink
0
Was ist die Editierdistanz?
- Kosten der Überführung von in mit elementaren
  Operationen
- verschiedene Folgen von Editier- Operationen möglich
- optimale Folge ändert jedes Zeichen höchstens einmal

Syntax Beschreibung Kosten
(–, y) Einfügen von y in 1
(x, –) Löschen von x in 1
(x, y) Ersetzung von x durch y in 1
(x, x) Match, keine Änderung 0
Tags: Textsuche
Source:
57
Cardlink
0
Was ist dynamische Programmierung?
- definiere rekursiv, wie sich eine optimale Lösung aus kleineren
  optimalen Lösungen zusammensetzt
- konzipiere den Algorithmus bottom- up, sodass für n = 1, 2, 3,
  … optimale Teillösungen gefunden werden
- beim finden einer Teillösung der Größe k > 1 ist auf alle
  optimalen Teillösungen der Größe < k zurück zu greifen

Voraussetzung: Bellmannsches Optimalitätsprinzip
         = Problem setzt sich aus optimalen Teillösungen kleinerer
            Größe zusammen
Tags: Optimierungsprobleme
Source:
58
Cardlink
0
Was sind Greedy- Algorithmen?
Prinzip
(1) Starte mit einer leeren Lösung
(2) Erweitere die bisher konstruierte Teillösung wie folgt: Wenn
     zur Erweiterung dieser Teillösung k
     Erweiterungsmöglichkeiten zur Verfügung stehen, die auf die  
     vergrößerten Teillösungen führen, wähle diejenige Teillösung 
     mit maximal

→ greedy = gierig / gefräßig = "nimm immer das größte Stück"
- führt in vielen Fällen zu einer optimalen Lösung
- geringerer Aufwand als dynamische Programmierung
Tags: Optimierungsprobleme
Source:
59
Cardlink
0
Was ist ein Mengensystem?
Sei E eine endliche Menge und M eine Menge von Teilmengen
von E, dann heißt (E, M) Mengensystem
Tags: Optimierungsprobleme
Source:
60
Cardlink
0
Was ist ein Unabhängigkeitssystem?
Ein Mengensystem (E, M) heißt Mengensystem, wenn ∅ ∈ M und zu jeder Menge in M auch alle Teilmengen enthalten sind
Tags: Optimierungsprobleme
Source:
61
Cardlink
0
Wie funktioniert der kanonische Greedy- Algorithmus?
(1) Ordne die Elemente in absteigend nach
     ihrem Gewicht, so dass
(2) Setze T := ∅
(3) Füge jeweils das größte noch nicht betrachtete Element zu T
      hinzu, sofern die resultierende Menge in M enthalten ist
(4) Gibt Menge T aus

→ liefert nur für einen Matroid immer eine optimale Lösung
Tags: Optimierungsprobleme
Source:
62
Cardlink
0
Was ist ein Matroid?
- Ein Unabhängigkeitssystem (E, M) heißt Matroid, wenn für alle
  Elemente folgende Austauscheigenschaft gilt:
  Ist |A| > |B|, dann gibt es ein x ∈ A \ B, so dass B ∪ {x} ∈ M
- eine Menge A ∈  M heißt Basis oder maximales Element, 
  wenn es keine Menge B ∈ M mit einer größeren Kardinalität gibt
→ alle Basen enthalten dieselben Anzahl Elemente

|A| … Kardinalität der Teilmenge
Tags: Optimierungsprobleme
Source:
63
Cardlink
0
Was ist das Prinzip von Branch and Bound?
- identifiziere möglichst große Teilmengen des Lösungsraums,
  die keine optimale Lösung enthalten können und überspringe
  diese beim Aufzählen

Branch- Schritt
= Verzweigung
- Problem wird in zwei oder mehr Teilprobleme aufgeteilt
→ Splitoperation: Split (010**) = (0100*, 0101*)
- durch rekursives ausführen entsteht eine Baumstruktur

Bound- Schritt
= Schranke
- bestimmte Zweige des Baumes werden "abgeschnitten", also
  nicht mehr betrachtet
- Festlegen einer unteren Schranke
          - möglichst nah am Kostenminimum
          - möglichst geringer Zeitaufwand
Tags: Optimierungsprobleme
Source:
64
Cardlink
0
Wie wird die untere Schranke bestimmt?
   Kosten für die bereits gewählten Kosten
+ minimale Kosten für ausgehende Kanten
+ minimale Kosten für eingehende Kanten
= untere Schranke
Tags: Optimierungsprobleme
Source:
65
Cardlink
0
Wie funktionieren stochastische Optimierungsalgorithmen?
Prinzip
(1) endliche Menge A von erlaubten Lösungen (Population)
     mit |A| = n
(2) Erzeuge erweiterte Lösungsmenge B mit |B| = m > n
(3) Selektiere eine neue Population A' ∈ B mit |A'| = n, welche die
     besseren Lösungen enthält
(4) Gehe zu (2), solange Abbruchbedingung nicht erfüllt ist

Voraussetzung
- Bewertungsfunktion f für gefundene Lösungen
- globales Minimum von f als Abbruchbedingung
Tags: Optimierungsprobleme
Source:
66
Cardlink
0
Was sind Moves?
= Schritte
Annahme: Gute Lösungen werden ähnlich zu anderen, bisher
                 gefunden Lösungen, sein
→ Definition von erlaubten Schritten um von einer Lösung zur
    nächsten zu gelangen
= erlaubte Nachbarschaft N(x) für jedes x ∈ X
- wähle ein y ∈ N(x) mit Wahrscheinlichkeit
→ resultierender Graph muss stark zusammenhängend sein, da
    der Prozess sonst innerhalb einer
    Zusammenhangskomponente eingesperrt bleibt, die eventuell
    kein globales Minimum enthält
67
Cardlink
0
Welche stochastischen Optimierungsalgorithmen gibt es?
Adaptive Walk & Gradient Descent
→ enden beide im lokalen Minimum, da nur abwärts- Schritte
    zulässig sind
Metropolis Walks
→ auch Aufwärts- Schritte zulässig um lokales Minimum zu
    entkommen
→ Abbruchbedingung notwendig
Simulated Annealing
Genetische Algorithmen
- Selektion
- Crossover: Mischung aus 2 Eltern erzeugt Mutanten
          - 1- Punkt Crossover
                    - Bestimme einen zufälligen Bruchpunkt k und
                      vertausche die Suffixe
          - Uniformer Crossover
                    - übernimmt jede Position zufällig von einem der
                      beiden Elternteile
Tags: Optimierungsprobleme
Source:
Flashcard set info:
Author: David
Main topic: Informatik
Topic: Algorithmen und Datenstrukturen
School / Univ.: Universität Leipzig
City: Leipzig
Published: 22.07.2010
Tags: Stadtler, Wirtschaftsinformatik
 
Card tags:
All cards (67)
Datenkomprimierung (8)
Graphenalgorithmen (31)
Optimierungsprobleme (10)
Suffixbäume (7)
Textsuche (9)
Report abuse

Cancel
Email

Password

Login    

Forgot password?
Deutsch  English