Home
Writing
ETH

Quiz on AuD Proofs and Theory

Wenn ein Algorithmus für jeden Induktionsschritt korrekt ist und für den Basisfall korrekt ist, dann ist er für alle Eingaben korrekt.

True False

Dies ist die Grundlage für Korrektheitsbeweise von Algorithmen mittels Induktion über die Eingabegröße oder die Anzahl der Iterationen.

Ein Graph mit $n$ Knoten und mehr als $n-1$ Kanten enthält mindestens einen Zyklus.

True False

Ein zusammenhängender azyklischer Graph (Baum) hat genau $n-1$ Kanten. Mehr Kanten bedeuten entweder einen Zyklus oder mehrere Komponenten – aber selbst dann würde eine Komponente einen Zyklus haben müssen.

Es gilt $\frac{n^3}{2} \ge \sum_{i=1}^n i(i-1)$ für $n \ge 1$.

True False

Die Summe $\sum_{i=1}^n i(i-1) = \sum_{i=1}^n (i^2 – i) = \frac{n(n+1)(2n+1)}{6} – \frac{n(n+1)}{2}$. Vereinfacht: $\frac{n(n+1)(n-1)}{3} = \frac{n^3-n}{3}$, was $\le \frac{n^3}{2}$ ist.

Es gilt $n! \le 2^{n(n+1)}$ für $n \ge 1$.

True False

Basisfall: $1! = 1 \le 4 = 2^2$. Induktionsschritt: $(k+1)! \le (k+1) \cdot 2^{k(k+1)}$. Da $(k+1) \le 2^{2k+2}$ für $k \ge 1$, folgt $(k+1)! \le 2^{(k+1)(k+2)}$.

Sei $G=(V, E)$ ein ungerichteter Graph und $F$ die Kanten eines Kreises. Sei $H = (V, E \setminus F)$. Wenn $G$ einen Hamiltonkreis hat, hat $H$ notwendigerweise auch einen.

True False

Das Entfernen der Kreiskanten $F$ könnte einen Knoten isolieren oder den Grad unter 2 reduzieren, was einen Hamiltonkreis unmöglich macht.

Quiz on AuD Proofs and Theory

Recent posts

Lecture Notes

Quizzes

New Siri needs that Steve Jobs touch

Conversations don’t flow linearly, so LLM interfaces shouldn’t either

LaTeX Collection