Welche herangehensweisen gibt es für den Algorithmenentwurf?
Iterativ
Rekursiv
Bei einem iterativen Algorithmus werden?
Einzelanweisungen wiederholt aufgerufen
Bei einem iterativen Algorithmus ist der?
Algorithmenaufruf leichter Nachvollziehbar, wodurch sich die Laufzeit und der Speicherbedarf einfacher abschätzen lässt
Ein rekursiver Algorithmus?
Ruft sich selbst auf
Ein rekursiver Algorithmus ist gegenüber einem iterativen Alogorithmus?
Meist weniger Effizient
Weshalb ist ein rekursiver Algorithmus meist weniger effizient als ein iterativer Algorithmus?
Da wiederholt die gleiche Methode aufgerufen wird und der entsprechende Kontext gespeichert werden muss
Bedeutung: Induktion
Beweisführung
Woraus besteht eine Induktion
Induktionsanfang
Induktionsvoraussetzung
Induktionsschritt
Es wird bewiesen, dass die Aussage für den Startwert gilt
Induktionsvorraussetzung
Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt
Kann weggelassen werden da reine Schreibarbeit
Folgendes wird bewiesen: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für die Zahl eins größer
Methoden des Algorithmen-Entwurfs
Greedy
Divide and Conquer
Dynamische Programmierung
Was ist Charachteristisch für einen Greedy Algorithmus?
Dass dieser zu jedem Zeitpunkt die aktuell beste bekannte Lösung als nächsten Schritt des Algorithmus realisiert
Besipiele von Greedy Algorithmen
Dijkstra-Algorithmus
Kruskal-Algorithmus
Prim-Algorithmus
Funktionsweise von Divide and Conquer Algorithmen?
Hauptproblem in Teilprobleme zerlegen
Teilprobleme isoliert lösen
Nach erfolgreichem Lösen der Teilprobleme, zusammensetzten der Teillösungen zur Lösung
Beispiele von Divide and Conquer Algorithmen
Binary-Search
Min-Max-Algorithmus
Die Dynamische Programmierung ist?
Ein Extremfall des Teile-und-beherrsche-Vorgehens
Grundidee der Dynamischen Programmierung?
Alle Teilprobleme werden der Reihenfolge nach gelöst, die so gewonnenen Ergebnisse abgespeichert und wiederverwendet, um das Lösen des nächsten größeren Problems zu ermöglichen
Die Korrektheit eines Algorithmus ist?
Meist nur sehr schwer bis gar nicht zu bewiesen
Anstatt die Korrektheit eines Algorithmus zu beweisen wird der Algorithmus?
Unter vielen verschiedenen Fallszenarien getestet
Gilt als korrekt wenn er im Bezug auf eine gegebene Spezifikation korrekt arbeitet
Mögliche Fehlerquellen, die die Korrektheit eines Algorithmus beeinflussen?
Sprach- oder Syntaxfehler
Logische oder semantische Fehler
Endlosschleifen
Da Algorithmen auf Daten operieren, muss deren Spezifikation auf?
Den Zustand dieser Daten vor Ausführung des Algorithmus (Vorbedingung) und den Zustand der Daten nach Ausführung des Algorithmus (Nachbedingung) spezifiziert werden
Ein Charakteristikum, das einen wesentlichen Teil der Korrektheit eines Algorithmus darstellt sind?
Randbedingungen, unter denen ein Algorithmus terminiert
Das Halteproblem ist?
Nicht entscheidbar
Ein Algorithmus kann allgemein die Frage, ob ein Programm am Ende terminiert oder nicht?
Nicht allumfassend beantworten
Es existiert kein Algorithmus, welcher entscheided?
Ob ein Algorithmus korrekt ist oder nach welcher Laufzeit dieser terminiert, was die individuelle Beantwortung dieses Problems erfordert
Ein Algorithmus kann jenachdem ob die terminierung eine notwendige Eigenschaft ist wie sein?
partiell korrekt
total korrekt
Ein partiell korrekter Algorithmus ist korrekt wenn?
Die gelieferten Ergebnisse für alle Eingabewerte korrekt sind, der Algorithmus aber nicht notwendigerweise für jede zulässige Eingabe terminiert
Ein total korrekter Algorithmus ist korrekt wenn?
Ein korrekter Algorithmus für alle zulässigen Eingaben auch terminiert
Was wird bei dem Backtesting eines Algorithmus getan?
Der Vergleich der vom Algorithmus berechneten Ergebnisse und der bereits vorab bekannten Ergebnisse
Das Backtesting ist?
Eine unvollständige Verifikation eines Algorithmus
Neben der Korrektheit eines Algorithmus ist es insbesondere von großer Bedeutung, dass ein Algorithmus?
Möglichst schnell terminiert
Die möglichst schnelle Terminierung eines Algorithmus fällt unter das Problemfeld der?
Laufzeitbestimmung
Das Ziel der Laufzeitbestimmung ist?
Eine obere asymptotische Grenze zu finden, der sich die Laufzeit des Algorithmus in Abhängigkeit der zur Berechnung notwendigen Rechenschritte annähert
Welche Notation wird bei der Laufzeitbestimmung verwendet?
Die O-Notation
Die Laufzeit eines Algorithmus wird dabei in der Informatik so angegeben, dass?
Llediglich die Funktion genannt wird, die die eigentliche Laufzeit des vorliegenden Algorithmus nach oben hin beschränkt
Was wird bei der Laufzeitbestimmung vernachlässigt?
Lineare Vorfaktoren
Ein Algorithmus zeigt eine polynominelle Zeitkomplexität, wenn?
Für die Laufzeit des Algorithmus O(n^k) gilt
Was bezeichntet P?
Die Menge aller Entscheidungsprobleme mit einer polynominellen Laufzeit
Ein Nichtdeterministischer Algorithmus ist ein Algorithmus?
Dessen Zustand nicht deterministisch erfassbar ist
Ein Entscheidungsproblem hat eine nichtdeterministische polynominelle Zeitkomplexität, wenn es zur Lösung des Problems einen?
Nichtdeterministischen Algorithmus gibt, welcher eine polynominelle Laufzeit aufweist
Was bezeichnte NP?
Die Menge aller Entscheidungsprobleme mit einer nichtdeterministischen polynominellen Laufzeit
Es wird vermutet, dass was gilt?
P teilmenge NP
Beispiel für ein NP Problem?
Handelsreisender Problem
Aufbau einer Turingmaschiene
Unendlich Langes Band mit Feldern, in denen die Eingangsdaten abgelegt sind
Ablauf einer Turingmaschiene
Einlesen der felder
Ausführen der Rechenoperationen
Ausgeben der Resultate
Mit jeder Rechenoperation und jedem eingelesenem Zeichen nimmt die Turingmaschine?
verschiedene Zustände an
Eine Funktion, welche durch eine Turingmaschine berechnet werden kann, wird wie bezeichnet?
„Turing-berechenbar“ bzw. „berechenbar“
Turingmaschinen werden vor allem für?
Entscheidungsprobleme verwendet
Entscheidungsprobleme sind?
Probleme mit nur zwei möglichen Lösungen, Ja oder Nein
Zuletzt geändertvor einem Jahr