This answer only contains an image and but text.

BKT

BKT mündliche Prüfung

0.0 (0)

C. M.

Study

C. M.

About these flashcards

Diese Lernkarten bieten einen Überblick über grundlegende Konzepte der Informatik auf Universitätsniveau. Sie behandeln Themen wie Automaten, Sprachen und Turing-Maschinen, wobei auch spezifische Begriffe wie NEA, DEA und reguläre Ausdrücke erklärt werden. Die Karteikarten sind besonders nützlich für Studierende, die sich mit der Theorie der Berechenbarkeit und Komplexität auseinandersetzen, da sie wichtige Algorithmen und Beweise, wie den Satz von Kleene, abdecken. Zudem werden NP-vollständige Probleme wie 3SAT und CLIQUE behandelt, was für das Verständnis der Komplexitätstheorie essenziell ist.

Flashcards

Students

Language

German

Category

Computer Science

Level

University

Created / Updated

08.03.2017 / 16.06.2021

Similar cards

Definition eines Alphabetes

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition Wort

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition formale Sprache

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition reguläre Sprache

Keyboard commands:

= turn,

= for-/backward,

= scroll

Wort / Suffix / Präfix

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition Palindrom

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition Automat

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definiton Automat akzeptiert Wort

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition erkennbare Sprache

Keyboard commands:

= turn,

= for-/backward,

= scroll

Äquivalenz / Nützlichkeit / Reduzierbarkeit von Automaten

Keyboard commands:

= turn,

= for-/backward,

= scroll

Definition normalisierter Automat

Definition DFA = deterministischer endlicher Automat

Definition abzählbar unendlich / abzählbar / überabzählbar

Definition Turingmaschine

(turing-) erkennbar / (turing-) entscheidbar

Definition Reduzierbarkeit von Problemen

Definition LBA

Komplexitatsklassen

PATH

RELPRIME

HAMPATH

CLIQUE

CLIQUE ist NP-vollstandig.

SUBSET-SUM

Definition Polynomialzeit reduzierbar

3SAT

3SAT ist NP-vollstandig

Satz von Kleene

Der Satz von Kleene besagt, dass die Sprachen die durch einen Regulären Ausdruck beschrieben werden können identisch mit den Regulären Sprachen sind.

Satz von Rice

Ardens Lemma

Unterschied DEA <> NEA

- NEA mehrere Kanten für ein Zustand

- NEA kein Übergang für einen Zustand

- NEA kann ein oder mehrere Übergänge mit dem leeren Wort haben

1 / 29

Flashcards

Definition eines Alphabetes

Definition Wort

Definition formale Sprache

Definition reguläre Sprache

Wort / Suffix / Präfix

Definition Palindrom

Definition Automat

Definiton Automat akzeptiert Wort

Definition erkennbare Sprache

Äquivalenz / Nützlichkeit / Reduzierbarkeit von Automaten

Definition normalisierter Automat

Definition DFA = deterministischer endlicher Automat

Definition abzählbar unendlich / abzählbar / überabzählbar

Definition Turingmaschine

(turing-) erkennbar / (turing-) entscheidbar

Definition Reduzierbarkeit von Problemen

Definition LBA

Komplexitatsklassen

PATH

RELPRIME

HAMPATH

CLIQUE

CLIQUE ist NP-vollstandig.

SUBSET-SUM

Definition Polynomialzeit reduzierbar

3SAT

3SAT ist NP-vollstandig

Satz von Kleene

Der Satz von Kleene besagt, dass die Sprachen die durch einen Regulären Ausdruck beschrieben werden können identisch mit den Regulären Sprachen sind.

Satz von Rice

Ardens Lemma

Unterschied DEA <> NEA

- NEA mehrere Kanten für ein Zustand

- NEA kein Übergang für einen Zustand

- NEA kann ein oder mehrere Übergänge mit dem leeren Wort haben

Study

BKT

Create or copy sets of flashcards

Flashcards

Please log in

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog