Theoretische Informatik an der Universität Würzburg

Karteikarten und Zusammenfassungen für Theoretische Informatik an der Universität Würzburg

Arrow Arrow

Komplett kostenfrei

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Lerne jetzt mit Karteikarten und Zusammenfassungen für den Kurs Theoretische Informatik an der Universität Würzburg.

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Beispiele NP-Vollständige, NP-hard

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Wann ist eine Funktion total, surjektiv, injektiv, bijektiv?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Wie arbeitet eine RAM?

Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Erkläre den Unterschied zwischen While- und Python-Programmen!

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Erkläre die Arbeitsweise von Turing-Maschinen!

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Was ist der Unterschied zwischen "Laufzeit für konkrete Eingaben" und "Laufzeitschranken bezüglich Eingabelänge"?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Wie arbeitet ein DEA?

Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Erkläre die Akzeptierung durch DEA

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Wie arbeitet ein NEA?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Wie funktioniert der Leerheitstest?

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Sind reguläre Sprachen äquivalent zu Sprachen vom Typ 3?

Das war nur eine Vorschau der Karteikarten auf StudySmarter.
Flascard Icon Flascard Icon

Über 50 Mio Karteikarten von Schülern erstellt

Flascard Icon Flascard Icon

Erstelle eigene Karteikarten in Rekordzeit

Flascard Icon Flascard Icon

Kostenlose Karteikarten zu STARK Inhalten

Kostenlos anmelden

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Was ist besonders an nicht deterministischen Algorithmen und Maschinen?

Kommilitonen im Kurs Theoretische Informatik an der Universität Würzburg. erstellen und teilen Zusammenfassungen, Karteikarten, Lernpläne und andere Lernmaterialien mit der intelligenten StudySmarter Lernapp. Jetzt mitmachen!

Jetzt mitmachen!

Flashcard Flashcard

Beispielhafte Karteikarten für Theoretische Informatik an der Universität Würzburg auf StudySmarter:

Theoretische Informatik

Beispiele NP-Vollständige, NP-hard

Vollständig:

  • Rundreise
  • Rucksack

NP-hard:

  • Halteproblem

Theoretische Informatik

Wann ist eine Funktion total, surjektiv, injektiv, bijektiv?

total = Keine Definitionslücke

surjektiv = Alle Werte des Zielbereichs min. 1-mal vorhanden

injektiv = Jeder Wert aus Zielbereich max. 1-mal

bijektiv = total, surjektiv, injektiv

Theoretische Informatik

Wie arbeitet eine RAM?

  • taktweise
  • pro Takt wird genau ein Befehl ausgeführt (der Befehl dessen Nummer im Befehlsregister BR steht)
  • Start: in BR steht 0, d.h. Befehl mit Nummer 0 wird ausgeführt
  • Stopp: falls BR auf Stopp-Befehl zeigt, oder Befehl mit Nummer nicht existiert

Theoretische Informatik

Erkläre den Unterschied zwischen While- und Python-Programmen!

Python:

  • alle Konstrukte aus While erlaubt
  • Listen
  • keine strikte Klammerung notwendig
  • *, //, % erlaubt
  • Funktion ohne Rückgabewert

Theoretische Informatik

Erkläre die Arbeitsweise von Turing-Maschinen!

  • Start in Anfangssituation
  • Stopp, falls z_1 erreicht
  • taktweise in Abhängigkeit des Zustands und gelesener Symbole:
    • Zustand beibehalten/wechseln
    • Symbol schreiben
    • jeden Kopf um max. 1 Feld bewegen
    • (alles gleichzeitig)

Theoretische Informatik

Was ist der Unterschied zwischen "Laufzeit für konkrete Eingaben" und "Laufzeitschranken bezüglich Eingabelänge"?

  • Laufzeit für konkrete Eingaben:
    • Hier interessiert einen die Schritte/Takte bis zum Stopp
    • Eingabelänge höchstens indirekt interessant
  • Laufzeitschranke bezüglich der Eingabelänge:
    • Eingabelänge = Länge der dya Darstellung
    • Statt einer konkreten Eingabe, werden alle einer bestimmten Länge betrachtet
    • Auch wenn Eingaben alle gleich Lang sind, haben sie unterschiedliche Laufzeiten
    • => Also geben wir Laufzeitschranke an!

Theoretische Informatik

Wie arbeitet ein DEA?

  • Immer nur in einem von endlichen vielen Zuständen
  • Bekommt Wort als Eingabe
  • liest Eingabewort zeichenweise von links nach rechts
  • kann nach jedem gelesenen Zeichen Zustand wechseln

Theoretische Informatik

Erkläre die Akzeptierung durch DEA

  • Durchlaufe Eingabewort, wenn DEA am Ende in akzeptierenden Zustand 
    • => Eingabe akzeptiert

Theoretische Informatik

Wie arbeitet ein NEA?

Wie DEA außer:

  • kann in mehreren Zuständen gleichzeitig sein
  • kann nach jedem Zeichen in keinen/einen/mehrere Zustände wechseln
  • akzeptiert Wort, wenn min. einer der am Ende erreichten Zustände in F ist

Theoretische Informatik

Wie funktioniert der Leerheitstest?

Einfach nachschauen ob ein akzeptierender Zustand vom Start erreichbar ist

Theoretische Informatik

Sind reguläre Sprachen äquivalent zu Sprachen vom Typ 3?

Ja

Theoretische Informatik

Was ist besonders an nicht deterministischen Algorithmen und Maschinen?

  • nicht deterministische Algorithmen:
    • Arbeit kann auf parallele Rechenwege aufgeteilt werden
    • Eingabe akzeptiert, wenn min. 1 Rechenweg akzeptiert
    • (Rechenwege spalten sich also auf, man weiß nicht welchen man weiterverfolgt)
  • nicht deterministische Maschinen:
    • TM: Mehrere gleiche Befehle für eine Situation
    • RAM: Mehrere Befehle mit gleicher Nummer
    • WHILE: a1 = b1 | ... | ak = bk

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Theoretische Informatik an der Universität Würzburg zu sehen

Singup Image Singup Image

Theoretische Informatik III an der

Universität Stuttgart

Theoretische Informatik und Algorythmik an der

Technische Hochschule Mittelhessen

theoretische Informatik an der

Universität Tübingen

Theoretische Informatik I an der

Duale Hochschule Baden-Württemberg

Theorethische Informatik 3 (Arras) an der

Duale Hochschule Baden-Württemberg

Ähnliche Kurse an anderen Unis

Schau dir doch auch Theoretische Informatik an anderen Unis an

Zurück zur Universität Würzburg Übersichtsseite

Was ist StudySmarter?

Was ist StudySmarter?

StudySmarter ist eine intelligente Lernapp für Studenten. Mit StudySmarter kannst du dir effizient und spielerisch Karteikarten, Zusammenfassungen, Mind-Maps, Lernpläne und mehr erstellen. Erstelle deine eigenen Karteikarten z.B. für Theoretische Informatik an der Universität Würzburg oder greife auf tausende Lernmaterialien deiner Kommilitonen zu. Egal, ob an deiner Uni oder an anderen Universitäten. Hunderttausende Studierende bereiten sich mit StudySmarter effizient auf ihre Klausuren vor. Erhältlich auf Web, Android & iOS. Komplett kostenfrei. Keine Haken.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards