https://wiki.cs.hse.ru/index.php?action=history&feed=atom&title=Theory_of_Computation_2024 2026-09-21T06:34:01Z История изменений этой страницы в вики MediaWiki 1.43.9 https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=92939&oldid=prev 2025-10-08T16:37:00Z

<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;">Версия от 16:37, 8 октября 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l49">Строка 49:</td> <td colspan="2" class="diff-lineno">Строка 49:</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>  || [https://www.youtube.com/watch?v=VR_A62kFXH8 02.10] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness.  || [https://drive.google.com/file/d/1SJq-s80aGYKBEtF84fz6pMYQM2ZE1UyA/view?usp=sharing problem list 3]</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>  || [https://www.youtube.com/watch?v=VR_A62kFXH8 02.10] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness.  || [https://drive.google.com/file/d/1SJq-s80aGYKBEtF84fz6pMYQM2ZE1UyA/view?usp=sharing problem list 3]</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>  || [https://www.youtube.com/watch?v=sGfulQ1YoUU 10.10] ||  NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&amp;dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/1KtVCvyhO99T5cU_jYLG62Zwnqj5aDCor/view?usp=sharing problem list 4]</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>  || [https://www.youtube.com/watch?v=sGfulQ1YoUU 10.10] ||  NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. <ins style="font-weight: bold; text-decoration: none;">[</ins>https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&amp;dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/1KtVCvyhO99T5cU_jYLG62Zwnqj5aDCor/view?usp=sharing problem list 4]</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>  || [https://www.youtube.com/watch?v=Jqy89FPbFj4 17.10] || Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete.  [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&amp;dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/15uGUYwI2GfNaEi0upjgjCqmclrWUk75c/view?usp=sharing problem list 5]</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>  || [https://www.youtube.com/watch?v=Jqy89FPbFj4 17.10] || Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete.  [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&amp;dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/15uGUYwI2GfNaEi0upjgjCqmclrWUk75c/view?usp=sharing problem list 5]</div></td></tr> </table>

Brbauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90279&oldid=prev 2025-03-23T20:32:21Z

<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;">Версия от 20:32, 23 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l82">Строка 82:</td> <td colspan="2" class="diff-lineno">Строка 82:</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>  || [https://youtube.com/live/TBX8sWx7nO0 12.03] || Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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>  || [https://youtube.com/live/TBX8sWx7nO0 12.03] || Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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.03 || Optional: problems that are FPT on graphs with small treewidth.|| [https://drive.google.com/file/d/1mYkshv6q-c_5nY5qfHgosKxBd1zDDvGK/view?usp=sharing problem list 14]</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.03 || Optional: problems that are FPT on graphs with small treewidth.<ins style="font-weight: bold; text-decoration: none;">(No recording, sorry.) </ins>|| [https://drive.google.com/file/d/1mYkshv6q-c_5nY5qfHgosKxBd1zDDvGK/view?usp=sharing problem list 14]</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=Theory_of_Computation_2024&diff=90278&oldid=prev 2025-03-23T20:31:05Z

<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;">Версия от 20:31, 23 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l80">Строка 80:</td> <td colspan="2" class="diff-lineno">Строка 80:</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>&#039;&#039;Update 03.12&#039;&#039;</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>&#039;&#039;Update 03.12&#039;&#039;</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.03 || Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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;">[https://youtube.com/live/TBX8sWx7nO0 </ins>12.03<ins style="font-weight: bold; text-decoration: none;">] </ins>|| Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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.03 || Optional: problems that are FPT on graphs with small treewidth.|| [https://drive.google.com/file/d/1mYkshv6q-c_5nY5qfHgosKxBd1zDDvGK/view?usp=sharing problem list 14]</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.03 || Optional: problems that are FPT on graphs with small treewidth.|| [https://drive.google.com/file/d/1mYkshv6q-c_5nY5qfHgosKxBd1zDDvGK/view?usp=sharing problem list 14]</div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90248&oldid=prev 2025-03-19T16: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;">Версия от 16:59, 19 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l82">Строка 82:</td> <td colspan="2" class="diff-lineno">Строка 82:</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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming. Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  || [https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13]  </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.03 || Optional: problems that are FPT on graphs with small treewidth.||  </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.03 || Optional: problems that are FPT on graphs with small treewidth.|| <ins style="font-weight: bold; text-decoration: none;">[https://drive.google.com/file/d/1mYkshv6q-c_5nY5qfHgosKxBd1zDDvGK/view?usp=sharing problem list 14]</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=Theory_of_Computation_2024&diff=90139&oldid=prev 2025-03-12T16:06:00Z

<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;">Версия от 16:06, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l80">Строка 80:</td> <td colspan="2" class="diff-lineno">Строка 80:</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>&#039;&#039;Update 03.12&#039;&#039;</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>&#039;&#039;Update 03.12&#039;&#039;</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.03 || Linear programming kernel for VC, color coding, dynamic programming <del style="font-weight: bold; text-decoration: none;">(iterated compression)</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.03 || Linear programming kernel for VC, color coding, dynamic programming. <ins style="font-weight: bold; text-decoration: none;">Colorcoding [https://drive.google.com/file/d/1RMoIpd6p_L1XXOVeV36g0pdJdbtltbPF/view?usp=sharing from slide 39]  </ins>|| <ins style="font-weight: bold; text-decoration: none;">[https://drive.google.com/file/d/16wjIGqbS5UvEUZCxuUfGROUxk2RlLqZl/view?usp=sharing problem list 13] </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.03 || Optional: problems that are FPT on graphs with small treewidth.||  </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.03 || Optional: problems that are FPT on graphs with small treewidth.||  </div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90135&oldid=prev 2025-03-12T12:50:25Z

<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;">Версия от 12:50, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l78">Строка 78:</td> <td colspan="2" class="diff-lineno">Строка 78:</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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]  </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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]  </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>''Update <del style="font-weight: bold; text-decoration: none;">02</del>.<del style="font-weight: bold; text-decoration: none;">10</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>''Update <ins style="font-weight: bold; text-decoration: none;">03</ins>.<ins style="font-weight: bold; text-decoration: none;">12</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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90134&oldid=prev 2025-03-12T12:49:57Z

