Grundlagen der Informatik zusammengefasst
Grundlagen der Informatik zusammengefasst für Klausur
Grundlagen der Informatik zusammengefasst für Klausur
-
- 1 / 115
-
Lernkarten
2.3.6 Quick-Sort
2.3.6.1 Funktionsweise
Aufteilung der zu sortierenden Liste in zwei Teillisten („linke“ und „rechte“ Teilliste. Dazu wählt Quicksort ein Pivotelement aus der Liste aus. Alle Elemente, die kleiner als diese sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Anschließend muss man also nur noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion.
Die Positionen der Elemente, die gleich dem Pivotelement sind, hängen vom verwendeten Teilungsalgorithmus ab. Sie können sich beliebig auf die Teillisten verteilen.
Das Verfahren muss sicherstellen, dass jede der Teillisten mindestens um eins kürzer ist als die Gesamtliste. Dann endet die Rekursion garantiert nach endlich vielen Schritten. Das kann z. B. dadurch erreicht werden, dass das ursprünglich als Pivot gewählte Element auf einen Platz zwischen den Teillisten gesetzt wird und somit zu keiner Teilliste gehört.
Das ganze ist multiprozessorfähig, da man die Daten zweiteilt -> Rekursion pro Teil ein Thread
2.3.6 Quick-Sort
2.3.6.2 Komplexität
Best Case: O(n * log (n)) - gilt auch für den Average Case
Worst Case: O(n²) - Pivot wählt stets das größte Element
2.3.6 Quick-Sort
2.3.6.3 Pseudocode
funktion quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler-1)
quicksort(teiler+1, rechts)
ende
ende
Funktion teilen:
funktion teile(links, rechts)
i := links
// Starte mit j links vom Pivotelement
j := rechts - 1
pivot := daten[rechts]
wiederhole
// Suche von links ein Element, welches größer als das Pivotelement ist
wiederhole solange daten[i] ≤ pivot und i < rechts
i := i + 1
ende
// Suche von rechts ein Element, welches kleiner als das Pivotelement ist
wiederhole solange daten[j] ≥ pivot und j > links
j := j - 1
ende
falls i < j dann
tausche daten[i] mit daten[j]
ende
solange i < j // solange i an j nicht vorbeigelaufen ist
// Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
falls daten[i] > pivot dann
tausche daten[i] mit daten[rechts]
ende
// gib die Position des Pivotelements zurück
antworte i
ende
2.3.7 Bucket-Sort
2.3.7.1 Funktionsweise
Sortierverfahren, welches für bestimmte Werte-Verteilungen eine Eingabe-Liste in linearer Zeit sortiert. Algorithmuseinteilung in drei Phasen:
-
Verteilung der Elemente auf die Buckets (Partitionierung)
-
Jeder Bucket wird mit einem weiteren Sortierverfahren, wie beispielsweise Insertionsort sortiert.
-
Der Inhalt der sortierten Buckets wird wieder zu einer Liste zusammengefasst, ohne dabei die Reihenfolge der sortierten Elemente zu verändern.
Verfahren arbeitet also „out-of-place“ (= wenn die Ausgabedaten gesondert gespeichert und nicht die Eingabedaten damit überschrieben werden).
2.3.7 Bucket-Sort
2.3.7.2 Komplexität
Best Case: O(n) - einer pro Bucket
Worst Case: O(n2) alles in einem Bucket mit Insertionsort
2.3.7 Bucket-Sort
2.3.7.3 Pseudo-Code
bucket_sort(l, f)
n = l.size
buckets = array(n)
foreach (e in l)
buckets[ floor(f(e) * n) ].add(e)
r = []
foreach (b in buckets)
x = insertion_sort(b)// auch anderer Sortieralgorithmus möglich
r.append(x)
return r
3. Graphen
3.1 Allgemeines zu Graphen
3.1.1 Definition:
Darstellung einer Menge von Objekten zusammen mit deren Beziehungen(Relationen)
3.1.2 Arten (Gerichtet/Ungerichtet)
Gerichtet: Gerichteter Graph ist durch einen Pfeil, der in eine bestimmte Richtung zeigt, erkennbar.
-
Ungerichtet: sind symmetrisch, haben keine Richtung
-
Ungerichtete Graphen kann man stets durch gerichtete ersetzen, jedoch NICHT umgekehrt.
3.1.3 Knoten/Kanten
Eine Kante ist ein Paar von Knoten und verbindet diese in Relation bestehende Objekte. Somit sind die Knoten Nachbarn ("adjazent").
3.1.4 Grad
Gesamtzahl aller eingehenden und ausgehenden Kanten. Hierbei nochmalige Unterscheidiung in Eingangsgrad & Ausgangsgrad
3.1.5 Pfad
Ein Pfad ist eine Folge von, mit Kanten verbundenen, Knoten 1 bis Knoten n.
3.1.6 Länge
Länge = Anzahl der Knoten -1
z.B.: Man hat einen Knoten -> Länge = 0; Man hat 3 Knoten -> Länge = 2
3.1.7 Einfacher Pfad
Für einen einfachen Pfad gilt stets, dass alle enthaltenen Knoten paarweise verschieden sind. Eine erlaubte Ausnahme besteht im "Anfangs- und Endknoten" -> v1 = vn
3.1.8 Zyklus
Bedingung, dass "Anfangs- und Endknoten" identisch sind. Erfüllt der Zyklus die Bedingungen des einfachen Pfades= einfacher Zyklus
3.1.9 Eulerweg
Ein Pfad heißt dann Eulerweg, wenn er jede Kante des Graphen genau einmal durchläuft.
Beispiel: Haus vom Nikolaus
3.1.10 Eulerkreis
Ein Zyklus heißt dann Eulerkreis, wenn er jede Kante des Graphen genau einmal durchläuft.
3.1.11 Unterschied Eulerweg und Eulerkreis
Der Eulerweg fängt an einem Punkt an, endet an einem anderen Punkt.
Beim Eulerkreis: Anfangspunkt = Endpunkt. Somit handelt es sich hier um einen Zyklus.
3.1.12 Baum
Ein Baum ist ein zusammenhängender, zyklenfreier Graph
3.1.13 Wald
Ein Wald ist eine Menge paarweise, zusammenhängender Bäume.
3.1.14 Teilgraph
Graph (D'B') ist ein von Teilgraph von Graph (DB), wenn D' eine Teilmenge von D und B' eine Teilmenge von B ist
3.1.15 Starke Verbindung
zwei Knoten eines gerichteten Graphs sind dann stark verbunden, wenn es einen Pfad hin und einen Pfad zurück gibt
3.2 Möglichkeiten, um mit Graphen zu agieren
3.2.1 Adjazenz
3.2.1.1 Adjazenzliste
Möglichkeit, Graphen im Computer zu speichern. Sie wird in ihrer einfachsten Form durch eine einfach verkettete Liste dargestellt, wobei jeder Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) besitzt. Das Array hat dabei die Länge n = |V|.
Vorteile: Geringer Platzbedarf: O(|V| + |E|)
Nachteil: Test auf Nachbarn: O(n)
3.2.1.2 Adjazenzmatrix
Möglichkeit, Graphen im Computer zu speichern. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine nXn-Matrix ergibt. Ein Eintrag in der i-ten Zeile und j-ten Spalte gibt hierbei an, ob eine Kante von dem i-ten zu dem j-ten Knoten führt. Steht an dieser Stelle eine 0, ist keine Kante vorhanden – eine 1 gibt an, dass eine Kante existiert.
Vorteile: → Existenz einer Kante (Inzidenz): O(1)
Nachteile: → Platzbedarf: O(n²)
Auffinden aller Nachfolger eines Knoten: O(n)
3.2.2 Expansion
Die Expansion X(v) eines Graphen G mit einem Knoten v ist ein Baum, der wie folgt definiert ist:
-
Ist v ein Blatt, dann ist X(v) der Baum, der nur aus dem Knoten v besteht.
-
Wenn v1, ..., vk Nachfolger von v sind, so ist X(v) der Baum (v, X(v1), ..., X(vk)("einfacher": Der Baum listet alle vom Knoten v in G ausgehenden Pfade.)
-
Er ist unendlich, wenn der Graph Zyklen enthält.
-
Vorraussetzung für Tiefendurchlauf und für Breitendurchlauf.
3.2.3 Graphendurchlauf
3.2.3.1 Tiefendurchlauf
Bei der Tiefensuche zunächst ein Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden. Dabei sollen alle erreichbaren Knoten des Graphen besucht werden
Algorithmus (informell)
-
Bestimme den Knoten, an dem die Suche beginnen soll
-
Expandiere den Knoten und speichere den kleinsten/größten (optional) noch nicht erschlossenen Nachfolger in einem Stack
-
Rufe rekursiv für jeden der Knoten in dem Stack DFS (Tiefensuche) auf
-
Falls der Stack leer sein sollte, tue nichts
-
Falls es keine nicht erschlossenen Nachfolger mehr gibt, lösche den obersten Knoten aus dem Stack und Rufe für den jetzt oberen Knoten im Stack DFS (depth first search oder Tiefensuche) auf
-
Falls das gesuchte Element gefunden worden sein sollte, brich die Suche ab und liefere ein Ergebnis
-
3.2.3.2 Breitendurchlauf
Es werden zunächst alle Knoten beschritten, die vom Ausgangsknoten erreichbar sind. Erst danach werden Folgeknoten beschritten (siehe Abbildung).
Algorithmus (informell)
-
Bestimme den Knoten, an dem die Suche beginnen soll, markiere ihn als besucht und speichere ihn in einer Warteschlange ab.
-
Entnimm einen Knoten vom Beginn der Warteschlange.
-
Falls das gesuchte Element gefunden wurde, brich die Suche ab und liefere „gefunden“ zurück.
-
Anderenfalls hänge alle bisher unmarkierten Nachfolger dieses Knotens ans Ende der Warteschlange an und markiere sie als besucht.
-
-
Wenn die Warteschlange leer ist, dann wurde jeder Knoten bereits untersucht. Beende die Suche und liefere „nicht gefunden“ zurück.
-
Wiederhole Schritt 2.
3.2.4 Dijikstra-Algorithmus
Der Dijikstra-Algorithmus ist ein Algorithmus aus der Klasse der "Greedy(Gierig)" Alogrithmen, der das Problem der kürzesten Pfade für einen gegebenen Startknoten löst. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem markierten Graphen.
3.2.5 Floyd-Algorithmus
In Floyds Version findet er die kürzesten Pfade zwischen allen Paaren von Knoten eines Graphen und berechnet deren Länge (APSP, all-pairs shortest path).
Geht der kürzeste Weg von u nach v durch w, dann sind die enthaltenen Teilpfade von u nach w und von w nach v schon minimal. Nimmt man also an, man kennt schon die kürzesten Wege zwischen allen Knotenpaaren, die nur über Knoten mit Index kleiner als k führen und man sucht alle kürzesten Wege über Knoten mit Index höchstens k, dann hat man für einen Pfad von u nach v zwei Möglichkeiten: Entweder er geht über den Knoten k, dann setzt er sich zusammen aus schon bekannten Pfaden von u nach k und von k nach v, oder es ist der schon bekannte Weg von u nach v über Knoten mit Index kleiner als k
3.3 TSP – Travelling Salesman Problem
3.3.1 Definition
Das Problem des Handelsreisenden(engl. "Traveling Salesman Problem", kurz: TSP) bedeutet, er (der Handelsreisende) soll alle Kanten eines Graphen passieren, ohne einen Knotenpunkt 2 mal besucht zu haben. Dabei soll er die kürzeste Route wählen. Der TSP ist eine Variante des Hamiltonkreisproblems.
Problem: Es gibt (n-1)!/2 Varianten, alle Knoten des Graphen zu passieren. Das Problem ist also NP-Vollständig.
3.3.2 NP-Vollständig
Ein NP-Vollständiges Problem bezeichnet ein Problem, das in Nichtdeterministische Polynomialzeit gelöst werden kann . Das heißt es gibt keine optimale Lösung, die in vertretbarer Zeit mit einer Rechenmaschine erarbeitet werden kann, denn die Lösungsmenge wächst überexponential. Das bedeutet auch, dass fur das betrachtete Problem (bisher) kein polynomieller Algorithmus gefunden wurde. NP-Vollständig ist die schwerste Gewichtung eines polynomialzeitlichen Problems
3.3.3 NP-Schwer/NP-Hart
Ein NP-Schwer oder NP-Hartes Problem bezeichnet ein Problem, das, wie das NP-Vollständige Problem, in Nichtdeterministische Polynomialzeit gelöst werden kann. Es gibt allerdings einen polynomiellen Algorithmus, der das Problem in absehbarer oder angemessener Zeit, wennn auch mit großer Rechenleistung lösen kann. Das bedeutet, dass ein Algorithmus, der ein NP-schweres Problem löst, benutzt werden kann, um alle Probleme in NP zu lösen.
3.3.4 Hamiltonkreis
Ein Pfad in einem Graphen, der jede Kante nur einmal durchläuft wird als Hamiltonkreis bezeichnet. Im Gegensatz zum Eulerkreis ist der Hamiltonkreis jedoch NP-Vollständig. Das TSP ist eine besondere Form des Hamiltonkreis, bei dem, bei einem Graphen mit gewichteten Pfaden, nach dem kürzesten/leichtesten Hamiltonkreis ermittelt wird.
3.3.5 Brute-Force Methode
Die Brute-Force (deutsch: "Rohe Gewalt") Methode ist eine simple Methode um eine Problemstellung in einer Variation zu lösen. Er testet einfach alle potentiellen Lösungswege durch und merkt sich das Resultat.
Die Brute-Force-Methode ist einfach zu implementieren und führt in aller Regel zum richtigen Ergebnis. Allerdings steigt der Aufwand proportional mit zunehmender Kombinationsmöglichkeit. Die Brute-Force Methode scheitert also an der Lösung sehr komplexer Problemstellungen, da die Rechenleistung exponential beansprucht wird.
3.4 Heuristik
3.4.1 Der Greedy-Algorithmus (Der gierige Algorithmus)
Ein Greedy-Algorithmus zeichnet sich dadurch aus, dass grundsätzlich immer die „beste“ Kante gewählt wird, (also die, die zum Zeitpunkt der Auswahl den größten Erfolg verspricht , deshalb „gierig“) ohne das Gesamtresultat zu berücksichtigen. Greedy-Algorithmen sind zwar schnell, doch ihre Lösungen sind oft nur kurzfristig optimal. Beispiele sind der Dijkstra-Algorithmus oder die Nearest-Neighbour-Heuristik.
Komplexität: T(n) = Θ (n²logn)
3.4 Heuristik
3.4.1 Der Greedy-Algorithmus (Der gierige Algorithmus)
Ein Greedy-Algorithmus zeichnet sich dadurch aus, dass grundsätzlich immer die „beste“ Kante gewählt wird, (also die, die zum Zeitpunkt der Auswahl den größten Erfolg verspricht , deshalb „gierig“) ohne das Gesamtresultat zu berücksichtigen. Greedy-Algorithmen sind zwar schnell, doch ihre Lösungen sind oft nur kurzfristig optimal. Beispiele sind der Dijkstra-Algorithmus oder die Nearest-Neighbour-Heuristik.
Komplexität: T(n) = Θ (n²logn)
3.4.2 Der Nearest-Neighbour-Algorithmus
3.4.2.1 Funktionsweise:
Gestartet wird an einem beliebigen Knoten. Von hier aus wird als nächster Knoten immer der gewählt, der den geringsten Abstand zum aktuellen Knoten hat und zuvor noch nicht gewählt wurde. Auf diese Weise wird fortgefahren, bis alle Knoten besucht wurden und man wieder am Startpunkt ankommt.
Algorithmus:
NearestNeighbour_TSP(w)
For i=1 To n Do
tour[i]=i
tour[n+1]=1
For i=2 To n-1 Do
next=argmin{ω[i-1,j] | j Є tour[i...n]}
vertausche tour[i] mit tour[next]
Return(tour)
Die Nearest-Neighbour-Heuristik wird beim TSP verwendet. Er gilt als ein Greedy-Algorithmus, da er immer die „beste“ Kante, in diesem Fall also die Kante mit dem geringsten Gewicht wählt, ohne die Distanz zwischen End- und Startknoten zu berücksichtigen. So kann es zu einer suboptimalen Lösung kommen.
Komlexität: T(n) = Θ (n²)
3.4.3 Minimum Spanning Tree-Heuristik
Die MST-Heuristik dient dazu, das Travelling salesman-Problem näherungsweise zu lösen. Folgende Vorgehensweise wird benutzt:
1. Man nimmt den ersten Knoten auf der linken Seite.
2. Von diesem Knoten aus werden sämtliche Knoten bis nach rechts hin besucht.
3. Löschung aller Wiederholungen
4. Erhalt eines einfachen Pfades, der alle Knoten besucht
3.4.4 Der Christofides Algorithmus (aufbauend auf der MST-Heuristik):
Der Christofides Algorithmus verwendet einen minimalen Spannbaum um eine erste Auswahl der für die Rundreise zu wählenden Kanten zu treffen. Es wird eine Rundreise ermittelt indem eine Eulertour durch einen Multigraphen gesucht wird. Dieser wird durch Bestimmen eines gewichtsminimalen perfekten Matchings auf der Menge der Knoten des Spannbaumes mit ungeradem Grad und Hinzufügen jeder Kante dieses Matchings zum Spannbaum. Die Auswertung des Multigraphen und somit die Eulertour wird nach Christofides nicht genauer beschrieben, da nur eine beliebige Eulertour gefordert ist.
3.4.5 Union – Find – Datenstruktur
Der Greedy Algorithmus muss herausfinden, ob ein Zyklus in einem Graph vorleigt oder nicht, wenn man eine Kante hinzugefügt hat. Union-Find ist hier sehr effizient, um dies festzustellen.
