https://lib.custis.ru/index.php?action=history&feed=atom&title=DTIME 2026-04-27T12:18:27Z История изменений этой страницы в вики MediaWiki 1.26.4 https://lib.custis.ru/index.php?title=DTIME&diff=27264&oldid=prev 2011-06-13T17:39:44Z

<p>Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»</p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 17:39, 13 июня 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">Класс ''DTIME(t(n))'', означает класс задач, </del></div></td><td class='diff-marker'>+</td><td style="color:black; 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">#REDIRECT </ins>[[<ins class="diffchange diffchange-inline">discopal</ins>:{{<ins class="diffchange diffchange-inline">PAGENAME}</ins>}]]</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">разрешимых на </del>[[<del class="diffchange diffchange-inline">Машина Тьюринга|машине Тьюринга]] за время ''t(n)''.</del></div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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 class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">Более формально</del>:</div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">Язык &lt;amsmath&gt;L \subset \Sigma^*&lt;/amsmath&gt; принадлежит классу &lt;amsmath&gt;</del>{<del class="diffchange diffchange-inline">\cal DTIME}(t(n))&lt;/amsmath&gt;,</del></div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">если существует [[машина Тьюринга]] ''T'', разрешающая данный язык, и сложность ее работы в наихудшем случае, &lt;amsmath&gt;time_</del>{<del class="diffchange diffchange-inline">T(n)</del>} <del class="diffchange diffchange-inline">\leq t(n)&lt;/amsmath&gt;, т.е. не превышает ''t(n)'', где ''n''-длина входного слова.</del></div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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 class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">[[Category:Классы сложности</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; 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">{{replicate-from-custiswiki-to-lib}}</del></div></td><td class='diff-marker'>+</td><td style="color:black; 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></div></td></tr> </table>

StasFomin https://lib.custis.ru/index.php?title=DTIME&diff=9675&oldid=prev 2008-08-04T09:55:46Z

<p>1 версия</p> <table class='diff diff-contentalign-left'> <tr style='vertical-align: top;' lang='ru'> <td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 09:55, 4 августа 2008</td> </tr><tr><td colspan='2' style='text-align: center;' class='diff-multi' lang='ru'>(не показана 1 промежуточная версия 1 участника)</td></tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div> </td></tr></table>

WikiSysop https://lib.custis.ru/index.php?title=DTIME&diff=2881&oldid=prev 2005-12-07T04:39:48Z

<p>реплицировано из внутренней CustisWiki</p> <p><b>Новая страница</b></p><div>Класс ''DTIME(t(n))'', означает класс задач, <br /> разрешимых на [[Машина Тьюринга|машине Тьюринга]] за время ''t(n)''.<br /> <br /> Более формально:<br /> Язык &lt;amsmath&gt;L \subset \Sigma^*&lt;/amsmath&gt; принадлежит классу &lt;amsmath&gt;{\cal DTIME}(t(n))&lt;/amsmath&gt;,<br /> если существует [[машина Тьюринга]] ''T'', разрешающая данный язык, и сложность ее работы в наихудшем случае, &lt;amsmath&gt;time_{T(n)} \leq t(n)&lt;/amsmath&gt;, т.е. не превышает ''t(n)'', где ''n''-длина входного слова.<br /> <br /> [[Category:Классы сложности]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

BenderBot https://lib.custis.ru/index.php?title=DTIME&diff=9674&oldid=prev 2005-12-06T13:59:59Z

<p>{{replicate-from-custiswiki-to-lib}}</p> <table class='diff diff-contentalign-left'> <tr style='vertical-align: top;' lang='ru'> <td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 13:59, 6 декабря 2005</td> </tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div> </td></tr></table>

StasFomin