Bereits bearbeitete Fragen in diesem Semester

Mathe 1

Geben Sie für $f:\begin{cases}\mathbb{N}\rightarrow\mathbb{N}\\ n\mapsto n^{2}\end{cases}\quad$ und $g:\begin{cases}\mathbb{N}\rightarrow\mathbb{N}\\ n\mapsto 2^{n}\end{cases}\quad$ die folgenden Werte an:

Welche der folgenden Mengen von Paaren sind rechtseindeutig?

	$\{(x,y) \in \mathbb{R}^{2} : x^{2}=y\}$
	$\{(x,y) \in \mathbb{R}^{2} : y^{2}=x\}$
	$\{(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)\}$
	$\{(1,1),(2,2),(3,3),(4,1),(5,2),(6,3)\}$
	$\{(x,y) \in \mathbb{Q}^{2} : y=\lceil x\rceil \}$
	$\{(x,y) \in \mathbb{Q}^{2} : \lceil y \rceil=\lceil x\rceil \}$
	$\emptyset$

	Einige Bremer können nicht Fußball spielen.
	Es gibt einen Bremer, der nicht Fußball spielen kann.
	Kein Bremer kann Fußball spielen.
	Nicht alle Bremer können Fußball spielen.

Vor Ihnen liegen vier Spielkarten, von denen Sie wissen, dass jeweils auf der einen Seite eine Zahl und auf der anderen ein Buchstabe steht. Sie sollen überprüfen, ob die folgende Regel für alle Karten gilt: "Wenn auf der Buchstabenseite ein Vokal steht, dann steht auf der Zahlenseite eine gerade Zahl." Kreuzen Sie die Karten an, die Sie umdrehen MÜSSEN, damit Sie sich sicher sein können, dass diese Regel bei ALLEN vier Karten eingehalten wurde. Kreuzen Sie NUR diese Karten an, also möglichst wenige.

	A
	4
	F
	7

Zwei oder mehr von den folgenden vier Sätzen machen rein logisch exakt dieselbe Aussage (abgesehen vielleicht von grammatikalischen Feinheiten). Kreuzen Sie diese an.

	Wenn der HSV die Champions League gewinnt, dann springe ich in die Alster.
	Wenn der HSV nicht die Champions League gewinnt, dann springe ich nicht in die Alster.
	Wenn ich nicht in die Alster springe, dann hat der HSV die Champions League nicht gewonnen.
	Wenn der HSV die Champions League gewinnt, dann springe ich nicht in die Alster.

Welche der folgenden Funktionen von $\mathbb R$ nach $\mathbb R$ sind injektiv?

	$x \mapsto 2x$
	$x \mapsto x^{4}+x^{2}$
	$x \mapsto \lfloor x \rfloor$
	$x \mapsto \sin x$

Sie haben ein Startkapital von 1000 EUR, das pro Jahr mit 3% verzinst wird. Zum Ende des Jahres zahlen Sie jeweils weitere 120 EUR ein. Wie hoch ist Ihr Kapital am Ende des 30. Jahres?

Geben Sie jeweils $a_{5}$ für die sogenannte Collatz-Folge an, die folgendermaßen rekursiv definiert wird: $a_{n+1}:=\begin{cases}\frac12 a_{n}&\text{wenn }a_{n}\text{ gerade ist}\\3a_{n}+1\quad&\text{wenn }a_{n}\text{ ungerade ist}\end{cases}$

Wir definieren $a_{0} := 1$ und $a_{n+1} := 2a_n+1$ für $n\in\mathbb N$. Geben Sie die folgenden Folgenwerte an:

Geben Sie jeweils den nächsten Wert der Folge an. (Und überlegen Sie sich jeweils, wie Sie die Bildungsvorschrift für die Folgen aufschreiben würden.)

Wie viele verschiedene dreistellige Dezimalzahlen, bei denen alle Ziffern unterschiedlich sind, gibt es? [Hinweis: $007$ oder $042$ sind keine dreistellige Zahlen.]

Wenn jede beliebige Kombination von genau vier Dezimalziffern zugelassen ist, wie viele verschiedene PIN-Codes gibt es dann?

Bei einem Autorennen starten 20 Fahrer. Wie viele verschiedene Möglichkeiten für die Besetzung des Siegerpodestes gibt es?

Wenn man $(a+b)^5$ vollständig ausmultipliziert, wie oft kommen dann die folgenden Terme jeweils als Summanden vor?

Wie viele verschiedene Zahlen lassen sich (wie z.B. $110=2\cdot5\cdot11$ oder $63=3\cdot3\cdot7$) als Produkt dreier Primzahlen, die kleiner als 20 sind, darstellen?

Wie viele verschiedene Zahlen lassen sich (wie z.B. $55=5\cdot11$) als Produkt zweier verschiedener Primzahlen, die kleiner als 20 sind, darstellen?

Wie viele verschiedene Möglichkeiten gibt es, sechs Professoren auf sechs Büros zu verteilen, wenn jeder ein Büro für sich alleine bekommen soll?

Jeder Patient von Doktor A muss pro Tag mindestens eine Sorte Tabletten schlucken. 38 müssen rote Tabletten einnehmen, 30 grüne und 23 blaue. 12 der Patienten nehmen rote und blaue Tabletten, 14 grüne und blaue und 20 rote und grüne. Und 7 Patienten haben sogar alle drei Sorten verschrieben bekommen. Wie viele Patienten hat Doktor A?

Bei einer Mietwagenfirma hat jedes Auto mindestens ein Navigationssystem oder ein Automatikgetriebe. 38 haben ein Navigationssystem, 23 ein Automatikgetriebe, 12 beides. Wie viele Autos sind das insgesamt?

Berechnen Sie $\displaystyle\frac{11!}{9!}$ und denken Sie vorm Rechnen erst nach!

Berechnen Sie mit der geometrischen Summenformel $\displaystyle\sum_{i=1}^5 3^i$. (Hinweis: $3^{6}=729$.)

Berechnen Sie die Summe $1+2+3+\dots+999$.

Berechnen Sie das Produkt $\displaystyle\prod_{k=1}^{10}(2\cdot(-1)^k)$

Welchen Wert hat die Summe $\displaystyle\sum_{i=0}^4 ik$?

	$10$
	$10k$
	$k+10$
	$10ik$

Berechnen Sie die folgenden Summen:

Sei $f:\begin{cases}\mathbb{R}\rightarrow\mathbb{R}\\ x\mapsto x^{2}\end{cases}\quad$ und $g:\begin{cases}\mathbb{R}\rightarrow\mathbb{R}\\ x\mapsto 2x+3\end{cases}\quad$. Welche der folgenden Aussagen sind wahr?

	$f[\{1,2\}]=\{1,4\}$
	$f[\,[1,2)\,]=[1,4)$
	$f^{-1\,}[\{1,4\}]=\{1,2\}$
	$g[\,[1,2)\,]=[5,7]$
	$g[\mathbb{Z}]\subseteq\mathbb{Z}$

Welche der folgenden Abbildungsvorschriften definiert eine surjektive Funktion von $\mathbb R$ auf $\mathbb R$?

	$x \mapsto x^{\,2}$
	$x \mapsto x^{\,3}$
	$x \mapsto \sin x$

