From 442921c7bd93e9e111845de6c22f66753b41e11a Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 00:17:59 +0200 Subject: Renamin sonstiges ot other. --- other/bitOps.cpp | 14 ++++++++ other/josephus2.cpp | 8 +++++ other/josephusK.cpp | 4 +++ other/other.tex | 89 ++++++++++++++++++++++++++++++++++++++++++++++++ other/split.cpp | 9 +++++ sonstiges/bitOps.cpp | 14 -------- sonstiges/josephus2.cpp | 8 ----- sonstiges/josephusK.cpp | 4 --- sonstiges/sonstiges.tex | 89 ------------------------------------------------ sonstiges/split.cpp | 9 ----- tcr.pdf | Bin 265152 -> 265152 bytes tcr.tex | 2 +- 12 files changed, 125 insertions(+), 125 deletions(-) create mode 100644 other/bitOps.cpp create mode 100644 other/josephus2.cpp create mode 100644 other/josephusK.cpp create mode 100644 other/other.tex create mode 100644 other/split.cpp delete mode 100644 sonstiges/bitOps.cpp delete mode 100644 sonstiges/josephus2.cpp delete mode 100644 sonstiges/josephusK.cpp delete mode 100644 sonstiges/sonstiges.tex delete mode 100644 sonstiges/split.cpp diff --git a/other/bitOps.cpp b/other/bitOps.cpp new file mode 100644 index 0000000..b75304f --- /dev/null +++ b/other/bitOps.cpp @@ -0,0 +1,14 @@ +// Bit an Position j auslesen. +(a & (1 << j)) != 0 +// Bit an Position j setzen. +a |= (1 << j) +// Bit an Position j löschen. +a &= ~(1 << j) +// Bit an Position j umkehren. +a ^= (1 << j) +// Wert des niedrigsten gesetzten Bits. +(a & -a) +// Setzt alle Bits auf 1. +a = -1 +// Setzt die ersten n Bits auf 1. Achtung: Overflows. +a = (1 << n) - 1 diff --git a/other/josephus2.cpp b/other/josephus2.cpp new file mode 100644 index 0000000..c0bcc2f --- /dev/null +++ b/other/josephus2.cpp @@ -0,0 +1,8 @@ +int rotateLeft(int n) { // Gibt Index des letzten Überlebenden zurück, 1-basiert. + for (int i = 31; i >= 0; i--) + if (n & (1 << i)) { + n &= ~(1 << i); + break; + } + n <<= 1; n++; return n; +} \ No newline at end of file diff --git a/other/josephusK.cpp b/other/josephusK.cpp new file mode 100644 index 0000000..8758fee --- /dev/null +++ b/other/josephusK.cpp @@ -0,0 +1,4 @@ +int josephus(int n, int k) { // Gibt Index des letzten Überlebenden zurück, 0-basiert. + if (n == 1) return 0; + return (josephus(n - 1, k) + k) % n; +} \ No newline at end of file diff --git a/other/other.tex b/other/other.tex new file mode 100644 index 0000000..6bc4733 --- /dev/null +++ b/other/other.tex @@ -0,0 +1,89 @@ +\section{Sonstiges} + +\subsection{2-SAT} +\begin{enumerate} + \item Bedingungen in 2-CNF formulieren. + \item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$. + \item Finde die starken Zusammenhangskomponenten. + \item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt. +\end{enumerate} + +\subsection{Zeileneingabe} +\lstinputlisting{other/split.cpp} + +\subsection{Bit Operations} +\lstinputlisting{other/bitOps.cpp} + +\subsection{Josephus-Problem} +$n$ Personen im Kreis, jeder $k$-te wird erschossen. +\begin{description} + \item[Spezialfall $k=2$:] Betrachte Binärdarstellung von $n$. + Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n1$ die Position des letzten Überlebenden. + (Rotiere $n$ um eine Stelle nach links) + \lstinputlisting{other/josephus2.cpp} + \item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden. + Nummeriere die Personen mit $0, 1, \ldots, n-1$. + Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$. + Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. + \lstinputlisting{other/josephusK.cpp} +\end{description} +\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $1, \ldots, n$ nummeriert sind, im zweiten Fall von $0, \ldots, n-1$!} + +\subsection{Gemischtes} +\begin{itemize}[itemsep=5mm] + \item \emph{\textsc{Johnsons} Reweighting Algorithmus:} + Füge neue Quelle \lstinline{S} hinzu, mit Kanten mit Gewicht 0 zu allen Knoten. + Nutze \textsc{Bellmann-Ford} zum Betsimmen der Entfernungen \lstinline{d[i]} von \lstinline{S} zu allen anderen Knoten. + Stoppe, wenn es negative Zyklen gibt. + Sonst ändere die gewichte von allen Kanten \lstinline{(u,v)} im ursprünglichen Graphen zu \lstinline{d[u]+w[u,v]-d[v]}. + Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden. + \item Für ein System von Differenzbeschränkungen: + Ändere alle Bedingungen in die Form $a-b \leq c$. + Für jede Bedingung füge eine Kante \lstinline{(b,a)} mit Gweicht \lstinline{c} ein. + Füge Quelle \lstinline{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0. + Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \lstinline{s} aus zu finden. + \lstinline{d[v]} ist mögliche Lösung für \lstinline{v}. + \item Min-Weight-Vertex-Cover im bipartiten Graph: + Partitioniere in \lstinline{A, B} und füge Kanten \lstinline{s -> A} mit Gewicht \lstinline{w(A)} und Kanten \lstinline{B -> t} mit Gewicht \lstinline{w(B)} hinzu. + Füge Kanten mit Kapazität $\infty$ von \lstinline{A} nach \lstinline{B} hinzu, wo im originalen Graphen Kanten waren. + Max-Flow ist die Lösung.\newline + Im Residualgraphen: + \begin{itemize} + \item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder} + \item Die Knoten in \lstinline{A}, die \emph{nicht} von \lstinline{s} erreichber sind und die Knoten in \lstinline{B}, die von \lstinline{erreichber} sind. + \end{itemize} + \item Allgemeiner Graph: + Das Komplement eines Vertex-Cover ist ein Independent Set. + $\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover. + \item Bipartiter Graph: + Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching. + \item Bipartites Matching mit Gewichten auf linken Knoten. + Minimiere Matchinggewicht. + Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normlen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn}) + \item \textbf{Tobi, cool down!} +\end{itemize} + +\subsection{Sonstiges} +\begin{lstlisting} +// Alles-Header. +#include + +// Setzt das deutsche Tastaturlayout. +setxkbmap de + +// Schnelle Ein-/Ausgabe mit cin/cout. +ios::sync_with_stdio(false); + +// Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden. +set set1(comp); + +// PI +#define PI (2*acos(0)) + +// STL-Debugging, Compiler flags. +-D_GLIBCXX_DEBUG +#define _GLIBCXX_DEBUG + +// 128-Bit Integer. Muss zum Einlesen/Ausgeben in einen int oder long long gecastet werden. +__int128 +\end{lstlisting} diff --git a/other/split.cpp b/other/split.cpp new file mode 100644 index 0000000..ea7d5ff --- /dev/null +++ b/other/split.cpp @@ -0,0 +1,9 @@ +vector split(string &s, string delim) { // Zerlegt s anhand aller Zeichen in delim. + vector result; char *token; + token = strtok((char*)s.c_str(), (char*)delim.c_str()); + while (token != NULL) { + result.push_back(string(token)); + token = strtok(NULL, (char*)delim.c_str()); + } + return result; +} \ No newline at end of file diff --git a/sonstiges/bitOps.cpp b/sonstiges/bitOps.cpp deleted file mode 100644 index b75304f..0000000 --- a/sonstiges/bitOps.cpp +++ /dev/null @@ -1,14 +0,0 @@ -// Bit an Position j auslesen. -(a & (1 << j)) != 0 -// Bit an Position j setzen. -a |= (1 << j) -// Bit an Position j löschen. -a &= ~(1 << j) -// Bit an Position j umkehren. -a ^= (1 << j) -// Wert des niedrigsten gesetzten Bits. -(a & -a) -// Setzt alle Bits auf 1. -a = -1 -// Setzt die ersten n Bits auf 1. Achtung: Overflows. -a = (1 << n) - 1 diff --git a/sonstiges/josephus2.cpp b/sonstiges/josephus2.cpp deleted file mode 100644 index c0bcc2f..0000000 --- a/sonstiges/josephus2.cpp +++ /dev/null @@ -1,8 +0,0 @@ -int rotateLeft(int n) { // Gibt Index des letzten Überlebenden zurück, 1-basiert. - for (int i = 31; i >= 0; i--) - if (n & (1 << i)) { - n &= ~(1 << i); - break; - } - n <<= 1; n++; return n; -} \ No newline at end of file diff --git a/sonstiges/josephusK.cpp b/sonstiges/josephusK.cpp deleted file mode 100644 index 8758fee..0000000 --- a/sonstiges/josephusK.cpp +++ /dev/null @@ -1,4 +0,0 @@ -int josephus(int n, int k) { // Gibt Index des letzten Überlebenden zurück, 0-basiert. - if (n == 1) return 0; - return (josephus(n - 1, k) + k) % n; -} \ No newline at end of file diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex deleted file mode 100644 index 8148dbf..0000000 --- a/sonstiges/sonstiges.tex +++ /dev/null @@ -1,89 +0,0 @@ -\section{Sonstiges} - -\subsection{2-SAT} -\begin{enumerate} - \item Bedingungen in 2-CNF formulieren. - \item Implikationsgraph bauen, $\left(a \vee b\right)$ wird zu $\neg a \Rightarrow b$ und $\neg b \Rightarrow a$. - \item Finde die starken Zusammenhangskomponenten. - \item Genau dann lösbar, wenn keine Variable mit ihrer Negation in einer SCC liegt. -\end{enumerate} - -\subsection{Zeileneingabe} -\lstinputlisting{sonstiges/split.cpp} - -\subsection{Bit Operations} -\lstinputlisting{sonstiges/bitOps.cpp} - -\subsection{Josephus-Problem} -$n$ Personen im Kreis, jeder $k$-te wird erschossen. -\begin{description} - \item[Spezialfall $k=2$:] Betrachte Binärdarstellung von $n$. - Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n1$ die Position des letzten Überlebenden. - (Rotiere $n$ um eine Stelle nach links) - \lstinputlisting{sonstiges/josephus2.cpp} - \item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden. - Nummeriere die Personen mit $0, 1, \ldots, n-1$. - Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$. - Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. - \lstinputlisting{sonstiges/josephusK.cpp} -\end{description} -\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $1, \ldots, n$ nummeriert sind, im zweiten Fall von $0, \ldots, n-1$!} - -\subsection{Gemischtes} -\begin{itemize}[itemsep=5mm] - \item \emph{\textsc{Johnsons} Reweighting Algorithmus:} - Füge neue Quelle \lstinline{S} hinzu, mit Kanten mit Gewicht 0 zu allen Knoten. - Nutze \textsc{Bellmann-Ford} zum Betsimmen der Entfernungen \lstinline{d[i]} von \lstinline{S} zu allen anderen Knoten. - Stoppe, wenn es negative Zyklen gibt. - Sonst ändere die gewichte von allen Kanten \lstinline{(u,v)} im ursprünglichen Graphen zu \lstinline{d[u]+w[u,v]-d[v]}. - Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden. - \item Für ein System von Differenzbeschränkungen: - Ändere alle Bedingungen in die Form $a-b \leq c$. - Für jede Bedingung füge eine Kante \lstinline{(b,a)} mit Gweicht \lstinline{c} ein. - Füge Quelle \lstinline{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0. - Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \lstinline{s} aus zu finden. - \lstinline{d[v]} ist mögliche Lösung für \lstinline{v}. - \item Min-Weight-Vertex-Cover im bipartiten Graph: - Partitioniere in \lstinline{A, B} und füge Kanten \lstinline{s -> A} mit Gewicht \lstinline{w(A)} und Kanten \lstinline{B -> t} mit Gewicht \lstinline{w(B)} hinzu. - Füge Kanten mit Kapazität $\infty$ von \lstinline{A} nach \lstinline{B} hinzu, wo im originalen Graphen Kanten waren. - Max-Flow ist die Lösung.\newline - Im Residualgraphen: - \begin{itemize} - \item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder} - \item Die Knoten in \lstinline{A}, die \emph{nicht} von \lstinline{s} erreichber sind und die Knoten in \lstinline{B}, die von \lstinline{erreichber} sind. - \end{itemize} - \item Allgemeiner Graph: - Das Komplement eines Vertex-Cover ist ein Independent Set. - $\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover. - \item Bipartiter Graph: - Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching. - \item Bipartites Matching mit Gewichten auf linken Knoten. - Minimiere Matchinggewicht. - Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normlen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn}) - \item \textbf{Tobi, cool down!} -\end{itemize} - -\subsection{Sonstiges} -\begin{lstlisting} -// Alles-Header. -#include - -// Setzt das deutsche Tastaturlayout. -setxkbmap de - -// Schnelle Ein-/Ausgabe mit cin/cout. -ios::sync_with_stdio(false); - -// Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden. -set set1(comp); - -// PI -#define PI (2*acos(0)) - -// STL-Debugging, Compiler flags. --D_GLIBCXX_DEBUG -#define _GLIBCXX_DEBUG - -// 128-Bit Integer. Muss zum Einlesen/Ausgeben in einen int oder long long gecastet werden. -__int128 -\end{lstlisting} diff --git a/sonstiges/split.cpp b/sonstiges/split.cpp deleted file mode 100644 index ea7d5ff..0000000 --- a/sonstiges/split.cpp +++ /dev/null @@ -1,9 +0,0 @@ -vector split(string &s, string delim) { // Zerlegt s anhand aller Zeichen in delim. - vector result; char *token; - token = strtok((char*)s.c_str(), (char*)delim.c_str()); - while (token != NULL) { - result.push_back(string(token)); - token = strtok(NULL, (char*)delim.c_str()); - } - return result; -} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index 27ccfcb..ab87f80 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 03d1ce3..4598bec 100644 --- a/tcr.tex +++ b/tcr.tex @@ -35,7 +35,7 @@ \input{math/math} \input{string/string} \input{java/java} - \input{sonstiges/sonstiges} + \input{other/other} \end{multicols} \end{document} -- cgit v1.2.3