Einführung Komplexität

Question 1

Nichtdeterministische Turing-Maschine

Answer 1

Question 2

k kann von Startkonfiguration erreicht werden (Berechnungspfad)

Answer 2

Question 3

Zertifikat - Definition

Answer 3

Question 4

M berechnete Funktion

Answer 4

Question 5

Mächtigkeit von DTM und NTM - Theorem

Answer 5

Für jede NTM N gibt es eine DTM M mit T(M) = T(N)

Question 6

Was ist die Zentrale Frage der algorithmischen Komplexität

Answer 6

Wann ist ein Algorithmus effizient bzw. ein Berechnungsproblem effizient lösbar?

Question 7

0-Notation zur Laufzeitanalyse - Definition

Answer 7

Question 8

Was will man mit der 0-Notation erreichen

Answer 8

Effizienz von Algorithmen unabhängig von Rechnetechnik & Programmiersprache bestimmen.

Question 9

time_M - Definition

Answer 9

Question 10

DTIME(f(n)) - Definition

Answer 10

Question 11

P - Definition

Answer 11

“deterministisch, in Plynomzeit”

Question 12

time_N - Definition

Answer 12

Question 13

NTIME(f(n)) - Definition

Answer 13

Question 14

NP - Definition

Answer 14

Question 15

In welchem Mengenverhältnis stehen P und NP

Answer 15

P ist eine Teilmenge von NP

Question 16

Alternative Definition für NP (“Guess and Check”)

Answer 16

Question 17

Ist P = NP?

Answer 17

Man weis es nicht, geht aber davon aus, das P eine echte Teilmenge von NP ist.

Question 18

3(2)-Coloring - Problem

Answer 18

Question 19

Wie schwierig ist das 3(2)-Coloring Problem?

Answer 19

Beide Probleme liegen in NP und 2-Coloring sogar in P

Question 20

Shortest Path (Longest Path) - Problem

Answer 20

Question 21

3-SAT (2-SAT) - Problem

Answer 21

Question 22

Wie schwierig ist das Shortest Path (Longest Path) Problem?

Answer 22

Beide Probleme liegen in NP und Shortest Path liegt sogar in P (Breitensuche).

Question 23

Wie schwierig ist das 3-SAT (2-SAT) Problem ?

Answer 23

Beide Probleme liegen in NP und 2-SAT liegt sogar in P.