Sei $R$ die Äquivalenzrelation $\{(x,y)\in\mathbb{R}^{2}\mid \lfloor x\rfloor = \lfloor y \rfloor\}$. Welche der folgenden Aussagen sind wahr?

	$[0]_{R}=[\frac12]_{R}$
	$[0]_{R}\in \mathbb{R}/R$
	$[0]_{R}$ hat unendlich viele Elemente.
	$[0]_{R}\cap[1]_{R}=\emptyset$

Sei $R = \{(x,y) \in \mathbb{R}^{2} \mid |x-y| \leq 3 \}$. Kreuzen Sie die Eigenschaften an, die $R$ hat:

	$R$ ist reflexiv auf $\mathbb R$.
	$R$ ist symmetrisch.
	$R$ ist transitiv.
	$R$ ist eine Äquivalenzrelation auf $\mathbb R$.

Sei $R = \{(x,y) \in \mathbb{Z}^{2} \mid |x-y| \text{ ist ungerade} \}$. Kreuzen Sie die Eigenschaften an, die $R$ hat:

	$R$ ist reflexiv auf $\mathbb Z$.
	$R$ ist symmetrisch.
	$R$ ist transitiv.
	$R$ ist eine Äquivalenzrelation auf $\mathbb Z$.

Welche der folgenden Relationen sind transitiv?

	$\{(m,n) \in \mathbb{N}^{2} \mid \operatorname{ggT}(m,n)=1 \}$
	$\{(a,b) \in \mathbb{Z}^{2} \mid ab \geq 0 \}$
	$\{(x,y) \in \mathbb{Q}^{2} \mid |x-y| \leq 42 \}$

Sei $R = \{(m,n) \in (\mathbb{N}^{+})^{2} \mid m\neq 1 \land m\neq n \land m \text{ teilt } n\}$. Welches der folgenden Paare gehört zu $R\circ R\,$?

	$(1,1)$
	$(3,3)$
	$(1,3)$
	$(1,6)$
	$(2,6)$
	$(2,8)$

Welche der folgenden Paare sind Elemente von $\{(1,2),(5,2)\}\circ\{(2,4),(2,5)\}$?

	$(1,1)$
	$(2,2)$
	$(4,4)$
	$(1,2)$
	$(2,1)$
	$(1,4)$
	$(4,1)$
	$(2,5)$
	$(5,2)$

Welche der folgenden Relationen sind symmetrisch?

	$\{(1,2),(3,1),(3,3),(1,3)\}$
	$\{(x,y)\in\mathbb{R}^{2} \mid x-y \neq 0 \}$
	$\mathbb{R}^{2} \setminus (\mathbb{Z} \times \mathbb{N})$
	$\{(x,y)\in\mathbb{Z}^{2} \mid xy < 0 \}$

Sei $R=\{(x,y)\in\mathbb{R}^{\,2}\mid x<2y\}$. Welche der folgenden Mengen ist die Umkehrrelation $R^{\,-1}\,$?

	$\{(x,y)\in\mathbb{R}^{\,2}\mid x>2y\}$
	$\{(y,x)\in\mathbb{R}^{\,2}\mid x>2y\}$
	$\{(x,y)\in\mathbb{R}^{\,2}\mid y<2x\}$
	$\{(y,x)\in\mathbb{R}^{\,2}\mid x<2y\}$
	$\{(x,y)\in\mathbb{R}^{\,2}\mid x > \frac y2\}$

Welche der folgenden Aussagen sind wahr?

	$\{(1,1),(1,2),(1,3),(1,4)\}$ ist reflexiv auf $\{1,2,3,4\}$
	$\{(x,y)\in\mathbb{R}^{2}\mid xy > 0\}$ ist reflexiv auf $\mathbb R$.
	$\{(x,y)\in(0,\infty)^{2}\mid xy > 0\}$ ist reflexiv auf $(0,\infty)$.
	$\mathbb{R}^{2} \setminus (\mathbb{N} \times \{\pi\})$ ist reflexiv auf $\mathbb R$.
	$\{(m,n)\in\mathbb{N}^{2}\mid m<2n\}$ ist reflexiv auf $\mathbb N$.

Welche der folgenden Aussagen sind wahr?

	$(0,42) \in \mathbb N \times \mathbb Z$
	$(-1,42) \in \mathbb N \times \mathbb Z$
	$(\sqrt{2},42) \in \mathbb Q^{2}$
	$(\pi,\sqrt{2}) \in \mathbb R^{3}$

Sei $A=\{42,43,44,45,46\}$ und $B=\{100,110,120,130\}$. Wie viele Elemente haben $A \times B$ und $B \times A$?

Sei $A=\{42,43,44\}$ und $B=\{100,110\}$. Welche der folgenden Aussagen sind wahr?

	$(42,42) \in A \times A$
	$(42,42) \in A \times B$
	$(42,43) \in A \times A$
	$(42,100) \in A \times B$
	$(110,42) \in B \times A$
	$(42,100) \in B \times A$

Geben Sie die folgenden Werte an:

Welche der folgenden Aussagen sind wahr?

	$\mathbb R_{\,\geq 0} \,\cap (-\infty,0) = \{0\}$
	$[0, \infty) \cup (-\infty,0) = \mathbb R \setminus \{0\}$
	$[0, \infty) \cap (-\infty,0] = \emptyset$
	$[42, \infty) \cap (42,100] = [42,100]$
	$[-2, 2) \cup (2,\infty) = [-2,\infty)$

Welche der folgenden Aussagen sind wahr?

	$[1,2] \cap [2,3] = \{2\}$
	$[1,2] \cap (2,3] = \{2\}$
	$[0,100] \cap (2,3] = (2,3]$
	$[1,3) \cup (2,4] = (1,4)$
	$[42,43] \setminus (43,44] = [42,43]$
	$[42,43) \setminus [43,44] = [42,43]$
	$[\sqrt{2\,},\pi] \subseteq (-\frac12,\frac{39}{10})$

Welche der folgenden Aussagen ist wahr?

	$\sqrt{2\,} \in [1,2]$
	$\sqrt{2\,} \in (0,3]$
	$\sqrt{2\,} \in [-1,1]$
	$42 \in (42,43]$
	$42 \in [42,43)$
	$42 \in (42,43)$
	$42 \in [41.99,42.01]$
	$42 \in (41.9999,42.0001)$

"Für jede natürliche Zahl $n$ gilt: Wenn $n$ gerade und größer als zwei ist, dann kann man $n$ als Summe zweier Primzahlen darstellen." Das ist die sogenannte Goldbachsche Vermutung. Was muss man finden, um diese Vermutung zu widerlegen?

	Zwei Primzahlen, deren Summe ungerade und größer als zwei ist.
	Eine ungerade natürliche Zahl, die größer als zwei ist und sich als Summe zweier Primzahlen darstellen lässt.
	Eine gerade natürliche Zahl, die größer als zwei ist und sich nicht als Summe von zwei Primzahlen darstellen lässt.
	Eine gerade natürliche Zahl, die größer als zwei ist und sich als Summe von mehr als zwei Primzahlen darstellen lässt.

Kreuzen Sie die Aussagen an, die wahr sind.

	$\sqrt{x^{\,2}\,}=x$ gilt für alle natürlichen Zahlen $x$.
	$\sqrt{x^{\,2}\,}=x$ gilt für alle positiven reellen Zahlen $x$.
	$\sqrt{x^{\,2}\,}=x$ gilt für alle reellen Zahlen $x$.
	Jede Menge $A$ hat mindestens zwei verschiedene Teilmengen (nämlich $A$ und $\emptyset$).

