Übungen

Wie groß ist im Beispielgraphen der kürzeste Abstand von $S$ nach $C$?

Warum darf der Algorithmus von Dijkstra keine negativen Kantengewichte enthalten?

Ein ungerichteter Graph hat die Kanten $X\!-\!Y$: $2$, $X\!-\!Z$: $7$, $Y\!-\!Z$: $3$, $Y\!-\!W$: $8$, $Z\!-\!W$: $1$. Bestimme den kürzesten Abstand von $X$ nach $W$.

Erkläre, warum die Breitensuche für gewichtete Graphen nicht den kürzesten Weg nach Gewicht liefert, und gib ein Beispiel an.

Welches Wort wird vom DEA für „endet auf $01$" akzeptiert?

Wie viele Zustände braucht ein DEA für die Sprache „gerade Anzahl von Einsen" mindestens?

Der DEA für „gerade Anzahl von Einsen" liest das Wort $0110101$. Wie oft wechselt er dabei zwischen den Zuständen $g$ und $u$?

Entwirf einen DEA über $\{0, 1\}$, der genau die Wörter akzeptiert, deren Länge durch $3$ teilbar ist. Gib Zustände, Startzustand, Endzustände und die Übergänge an.

Wie viele Kanten hat der vollständige ungerichtete Graph auf $6$ Knoten (jeder Knoten ist mit jedem anderen verbunden)?

Welche Datenstruktur benutzt die Breitensuche zur Verwaltung der noch zu besuchenden Knoten?

Wie viele Kanten hat im Beispielgraphen der kürzeste Weg von $A$ nach $F$ (laut Breitensuche)?

Führe auf dem Graphen mit den Kanten $1\!-\!2$, $1\!-\!3$, $2\!-\!4$, $3\!-\!4$, $4\!-\!5$ eine Breitensuche und eine Tiefensuche ab Knoten $1$ durch (kleinere Nachbarn zuerst) und gib jeweils die Besuchsreihenfolge an.

Eine äußere Schleife läuft für $i = 0, \dots, n-1$, die innere für $j = 0, \dots, i-1$. Wie oft wird der Rumpf der inneren Schleife für $n = 10$ ausgeführt?

Welche der folgenden Aussagen ist richtig?

Ein Verfahren braucht ungefähr $n \cdot \log_2 n$ Schritte. Wie viele sind es für $n = 1024$?

Zeige mit der Definition der O-Notation, dass $5n + 20 \in O(n)$ gilt. Gib $c$ und $n_0$ an.

Ein NEA hat $4$ Zustände. Wie viele Zustände kann der DEA aus der Potenzmengenkonstruktion höchstens haben?

Der NEA für „endet auf $01$" liest das Wort $0101$. Welche Menge von Zuständen ist nach dem letzten Zeichen aktiv?

Der drittletzte Buchstabe eines Wortes über $\{0,1\}$ soll eine $1$ sein. Wie viele Zustände hat der kleinste DEA für diese Sprache?

Erkläre, warum Nichtdeterminismus bei endlichen Automaten die Menge der erkennbaren Sprachen nicht vergrößert.