Anki Deck Changes

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Fh0sH>F}O$

added

New Note

Front

Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" ist NP-vollständig.

Back

Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" ist NP-vollständig.

Karp (1972)

undefined

Field-by-field Comparison

Field	Before	After
Text		<div>Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" ist {{c1::NP-vollständig}}.</div>
Extra		Karp (1972)<br><br><img alt="undefined" src="960px-Karp_mg_7725-b.cr2.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 2: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: G*KmSXW.j#

added

New Note

Front

Runtime Brute Force ob ein Hamiltonkreis existiert?

Back

Runtime Brute Force ob ein Hamiltonkreis existiert?

$O(n!)$

Field-by-field Comparison

Field	Before	After
Front		Runtime Brute Force ob ein Hamiltonkreis existiert?
Back		$O(n!)$

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 3: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: Iy!09]5^c4

added

New Note

Front

Wie kann man mit der Siebformel die Zahl der Hamiltonkreise berechnen?

Back

Wie kann man mit der Siebformel die Zahl der Hamiltonkreise berechnen?

(Skript S. 52)

Field-by-field Comparison

Field	Before	After
Front		Wie kann man mit der Siebformel die Zahl der Hamiltonkreise berechnen?<br><br><img src="paste-d454204da8de64a9c842a16065119d478d21ad19.jpg">
Back		<img src="paste-251c083b9141552084ce4c7b9a38b3775b174bc2.jpg"><br><br>(Skript S. 52)

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 4: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: JiQh1]E2XH

added

New Note

Front

Jeder Graph $G = (V, E)$ mit $|V| \geq 3$ und Minimalgrad $\delta(G) \geq |V|/2$ enthält einen Hamiltonkreis.

Back

Jeder Graph $G = (V, E)$ mit $|V| \geq 3$ und Minimalgrad $\delta(G) \geq |V|/2$ enthält einen Hamiltonkreis.

Satz von Dirac

undefined

Field-by-field Comparison

Field	Before	After
Text		<div>Jeder Graph $G = (V, E)$ mit $\|V\| \geq 3$ und {{c1::Minimalgrad $\delta(G) \geq \|V\|/2$}} enthält {{c2::einen Hamiltonkreis}}.<br></div>
Extra		Satz von Dirac<br><br><img alt="undefined" src="500px-Paul_Dirac,_1933.jpg">

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 5: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: NAMKNs@=})

added

New Note

Front

Was ist der Speicherbedarf von Hamiltonkreise mit DP?

Back

Was ist der Speicherbedarf von Hamiltonkreise mit DP?

$n\cdot2^n$

Field-by-field Comparison

Field	Before	After
Front		Was ist der Speicherbedarf von Hamiltonkreise mit DP?
Back		$n\cdot2^n$

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 6: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: eBef=Ei?a&

added

New Note

Front

Wie lautet die Siebformel für $n=2$?

Back

Wie lautet die Siebformel für $n=2$?

$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$

Field-by-field Comparison