<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;">Версия от 12:49, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l77">Строка 77:</td> <td colspan="2" class="diff-lineno">Строка 77:</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12] ''Update 02.10''</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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]  </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></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>''Update 02.10''</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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90133&oldid=prev 2025-03-12T12:49:23Z

<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;">Версия от 12:49, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l77">Строка 77:</td> <td colspan="2" class="diff-lineno">Строка 77:</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]</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>  || [https://youtube.com/live/xDaTpuVF0Es 05.03] || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12] <ins style="font-weight: bold; text-decoration: none;">''Update 02.10''</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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </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>  || 12.03 || Linear programming kernel for VC, color coding, dynamic programming (iterated compression). ||  </div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90131&oldid=prev 2025-03-12T08:49:03Z

<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;">Версия от 08:49, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l64">Строка 64:</td> <td colspan="2" class="diff-lineno">Строка 64:</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>  || [https://youtube.com/live/r9rP3ZojeqY 27.11] || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover.  [https://drive.google.com/file/d/1W9SU24HW0r5QhugzmrghpkzJUFuC8whq/view?usp=sharing Notes.] || [https://drive.google.com/file/d/1PpRK72BtyKYR0KVi03HDCy7HXvWpzcL6/view?usp=sharing problem list 10] &lt;!-- [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] --&gt;</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>  || [https://youtube.com/live/r9rP3ZojeqY 27.11] || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover.  [https://drive.google.com/file/d/1W9SU24HW0r5QhugzmrghpkzJUFuC8whq/view?usp=sharing Notes.] || [https://drive.google.com/file/d/1PpRK72BtyKYR0KVi03HDCy7HXvWpzcL6/view?usp=sharing problem list 10] &lt;!-- [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] --&gt;</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>  || 04.12 || Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. [https://drive.google.com/file/d/1f-085Gr7E01HepUR-brGJDet-fXJzUwb/view?usp=sharing presentation] [https://drive.google.com/file/d/1OIw7h31N2tt-npC0NrvVgNhYGw_HlJa_/view?usp=sharing Notes] || [https://drive.google.com/file/d/1xhUYMsj0iV2TMZfR8FtkxWUNlcCjdS-N/view?usp=sharing problem list 11] ''Update 05.12''</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;">[https://youtube.com/live/E4aNlvbYoLQ </ins>04.12<ins style="font-weight: bold; text-decoration: none;">] </ins>|| Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. [https://drive.google.com/file/d/1f-085Gr7E01HepUR-brGJDet-fXJzUwb/view?usp=sharing presentation] [https://drive.google.com/file/d/1OIw7h31N2tt-npC0NrvVgNhYGw_HlJa_/view?usp=sharing Notes] || [https://drive.google.com/file/d/1xhUYMsj0iV2TMZfR8FtkxWUNlcCjdS-N/view?usp=sharing problem list 11] ''Update 05.12''</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>  || 11.12 || &#039;&#039;Colloquium.&#039;&#039; [https://drive.google.com/file/d/1no8CbHKJluGRx7FROpSS7BqXdjOVgdT1/view?usp=sharing Rules and questions.] Version Dec 8th. [https://docs.google.com/spreadsheets/d/10zH6TVcdXWrecW8jcl57MIIq-a_Osk3-bKtPXzQIzA0/edit?usp=sharing Shedule.] || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]  </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>  || 11.12 || &#039;&#039;Colloquium.&#039;&#039; [https://drive.google.com/file/d/1no8CbHKJluGRx7FROpSS7BqXdjOVgdT1/view?usp=sharing Rules and questions.] Version Dec 8th. [https://docs.google.com/spreadsheets/d/10zH6TVcdXWrecW8jcl57MIIq-a_Osk3-bKtPXzQIzA0/edit?usp=sharing Shedule.] || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]  </div></td></tr> </table>

Bauwens https://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&diff=90130&oldid=prev 2025-03-12T08:46:54Z

<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;">Версия от 08:46, 12 марта 2025</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l77">Строка 77:</td> <td colspan="2" class="diff-lineno">Строка 77:</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>!  Date !! Software engineering: parameterized complexity, FPT algorithms !! Problem list</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>  || 05.03 || Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]</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;">[https://youtube.com/live/xDaTpuVF0Es </ins>05.03<ins style="font-weight: bold; text-decoration: none;">] </ins>|| Recap from last lecture. More examples of kernels: linear programming kernel for vertex cover problem.  [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&amp;dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].|| [https://drive.google.com/file/d/1sXA5F4gUZ-KvigQspz0ScVLOA38ZcxHb/view?usp=sharing problem list 12]</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.03 || Linear programming kernel for VC, color coding, iterated compression<del style="font-weight: bold; text-decoration: none;">, dynamic programming</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.03 || Linear programming kernel for VC, color coding, <ins style="font-weight: bold; text-decoration: none;">dynamic programming (</ins>iterated compression<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>|-</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.03 || Optional: problems that are FPT on graphs with small treewidth.||  </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.03 || Optional: problems that are FPT on graphs with small treewidth.||  </div></td></tr> </table>

Bauwens