This answer only contains an image and but text.

BKT

BKT mündliche Prüfung

0.0 (0)

C. M.

Étudier

C. M.

À propos de ce fichier

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.

Cartes-fiches

Utilisateurs

Langue

Allemand

Catégorie

Informatique

Niveau

Université

Créé / Mis à jour

08.03.2017 / 16.06.2021

Fichiers de cartes similaires

Definition eines Alphabetes

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition Wort

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition formale Sprache

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition reguläre Sprache

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Wort / Suffix / Präfix

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition Palindrom

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition Automat

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definiton Automat akzeptiert Wort

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Definition erkennbare Sprache

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

Äquivalenz / Nützlichkeit / Reduzierbarkeit von Automaten

Commandes clavier:

= tourner,

= avant/arrière,

= faire défiler

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

Cartes-fiches

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

Étudier

BKT

Créer ou copier des fichiers d'apprentissage

Cartes-fiches

Veuillez vous connecter

Google

Apple ID

Microsoft

Switch edu-ID

Edulog

Google

Apple ID

Microsoft

Switch edu-ID

Edulog