Field	Before	After
Front		Wie lautet die Siebformel für $n=2$?
Back		<div>$\|A_1 \cup A_2\| = \|A_1\| + \|A_2\| - \|A_1 \cap A_2\|$</div><div><br></div><div><img src="paste-8b0e902e8d41d078032e8f2ed3d33cfde63fe76e.jpg"></div><div></div><div></div>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 7: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: fqf[%vDy6F

added

New Note

Front

Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" kann man in Zeit {{c1::$O(|V|^2 \cdot 2^{|V|})$ entscheiden und, falls ja, einen solchen finden}}.

Back

Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" kann man in Zeit {{c1::$O(|V|^2 \cdot 2^{|V|})$ entscheiden und, falls ja, einen solchen finden}}.

Field-by-field Comparison

Field	Before	After
Text		<div>Das Problem „Gegeben ein Graph $G = (V, E)$, enthält $G$ einen Hamiltonkreis?" kann man in Zeit {{c1::$O(\|V\|^2 \cdot 2^{\|V\|})$ entscheiden und, falls ja, einen solchen finden}}.</div>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 8: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: rd?}|E1Z!9

added

New Note

Front

Hamiltonkreise mit DP

Für alle $S \subseteq [n]$ mit $1 \in S$ und alle $x \in S$ mit $x \neq 1$:

\[P_{S,x} := {{c1::\begin{aligned} &\begin{cases} 1, & \text{es gibt einen 1-x-Pfad, der genau die Knoten aus } S \text{ enthält} \\ 0, & \text{sonst} \end{cases} \end{aligned} }}\]

Back

Hamiltonkreise mit DP

Für alle $S \subseteq [n]$ mit $1 \in S$ und alle $x \in S$ mit $x \neq 1$:

\[P_{S,x} := {{c1::\begin{aligned} &\begin{cases} 1, & \text{es gibt einen 1-x-Pfad, der genau die Knoten aus } S \text{ enthält} \\ 0, & \text{sonst} \end{cases} \end{aligned} }}\]

Field-by-field Comparison

Field	Before	After
Text		<div>Hamiltonkreise mit DP</div><div><br></div><div><div>Für alle $S \subseteq [n]$ mit $1 \in S$ und alle $x \in S$ mit $x \neq 1$:</div> <div>\[P_{S,x} := {{c1::\begin{aligned} &\begin{cases} 1, & \text{es gibt einen 1-x-Pfad, der genau die Knoten aus } S \text{ enthält} \\ 0, & \text{sonst} \end{cases} \end{aligned} }}\]</div></div> <div></div>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 9: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Occlusio
GUID: w,M||$B!bf

added

New Note

Front

Hamiltonkreise mit DP

Back

Hamiltonkreise mit DP

Field-by-field Comparison

Field	Before	After
Occlusion		{{c1::image-occlusion:rect:left=.0549:top=.1775:width=.9042:height=.1202}}<br>{{c2::image-occlusion:rect:left=.0813:top=.4818:width=.8976:height=.407}}<br>{{c3::image-occlusion:rect:left=.1588:top=.8926:width=.7186:height=.0736}}<br>
Image		<img src="paste-8c6f28e5ec6b1544477701f70a5ddbb2124f7145.jpg">
Header		Hamiltonkreise mit DP

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 10: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: yS&M8GIM_[

added

New Note

Front

Was ist die Laufzeit von Hamiltonkreise mit DP?

Back

Was ist die Laufzeit von Hamiltonkreise mit DP?

$O(n^22^n)$

Field-by-field Comparison

Field	Before	After
Front		Was ist die Laufzeit von Hamiltonkreise mit DP?
Back		$O(n^22^n)$

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 11: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: G~p(S},tR5

added

New Note

Front

Das Traveling Salesman Problem (TSP) ist NP-vollständig.

Back

Das Traveling Salesman Problem (TSP) ist NP-vollständig.

Hieraus folgt auch: für kein $C > 0$ kann es einen polynominellen $C$-Approximationsalgorithmus geben (außer es gilt $P = NP$).

Field-by-field Comparison

Field	Before	After
Text		Das Traveling Salesman Problem (TSP) ist {{c1::NP-vollständig}}.
Extra		<img src="paste-60fd4107b18f779043ba63ecc64bf50f4bed5cde.jpg"><br><br><div>Hieraus folgt auch: für kein $C > 0$ kann es einen polynominellen $C$-Approximationsalgorithmus geben (außer es gilt $P = NP$).</div>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::4._Das_Travelling_Salesman_Problem

Note 12: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: cQU{Gyv:n7

added

New Note

Front

$P$ = effizient entscheidbare Probleme

$NP$ = (einseitig) effizient verifizierbare Probleme

Back

$P$ = effizient entscheidbare Probleme

$NP$ = (einseitig) effizient verifizierbare Probleme

P = polynomiell
NP = nichtdeterministisch polynomiell

Field-by-field Comparison

Field	Before	After
Text		<div>$P$ = {{c1::effizient entscheidbare Probleme}}</div> <div>$NP$ = {{c1::(einseitig) effizient verifizierbare Probleme}}</div>
Extra		P = polynomiell<br>NP = nichtdeterministisch polynomiell

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Note 13: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: l2h9S2i&Y?

added

New Note

Front

Travelling Salesman Problem

Gegeben: {{c1::vollständiger Graph auf

$n$ Knoten, Distanzen zw. je zwei Knoten: $\ell : \binom{[n]}{2} \to \mathbb{R}$ }}

Gesucht? {{c2:: Kürzeste Rundreise:

\[\min_{H: \text{Hamiltonkreis} } \sum_{e \in E(H)} \ell(e)\]

}}

Back

Travelling Salesman Problem

Gegeben: {{c1::vollständiger Graph auf

$n$ Knoten, Distanzen zw. je zwei Knoten: $\ell : \binom{[n]}{2} \to \mathbb{R}$ }}

Gesucht? {{c2:: Kürzeste Rundreise:

\[\min_{H: \text{Hamiltonkreis} } \sum_{e \in E(H)} \ell(e)\]

}}

Field-by-field Comparison

Field	Before	After
Text		Travelling Salesman Problem<br><br><div><strong>Gegeben:</strong> {{c1::vollständiger Graph auf </div>$n$ Knoten, Distanzen zw. je zwei Knoten: $\ell : \binom{[n]}{2} \to \mathbb{R}$ }} <div><strong>Gesucht?</strong> {{c2:: Kürzeste Rundreise:</div><div>\[\min_{H: \text{Hamiltonkreis} } \sum_{e \in E(H)} \ell(e)\]</div>}}

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::4._Das_Travelling_Salesman_Problem

Note 14: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: y@-]+Mp!&j

added

New Note

Front

Ein Problem $\Pi$ aus NP heißt NP-vollständig, falls gilt:

\[\Pi \in P \Rightarrow P = NP\]

Back

Ein Problem $\Pi$ aus NP heißt NP-vollständig, falls gilt:

\[\Pi \in P \Rightarrow P = NP\]

Es gibt sehr viele NP-vollständige Probleme:

Hamiltonkreis
Rucksackproblem
Clique: Gibt es in einem Graphen $k$ paarweise benachbarte Knoten?
Nullstelle mod $n$: Hat ein Polynom mod $n$ eine Nullstelle?
Satisfiability: Hat eine logische Formel eine Lösung?

Field-by-field Comparison

Field	Before	After
Text		<div>Ein Problem $\Pi$ aus NP heißt NP-vollständig, falls gilt:</div> <div>\[{{c1::\Pi \in P \Rightarrow P = NP}}\]</div>
Extra		<div>Es gibt sehr viele NP-vollständige Probleme:<br></div><div> <ul> <li><strong>Hamiltonkreis</strong></li> <li><strong>Rucksackproblem</strong></li> <li><strong>Clique</strong>: Gibt es in einem Graphen $k$ paarweise benachbarte Knoten?</li> <li><strong>Nullstelle mod $n$</strong>: Hat ein Polynom mod $n$ eine Nullstelle?</li> <li><strong>Satisfiability</strong>: Hat eine logische Formel eine Lösung?</li></ul></div>

Tags: ETH::2._Semester::A&W::1._Graphentheorie::5._Kreise::2._Hamiltonkreise

Field	Before	After
Text		<div>Das Problem „Gegeben ein Graph \(G = (V, E)\), enthält \(G\) einen Hamiltonkreis?" ist {{c1::NP-vollständig}}.</div>
Extra		Karp (1972)<br><br><img alt="undefined" src="960px-Karp_mg_7725-b.cr2.jpg">

Field	Before	After
Text		<div>Jeder Graph \(G = (V, E)\) mit \(\|V\| \geq 3\) und {{c1::Minimalgrad \(\delta(G) \geq \|V\|/2\)}} enthält {{c2::einen Hamiltonkreis}}.<br></div>
Extra		Satz von Dirac<br><br><img alt="undefined" src="500px-Paul_Dirac,_1933.jpg">

Field	Before	After
Front		Wie lautet die Siebformel für \(n=2\)?
Back		<div>\(\|A_1 \cup A_2\| = \|A_1\| + \|A_2\| - \|A_1 \cap A_2\|\)</div><div><br></div><div><img src="paste-8b0e902e8d41d078032e8f2ed3d33cfde63fe76e.jpg"></div><div></div><div></div>

Field	Before	After
Text		<div>\(P\) = {{c1::effizient entscheidbare Probleme}}</div> <div>\(NP\) = {{c1::(einseitig) effizient verifizierbare Probleme}}</div>
Extra		P = polynomiell<br>NP = nichtdeterministisch polynomiell

Field	Before	After
Text		<div>Ein Problem \(\Pi\) aus NP heißt NP-vollständig, falls gilt:</div> <div>\[{{c1::\Pi \in P \Rightarrow P = NP}}\]</div>
Extra		<div>Es gibt sehr viele NP-vollständige Probleme:<br></div><div> <ul> <li><strong>Hamiltonkreis</strong></li> <li><strong>Rucksackproblem</strong></li> <li><strong>Clique</strong>: Gibt es in einem Graphen \(k\) paarweise benachbarte Knoten?</li> <li><strong>Nullstelle mod \(n\)</strong>: Hat ein Polynom mod \(n\) eine Nullstelle?</li> <li><strong>Satisfiability</strong>: Hat eine logische Formel eine Lösung?</li></ul></div>

Note 1: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 2: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 3: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 4: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 5: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 6: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 7: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 8: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 9: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 10: ETH::2. Semester::A&W

Previous

New Note

Front

Back

Note 11: ETH::2. Semester::PProg

Previous

New Note

Front

Back

Note 12: ETH::2. Semester::PProg

Previous

New Note

Front

Back

Note 13: ETH::2. Semester::PProg

Previous

New Note

Front

Back

Note 14: ETH::2. Semester::PProg

Previous

New Note

Front

Back