Welche der folgenden Aussagen sind wahr?

	$(7 < 6) \lor (1 \neq 1)$
	$(2 < \pi) \land (42 > 42)$
	$(7 = 6 + 2) \lor \neg (\frac34 \in \mathbb N)$

Kreuzen Sie die Zahlen an, die Elemente von $\{3n+7 \mid n \in \mathbb N \}$ sind.

	0
	3
	7
	10
	42
	43

Welche der folgenden Mengen ist identisch mit $\mathbb N$?

	$\{ n \in \mathbb N \mid n^2 > 0 \}$
	$\{ z \in \mathbb Z \mid z^2 \geq 0 \}$
	$\{ x \in \mathbb Z \mid x = 0 \text{ und } x > 0 \}$
	$\{ z \in \mathbb Z \mid z = 0 \text{ oder } z > 0 \}$

Welche der folgenden Aussagen sind wahr?

	$4 \in \{n \mid n \in \mathbb N \text{ und } n^2 > 10 \}$
	$\{n \mid n \in \mathbb N \text{ und } n \geq 10 \} \subseteq \{n \mid n \in \mathbb N \text{ und } n > 10 \}$
	$\{m \mid m \in \mathbb N \text{ und } 2m \leq 1 \}=\emptyset$
	$\{x \mid x \in \mathbb Z \text{ und } x^2 = 4 \}=\{2\}$

Welche der folgenden Aussagen sind wahr?

	$\mathbb N \subseteq \mathbb Z$
	$\mathbb N \in \mathbb Z$
	$\mathbb N \cap \mathbb Z=\mathbb N$
	$\mathbb N \cup \mathbb Z=\mathbb N$
	$\mathbb Z \setminus \mathbb N = \emptyset$
	$\mathbb N \setminus \mathbb Z = \emptyset$

Wie viele Elemente hat die Potenzmenge von $\{1,2,3,4\}$?

Welche der folgenden Mengen sind für jede Menge $A$ Elemente der Potenzmenge von $A$?

	$\emptyset$
	$\{0\}$
	$A\setminus\{42\}$
	$A$

Kreuzen Sie alle Elemente von $\{100,101,102\} \setminus \{101,102,103,104\}$ an.

	100
	101
	102
	103
	104

Kreuzen Sie alle Elemente von $\{100,101,102\} \cap \{99,100,101\}$ an.

	98
	99
	100
	101
	102
	103

Kreuzen Sie alle Elemente von $\{100,101,102\} \cup \{99,100,101\}$ an.

	98
	99
	100
	101
	102
	103

Welche der folgenden Aussagen sind wahr?

	$\{2,2,3,3,1\}\subseteq\{1,2,3\}$
	$\{1\}\subseteq\{2,3,4,5\}$
	$\{1,2,3\}\subseteq\{2,3,4\}$
	$\emptyset \subseteq \{100,200,300\}$
	$\emptyset \in \{100,200,300\}$

Welche der folgenden Aussagen sind wahr?

	$\{1,3,4,2\}=\{1,2,4,4,1,1,3\}$
	$\{1,3,4,2\}=\{1,2,4,4,1,1+3\}$
	$\{1,1+1-1,1+1+1\}=\{3,1\}$
	$\{6,2+4,2\cdot3\}$ hat drei Elemente
	$2\in\{2+2\}$
	$42\notin\{39,40,41\}$

Mathe 2

Welche Aussage gilt für die Folge $((-1)^{n})$? [Das ist also die Folge $1,-1,1,-1,1,-1,\dots$]

	Sie konvergiert gegen $1$.
	Sie konvergiert gegen $-1$.
	Sie konvergiert gegen $1$ und gegen $-1$.
	Sie konvergiert weder gegen $1$ noch gegen $-1$.

Welche der folgenden Aussagen sind wahr?

	Fast alle Folgenglieder von $(10^{9-n})$ sind kleiner als $1$.
	Fast alle Folgenglieder von $(n!)$ haben mindestens eine Million Primteiler.
	Fast alle Folgenglieder von $(n)$ sind gerade.

Berechnen Sie:

Sei $\mathbf A=\begin{pmatrix}2&-1&5\\3&3&-4\end{pmatrix}$ und $\mathbf B=\begin{pmatrix}1&2&3&-2&-3\\0&0&1&8&2\\11&-1&2&0&2\end{pmatrix}$ Geben Sie die folgenden Werte an:

Seien $\mathbf A\in\mathbb{R}^{3\times5}\,$, $\mathbf B\in\mathbb{R}^{3\times3}\,$ und $\mathbf C\in\mathbb{R}^{5\times3}\,$. Welche der folgenden Produkte kann man bilden?

	$\mathbf{A}\cdot\mathbf{A}$
	$\mathbf{A}\cdot\mathbf{B}$
	$\mathbf{A}\cdot\mathbf{C}$
	$\mathbf{B}\cdot\mathbf{A}$
	$\mathbf{B}\cdot\mathbf{B}$
	$\mathbf{B}\cdot\mathbf{C}$
	$\mathbf{C}\cdot\mathbf{A}$
	$\mathbf{C}\cdot\mathbf{B}$
	$\mathbf{C}\cdot\mathbf{C}$

Berechnen Sie:

Welche der folgenden Matrizen ist in $\mathbb{R}^{3\times3}\,$ das neutrale Element der Multiplikation?

	$\begin{pmatrix}1&1&1\\1&1&1\\1&1&1\end{pmatrix}$
	$\begin{pmatrix}1&1&1\\0&0&0\\0&0&0\end{pmatrix}$
	$\begin{pmatrix}1&0&0\\1&0&0\\1&0&0\end{pmatrix}$
	$\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}$
	$\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix}$
	Es gibt kein neutrales Element der Multiplikation.

Welche der folgenden Aussagen gilt für alle Polynome $p$ und $q$?

	$\deg(p + q) = \deg(p) + \deg(q)$
	$\deg(p + q) = \max(\deg(p),\deg(q))$
	$\deg(p + q) \leq \max(\deg(p),\deg(q))$

Welche der folgenden Funktionen sind Polynome?

	$x\mapsto x^2-3$
	$x\mapsto 1/x$
	$x\mapsto -1$
	$x\mapsto (x+1)\cdot(x-1)$
	$x\mapsto x^{2}+x^{-2}$
	$x\mapsto 42\sqrt{x}$
	$x\mapsto 2xy+4x-3$

$\mathrm i$ ist keine reelle Zahl. Aber was ist z.B. mit $2\mathrm i$ und $1+\mathrm i$?

	$2\mathrm i$ ist reell, aber $1+\mathrm i$ nicht.
	$1+\mathrm i$ ist reell, aber $2\mathrm i$ nicht.
	$2\mathrm i$ und $1+\mathrm i$ sind beide nicht reell.
	$2\mathrm i$ und $1+\mathrm i$ sind beide reell.

Kann $3^{\,561-1}\,=1$ in $\mathbb{Z}/561\mathbb{Z}$ gelten? (Beachten Sie, dass $561$ durch $3$ teilbar ist.)

	Nein, denn nach dem kleinen Satz von Fermat wäre $561$ dann ja eine Primzahl.
	Nein, denn $3$ ist ja ein Teiler von $561$.
	Warum nicht? Der kleine Satz von Fermat sagt über zusammengesetzte Zahlen nichts aus.

Wie viele Multiplikationen braucht man bei der binären Exponentiation zur Berechnung von $5^{42}$?

Eine mit Butter bestrichene Toastscheibe wird zwanzig Mal fallengelassen. Welche Menge eignet sich als Ergebnismenge dieses Experimentes?

	$\Omega = \{1,2,3,\dots,20\}$
	$\Omega = \{1,2,3,\dots,20\} \times \{1,2,3,\dots,20\}$
	$\Omega = \{0,1\}^{20}$
	$\Omega = \mathbb N$
	$\Omega = \mathbb N^{20}$

Wenn $\mathbf A$ eine $n\times n$-Matrix ist, welchen Wert hat dann $\det(\lambda \cdot \mathbf A)$, wenn $\lambda$ ein Skalar ist?

	$\det(\mathbf{A})$
	$\lambda\cdot\det(\mathbf{A})$
	$\lambda^{n}\cdot\det(\mathbf{A})$
	$(\lambda\cdot\det(\mathbf{A}))^{n}$

Berechnen Sie mit dem Gauß-Verfahren die folgenden Werte:

Geben Sie die folgenden Grenzwerte an:

Geben Sie die folgenden Grenzwerte an:

Welche der folgenden Matrizen sind orthogonal?

	$\frac12\cdot\begin{pmatrix}1&\sqrt{2\,}&-1\\-\sqrt{2\,}&0&-\sqrt{2\,}\\-1&\sqrt{2\,}&1\end{pmatrix}$
	$\frac12\cdot\begin{pmatrix}1&\sqrt{2\,}&1\\-\sqrt{2\,}&0&-\sqrt{2\,}\\-1&\sqrt{2\,}&1\end{pmatrix}$
	$\begin{pmatrix}1&\sqrt{2\,}&-1\\-\sqrt{2\,}&0&-\sqrt{2\,}\\-1&\sqrt{2\,}&1\end{pmatrix}$

Sei $\mathbf A=\begin{pmatrix}1&2&3\\2&3&4\\0&1&3\end{pmatrix}$ und $\begin{pmatrix}c_{11}&c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{pmatrix}$ die Inverse von $\mathbf A$ über $\mathbb Z_{5}$. Berechnen Sie:

Was ist der Wert von $\det(\mathbf A^{-1})$, wenn $\mathbf A$ regulär ist?

	$\det(\mathbf A)$
	$(\det(\mathbf A))^{-1}$
	$-\det(\mathbf A)$
	Der Wert hängt nicht von $\det(\mathbf A)$ ab.

Berechnen Sie mit dem Laplace-Verfahren die folgende Determinante:

Sei $\mathbf A=\begin{pmatrix}2&3&-1\\0&2&-2\\1&0&4\end{pmatrix}$ und $\begin{pmatrix}c_{11}&c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{pmatrix}$ die Inverse von $\mathbf A$. Berechnen Sie:

Das lineare Gleichungssystem $\begin{pmatrix}2&1&1\\-3&3&3\\5&8&1\end{pmatrix}\cdot \mathbf{x}= \begin{pmatrix}6\\0\\5\end{pmatrix}$ hat genau eine Lösung $\mathbf v$. Geben Sie an:

Sei $\mathbf A=\begin{pmatrix}2&0\\1&1\end{pmatrix}$ und $\mathbf B=\begin{pmatrix}1&2\\0&0\end{pmatrix}$ sowie $\mathbf{A}\cdot\mathbf{B}=\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}$ und $\mathbf{B}\cdot\mathbf{A}=\begin{pmatrix}d_{11}&d_{12}\\d_{21}&d_{22}\end{pmatrix}$. Geben Sie die folgenden Werte an:

Geben Sie die Matrix $\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}$ an, die die Spiegelung an der Geraden $\mathbb R\begin{pmatrix}1\\1\end{pmatrix}$ beschreibt.

Sei $\mathbf A=\begin{pmatrix}3&0&4\\1&-2&-1\\0&\frac12&\frac13\end{pmatrix}$ und $\mathbf v=\begin{pmatrix}2\\0\\-1\end{pmatrix}$. Berechnen Sie $\mathbf{Av}$.

Sei $\mathbf a=\begin{pmatrix}2\\0\\2\end{pmatrix}$ und $\mathbf b=\begin{pmatrix}1\\1\\0\end{pmatrix}$. Berechnen Sie den Winkel zwischen $\mathbf a$ und $\mathbf b$.

Normieren Sie den Vektor $\begin{pmatrix}-12\,\,\\5\,\,\end{pmatrix}$.

Seien $\mathbf a=\begin{pmatrix}\frac23\\3\end{pmatrix}$, $\mathbf b=\begin{pmatrix}9\\-2\end{pmatrix}$ und $\mathbf c=-\mathbf b$. Berechnen Sie die folgenden Skalarprodukte:

Wenn man in der Ebene $\mathbb R^{\,2}$ oder im Raum $\mathbb R^{\,3}$ die Schnittmenge von zwei Geraden $g$ und $h$ betrachtet, welche der folgenden Fälle sind dann möglich?

	$g\cap h=\emptyset$
	$g\cap h$ besteht aus genau einem Punkt.
	$g\cap h$ besteht aus genau zwei Punkten.
	$g\cap h$ besteht aus genau drei Punkten.
	$g\cap h=g=h$

Welche der folgenden Punkte liegen auf der Geraden $\begin{pmatrix}1\\3\end{pmatrix} + \mathbb{R}\begin{pmatrix}2\\-1\end{pmatrix}$?

	$\begin{pmatrix}2\\3\end{pmatrix}$
	$\begin{pmatrix}3\\2\end{pmatrix}$
	$\begin{pmatrix}0\\0\end{pmatrix}$
	$\begin{pmatrix}\frac12\\\frac{13}4\end{pmatrix}$
	$\begin{pmatrix}1+2\pi\\3-\pi\end{pmatrix}$

Wir betrachten $p(x)=x^{3}+x+1$ in $\mathbb Z_{2}[x]$. Geben Sie die folgenden Polynome als Bitfolgen an:

Wir betrachten $p(x)=x^{3}+x+1$ und $q(x)=x^{4}+x^{3}+x^{2}+1$ in $\mathbb Z_{2}[x]$. Geben Sie die folgenden Polynome als Bitfolgen an:

Sei $p(x)=x^{2}+3x+2$ berechnen Sie in $\mathbb Z/6\mathbb Z$:

Berechnen Sie für $p(x)=x^{3}+x+1$ und $q(x)=2x^{5}+1$ in $\mathbb Z_{3}$ die folgenden Werte:

Berechnen Sie $(6x^{3}+3x^{2}+1):(2x+4)$ in $\mathbb Z_{7}$.

Kreuzen Sie alle Nullstellen von $p(x)=x^{2}+6x+1$ in $\mathbb Z_{7}$ an.

	0
	1
	2
	3
	4
	5
	6

Sei $p(x)=x^{2}+3x+4$. Berechnen Sie in $\mathbb Z_{5}$:

$2$ ist eine Nullstelle von $p(x)=x^{3}-6x^{2}+13x-10$. Ermitteln Sie das Ergebnis der Division von $p(x)$ durch $x-2$ mit dem Horner-Schema.

Sei $p(x)=x^{3}-6x^{2}+13x-10$. Berechnen Sie mit dem Horner-Schema:

Geben Sie den Rest an, der sich bei der Polynomdivision $(x^{3}-4x^{2}-9x-84):(x-7)$ ergibt.

Geben Sie das eindeutig bestimmte Polynom $p$ maximal zweiten Grades mit $p(1)=2$, $p(-2)=-1$ und $p(0)=3$ an.

