Unlösbarkeit

Question 1

Was sind unlösbare Probleme?

Answer 1

• Halteproblem <
• Vollständigkeitsproblem <
• Äquivalenzproblem
• Korrespondenzproblem

Question 2

Wie ist die Reduktion definiert?

Answer 2

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.

Question 3

Was ist das Vollständigkeitsproblem?

Answer 3

Wenn etwas in der Mathematik wahr ist, können wir auch zeigen, dass es wahr ist.

Question 4

Was ist das Äquivalenzproblem?

Answer 4

Programm, dass zwei Funktionen als Eingang hat, und prüft, ob diese denselben Ausgang haben.

Question 5

Wie nennt man die Klassen die nicht getestet werden können?

Answer 5

Funktionale Eigenschaften

Question 6

Wie lautet die Definition von funktionalen Eigenschaften?

Answer 6

1. Stellt funktionalen Zusammenhang zwischen Input und Output her
2. sie ist die Eigenschaft einiger Programme, aber nicht aller Programme.

Question 7

Satz von Rice?

Answer 7

Zu bestimmen, ob ein gegebenes Programm irgendeine funktionale Eigenschaft besitzt, ist unlösbar.

Question 8

Wie lautet, die erweiterte Church Turing These?

Answer 8

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.

Question 9

Welche 2 Problemklassen werden voneinander getränt?

Answer 9

• polynomieller Zeit lösbar

- exponentieller Zeit lösbar

Question 10

Wie viele mögliche Instruktionen könnte man auf der Erde ausführen?

Answer 10

10^51

Question 11

Problem wird in Abhängigkeit wovon betrachtet?

Answer 11

Problemgröße wird reduziert auf die n Symbole auf dem Band.

Question 12

Ist Quicksort ein langsamer Algorithmus?

Answer 12

Ja aus sich von KT ist Quicksort langsam.
Mehrheitlich: linear Log Laufzeit
Worstcase: quadratische Laufzeit

Question 13

Wann ist ein Algorithmus langsam und wann schnell?

Answer 13

Quadratische Laufzeit: langsam

linear-logarithmische Laufzeit: schnell

Question 14

Definition Polynomialzeit-Algorithmus?

Answer 14

Nach oben begrenzt durch a n^b.

-> leicht zu lösen

Question 15

Definition Exponetialzeit-Algorithmen?

Answer 15

Nach unten begrenzt durch 2^a*n^b

-> schwer zu lösen

Question 16

Wie lässt sich ein Int Multiplikator Algorithmus klassifizieren?

Answer 16

Laufzeit ist Lösbar in Polynomialzeit.

=> leicht lösbares Problem

Question 17

Zahlen in Primfaktorzerlegung?

Answer 17

schweres lösbares Problem Anzahl Iterationen: 10^n/2

Question 18

Teilmengensummen 3 Zahlen Problem?

Answer 18

Summe aus Integer-array muss eine Zahle ergeben. Mögliche Kombinationen finden.
=> leicht lösbares Problem
Laufzeit: n^3

Question 19

Knotenüberdeckungsproblem:

Answer 19

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

Question 20

Ist der kürzeste Wege Algo ein Leicht lösbares Problem?

Answer 20

Ja,

längste Wege Problem ist Exponentiell

Question 21

Was ist das muster eines schwer lösbaren Problems?

Answer 21

Versuche alle Möglichkeiten, um Problem zu lösen.

Nicht effektiv

Question 22

Was ist ein schwer lösbares Problem?

Answer 22

Probleme die der beste bekannte Algorithmus in exponentieller Zeit löst.

Question 23

Was ist ein leicht lösbares Problem?

Answer 23

Probleme, die in polynomieller Zeit gelöst werden können.

Question 24

Welche Erfüllbarkeitsproblem gibt es?

Answer 24

• Lineare Gleichung
• Lineare Ungleichung
• Ganzzahlige lineare Ungleichungen
• Boolesche Gleichungen

Question 25

Was für ein Problem stellt die lineare Gleichung dar?

Answer 25

“leicht lösbares” Problem

Gaußsches Eliminierungsverfahren

Question 26

Was für ein Problem stellt die lineare Ungleichung dar?

Answer 26

“leicht lösbares” Problem

Simplexalgorithmus

Question 27

Was für ein Problem stellt die ganzzahlige lineare Ungleichungen dar?

Answer 27

“schwer Lösbares” Problem
ILP -> oder 0/1 ILP
- Lösung des LP und dann runden auf nächsten Integer.

Question 28

Was für ein Problem stellt die boolesche Gleichungen dar?

Answer 28

“schwer Lösbares” Problem
SAT Problem
2 hoch Anzahl variablen Kombinationen.

Question 29

Was ist ein Suchproblem?

Answer 29

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.

Question 30

Such Problem normal?

Answer 30

Beim Suchproblem geht das darum einen Algorithmus zu finden der eine gefundene Lösung überprüft.

Question 31

Was heißt NP und wofür wird er verwendet?

Answer 31

Nichtdeterministisch Polynomielle Zeit

Um Suchprobleme zu beschreiben.

Question 32

Nenne NP Probleme?

Answer 32

Längste Wege
Faktorisieren
N-Teilmengen-Summe
Erfüllbarkeit linearer Gleichungen und Ungleichungen

Question 33

Mit welchen 3 Ansätz lässt sich das NP Problem definieren?

Answer 33

Suchproblem
Entscheidungsproblem
Optimierungsproblem

Question 34

Was bedeutet der Nichtdeterminismus bei einer TM?

Answer 34

Computer hat die Macht richtige von zwei Optionen zu erraten.

Question 35

Wie sind die Probleme P definiert?

Answer 35

P ist Menge aller Suchprobleme die in Polynomialzeit gelöst werden können.

Question 36

Was heißt intectable?

Answer 36

Ein Problem ist nicht effizient lösbar, wenn es keinen Polynomialzeit-Algo gibt der es löst.