Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)

Ссылки сюда (11) →

Короткая ссылка: Course-3y-ispras

Подстраницы (3) →

• 2023-03-06: Feedback ← Advanced Algorithms
• 2023-03-02: Feedback ← Advanced Algorithms
• 2023-02-19: Жадные алгоритмы, Python, Leetcode, система визуализации алгоритмов — начинаем «в алгоритмы» ← Advanced Algorithms
• 2023-02-09: Вводное знакомство ← Advanced Algorithms
• 2022-12-22: Хорошие практики компактных Pyomo-формулировок на примере решения «Производство подразделяемых задач» ← Advanced Algorithms
• 2022-12-19: Разбор задачи «Хранилище артефактов» ← Advanced Algorithms
• 2022-12-11: Feedback ← Advanced Algorithms
• 2022-12-06: «Воспроизведение статей» — на отл. ← Advanced Algorithms
• 2022-12-05: Разбор оптимизационной задачи «Группировка людей» ← Advanced Algorithms
• 2022-12-05: Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках» ← Advanced Algorithms
• 2022-12-05: Задача о двух кучах камней и примеры использования различных ЦЛП-солверов ← Advanced Algorithms

• Логинимся, и разогревочный тест проверки заданий который были в фокусе 5 недель → Cозвонный тест

Проходим квест:

• Зарегистрироваться здесь. Залогинится.
• Зайти на страницу настроек, указать свой email и подтвердить его.
• На своей личной странице (это не страница настроек, это то, что сверху слева, с иконкой человечка), написать хотя бы ФИО и группу.
  • Боже, как много народу с рассеянным вниманием уже до сюда не дочитывает.
• Присоединится к телеграмм-группе.
• Отметится в этом голосовании:

---

Записываемся на курс «Сложность алгоритмов-2023»?

Да 20 100% Abel1502, Artklyachin, Belodedovts, Belov, Bruks, Da karakum, DamirShodiev, DmitryTeterin, Evtushenko.ds, Filippenkops, Iamkrendel, Ilya, JulesIMF, Krym4s, Loochek, Panterrich, Riggertt, StasFomin, TrunaevSA, Анна Савчук Нет 0 0%

Вы должны войти в систему, чтобы участвовать в этом голосовании.

Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.

Лекторы

Стас Фомин,

---

Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.

Ведется список посещений.

В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус», читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.

Успеваемость зарегистрированных студентов

Эффективные алгоритмы(студенты).2007

Книга

На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).

Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.

?

• [zoo]

Темы

Пройдено

• Формально об алгоритмах. Вычислительные модели
• Временная и пространственная сложность алгоритмов

Фокус

• Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
• Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
• Жадный алгоритм в задачах о покрытии
• Жадный алгоритм в задаче о рюкзаке
• Динамическое программирование для задачи о рюкзаке
• Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
• Полиномиальный в среднем алгоритм для задачи о рюкзаке

Не пройдено

• Полиномиальный в среднем алгоритм для SAT
• Полиномиальный в среднем алгоритм для задачи упаковки
• Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема
• PCP и аппроксимируемость
• Вероятностная проверка тождеств
• MAX-SAT: вероятностное округление
• MAX-SAT: дерандомизация
• MAX-CUT: вероятностное округление

На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.

В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.

https://cs9.pikabu.ru/post_img/2020/07/10/7/1594377617181633223.webp

• Полиномиальная иерархия
• Схемная сложность

---

Тренировка

Проверь себя, помнишь ли элементарные понятия и факты из курса.

Теоретические задачи

Все статьи в этой категории — задачи, которые можно пытаться решать.

• Category:Нерешенные задачи. Осталось 23 нерешенных задач.

Решать надо создавая для решения подстраницу личной страницы, и ссылаясь в решении на задачу.

Пример

Задача Вероятностная_проверка_тождеств/Задачи/determinant → Решение Участник:StasFomin/Задача determinant.

Cтатьи-решения задач помечать вставляя строку

[[Category:На проверку]]

и подписываться на изменения («watch this page»).

Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:

• Category:Решенные задачи.

Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.

Т.е. очередь решений на проверку → Category:На проверку (там сейчас 7 задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).

Все статьи в этой категории — задачи, которые можно пытаться решать.

• Category:Нерешенные задачи.

Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:

• Category:Решенные задачи — кстати, полезно смотреть чужие решения.

Cтатьи-решения задач помечать вставляя строку в текст

[[Category:На проверку]]

(ну или «На проверку» в поле формы «Категории») и подписываться на изменения («watch this page»).

Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.

Т.е. очередь решений на проверку → Category:На проверку, проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).

Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.

Эти задачи заводим в Category:Предложенные студентами задачи

---

Практика

Концептуально:

• Win-Win!
• Абсолютно практические задачи с собеседований.
  • LeetCode
  • CodeChef
  • SpojCode
  • Сотни решенных и нерешенных
• Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
• Нужно быть залогиненным
  • Скрыто из интернета
• Изучайте Решенные практические задачи (Их там 721)
• Надо решить 8 задач из 4 разных разделов. На Python.
• За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (+3 очка)
• 10 очков — улучшение оценки на балл.

• Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

• • помечайте их как {{reserve-task|~~~~~}}
• Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 19)

• • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
• Решенное
  • Ну смотрите, как оформлено в прошлые годы
  • Решение на подстранице вашей личной страницы
    • Вики-ссылка на задачу
    • Python-код в «<source lang="python"></source>»
    • Метка «{{checkme}}», когда решите.

• • • Внизу вставка всего этого по клику →
• Они попадут в Категория:На проверку

(Их там 7)

• Как легче решать Python
  • Загрузка данных
  • Выбирайте более свежий CPython или PyPy.

Книга

Специальная верстка для чтения с ноутбуков и КПК:

• альбомная ориентация
• крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

File:book-advanced-algorithms.pdf

Смешное — реакция «обычных программистов»

Видео

Update

Можно не смотреть, технология многопоточных MKV-перестала работать, будет новое видео, небольшими блоками.

Записанное видео лекций Николая Николаевича Кузюрина и Стаса Фомина, за весенний семестр 2013 года.

• Как смотреть многопоточное MKV-видео

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv^1:23:15 — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv^2:12:00 — временная и пространственная сложность алгоритмов.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv^2:36:30 — NP-полнота и сводимости.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv^0:00:22 — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv^1:19:30 — метрическая задача коммивояжера, алгоритм Кристофидеса.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv^0:03:31 — вероятностная проверка тождеств.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv^0:37:40 — вероятностное округление для MAX-SAT

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv^0:03:59 — криптография, 4 курс

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv^0:01:10 — Дерандомизация MAX-SAT

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv^0:55:40 — Вероятностные классы сложности сложности RP/ZPP.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv^2:02:34 — Вероятностные классы сложности BPP

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv^0:00:20 — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv^0:00:30 — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv^0:01:12 — BPP, полиномиальная иерархия, схемная сложность.

Примечания и ссылки

• Рекомендуем изучить Python. Ресурсов миллиарды, вот, например,
• Рекомендуется прочитать хотя бы лекции, а еще лучше — интерактивный учебник.

Полезная сопутствующая литература по курсу.

• Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
• Более краткий курс по классической теории сложности, университет Technion.
• Еще один классический курс лекций по теории сложности от László Lovász.
• А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.
• Лекции Сложность вычислений (3 курс, осень 2019) - лектор -- Мусатов Д.В.

---

[ Хронологический вид ]Комментарии

Здесь можно писать вопросы к курсу

— Стас Фомин • 27 марта 2014 в 09:32

• страница

Войдите, чтобы комментировать.