https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9A%D1%83%D1%80%D1%81_%C2%AB%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%C2%BB Курс «Эффективные алгоритмы для труднорешаемых задач» - История изменений 2026-04-15T16:00:22Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9A%D1%83%D1%80%D1%81_%C2%AB%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%C2%BB&diff=28774&oldid=prev StasFomin в 18:34, 30 марта 2024 2024-03-30T18:34:03Z <p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 18:34, 30 марта 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l40" >Строка 40:</td> <td colspan="2" class="diff-lineno">Строка 40:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;poll&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;poll&gt;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>UNSAFE_ID=aa-<del class="diffchange diffchange-inline">20240210</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>UNSAFE_ID=aa-<ins class="diffchange diffchange-inline">20240901</ins></div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>ALTERNATIVE</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>ALTERNATIVE</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>OPEN_RESULTS</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>OPEN_RESULTS</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l47" >Строка 47:</td> <td colspan="2" class="diff-lineno">Строка 47:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>ALLOW_REVOTE</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>ALLOW_REVOTE</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>END_POLL 2024-03-15</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>END_POLL 2024-03-15</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Записываемся на курс <del class="diffchange diffchange-inline">«Сложность алгоритмов</del>-2024»?</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Записываемся на курс <ins class="diffchange diffchange-inline">«Эффективные алгоритмы (Иннополис)</ins>-2024»?</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Да</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Да</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Нет</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Нет</div></td></tr> </table> StasFomin https://discopal.ispras.ru/index.php?title=%D0%9A%D1%83%D1%80%D1%81_%C2%AB%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%C2%BB&diff=28752&oldid=prev StasFomin: /* Темы */ 2024-03-30T17:09:59Z <p>‎<span dir="auto"><span class="autocomment">Темы</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 17:09, 30 марта 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l178" >Строка 178:</td> <td colspan="2" class="diff-lineno">Строка 178:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==&#160; Темы ==</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==&#160; Темы ==</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">=== Пройдено ===</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Усвоим весь объем — вовсе нет.png|360px|right]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Файл:Усвоим весь объем — вовсе нет.png|360px|right]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Формально об алгоритмах. Вычислительные модели]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Формально об алгоритмах. Вычислительные модели]]</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l186" >Строка 186:</td> <td colspan="2" class="diff-lineno">Строка 185:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Жадный алгоритм в задачах о покрытии]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Жадный алгоритм в задачах о покрытии]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Жадный алгоритм в задаче о рюкзаке]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Жадный алгоритм в задаче о рюкзаке]]</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">=== Фокус ===</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Динамическое программирование для задачи о рюкзаке]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Динамическое программирование для задачи о рюкзаке]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l193" >Строка 193:</td> <td colspan="2" class="diff-lineno">Строка 190:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полиномиальный в среднем алгоритм для SAT]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полиномиальный в среднем алгоритм для SAT]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полиномиальный в среднем алгоритм для задачи упаковки]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Полиномиальный в среднем алгоритм для задачи упаковки]]</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">=== Не пройдено ===</del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Приближенный алгоритм для метрической задачи коммивояжера]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Приближенный алгоритм для метрической задачи коммивояжера]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностная проверка тождеств]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностная проверка тождеств]]</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l201" >Строка 201:</td> <td colspan="2" class="diff-lineno">Строка 196:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[MAX-CUT: вероятностное округление]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[MAX-CUT: вероятностное округление]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">=== Может и не будем === </del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[PCP и аппроксимируемость]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[PCP и аппроксимируемость]]</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l213" >Строка 213:</td> <td colspan="2" class="diff-lineno">Строка 206:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. &#160;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. &#160;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2">&#160;</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr> </table> StasFomin https://discopal.ispras.ru/index.php?title=%D0%9A%D1%83%D1%80%D1%81_%C2%AB%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B4%D0%BB%D1%8F_%D1%82%D1%80%D1%83%D0%B4%D0%BD%D0%BE%D1%80%D0%B5%D1%88%D0%B0%D0%B5%D0%BC%D1%8B%D1%85_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%C2%BB&diff=28751&oldid=prev StasFomin: Новая страница: «{{SideBar| {{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/11/sort=wlp_talk_updated}} |style=max-width:35% }} <!-- * Логинимся, и…» 2024-03-30T17:09:23Z <p>Новая страница: «{{SideBar| {{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/11/sort=wlp_talk_updated}} |style=max-width:35% }} &lt;!-- * Логинимся, и…»</p> <p><b>Новая страница</b></p><div>{{SideBar|<br /> {{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/11/sort=wlp_talk_updated}}<br /> |style=max-width:35%<br /> }}<br /> &lt;!--<br /> * Логинимся, и разогревочный тест проверки заданий который были в фокусе несколько недель → [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]<br /> --&gt;<br /> <br /> * [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]]<br /> <br /> &lt;!--<br /> * [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]<br /> * [[Special:MediawikiQuizzer/Python|Приветственная созвонная проверка]]<br /> --&gt;<br /> <br /> * [https://i.0x1.tv/apps/raw/s/mipt-course-03/hard-problems.svg Обзор курса]<br /> <br /> <br /> &lt;!--<br /> * [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест для экстренного набора очков]]<br /> --&gt;<br /> <br /> &lt;!--<br /> Зум-созвон, пока по четвергам, 10:00.<br /> <br /> &lt;blockquote&gt;<br /> https://ispras.zoom.us/j/6020710675?pwd=SWxUb3ZjK3NxUzhHTzJRY2Z4YmwxZz09<br /> Meeting ID: 602 071 0675<br /> Passcode: 1729<br /> &lt;/blockquote&gt;<br /> --&gt;<br /> <br /> <br /> <br /> <br /> <br /> Проходим квест:<br /> {{:Как зарегистрироваться на курс}}<br /> <br /> ----<br /> &lt;poll&gt;<br /> UNSAFE_ID=aa-20240210<br /> ALTERNATIVE<br /> OPEN_RESULTS<br /> OPEN_VOTERS<br /> AUTHORIZED<br /> ALLOW_REVOTE<br /> END_POLL 2024-03-15<br /> Записываемся на курс «Сложность алгоритмов-2024»?<br /> Да<br /> Нет<br /> &lt;/poll&gt;<br /> <br /> <br /> <br /> &lt;!--<br /> &lt;poll&gt;<br /> UNSAFE_ID=git-20220210<br /> ALTERNATIVE<br /> AUTHORIZED<br /> ALLOW_REVOTE<br /> END_POLL 2022-02-25<br /> Знаете ли вы Git?<br /> Да<br /> Нет<br /> &lt;/poll&gt;<br /> --&gt;<br /> &lt;!--<br /> * [[Special:MediawikiQuizzer/GRE-CS-v01|Сегодняшний квест]]<br /> --&gt;<br /> <br /> &lt;!-- * [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест перед экзаменом]] --&gt; <br /> &lt;!--<br /> [[Special:MediawikiQuizzer/GRE-CS-v01|Обещанный тест на повышение оценки с 15:00-15:30]]<br /> --&gt;<br /> <br /> __TOC__<br /> <br /> &lt;!-- Если кто-то еще хочет в этом семестре сдавать — [mailto:stas-fomin@yandex.ru пишите], будем договариваться.<br /> --&gt;<br /> <br /> &lt;!--<br /> &lt;poll&gt;<br /> AUTHORIZED<br /> UNSAFE ID=2019-05-21-record-for-exam<br /> REVOTE<br /> OPEN_RESULTS<br /> OPEN_VOTERS<br /> Выберите удобный день для сдачи зачета (можно несколько).<br /> 2019-05-27<br /> 2019-05-28<br /> 2019-05-29<br /> 2019-05-30<br /> 2019-05-31<br /> &lt;/poll&gt;<br /> <br /> &lt;s&gt;Хорошо, по результатам голосования встречаемся в четверг, в 11:00, 2019-05-30&lt;/s&gt;<br /> Хорошо, по результатам переголосования встречаемся в среду, в 10:00, 2019-05-29<br /> <br /> [[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.<br /> --&gt;<br /> <br /> &lt;!--<br /> &lt;poll&gt;<br /> AUTHORIZED<br /> POINTS 3<br /> UNSAFE ID=2017-05-26-record-for-exam<br /> REVOTE<br /> OPEN_RESULTS<br /> OPEN_VOTERS<br /> Какие дни утром удобны для сдачи? Можно использовать три голоса.<br /> 2017-05-30, вторник<br /> 2017-05-31, среда<br /> 2017-06-01, четверг<br /> 2017-06-02, пятница<br /> &lt;/poll&gt;<br /> --&gt;<br /> <br /> &lt;!--<br /> [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Предэкзаменационный тест]]<br /> --&gt;<br /> <br /> &lt;!-- Курс лекций «Сложность алгоритмы» для 3 курса курса МФТИ. --&gt;<br /> <br /> Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.<br /> <br /> ;Лекторы: [mailto:stas-fomin@yandex.ru Стас Фомин], <br /> <br /> <br /> &lt;!-- Место чтения курса - ИСПРАН, Станиславского 19.<br /> Солженицына, можно найти в общем, 110 аудитория. --&gt;<br /> <br /> &lt;!--<br /> * В этом году это не экзамен, а дифференцированный зачет. Почти все получили оценку&lt;ref&gt;10 мая&lt;/ref&gt; по результатам активности на семинарах и в домашних задачах. <br /> ** Пара оставшихся будет сдавать зачет Николаю Николаевичу Кузюрину, следите за обьявлениями. Ближайший прием — вторник, 29 мая, c 13:00 до 16-17, 301.<br /> ** Если кто-то недоволен оценкой — пишите, договаривайтесь о пересдаче и т.п.<br /> ** Ведомости пока не заполнены, буду заполнены и сданы по гуглтаблице где-то в июне.<br /> --&gt;<br /> <br /> &lt;!--<br /> [https://titanpad.com/discopal Интерактивная Доска]<br /> --&gt;<br /> ----<br /> <br /> Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.<br /> <br /> Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&amp;single=true&amp;gid=11&amp;output=html список посещений].<br /> <br /> &lt;blockquote&gt;<br /> В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус»,<br /> читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.<br /> &lt;/blockquote&gt;<br /> <br /> <br /> <br /> &lt;html&gt;&lt;center&gt;<br /> &lt;/p&gt;&lt;div class=&quot;sites-embed-align-left-wrapping-off&quot;&gt;&lt;div class=&quot;sites-embed-border-on sites-embed sites-embed-full-width&quot; style=&quot;width: 100%;&quot;&gt;&lt;h4 class=&quot;sites-embed-title&quot;&gt;Успеваемость зарегистрированных студентов&lt;/h4&gt;&lt;div class=&quot;sites-embed-object-title&quot; style=&quot;display: none;&quot;&gt;Эффективные алгоритмы(студенты).2007&lt;/div&gt;&lt;div class=&quot;sites-embed-content sites-embed-type-spreadsheet&quot;&gt;&lt;iframe src=&quot;https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&amp;single=true&amp;gid=11&amp;output=html&quot; id=&quot;1695919049&quot; frameborder=&quot;0&quot; height=&quot;400&quot; width=&quot;100%&quot;&gt;&lt;/iframe&gt;&lt;/div&gt;&lt;/div&gt;&lt;/div&gt;<br /> &lt;/center&gt;&lt;/html&gt;<br /> <br /> &lt;!--<br /> == Надо зарегистрироваться ==<br /> * Зарегистрироваться здесь. Залогиниться. <br /> * Зайти на страницу [http://discopal.ispras.ru/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:Preferences настроек], указать свой email и подтвердить его. Почту от mail.ru не используйте. Она ужасно проблемная (все нотификации уйдут в спам или отразятся сервисом).<br /> * На своей личной странице, написать хотя бы ФИО и группу.<br /> * На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.<br /> --&gt;<br /> <br /> == Книга ==<br /> На растерзание отдается &lt;!-- [https://www.dropbox.com/s/co3zye1k98efsfa/book-advanced-algorithms.pdf?dl=0 свежая сборка] --&gt; <br /> [[:Файл:Book-advanced-algorithms.pdf|свежая сборка]]<br /> — можно искать в ней ошибки (они 100% есть — даже орфографические).<br /> <br /> Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru.<br /> И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.<br /> <br /> === ? ===<br /> * [[https://www.math.ucdavis.edu/~greg/zoology/diagram.xml zoo]]<br /> <br /> == Темы ==<br /> === Пройдено ===<br /> [[Файл:Усвоим весь объем — вовсе нет.png|360px|right]]<br /> * [[Формально об алгоритмах. Вычислительные модели]]<br /> * [[Временная и пространственная сложность алгоритмов]]<br /> * [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]<br /> * [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]<br /> * [[Жадный алгоритм в задачах о покрытии]]<br /> * [[Жадный алгоритм в задаче о рюкзаке]]<br /> <br /> === Фокус ===<br /> * [[Динамическое программирование для задачи о рюкзаке]]<br /> * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]<br /> * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]<br /> * [[Полиномиальный в среднем алгоритм для SAT]]<br /> * [[Полиномиальный в среднем алгоритм для задачи упаковки]]<br /> <br /> === Не пройдено ===<br /> * [[Приближенный алгоритм для метрической задачи коммивояжера]]<br /> * [[Вероятностная проверка тождеств]]<br /> * [[MAX-SAT: вероятностное округление]]<br /> * [[MAX-SAT: дерандомизация]]<br /> * [[MAX-CUT: вероятностное округление]]<br /> * [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]<br /> <br /> === Может и не будем === <br /> * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]<br /> * [[PCP и аппроксимируемость]]<br /> * [[Полиномиальная иерархия]]<br /> * [[Схемная сложность]]<br /> <br /> На этих страницах слайды презентаций, задачи, и т.п.<br /> Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.<br /> <br /> В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.<br /> Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. <br /> <br /> <br /> ----<br /> <br /> &lt;!--<br /> * [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]<br /> --&gt;<br /> <br /> == Тренировка ==<br /> <br /> [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.<br /> <br /> == Практика ==<br /> {{:Практикуемся В Алгоритмах}}<br /> <br /> == Моделирование труднорешаемых задач ==<br /> {{:Моделирование труднорешаемых задач}}<br /> <br /> ----<br /> Кому надо 10-баллов — запишите видеоролики по вашим питон-ноутбукам, см. [[Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики]]<br /> <br /> == Теоретические упражнения ==<br /> Достаточно 3 задач из двух тем.<br /> <br /> {{:Решаем теоретические упражнения}}<br /> <br /> &lt;!--<br /> Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).<br /> Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.<br /> <br /> Эти задачи заводим в<br /> [[:Category:Предложенные студентами задачи]]<br /> --&gt;<br /> <br /> ----<br /> <br /> <br /> <br /> &lt;!--<br /> * Дискретный логарифм<br /> ** Почему ДЛ обратим в среднем так же плохо, как в худшем.<br /> * Начала криптографии (односторонние функции)<br /> ** Протокол диффи-хелмана<br /> --&gt;<br /> <br /> == Книга ==<br /> Специальная верстка для чтения с ноутбуков и КПК:<br /> * альбомная ориентация<br /> * крупные беззасечные шрифты<br /> <br /> Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).<br /> <br /> Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.<br /> <br /> [[:File:book-advanced-algorithms.pdf]]<br /> <br /> Смешное — [https://vk.com/im?sel=1712504&amp;w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]<br /> <br /> == Примечания и ссылки ==<br /> <br /> * Рекомендуем изучить Python. Ресурсов миллиарды, вот, например, хотя бы [http://ru.wikiversity.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B8_%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_Python лекции], а еще лучше — [http://pythontutor.ru интерактивный учебник].<br /> <br /> == Полезная сопутствующая литература по курсу. ==<br /> <br /> {{:Дополнительные_материалы_по_сложности_вычислений}} <br /> {{:Дополнительные материалы по приближенным алгоритмам}} <br /> ----<br /> {{:Библиотека}}<br /> <br /> <br /> &lt;references/&gt;</div> StasFomin