Geben Sie das eindeutig bestimmte Polynom $p$ maximal zweiten Grades mit $p(2)=0$, $p(3)=0$ und $p(0)=1$ an.

Entwickeln Sie das Polynom $3x^{2}+4x-8$ bei $x_{0}=-1$:

Seien $x_{1}$ und $x_{2}$ die Lösungen von $x^{2}+2x+1+2\mathrm i=0$ und $x_{1}$ die mit dem kleineren Betrag. Berechnen Sie:

Sei $w_{1}$ die Lösung von $w^{2}=-8\mathrm i$, die oberhalb der reellen Achse liegt. Berechnen Sie:

$z=-\sqrt{12}+2\mathrm i$ hat den Betrag $d$ und das Argument $c\cdot\pi$. Geben Sie diese Werte an, wobei $c$ zwischen 0 und 2 liegen soll:

Seien $z_1=1+2\mathrm i$, $z_2=\frac{1-\mathrm i\,}2$ und $z_3=-2+\mathrm i$. Berechnen Sie:

Sei $z_1=1+2\mathrm i$. Berechnen Sie:

Berechnen Sie:

Welche der folgenden Aussagen sind wahr?

	$x=-\frac12\cdot\mathrm i$ löst die Gleichung $x^{2}=-\frac14$
	$x=\frac12\cdot\mathrm i$ löst die Gleichung $x^{2}=-\frac14$
	$x=\frac12\cdot\mathrm i$ löst die Gleichung $x^{2}=\frac14$
	$x=\frac1{\sqrt 2}\cdot\mathrm i$ löst die Gleichung $x^{2}=-\frac14$

Sei $\pi_{1}=(1\;2)\,(3\;4)\,(2\;3)\,(3\;4)\,(1\;2)$ und $\pi_{2}=(1\;4)$. Beschreiben $\pi_{1}$ und $\pi_{2}$ dieselbe Permutation?

	Ja
	Nein

In wie viele Zyklen zerfällt die Permutation $\begin{pmatrix}1&2&3&4&5&6&7&8&9\\8&6&7&2&9&1&5&4&3\end{pmatrix}$?

Sei $\pi_{1}=(1\;2\;4)\;(5\;7)$, $\pi_{2}=(5\;7)\;(4\;1\;2)$ und $\pi_{3}=(1\;2\;4)$. Welche der folgenden Aussagen sind wahr?

	$\pi_{1}=\pi_{2}$
	$\pi_{1}^{3}=(5\;7)$
	$\pi_{2}^{6}=\operatorname{id}$
	$\pi_{1}\,\pi_{2}\,\pi_{3}=\operatorname{id}$

Sei $\pi$ die Permutation $(1\;2\;4)(5\;7)$ aus $\mathrm S_{7}$. Geben Sie die folgenden Werte an:

Wir betrachten $\mathbb{Z}/6\mathbb{Z}=\{0,1,2,3,4,5\}$ mit der Addition als Verknüpfung. Welche der folgenden Mengen sind Untergruppen dieser Gruppe?

	$\{0,2\}$
	$\{0,3\}$
	$\{0,2,4\}$
	$\{0,3,5\}$

Wir betrachten vier verschiedene Verknüpfungen. Kreuzen Sie die an, die assoziativ sind.

	$(a,b) \mapsto a - b$ auf $\mathbb{Z}$
	$(a,b) \mapsto \max(a,b)$ auf $\mathbb{N}$
	$(a,b) \mapsto a^{b}$ auf $\mathbb{N}$
	$(a,b) \mapsto \frac12 \cdot (a+b)$ auf $\mathbb{Q}$

Wir betrachten $\mathbb{N}=\{0,1,2,3,4,\dots\}$ mit der Addition als Verknüpfung. Welche der folgenden Aussagen sind wahr?

	Die Verknüpfung ist assoziativ.
	Es gibt ein neutrales Element.
	Es gibt zu jedem Element ein Inverses.
	Es handelt sich um eine Gruppe.

Wir betrachten $\mathbb{Z}_{5}=\{0,1,2,3,4\}$ mit der Multiplikation als Verknüpfung. Welche der folgenden Aussagen sind wahr?

	Die Verknüpfung ist assoziativ.
	Es gibt ein neutrales Element.
	Es gibt zu jedem Element ein Inverses.
	Es handelt sich um eine Gruppe.

Geben Sie die kleinste positive Zahl $x$ mit $x \equiv 2 \pmod{11}$, $x \equiv 1 \pmod 3$ und $x \equiv 6 \pmod 7$ an.

Im RSA-Algorithmus seien die Primzahlen $p=3$ und $q=11$ und der öffentliche Schlüssel $e=3$.

Geben Sie die fehlende Prüfziffer der ISBN 1-484-21177-? an.

Geben Sie die Lösung der Gleichung $13x=4$ in $\mathbb{Z}/100\mathbb{Z}$ an.

Geben Sie die Lösung der Gleichung $13x=1$ in $\mathbb{Z}/100\mathbb{Z}$ an.

Wir rechnen in $\mathbb{Z}/8\mathbb{Z}$. Kreuzen Sie die Lösungen von $x^2+6x=0$ an.

	$x=0$
	$x=1$
	$x=2$
	$x=3$
	$x=4$
	$x=5$
	$x=6$
	$x=7$

Kreuzen Sie die Aussagen an, die wahr sind.

	$[13]_3 = [2]_3$
	$[13]_{11} = [2]_{11}$
	$[13]_3 = [-2]_3$
	$[11]_{11} = [-11]_{11}$
	$[11]_{10} = [-11]_{10}$
	$[-1]_8=[87]_8$
	$[-10]_7=[32]_7$

Kreuzen Sie die Aussagen an, die wahr sind.

	$42 \equiv 42 \pmod{10}$
	$42 \equiv 2 \pmod{10}$
	$2 \equiv 42 \pmod{10}$
	$-42 \equiv 2 \pmod{10}$
	$-42 \equiv -2 \pmod{10}$
	$0 \equiv 10 \pmod{10}$
	$0 \equiv 10 \pmod{5}$
	$0 \equiv 10 \pmod{20}$

Wenn man prüfen will, ob 999983 eine Primzahl ist, durch welche Zahlen sollte man dann dividieren?

	Alle Zahlen von 2 bis 999982.
	Alle Zahlen von 2 bis zur Hälfte (also 499992).
	Alle Primzahlen von 2 bis zur Hälfte.
	Alle Zahlen von 2 bis 1000.
	Alle Primzahlen von 2 bis 1000.

Geben Sie das in der Zahl 15360000 "verschlüsselte" Wort (in Großbuchstaben) ein:

Welche der folgenden Zahlen sind Primzahlen?

	42
	1
	0
	-13
	101

Geben Sie den größten gemeinsamen Teiler von 12675 und 10285 an.

Geben Sie den größten gemeinsamen Teiler an...

Wenn $a$ und $b$ zwei beliebige ganze Zahlen sind, wie viele gemeinsame Teiler haben $a$ und $b$ dann mit Sicherheit mindestens?

	keinen
	einen
	zwei
	mehr als zwei

Wenn $a$ irgendeine ganze Zahl ist, welche der folgenden Zahlen sind dann auf jeden Fall Teiler von $a$?

	1
	-1
	$a$
	$-a$

Welche der folgenden Aussagen sind wahr?

	$3\mid18$
	$18\mid3$
	$-3\mid6$
	$-3\nmid-6$
	$3\mid-6$
	$42\mid42$
	$1\nmid7$
	$7\mid1$
	$10\mid0$

Konvergiert die Reihe $\displaystyle \sum_{k=0}^\infty (-1)^k$?

	Ja
	Nein

Geben Sie die ersten vier Partialsummen der Reihe $\displaystyle \sum_{k=0}^\infty (-1)^k$ an.

Wenn man das Skalarprodukt eines Vektors $\mathbf v\in \mathbb{Z}_{2}^{n}$ mit dem Vektor $(1,1,1,\dots,1)$ bildet, was erhält man dann?

	Die Anzahl der Einsen von $\mathbf v$.
	Eine 1 genau dann, wenn die Anzahl der Einsen von $\mathbf v$ gerade ist.
	Eine 0 genau dann, wenn die Anzahl der Einsen von $\mathbf v$ gerade ist.
	Das Ergebnis hat mit der Anzahl der Einsen von $\mathbf v$ nichts zu tun.

Mutter und Tochter sind zusammen 62 Jahre alt. Vor sechs Jahren war die Mutter viermal so alt wie die Tochter. Berechnen Sie:

Seien $z_1=1+2\mathrm i$, $z_2=\frac{1-\mathrm i\,}2$ und $z_3=-2+\mathrm i$. Berechnen Sie:

Geben Sie die kleinste positive Zahl $x$ mit $x \equiv 2 \pmod 3$ und $x \equiv 3 \pmod 5$ an.

Geben Sie die kleinste positive Zahl $x$ mit $x \equiv 2 \pmod 3$ an.

Theoretische Informatik

Welche der folgenden Aussagen sind wahr?

	${\cal L}(\mathtt{a}\mathtt{a}^\ast) = \{\mathtt{a}\}^+$
	${\cal L}(\mathtt{a}\mathtt{a}^\ast) = \{\mathtt{aa}\}^\ast$
	${\cal L}(\mathtt{a}(\mathtt{b}+\mathtt{c})) = \{\mathtt{ac},\mathtt{ab}\}$
	${\cal L}(\mathtt{a}(\mathtt{b}+\mathtt{c})) = \{\mathtt{ba},\mathtt{bc}\}$
	${\cal L}(\mathtt{a}(\mathtt{b}+\mathtt{c})) = \{\mathtt{abc}\}$
	${\cal L}(\mathtt{a}(\mathtt{a}+\mathtt{a}^\ast)) = {\cal L}(\mathtt{a}^\ast\mathtt{a})$

Welche der folgenden Zeichenfolgen sind reguläre Ausdrücke über $\Sigma_{\text{bool}}$?

	$\varepsilon\varepsilon\varepsilon$
	$\mathtt{0}+\mathtt{1}$
	$\emptyset(\mathtt{0}+\mathtt{1})\emptyset$
	$(\emptyset\mathtt{0}+\mathtt{1}\emptyset)$
	$\mathtt{0}(\mathtt{1})^\ast$
	$(\mathtt{0}\mathtt{1})^\ast$
	$\mathtt{0}\mathtt{1}^\ast$

Welche der folgenden Aussagen sind wahr?

	$\{\mathtt{aa}\}^4=\{\mathtt{aaaa}\}^2$
	$\{\mathtt{aa}\}^\ast=\{\mathtt{aa},\mathtt{aaaa}\}^\ast$
	$\{\mathtt{0}\}^\ast\cup\{\mathtt{1}\}^\ast=\Sigma_{\text{bool}}^\ast$
	$\emptyset^\ast=\emptyset$
	$\emptyset^+=\emptyset$

Welche der folgenden Aussagen sind wahr?

	$\{\mathtt{ab},\mathtt{a}\} \circ \{\mathtt{a},\mathtt{ba},\mathtt{c}\}$ hat sechs Elemente.
	$\Sigma_{\text{bool}}^\ast \circ \Sigma_{\text{bool}}^\ast = \Sigma_{\text{bool}}^\ast$
	$\Sigma_{\text{bool}}^+ \circ \Sigma_{\text{bool}}^+ = \Sigma_{\text{bool}}^+$
	$\{\mathtt{ab},\mathtt{a}\} \circ \varnothing = \{\mathtt{ab},\mathtt{a}\}$

Sei $L_1=\{ \mathtt{01}w : w \in \Sigma_{\text{bool}}^\ast \}$ und $L_2 = \{ w\mathtt{10} : w \in \Sigma_{\text{bool}}^\ast \}$. Welche der folgenden Aussagen sind wahr?

	$\varepsilon \in L_1 \setminus L_2$
	$L_1 \cup L_2 = \Sigma_{\text{bool}}^+$
	Alle Wörter in $L_1 \cap L_2$ haben mindestens vier Zeichen.

Geben Sie die folgenden Werte an:

Welche der folgenden Aussagen sind wahr?

	$(0,0,0)$ ist ein Wort über $\{0\}$.
	$(0,1,0,1,0,1,0,1,\dots)$ ist ein Wort über $\{0,1\}$.
	$(0,1,2)$ ist ein Wort über $\{1,2\}$.
	$(\mathtt{a},\mathtt{aa})$ ist ein Wort über $\{\mathtt{a},\mathtt{aa},\mathtt{aaa}\}$.
	$(\mathtt{a},\mathtt{aa})$ ist dasselbe Wort wie $(\mathtt{aa}, \mathtt{a})$.

Welche der folgenden Mengen ist ein Alphabet?

	$\{0\}$
	$\emptyset$
	$\{\mathtt{begin},\mathtt{end},\mathbb{N}\}$
	$\{\mathtt{a},\mathtt{b},\mathtt{c}\}$
	$\{\mathtt{a},\mathtt{bb},\mathtt{ccc}\}$
	$\{\mathtt{a},\mathtt{aa},\mathtt{aaa},\mathtt{aaaa},\dots\}$

Wenn wir maximal eine Milliarde Zuordnungen testen wollen, wie groß darf $n$ höchstens sein?

$3^{\frac n2}$ ist dasselbe wie...

	$\frac12 \cdot 3^{n}$
	$(\sqrt3)^{n}$
	$2^{\frac n3}$
	$(\frac 32)^{n}$
	$3^{\sqrt n}$

Wie viele Zuordnungen werden maximal untersucht? (Also: Wie viele "Blätter" hat der Baum maximal?)

	$2^{n}$
	$3^{\frac n2}$
	$3^{n}$
	$2^{3n}$
	$2^{\frac n2}\cdot3$

Was sind die Eigenschaften dieses Suchbaum-Algorithmus?

	Der Algorithmus findet immer eine minimale Lösung.
	Es gibt Spezialfälle, in denen der Algorithmus keine Lösung findet.
	Auf jedem Level wird für mindestens eine Ecke entschieden, ob sie rot oder grün wird.
	Auf jedem Level wird für mindestens zwei Ecken entschieden, ob sie rot oder grün werden.

Wie viel schneller ist $2^{\sqrt n}$ als $2^{n}$ für $n=50$?

	Mehr als eine Million Mal so schnell.
	Mehr als eine Milliarde Mal so schnell.
	Mehr als eine Billion Mal so schnell.

Wie viel schneller ist $1.1^{n}$ als $2^{n}$ für $n=50$?

	Mehr als eine Million Mal so schnell.
	Mehr als eine Milliarde Mal so schnell.
	Mehr als eine Billion Mal so schnell.

Wann kann "brute force" ggf. sinnvoll sein?

	Wenn man wenig Zeit für das Design von Algorithmus und Programm hat.
	Wenn $n$ (die "Größe" des Problems) relativ klein ist.
	Wenn das Programm nur einmal laufen muss.

Wenn Ihre Chefin Sie bittet, ein Programm für ein Problem zu schreiben, von dem Sie nachweisen können, dass es $\cal{NP}$-vollständig ist, was sollten Sie dann sagen?

	Ich hätte gerne eine andere Aufgabe.
	Ich kündige!
	Hören Sie sich mal die TI-Vorlesung von Herrn Weitz an, Sie illiterate Nervensäge!!!
	Ich kann beweisen, dass das unmöglich ist.
	Man kann beweisen, dass das extrem schwer ist, aber ich kann's ja mal probieren...

Wie lang ist die längste gemeinsame Sequenz von (nicht notwendig benachbarten) Buchstaben der beiden Wörter "BUNDESTAGSWAHL" und "UNTERWASSERKABEL"?

Kann man die Ecken des skizzierten Graphen mit zwei Farben so färben, dass je zwei durch Kanten verbundene Ecken verschiedene Farben haben?

	Ja
	Nein

Kann man die Ecken des skizzierten Graphen mit zwei Farben so färben, dass je zwei durch Kanten verbundene Ecken verschiedene Farben haben?

	Ja
	Nein

Wenn man in so einem Graphen (ausgehend von einer CNF-Formel mit $m$ Klauseln) eine Clique der Größe $m$ findet, was folgt daraus?

	Die Clique enthält mindestens eine Ecke von jeder "Klausel-Gruppe".
	Die Clique kann mehrere Ecken einer "Klausel-Gruppe" enthalten.

Geben Sie eine Belegung für $x_{1}$ bis $x_{3}$ an, die die Formel $(x_{1} \vee x_{3}) \wedge (x_{1} \wedge (x_{2} \vee \overline{x_{3}})) \wedge (\overline{x_{2}} \vee \overline{x_{3}}) \wedge (\overline{x_{1}} \vee \overline{x_{2}})$ erfüllt.

Welche der folgenden Aussagen haben wir bisher schon gelernt?

	Jedes Problem aus $\cal P$ ist auch in $\cal NP$.
	Jedes Problem aus $\cal NP$ ist auch in $\cal P$.
	$\cal P$ und $\cal NP$ sind identisch.
	Es sieht so aus, als wären in $\cal NP$ Probleme enthalten, die nicht in $\cal P$ sind.
	Vertex Cover, Independent Set und Clique liegen in $\cal P$.
	Vertex Cover, Independent Set und Clique liegen in $\cal NP$.

Wenn der Befehl $\mathtt{if\_better}$ $n$-mal ausgeführt wird, wie viele Simulationen laufen dann im worst case parallel ab?

	$n$
	$2n$
	$n^{2}$
	$n^{n}$
	anderer Wert

Nach unserem bisherigen Wissensstand: In welchen Klassen liegen unsere drei Probleme außerdem?

	A
	B
	C

Was haben die Probleme von Valerie, Carla und Ian gemeinsam?

	Es ist bisher keine polynomiale Lösung bekannt.
	Sie haben keine praktische Relevanz.
	Jeder 'einfache' Algorithmus muss eine exponentielle Anzahl von möglichen Lösungen untersuchen.
	Es ist einfach (d.h. mit polynomialem Zeitaufwand) feststellbar, ob eine potentielle Lösung korrekt ist.

Teil 4: Wenn man den Graphen nach diesem Muster auf insgesamt 20 Ecken ausdehnt, wie viele verschiedene Wege von $A$ nach $B$ gibt es dann?

Teil 3: Wie viele verschiedene Wege gibt es von $A$ nach $B$, wenn man nicht rückwärts gehen darf?

Teil 2: Wie viele verschiedene Wege gibt es von $A$ nach $B$, wenn man nicht rückwärts gehen darf?

Teil 1: Wie viele verschiedene Wege gibt es von $A$ nach $B$, wenn man nicht rückwärts gehen darf?

Welche der folgenden Aussagen sind wahr?

	Wenn die Optimierungsversion eines Problems machbar ist, dann ist auch die Entscheidungsversion dieses Problems machbar.
	Wenn die Optimierungsversion eines Problems widerspenstig ist, dann ist auch die Entscheidungsversion dieses Problems widerspenstig.
	Wenn die Entscheidungsversion eines Problems machbar ist, dann ist auch die Optimierungsversion dieses Problems machbar.
	Wenn die Entscheidungsversion eines Problems widerspenstig ist, dann ist auch die Optimierungsversion dieses Problems widerspenstig.

Welcher Algorithmus hat das 'bessere' Laufzeitverhalten?

	Algorithmus A: $10n^{4}+12n+8$
	Algorithmus B: $2^{n}+2n+3$

Geben Sie für beide Graphen jeweils die Größe (Anzahl der Ecken) des kleinsten Vertex Covers an.

Welche Ecken gehören zum größten Independent Set?

	A
	B
	C
	D
	E
	F

Welche Ecken gehören zur größten Clique?

	A
	B
	C
	D
	E
	F

Was ist die maximale Anzahl von Investments, die gemeinsam im Portfolio sein können?

Was ist für ein gegebenes Problem wohl leichter zu zeigen?

	Dass es machbar ist.
	Dass es widerspenstig ist.
	Beides ist ungefähr gleich schwer.

Sind die Probleme von Valerie und Carla widerspenstig?

	Ja.
	Nein.
	Kann man aufgrund der bisherigen Informationen nicht sagen.

Carlas Algorithmus hat ein Laufzeitverhalten von ${\cal O}(a^{n} \cdot n^{b})$ für $n$ Gene. Geben Sie $a$ und $b$ an.

Welche Gene gehören zu der größten Gruppe, innerhalb derer jedes Gen mit jedem anderen verbunden ist?

	A
	B
	C
	D
	E
	F
	G
	H
	I

In welchen Fällen liegt exponentielles Laufzeitverhalten vor?

	$2^{n}\cdot\log_2(n)$
	$2^{\log_2(n)}$
	$1{,}0001^{n}$
	$n^{1000}$
	Valeries Algorithmus

Welches Laufzeitverhalten - also ${\cal O}(\dots)$ - hat der Algorithmus von Valerie?

	$2^{n}+n^{2}$
	$2^{n}$
	$2^{n}\cdot n^{3}$
	$2^{n}\cdot n^{2}$
	$n^{3}$
	$n^{2}$
	$n$

In welchen Fällen ist die Aussage wahr und außerdem auch bestmöglich?

	$5n^{2}+42n-10 \in {\cal O}(n^{2})$
	$5n^{2}+42n-10 \in {\cal O}(n^{3})$
	$3^{n}+12n^{2}+28 \in {\cal O}(2^{n})$
	$3^{n}+12n^{2}+28 \in {\cal O}(3^{n})$
	$3^{n}+12n^{2}+28 \in {\cal O}(4^{n})$
	$3n^{4}\cdot2^{n}+7n+2\log(n) \in {\cal O}(2^{n})$
	$3n^{4}\cdot2^{n}+7n+2\log(n) \in {\cal O}({2{,}1}^{n})$

Welche von den folgenden Eingaben ist ein worst case?

	ABABABABABABAB...
	AAAAAAAAAAAAAA...
	ACACACACACACAC...
	BBBBBBBBBBBBBB...

Wie viele Zeiteinheiten dauert die Ausführung des Programms 3 aus der Vorlesung im worst case?

Wie viele Zeiteinheiten dauert die Ausführung des Programms 3 aus der Vorlesung?

Wie viele Zeiteinheiten dauert die Ausführung des Programms 2 aus der Vorlesung?

Wie viele Zeiteinheiten dauert die Ausführung des Programms 1 aus der Vorlesung?

Welche der folgenden Eigenschaften unseres Computermodells sind unrealistisch?

	Alle primitiven Operationen brauchen gleich lange.
	Der Speicher ist beliebig groß.
	Der Zugriff auf den Speicher ist 'kostenlos'.
	Einzelne Speicherzellen können nicht beliebig große Werte aufnehmen.

Was muss ein minimales abstraktes Modell zur Untersuchung der Komplexität von Algorithmen unbedingt haben?

	Speicher
	Grafikkarte
	Ein- und Ausgabe
	Maus
	Monitor
	Dateisystem
	Betriebssystem
	Programmierbarkeit
	CD-ROM

Die Laufzeit eines Algorithmus hängt ab von ...

	der Größe des Inputs.
	Inhalt bzw. Struktur des Inputs.
	der Art des benutzten Computers.
	der Speichergröße des benutzten Computers.
	der Implementation des Algorithmus.
	der benutzten Programmiersprache.

Wenn man eine Million Teilmengen pro Sekunde testen kann, wie lange braucht das Programm dann für 100 Ecken?

	einen Tag
	eine Woche
	einen Monat
	20 Jahre
	noch länger

Bei einem Graphen mit $n$ Ecken: Wie oft wird die Zeile 3 des Programms ausgeführt?

Was ist die minimale Anzahl an Geräten für das in der Vorlesung gezeigte Beispiel?

Wie kann man die ganze Ebene parkettieren?

	Wenn man nur $A$-Polyominos benutzt.
	Wenn man nur $B$-Polyominos benutzt.
	Wenn man nur $C$- und $D$-Polyominos benutzt.

Was meinen Sie: Ist $H$ (die nicht-entscheidbare Menge des Halteproblems) rekursiv aufzählbar?

	Ja
	Nein

Welche der folgenden Eigenschaften, die ein Programm $P$ haben kann, sind funktional?

	$P$ ist ein Programm.
	$P$ hält bei jeder Eingabe mit der Ausgabe 42 an.
	$P$ löst das Problem des Handlungsreisenden.
	$P$ gibt bei der Eingabe 2 etwas anderes aus als bei der Eingabe 3.
	$P$ hat bei einer Eingabe der Länge $n$ eine Laufzeit von mindestens $n^2$ Minuten.

Wie wird sich $\mathtt{inverse\_halt(}p\mathtt{)}$ verhalten?

	Hält sowohl für $p=P_{1}$ als auch für $p=P_{2}$ an.
	Hält für $p=P_{1}$ an und für $p=P_{2}$ nicht.
	Hält für $p=P_{1}$ nicht an, für $p=P_{2}$ aber schon.
	Hält weder für $p=P_{1}$ noch für $p=P_{2}$ an.

Welche der vorgestellten Programme halten mit der jeweiligen Eingabe an?

	Programm 1
	Programm 2
	Programm 3

Welche der folgenden Probleme sind nach unserer Definition "Computer-Probleme"?

	Eingabe: ein Aufsatz. Ausgabe: Hat der Aufsatz mehr als 10000 Worte?
	Eingabe: ein Aufsatz. Ausgabe: Welche Note soll der Aufsatz bekommen?
	Eingabe: ein Aufsatz. Ausgabe: Enthält der Aufsatz Tippfehler?
	Eingabe: zwei verschiedene ganze Zahlen. Ausgabe: Summe der beiden Zahlen.
	Eingabe: zwei verschiedene ganze Zahlen. Ausgabe: Ist die kleinere Zahl ein Teiler der größeren?
	Eingabe: zwei verschiedene ganze Zahlen. Ausgabe: Eine zufällige Zahl zwischen den beiden.
	Eingabe: eine endliche Folge von Einsen und Nullen. Ausgabe: Wurde diese Folge zufällig erzeugt?
	Eingabe: eine natürliche Zahl $n$. Ausgabe: Berechne die Quadratwurzel von $n$.

Welche der folgenden Features von $\mathtt{TOLL}$ sind nach Ihrer Meinung "überflüssig"?

	Fließkommazahlen
	Arrays
	Negative ganze Zahlen
	$\mathtt{FOR}$-Schleifen
	$\mathtt{WHILE}$-Schleifen
	$\mathtt{CASE}$-Konstrukte
	$\mathtt{ELSE}$-Teile von $\mathtt{IF}$-Befehlen
	Arithmetik (Multiplikation, Addition, etc.)
	$\mathtt{AND}$, $\mathtt{OR}$ und $\mathtt{NOT}$
	Zuweisungen

Welche der folgenden Sprachen sind wohl NICHT regulär?

	$\{w \in \{\mathtt{a},\mathtt{b}\}^\ast \mid |w| > 42 \}$
	$\{w \in \{\mathtt{a},\mathtt{b}\}^\ast \mid |w|_{\mathtt{a}} < 42 \}$
	$\{w \in \{\mathtt{a},\mathtt{b}\}^\ast \mid |w|_{\mathtt{a}} < |w|_{\mathtt{b}} \}$
	$\{w \in \{\mathtt{a},\mathtt{b}\}^\ast \mid |w|_{\mathtt{a}} < |w| \}$

Welche der folgenden Aussagen sind wahr?

	$\mathtt{a}(\mathtt{a}+(\mathtt{a})^\ast) \equiv (\mathtt{a})^\ast\mathtt{a}$
	$\mathtt{a}(\mathtt{b}+(\mathtt{a})^\ast) \equiv (\mathtt{a})^\ast\mathtt{b}$
	$(\mathtt{a}(\mathtt{b})^\ast + \mathtt{b}(\mathtt{a})^\ast) \equiv (\mathtt{a}+\mathtt{b})((\mathtt{a}+\mathtt{b}))^\ast$
	$((\mathtt{a}+\mathtt{b}))^\ast \equiv ((\mathtt{a})^\ast+(\mathtt{b})^\ast)^\ast$

Sei $L_1 = \{w^{n+3} \mid w \in \Sigma_{\text{bool}}^+ \land n \in \mathbb{N} \}$ und $L_2 = \{uw^{|u|} \mid u,w \in \Sigma_{\text{lat}}^\ast \}$. Welche der folgenden Aussagen sind wahr?

	$\mathtt{001001001} \in L_1$
	$\mathtt{000000} \in L_1$
	$\mathtt{001001} \in L_1$
	$\varepsilon \in L_1$
	$\varepsilon \in L_2$
	$L_2 = \Sigma_{\text{lat}}^\ast$

Sei $\Sigma_1=\{\mathtt{a},\mathtt{b}\}$ und $\Sigma_2=\{\mathtt{a},\mathtt{b},\mathtt{c}\}$. Welche der folgenden Aussagen sind wahr?

	$\Sigma_1^\ast \subseteq \Sigma_2^\ast$
	$\Sigma_1^\ast \subseteq \Sigma_2^+$
	$\mathtt{cac} \in \Sigma_1^\ast$
	$\mathtt{cac} \in \Sigma_2^+$