Informatik (Fach) / Grundlagen -Info 2 (Lektion)

...

Diese Lektion wurde von jakobdanel erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• (deterministischer) Algorithmus 5 Stichpunkte - Diskretheit - Effektivität - Terminierung - Finitheit - Vollständigkeit
• Analyse von Algorithmen (3 Punkte) - Korrektheit - Zeitkomplexität - Speicherkomplexität
• Leistungsfähigkeit (Algorithmus) - Beschreibt die Perfomanz - Schnelligkeit ein Problem einer bestimmten Größe zu lösen -(kann praktische Grenzen eines Algorithmus benennen)
• Verwendung von Ressourcen (Algorithmus) - Speicherkomplexität - Wie viele Ressourcen werden pro Komplexitätsgrad verbraucht
• Güte (Algorithmus) - Analyse von Zeit- und Speicherkomplexität - Muss von Fall zu Fall abgewogen werden
• Datenstruktur Konstrukt zum speichern und verwalten von Daten, wobei Zugriffs- und Modifikationsoperation möglichst effizient sein sollen
• Insertion Sort Sortieralgorithmus Unter der Annahme die ersten n Elemente richtig sortiert zu haben, dass n+1.te Element einfügen und dafür die sortierte Liste von hinten nach vorne durchlaufen
• Schleifeninvarianten Ein Wahrheitswert, der in jeder Interation der Schleife wahr ist, sowie nach der letzten Schleife Wird zum Zeigen der Korrektheit eines Algorithmus benötigt.
• Korrektheit (Schleifeninvariante) 3 Schritte 1. Initialisierung 2. Schritt 3. Terminierung
• Absolute Laufzeit - Laufzeit die ein Computerprogramm zum ausführen eines Algorithmus benötigt - Ist abhängig von Hardware/Software - Nicht sinnvoll um Laufzeiten theoretisch zu Vergleichen
• Laufzeit in abstrakten Rechnermodellen - Betrachtung der Laufzeit in einem abstrakten Rechnermodell - Hat nur Elementare Operationen - Kann sehr komplex werden zu berechnen
• Asymptotische Komplexität - Problem hat eine größe n - Betrachtung einer Funktion, welche den Aufwand abschätzt -Weglassen von konstanten
• Worst Case (Laufzeit) Schlechtmöglichste/längste Laufzeit eines Algorithmus
• Average Case (Laufzeit) Durchschnittliche/mittlere Laufzeit eines Algorithmus
• Best Case (Laufzeit) - Schnellstmöglichste/bestmöglichste Laufzeit eines Algorithmus
• Asymptotische Komplexitätsklasse - Nur asymptotische Betrachtung der Laufzeit, d.h. konstanten fallen weg, Einordnung eines Algoritmus in eine Komplexitätsklasse
• Asymptotisch obere Schranke ?(?(?)) ={?(?)| ∃? > 0, ?0 ∈ ℕ: ∀? ≥ ?0: 0 ≤ ?(?) ≤ ? * ?(?)} - Menge aller Funktionen die höchstens so schnell wachsen wie g
• Asymptotisch untere Schranke Ω(?(?)) = {?(?)| ∃? > 0, ?0 ∈ ℕ: ∀? ≥ ?0: 0 ≤ ? * ?(?) ≤ ?(?)} - Menge aller Funktionen die mindestens so schnell wachsen wie g 
• Nicht-scharfe obere Schranke ?(?(?)) = {?(?) | ∀? > 0 ,∃?0 ∈ ℕ: ∀? ≥ ?0: 0 ≤ ?(?) ≤ ? * ?(?)} - beschreibt die Menge aller Funktionen, die asymptotisch weniger schnell wachsen als g - lim (f(n)/g(n)) = 0
• Nicht-scharfe untere Schranke ?(?(?)) = {?(?) | ∀? > 0 ∃?0 ∈ ℕ: ∀? ≥ ?0: 0 ≤ ? * ?(?) ≤ ?(?)} - Beschreibt die Menge aller Funktionen die asymptotisch schneller wachsen - lim ?→∞ ?(?) / ?(?) = ∞
• Laufzeiten: Insertion Sort Worst Case: Theta(n²) Best Case: Theta(n) Average: Theta(n²)
• Insertion Sort Speicherbedarf in-situ
• in-situ Alle Algorithmen, welche einen Speicherbedarf von Theta(1) haben heißen in-situ (Der Speicherbedarf für die Eingabefolge wird dabei nicht beachtet)
• Divide & Conquer (Ansatz) - Teile & Herrsche - Zerteilt das Teilproblem solange rekursiv in kleinere Probleme, bis diese trivial werden - Dann müssen diese Teile nur noch zusammengeführt werden 1. Teilen (Divide) 2. Bearbeiten ...
• Merge Sort (Idee) - Verfolgt D&C Ansatz - Rekursives Teilen der Liste in Teillisten, bis Listen die Länge 1 haben - Dann zusammenführen von zwei Listen mit dem Vorteil, das die Teillisten bereits sortiert sind
• Wächter - Auch Sentinel, ein Dummy Objekt, welches dem Algorithmus hinzugefügt wird, um sich bsps. Fallunterscheidungen in Randpunkten zu ersparen
• Rekurrenz Ist eine Gleichung, welche rekursiv eine Folge über einem gegebenen Startwert definiert, tritt bsp. beim aufstellen von Komplexitätsfunktionen von D&C Algorithmen auf
• Rekursionsbaum - Möglichkeit Rekurrenz zu lösen - Weiterführen der Rekurrenzschritte als Kinder des Baumes - Die Elternknoten dann durch den zusätzlichen Term ersetzen - Durchgehen bis zum Basisfall - Berechnung ...
• Merge Sort Zeitkomplexität T(n) =Θ(n * lg n)
• Merge Sort Speicherbedarf S(n) =Θ(n)
• Substitutionsmethode - Möglichkeit zum Lösen von Rekurrenzen - 3 Schritte: 1. Vermutung für Lösung 2. Beweis per Induktion 3. Aufstellen von Konstanten
• Mastertheorem - Möglichkeit zum Lösen von Rekurrenzen - Möglichkeit für Gleichungen der Form T(n) a * T(n/b) + f(n) - Dann wird f(n) mit nlogba verglichen und der dominante Term bestimmt - Es gibt demnach drei ...
• Mastertheorem 1. Fall f (n) = ?(n log ba- ε) ⇒ T(n) = Θ(n log ba )
• Mastertheorem 2. Fall f (n) = Θ(n log ba) ⇒ T(n) = Θ(n log ba lg n)
• Mastertheorem 3. Fall f (n) = Ω(n log ba+ ε) und a⋅ f (n/b) ≤ c⋅ f(n) für c > 1 ⇒ T(n) = Θ(f (n))
• Potenzen Naiver Ansatz die Basis n mal mit sich selbst multiplizieren, wobei n der Exponent ist
• Potenzen D&C Ansatz Ausnutzen der Potenzgesetze Potenz von n/2 rekursiv ausrechnen und diese Ergebnisse quadrieren Fallunterscheidung gerade/ungerader Exponent
• Fibonacci Zahlen Iterativ Iteratives Berechnen der Fibonacci Zahlen mit merken der beiden Vorgänger Laufzeit: Theta(n)
• Fibonacci D&C Man kann mithilfe einer 2 X 2 Matrix welche hoch n gerechnet wird, die Fibonacci Zahlen estimmen, dann kann der Divide & Conquer Ansatz zum Potenzieren genutzt werden
• Matrixmultiplikation Naiv Iterieren über Eingaben, berechnung nach Definition Lange Laufzeit, für große Matrizen
• Matrixmultiplikation D&C Teilen der Eingabematrix in 4 Teilmatrizen, diese dann rekursiv berechnen allerdings nicht schneller als Naive Ansatz
• Matrixmultiplikation Strassen - Folgt dem D&C Ansatz, braucht jedoch nur 7 Berechnungen pro Rekursionsschritt statt acht, und kann so die Laufzeit drücken
• Datenstruktur Heap - Ein fastvollständiger Binärbaum, zum Abspeichern von Objekten - Kann als Array gespeichert werden
• Tiefe eines Heaps Tiefe ℎ = floor (lg (n))
• Max-Heap (Min-Heap) - Folgt der Eigenschaft, dass Elternknoten immer größer (Min-Hap: Kleiner) sind als ihre Kinder
• Heap Sort Herstellen der Max-Heap Eigenschaft Vertauschen des ersten Elements mit dem letzten Element, dann verkleinern des Heapbereichs um 1 und wiederherstellen der Heap-Eigenschaft, dies Iterativ fortsetzen, ...
• Heap Sort - Laufzeit ?(?) = ?(? * lg ?)
• Heap Sort Speicheredarf in-situ (Außnahme Rekursionsstack)
• Vorrangwarteschlangen - Speichert welches Element als nächstes bearbeitet wird, nach einer gegebenen Ordnung - Lässt sich als max-Heap implementieren

zurück  |  weiter 1 / 1