http://uxul.de/4DQNJeqOrv/index.php?action=history&feed=atom&title=L 2026-05-11T18:32:05Z Versionsgeschichte dieser Seite in Einführung in die Theoretische Informatik und in die Mathematische Logik MediaWiki 1.31.0 http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=268&oldid=prev 2018-08-29T19:17:12Z

<p></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Version vom 29. August 2018, 19:17 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Zeile 1:</td> <td colspan="2" class="diff-lineno">Zeile 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, <del class="diffchange diffchange-inline">das heißt, zusätzlich zur </del>Eingabe <del class="diffchange diffchange-inline">(die man </del>in <del class="diffchange diffchange-inline">diesem Fall nicht dazuzählt, weil es sonst nicht möglich ist</del>, <del class="diffchange diffchange-inline">weniger als </del>linear viel <del class="diffchange diffchange-inline">Speicher zu brauchen)</del>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$<ins class="diffchange diffchange-inline">. Für sublinearen Speicherverbrauch vereinbart man</ins>, <ins class="diffchange diffchange-inline">dass die </ins>Eingabe in <ins class="diffchange diffchange-inline">einem eigenen Read-Only-Band übergeben wird</ins>, <ins class="diffchange diffchange-inline">da dieser einem ansonsten schon </ins>linear viel <ins class="diffchange diffchange-inline">zusätzlichen Speicherplatz brächte</ins>.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Beispiele ==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Beispiele ==</div></td></tr> </table>

Css http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=259&oldid=prev 2018-08-29T15:22:56Z

<p>‎<span dir="auto"><span class="autocomment">Beispiele</span></span></p> <table class="diff diff-contentalign-left" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Version vom 29. August 2018, 15:22 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Zeile 2:</td> <td colspan="2" class="diff-lineno">Zeile 2:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Beispiele ==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Beispiele ==</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== k-Cliquen in Graphen ===</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz.</ins></div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Erreichbarkeit in Graphen ===</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Erreichbarkeit in Graphen ===</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">'''TODO'''</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang,</ins></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:TODO]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:TODO]]</div></td></tr> </table>

Css http://uxul.de/4DQNJeqOrv/index.php?title=L&diff=237&oldid=prev 2018-08-24T13:39:58Z

<p>Die Seite wurde neu angelegt: „Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil…“</p> <p><b>Neue Seite</b></p><div>Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$, das heißt, zusätzlich zur Eingabe (die man in diesem Fall nicht dazuzählt, weil es sonst nicht möglich ist, weniger als linear viel Speicher zu brauchen).<br /> <br /> == Beispiele ==<br /> <br /> === Erreichbarkeit in Graphen ===<br /> <br /> '''TODO'''<br /> <br /> <br /> [[Kategorie:TODO]]</div>

Css