Unlösbarkeit Flashcards
Was sind unlösbare Probleme?
- Halteproblem <
- Vollständigkeitsproblem <
- Äquivalenzproblem
- Korrespondenzproblem
Wie ist die Reduktion definiert?
Ein Problem A reduziert sich auf ein anderes Problem B, wenn wir jede Instanz a von A für eine Subroutine von B wie folgt lösen können.
Was ist das Vollständigkeitsproblem?
Wenn etwas in der Mathematik wahr ist, können wir auch zeigen, dass es wahr ist.
Was ist das Äquivalenzproblem?
Programm, dass zwei Funktionen als Eingang hat, und prüft, ob diese denselben Ausgang haben.
Wie nennt man die Klassen die nicht getestet werden können?
Funktionale Eigenschaften
Wie lautet die Definition von funktionalen Eigenschaften?
- Stellt funktionalen Zusammenhang zwischen Input und Output her
- sie ist die Eigenschaft einiger Programme, aber nicht aller Programme.
Satz von Rice?
Zu bestimmen, ob ein gegebenes Programm irgendeine funktionale Eigenschaft besitzt, ist unlösbar.
Wie lautet, die erweiterte Church Turing These?
Eine TM kann jede Berechnung (d.h. sich für eine Sprache entscheiden oder eine Funktion berechnen) effizient ausführen, die durch jedes physikalisch realisierbares Rechengerät beschrieben werden kann.
Welche 2 Problemklassen werden voneinander getränt?
- polynomieller Zeit lösbar
- exponentieller Zeit lösbar
Wie viele mögliche Instruktionen könnte man auf der Erde ausführen?
10^51
Problem wird in Abhängigkeit wovon betrachtet?
Problemgröße wird reduziert auf die n Symbole auf dem Band.
Ist Quicksort ein langsamer Algorithmus?
Ja aus sich von KT ist Quicksort langsam.
Mehrheitlich: linear Log Laufzeit
Worstcase: quadratische Laufzeit
Wann ist ein Algorithmus langsam und wann schnell?
Quadratische Laufzeit: langsam
linear-logarithmische Laufzeit: schnell
Definition Polynomialzeit-Algorithmus?
Nach oben begrenzt durch a n^b.
-> leicht zu lösen
Definition Exponetialzeit-Algorithmen?
Nach unten begrenzt durch 2^a*n^b
-> schwer zu lösen
Wie lässt sich ein Int Multiplikator Algorithmus klassifizieren?
Laufzeit ist Lösbar in Polynomialzeit.
=> leicht lösbares Problem
Zahlen in Primfaktorzerlegung?
schweres lösbares Problem Anzahl Iterationen: 10^n/2
Teilmengensummen 3 Zahlen Problem?
Summe aus Integer-array muss eine Zahle ergeben. Mögliche Kombinationen finden.
=> leicht lösbares Problem
Laufzeit: n^3
Knotenüberdeckungsproblem:
Finde eine Teilmenge mit höchstens m Knoten, die durch alle Kanten berührt werden.
für kleine m → polynomiell
für große m → exponentiell
Ist der kürzeste Wege Algo ein Leicht lösbares Problem?
Ja,
längste Wege Problem ist Exponentiell
Was ist das muster eines schwer lösbaren Problems?
Versuche alle Möglichkeiten, um Problem zu lösen.
Nicht effektiv
Was ist ein schwer lösbares Problem?
Probleme die der beste bekannte Algorithmus in exponentieller Zeit löst.
Was ist ein leicht lösbares Problem?
Probleme, die in polynomieller Zeit gelöst werden können.
Welche Erfüllbarkeitsproblem gibt es?
- Lineare Gleichung
- Lineare Ungleichung
- Ganzzahlige lineare Ungleichungen
- Boolesche Gleichungen
Was für ein Problem stellt die lineare Gleichung dar?
“leicht lösbares” Problem
Gaußsches Eliminierungsverfahren
Was für ein Problem stellt die lineare Ungleichung dar?
“leicht lösbares” Problem
Simplexalgorithmus
Was für ein Problem stellt die ganzzahlige lineare Ungleichungen dar?
“schwer Lösbares” Problem
ILP -> oder 0/1 ILP
- Lösung des LP und dann runden auf nächsten Integer.
Was für ein Problem stellt die boolesche Gleichungen dar?
“schwer Lösbares” Problem
SAT Problem
2 hoch Anzahl variablen Kombinationen.
Was ist ein Suchproblem?
Ein Suchproblem ist ein Problem, dessen Lösungen die Eigenschaft haben, dass es einen Polynomialzeit-Algorithmus gibt, der überprüfen kann, ob eine gegebene Lösung eine gegebene Probleminstanz löst.
Such Problem normal?
Beim Suchproblem geht das darum einen Algorithmus zu finden der eine gefundene Lösung überprüft.
Was heißt NP und wofür wird er verwendet?
Nichtdeterministisch Polynomielle Zeit
Um Suchprobleme zu beschreiben.
Nenne NP Probleme?
Längste Wege
Faktorisieren
N-Teilmengen-Summe
Erfüllbarkeit linearer Gleichungen und Ungleichungen
Mit welchen 3 Ansätz lässt sich das NP Problem definieren?
Suchproblem
Entscheidungsproblem
Optimierungsproblem
Was bedeutet der Nichtdeterminismus bei einer TM?
Computer hat die Macht richtige von zwei Optionen zu erraten.
Wie sind die Probleme P definiert?
P ist Menge aller Suchprobleme die in Polynomialzeit gelöst werden können.
Was heißt intectable?
Ein Problem ist nicht effizient lösbar, wenn es keinen Polynomialzeit-Algo gibt der es löst.
