Курс по книге «Эффективные алгоритмы и сложность вычислений» - История изменений

https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9A%D1%83%D1%80%D1%81_%D0%BF%D0%BE_%D0%BA%D0%BD%D0%B8%D0%B3%D0%B5_%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%B8_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9%C2%BB Курс по книге «Эффективные алгоритмы и сложность вычислений» - История изменений 2026-05-03T06:08:18Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9A%D1%83%D1%80%D1%81_%D0%BF%D0%BE_%D0%BA%D0%BD%D0%B8%D0%B3%D0%B5_%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%B8_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9%C2%BB&diff=36018&oldid=prev StasFomin: Новая страница: «<!-- * Логинимся, и разогревочный тест проверки заданий который были в фокусе несколько не…» 2025-04-28T14:29:05Z

<p>Новая страница: «<br /> <br /> <br /> * [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]<br /> <br /> <br /> <br /> * [https://логос.испран.рф/mipt-course-03/hard-problems.svg Обзор курса]<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> Проходим квест:<br /> {{:Как зарегистрироваться на курс}}<br /> <br /> ----<br /> <poll><br /> UNSAFE_ID=aa-20250206<br /> ALTERNATIVE<br /> OPEN_RESULTS<br /> OPEN_VOTERS<br /> AUTHORIZED<br /> ALLOW_REVOTE<br /> END_POLL 2025-05-15<br /> Записываемся на курс «Сложность алгоритмов-2025»?<br /> Да<br /> Нет<br /> </poll><br /> <br /> <br /> <br /> <br />  <br /> <br /> <br /> __TOC__<br /> <br /> <br /> <br /> <br /> <br /> == Книга ==<br /> На растерзание отдается  <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 /> * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]<br /> * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]<br /> <br /> * [[Полиномиальный в среднем алгоритм для SAT]]<br /> * [[Полиномиальный в среднем алгоритм для задачи упаковки]]<br /> * [[Приближенный алгоритм для метрической задачи коммивояжера]]<br /> * [[Вероятностная проверка тождеств]]<br /> * [[MAX-SAT: вероятностное округление]]<br /> * [[MAX-CUT: вероятностное округление]]<br /> * [[MAX-SAT: дерандомизация]]<br /> * [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]<br /> <br /> * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]<br /> * [[PCP и аппроксимируемость]]<br /> * [[Полиномиальная иерархия]]<br /> * [[Схемная сложность]]<br /> <br /> На этих страницах слайды презентаций, задачи, и т.п.<br /> Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.<br /> <br /> В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.<br /> Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. <br /> <br /> <br /> ----<br /> <br /> <br /> <br /> == Тренировка ==<br /> <br /> [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.<br /> <br /> <br /> <br /> <br /> <br /> <br /> == Моделирование труднорешаемых задач ==<br /> {{:Моделирование труднорешаемых задач}}<br /> <br /> ----<br /> <br /> <br /> == Теоретические упражнения ==<br /> <br /> <br /> {{:Решаем теоретические упражнения}}<br /> <br /> <br /> <br /> ----<br /> <br /> == Бонусные квесты ==<br /> === Простые ===<br /> ==== «Ката» на Python ====<br /> {{:Ката_на_Питоне}}<br /> <br /> <br /> <br /> === Исследовательские ===<br /> ==== Разбор статей ====<br /> {{:Разбор статей}}<br /> <br /> <br /> === Для избранных ===<br /> * Обычно согласовывается с посещающими студентами, выбор некой темы, связанной и с алгоритмами, сложностью и областью научно-практических интересов студента.<br /> <br /> <br /> <br /> == Книга ==<br /> Специальная верстка для чтения с ноутбуков и КПК:<br /> * альбомная ориентация<br /> * крупные беззасечные шрифты<br /> <br /> Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).<br /> <br /> Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.<br /> <br /> [[:File:book-advanced-algorithms.pdf]]<br /> <br /> Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]<br /> <br /> <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 /> <br /> <references/></div>

StasFomin