Theoretische Informatik an der Hochschule Darmstadt

Karteikarten und Zusammenfassungen für Theoretische Informatik an der Hochschule Darmstadt

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 Hochschule Darmstadt.

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei Σ = {0,1}. Die Sprache L enthält genau die Zeichenketten s ∈ Σ∗, die

gleichzeitig den Präfix 01 und den Suffix 1 haben.

1. Wie viele Zeichenketten s ∈ Σ∗ mit |s| ≤  4 gehören zur Sprache L?

2. Wie viele Zeichenketten s ∈ Σ∗ mit |s| ≤ 4 gehören nicht zu L?

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Ist das Entscheidungsproblem K-Clique effizient? 

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei G = (V, E) ein Graph mit 6 Knoten.

Wie groß kann eine größte Clique in G sein, wenn es in ihm genau drei Kanten gibt? 

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei G = (V, E) ein Graph mit 6 Knoten.

Wie groß kann eine größte Clique in G sein, wenn es in ihm genau fünf Kanten gibt?

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Welche Eingaben muss dieser Lösungsalgorithmus verarbeiten? 

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Welche Ausgaben muss dieser Lösungsalgorithmus bestimmen? 

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

1

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Was ist ein Alphabet Σ und wie nennt man die Elemente ?

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Was ist eine Zeichenkette (Wort)?

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Was bezeichnet Σ* und Σ+ ?

Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Für was steht a^n?


Beispielhafte Karteikarten für Theoretische Informatik an der Hochschule Darmstadt auf StudySmarter:

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Sei G = (V, E) ein Graph mit 10 Knoten. 

Wie oft muss A im schlimmsten Fall aufgerufen werden, um mit ihm die Frage zu beantworten, wie groß eine größte Clique in G ist?

Kommilitonen im Kurs Theoretische Informatik an der Hochschule Darmstadt. 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 Hochschule Darmstadt auf StudySmarter:

Theoretische Informatik

Sei Σ = {0,1}. Die Sprache L enthält genau die Zeichenketten s ∈ Σ∗, die

gleichzeitig den Präfix 01 und den Suffix 1 haben.

1. Wie viele Zeichenketten s ∈ Σ∗ mit |s| ≤  4 gehören zur Sprache L?

2. Wie viele Zeichenketten s ∈ Σ∗ mit |s| ≤ 4 gehören nicht zu L?

1: 01,011,0101,0111 = 4

2: 2^4+2^3+2^2+2^1+2^0 = 31 mögliche Kombinationen für |s| ≤ 4. 

31 - 4 (in L) = 27 Elemente in co(L)

Theoretische Informatik

Ist das Entscheidungsproblem K-Clique effizient? 

Nein. Bei einem Graph mit bspw. 30 Knoten und einer Clique der Größe 20 muss der Algorithmus im schlimmsten Fall für 30 über 20 viele Teilmengen, also 30.045.015 Mengen testen, ob C eine Clique in G ist. Das dauert mehr als acht Stunden

Theoretische Informatik

Sei G = (V, E) ein Graph mit 6 Knoten.

Wie groß kann eine größte Clique in G sein, wenn es in ihm genau drei Kanten gibt? 

3

Theoretische Informatik

Sei G = (V, E) ein Graph mit 6 Knoten.

Wie groß kann eine größte Clique in G sein, wenn es in ihm genau fünf Kanten gibt?

3. Für die Größe 4 benötigt man 6 Kanten. 

Theoretische Informatik

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Welche Eingaben muss dieser Lösungsalgorithmus verarbeiten? 

Menge der Knoten

Menge der Kanten

Zahl k

Theoretische Informatik

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Welche Ausgaben muss dieser Lösungsalgorithmus bestimmen? 

Ob es in diesem Graphen eine Clique der Größe k gibt. Ja/Nein

Theoretische Informatik

1

2

Theoretische Informatik

Was ist ein Alphabet Σ und wie nennt man die Elemente ?

Eine endliche Menge voneinander unterscheidbarer Symbole. Die Elemente nennt man Zeichen oder Buchstaben.

Theoretische Informatik

Was ist eine Zeichenkette (Wort)?

Eine endliche Folge von Zeichen aus Σ, deren Länge |s| der Anzahl der Elemente dieser Folge entspricht. Die leere Zeichenkette (leere Folge von Zeichen) bezeichnet man ε.

Theoretische Informatik

Was bezeichnet Σ* und Σ+ ?

Die Menge aller Wörter über dem Alphabet Σ. Das leere Wort gehört zu Σ* (Σ+ = Σ* \{ε})

Theoretische Informatik

Für was steht a^n?


a^n ist eine Kurzform für a…a (n-Mal)

Theoretische Informatik

Sei A ein Lösungsalgorithmus für das Entscheidungsproblem K-CLIQUE.

Sei G = (V, E) ein Graph mit 10 Knoten. 

Wie oft muss A im schlimmsten Fall aufgerufen werden, um mit ihm die Frage zu beantworten, wie groß eine größte Clique in G ist?

Die größtmögliche Clique C ist so groß wie die Anzahl der Knoten in G, also 10. Es gibt also höchstens 10 mögliche k, somit wird A im schlimmsten Fall 10 Mal aufgerufen.

Melde dich jetzt kostenfrei an um alle Karteikarten und Zusammenfassungen für Theoretische Informatik an der Hochschule Darmstadt zu sehen

Singup Image Singup Image
Wave

Andere Kurse aus deinem Studiengang

Für deinen Studiengang Theoretische Informatik an der Hochschule Darmstadt gibt es bereits viele Kurse auf StudySmarter, denen du beitreten kannst. Karteikarten, Zusammenfassungen und vieles mehr warten auf dich.

Zurück zur Hochschule Darmstadt Ü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 Hochschule Darmstadt 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

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards
Awards

Bestes EdTech Startup in Deutschland

Awards
Awards

European Youth Award in Smart Learning

Awards
Awards

Bestes EdTech Startup in Europa

Awards