https://wiki.cs.hse.ru/index.php?action=history&feed=atom&title=Theoretical_computer_science_spring_2023 2026-09-21T12:38:24Z История изменений этой страницы в вики MediaWiki 1.43.9 https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77867&oldid=prev 2023-04-26T14:59:26Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:59, 26 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37">Строка 37:</td> <td colspan="2" class="diff-lineno">Строка 37:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] || <ins style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/f3t6ob6fuvi9fhe/9_HW.pdf?dl=0 hw9]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77865&oldid=prev 2023-04-26T14:39:34Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:39, 26 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37">Строка 37:</td> <td colspan="2" class="diff-lineno">Строка 37:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0<del style="font-weight: bold; text-decoration: none;">] </del>reductions] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77864&oldid=prev 2023-04-26T14:39:13Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:39, 26 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37">Строка 37:</td> <td colspan="2" class="diff-lineno">Строка 37:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0<ins style="font-weight: bold; text-decoration: none;">] </ins>reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.</div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77762&oldid=prev 2023-04-21T15:08:39Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 15:08, 21 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l39">Строка 39:</td> <td colspan="2" class="diff-lineno">Строка 39:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 <del style="font-weight: bold; text-decoration: none;">theory</del>] <del style="font-weight: bold; text-decoration: none;">The problem exam has about </del>4 exercises <del style="font-weight: bold; text-decoration: none;">like </del>the homework, including 1 <del style="font-weight: bold; text-decoration: none;">task to prove </del>NP-completeness.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 <ins style="font-weight: bold; text-decoration: none;">Theory questions.</ins>] <ins style="font-weight: bold; text-decoration: none;">Also solve </ins>4 exercises <ins style="font-weight: bold; text-decoration: none;">as in </ins>the homework, including 1 NP-completeness <ins style="font-weight: bold; text-decoration: none;">proof</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77761&oldid=prev 2023-04-21T15:00:58Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 15:00, 21 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l39">Строка 39:</td> <td colspan="2" class="diff-lineno">Строка 39:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 theory]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 theory] <ins style="font-weight: bold; text-decoration: none;">The problem exam has about 4 exercises like the homework, including 1 task to prove NP-completeness.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77760&oldid=prev 2023-04-21T14:58:27Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:58, 21 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l31">Строка 31:</td> <td colspan="2" class="diff-lineno">Строка 31:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 23.03 || Invariants (Chapt 5). Undecidability || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A]  || [https://www.dropbox.com/s/17ogtcftqh7ybzo/5_HW.pdf?dl=0 hw5]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 23.03 || Invariants (Chapt 5). Undecidability || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A]  || [https://www.dropbox.com/s/17ogtcftqh7ybzo/5_HW.pdf?dl=0 hw5]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] || <ins style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/5r16xyv2q65dt4m/6_HW.pdf?dl=0 hw6]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 12.04 || (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE. Time and space hierarchy theorems.  ||  See Sipser chapts 7 and 8 ||  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 12.04 || (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE. Time and space hierarchy theorems.  ||  See Sipser chapts 7 and 8 || <ins style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/t25x38vop05xnlu/7_HW.pdf?dl=0 hw7]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77759&oldid=prev 2023-04-21T14:54:30Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 14:54, 21 апреля 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l33">Строка 33:</td> <td colspan="2" class="diff-lineno">Строка 33:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 12.04 || (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE <del style="font-weight: bold; text-decoration: none;">and NP</del>. Time and space hierarchy theorems. <del style="font-weight: bold; text-decoration: none;">NP-completeness, </del>|| <del style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] </del> ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 12.04 || (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE. Time and space hierarchy theorems. <ins style="font-weight: bold; text-decoration: none;"> </ins>||  <ins style="font-weight: bold; text-decoration: none;">See Sipser chapts 7 and 8 </ins>||  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>|| 19.04 || <del style="font-weight: bold; text-decoration: none;">circuits</del>, <del style="font-weight: bold; text-decoration: none;">proof of the Levin</del>-<del style="font-weight: bold; text-decoration: none;">Cook theorem (see Mertens&amp;Moore chapter 5)  </del>|| [https://www.dropbox.com/s/<del style="font-weight: bold; text-decoration: none;">nen161dakmq3646</del>/<del style="font-weight: bold; text-decoration: none;">circuits</del>.pdf?dl=0 <del style="font-weight: bold; text-decoration: none;">circuits</del>] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>|| 19.04 || <ins style="font-weight: bold; text-decoration: none;">The class NP</ins>, <ins style="font-weight: bold; text-decoration: none;">NP</ins>-<ins style="font-weight: bold; text-decoration: none;">completeness, reduction from SAT to IND-SET </ins>|| [https://www.dropbox.com/s/<ins style="font-weight: bold; text-decoration: none;">90m0yxt62f02mmm</ins>/<ins style="font-weight: bold; text-decoration: none;">classNP</ins>.pdf?dl=0 <ins style="font-weight: bold; text-decoration: none;">notes</ins>] || <ins style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>|| 26.04 || Reductions. <del style="font-weight: bold; text-decoration: none;">The classes RP, coRP and BPP, primes in BPP </del>||[https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>|| 26.04 || Reductions. <ins style="font-weight: bold; text-decoration: none;">Proof of the Levin-Cook theorem. </ins>||<ins style="font-weight: bold; text-decoration: none;">[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]</ins>[https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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 style="font-weight: bold; text-decoration: none;"> </del>|| Exam <del style="font-weight: bold; text-decoration: none;"> </del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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;">17.05 </ins>|| Exam<ins style="font-weight: bold; text-decoration: none;">. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 theory]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|}</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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;"><br></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77287&oldid=prev 2023-03-29T15:12:45Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 15:12, 29 марта 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l33">Строка 33:</td> <td colspan="2" class="diff-lineno">Строка 33:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 12.04 || The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. NP-completeness, || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]  ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 12.04 || <ins style="font-weight: bold; text-decoration: none;">(online, in zoom) </ins>The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. NP-completeness, || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]  ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || circuits, proof of the Levin-Cook theorem (see Mertens&amp;Moore chapter 5)  || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || circuits, proof of the Levin-Cook theorem (see Mertens&amp;Moore chapter 5)  || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] ||</div></td></tr> </table>

Bbauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77215&oldid=prev 2023-03-24T15:52:15Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 15:52, 24 марта 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l29">Строка 29:</td> <td colspan="2" class="diff-lineno">Строка 29:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 16.03 || Recursion and induction. (Chapt 3 of discrete math book.) Turing machines. ||  || [https://www.dropbox.com/s/ee0kaxd8wrr5k7b/4_HW.pdf?dl=0 hw4]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 16.03 || Recursion and induction. (Chapt 3 of discrete math book.) Turing machines. ||  || [https://www.dropbox.com/s/ee0kaxd8wrr5k7b/4_HW.pdf?dl=0 hw4]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>  || 23.03 || Invariants (Chapt 5). Undecidability || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A]  || [https://www.dropbox.com/s/17ogtcftqh7ybzo/5_HW.pdf?dl=0 hw5]<del style="font-weight: bold; text-decoration: none;">||</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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>  || 23.03 || Invariants (Chapt 5). Undecidability || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A]  || [https://www.dropbox.com/s/17ogtcftqh7ybzo/5_HW.pdf?dl=0 hw5]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>  || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] ||</div></td></tr> </table>

Bbauwens https://wiki.cs.hse.ru/index.php?title=Theoretical_computer_science_spring_2023&diff=77214&oldid=prev 2023-03-24T15:51:46Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 15:51, 24 марта 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36">Строка 36:</td> <td colspan="2" class="diff-lineno">Строка 36:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || circuits, proof of the Levin-Cook theorem (see Mertens&amp;Moore chapter 5)  || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 19.04 || circuits, proof of the Levin-Cook theorem (see Mertens&amp;Moore chapter 5)  || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] ||</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; 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>-  </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; 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 class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. The classes RP, coRP and BPP, primes in BPP ||[https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|| 26.04 || Reductions. The classes RP, coRP and BPP, primes in BPP ||[https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; 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>|-  </div></td></tr> </table>

Bbauwens