This answer only contains an image and but text.

BKT

BKT mündliche Prüfung

0.0 (0)

C. M.

Lernen

C. M.

Über diese Lernkartei

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.

Karten

Lernende

Sprache

Deutsch

Kategorie

Informatik

Stufe

Universität

Erstellt / Aktualisiert

08.03.2017 / 16.06.2021

Ähnliche Karteien

Definition eines Alphabetes

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition Wort

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition formale Sprache

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition reguläre Sprache

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Wort / Suffix / Präfix

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition Palindrom

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition Automat

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definiton Automat akzeptiert Wort

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Definition erkennbare Sprache

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

Äquivalenz / Nützlichkeit / Reduzierbarkeit von Automaten

Tastatur-Befehle:

= drehen,

= vor-/rückwärts,

= scrollen

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

Lernkarten

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

Lernen

BKT

Lernkarteien erstellen oder kopieren

Lernkarten

Bitte melde dich an

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog