To receive notifications about scheduled maintenance, please subscribe to the mailing-list gitlab-operations@sympa.ethz.ch. You can subscribe to the mailing-list at https://sympa.ethz.ch

appendix.tex 3.1 KB
Newer Older
Theo von Arx's avatar
Theo von Arx committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
%! TEX root = DES.tex

\section{Mathematik}
\subsection{Spezielle Reihen}
\begin{itemize}
  \item $\displaystyle \sum_{k=0}^\infty aq^k=a+aq+aq^2+\ldots=\frac{a}{1-q}$ für $|q|<1$
  \item $\displaystyle \sum_{k=0}^\infty (k+1)q^k=1+2q+3q^2+\ldots=\frac{1}{(1-q)^2} $ für $|q|<1$
  \item $\displaystyle \sum_{k=1}^\infty \frac{1}{k^2}=1+\frac{1}{2^2}+\frac{1}{3^2}+\ldots=\frac{\pi^2}{6}$
  \item $\displaystyle \sum_{k=0}^\infty \frac{1}{k!}=1+1+\frac{1}{2}+\frac{1}{6}+\ldots=e$
\end{itemize}

\subsection{Spezielle Summen}
\begin{itemize}
  \item $\displaystyle \sum_{k = 1}^n k = \frac{n(n + 1)}{2}$
  \item $\displaystyle \sum_{k = 1}^n i^2 = \frac{n (n + 1) (2n + 1)}{6}$
  \item $\displaystyle \sum_{k = 0}^n q^i = \frac{1 - q^{n + 1}}{1 - q}$
  \item $\displaystyle \sum_{k = 1}^n \frac{1}{k} \approx \ln(n) + \gamma$
  \item $\displaystyle \sum_{k = 0}^n \begin{pmatrix}n \\k\end{pmatrix} a^{n - k} b^k = (a + b)^n$
\end{itemize}

\subsection{Prinzip der Inklusion / Exklusion:}
\begin{align*}
| A \cup B \cup C| &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \\
|A \cup B| &= |A| + |B| - |A\cap B| \\
| A \cap B \cap C| &= |A| + |B| + |C| - |A \cup B| - |A \cup C| - |B \cup C| + |A \cup B \cup C| \\
|A \cap B| &= |A| + |B| - |A\cup B|
\end{align*}

\section{Verschiedenes}
\paragraph*{Palindrom}
Bsp: $\displaystyle L = \{ u \, | \, u \in \{ 0, 1\}^*$ und $u^{reverse} = u \} = \{u \, | \, ''u \text{ ist ein Palindrom}'' \}$. Daran denken, dass $|u| = odd$ sein kann.

\paragraph*{DFA überprüfen}
Jeder FA braucht einen Start-State. \\
DFAs haben für alle Buchstaben im Alphabet $\Sigma$ eindeutige Folgezustände.
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
\paragraph*{De Morgansche Regeln}
\begin{tabular}{|l|c|}
\hline
Symbole & \dis{-0.3}\begin{tabular}{c} $\vee,\,+\,:=ODER$ \\ $\wedge,\,\cdot\,:=UND$ \end{tabular} \\
\hline
2-Fach Negation\dis{-0.2} & \dis{-0.3}$\overline{\overline{A}}=A$ \\
\hline
Kommutativ & \dis{-0.3}\begin{tabular}{c} $A\cdot B=B\cdot A$ \\ $A+B=B+A$ \end{tabular} \\
\hline
Assoziativ & \dis{-0.3}\begin{tabular}{c} $A\cdot (B\cdot C)=(A\cdot B)\cdot C$ \\ $A+(B+C)=(A+B)+C$ \end{tabular} \\
\hline
Distributiv & \dis{-0.3}\begin{tabular}{c} $A\cdot (B+C)=A\cdot B+ A\cdot C$ \\ $A+(B\cdot C)=(A+B)\cdot(A+C)$ \end{tabular}\dis{-0.3} \\ \hline
Idempotenz & \dis{-0.3}\begin{tabular}{c} $A\cdot A = A$ \\ $A+A=A$ \end{tabular} \\
\hline
Komplement & \dis{-0.3}\begin{tabular}{c} $A\cdot\overline{A}=0$\\$A+\overline{A}=1$ \end{tabular}\\
\hline
Neutrale & \dis{-0.3}\begin{tabular}{c} $A\cdot 1=A$, $A+0=A$  \end{tabular} \\
\hline
Dominanz & \dis{-0.3}\begin{tabular}{c} $A\cdot 0=0$, $A+1=1$ \end{tabular} \\
\hline
Absorption & \dis{-0.3}\begin{tabular}{c} $A\cdot (A+B)=A$\\$A+(A\cdot B)=A$ \end{tabular} \\
\hline
Adsorption & \dis{-0.3}\begin{tabular}{c} $A\cdot (\overline{A}+B)=A\cdot B$\\$A+(\overline{A}\cdot B)=A+B$ \end{tabular} \\
\hline
De Morgan & \dis{-0.3}\begin{tabular}{c} $Z=\overline{A\cdot B}=\overline{A}+\overline{B}$\\$Z=A\cdot B=\overline{\overline{A}+\overline{B}}$\\$Z=\overline{A+B}=\overline{A}\cdot\overline{B}$\\$Z=A+B=\overline{\overline{A}\cdot\overline{B}}$ \end{tabular} \\
\hline
\end{tabular}\\\\\\