modulares Inverses

5 files changed, 42 insertions, 0 deletions

diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp
new file mode 100644
index 0000000..e7ec0c3
--- /dev/null
+++ b/graph/dijkstra.cpp
@@ -0,0 +1,20 @@
+priority_queue<ii, vector<ii>, greater<ii> > pq;
+vector<int> dist;
+dist.assign(NUM_VERTICES, INF);
+dist[0] = 0;
+pq.push(ii(0, 0));
+
+while (!pq.empty()) {
+	di front = pq.top(); pq.pop();
+	int curNode = front.second, curDist = front.first;
+	
+	if (curDist > dist[curNode]) continue;
+	
+	for (i = 0; i < (int)adjlist[curNode].size(); i++) {
+		int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second;
+		
+		if (nextDist < dist[nextNode]) {
+			dist[nextNode] = nextDist; pq.push(ii(nextDist, nextNode));
+		}
+	}
+}
\ No newline at end of file
diff --git a/graph/graph.tex b/graph/graph.tex
index 4646ee3..2bf395c 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -2,7 +2,12 @@
 
 \subsection{Kürzeste Wege}
 
+\subsubsection{Algorithmus von \textsc{Dijkstra}}
+Kürzeste Pfade in Graphen ohne negative Kanten.
+\lstinputlisting{graph/dijkstra.cpp}
+
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
+Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen.
 \lstinputlisting{graph/bellmannFord.cpp}
 
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
diff --git a/math/math.tex b/math/math.tex
index 0b66163..f82ab65 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -4,5 +4,17 @@
 \lstinputlisting{math/gcd-lcm.cpp}
 \lstinputlisting{math/extendedEuclid.cpp}
 
+\subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
+Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
+\begin{description}
+	\item[Falls $d = 1$:] ~
+	\begin{itemize}[nosep]
+		\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit $\alpha x + \beta n = 1$
+		\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$
+		\item $x^{-1} :\equiv \alpha \mod n$
+	\end{itemize}
+	\item[Falls $d \neq 1$:] es existiert kein $x^{-1}$
+\end{description}
+
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index a19e113..07e4ceb 100644
--- a/tcr.pdf
+++ b/tcr.pdf
diff --git a/tcr.tex b/tcr.tex
index be8556d..4dce95e 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -4,6 +4,11 @@
 \usepackage[ngerman]{babel}
 \usepackage[utf8]{inputenc}
 
+\usepackage{amsmath}
+\usepackage{amssymb}
+
+\usepackage{enumitem}
+
 \usepackage{color}
 \definecolor{darkred}{rgb}{0.72,0.07,0.07}
 \definecolor{darkgreen}{rgb}{0.23,0.62,0.22}