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

Материал из DISCOPAL
Перейти к: навигация, поиск

Зум-созвон, пока по четвергам, 10:00.

https://ispras.zoom.us/j/6020710675?pwd=SWxUb3ZjK3NxUzhHTzJRY2Z4YmwxZz09

Meeting ID: 602 071 0675 Passcode: 1729


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

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

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

Да22
100%
AlbatraozRUS, Aleksei Volkov, Artem Dashkevich, Ddergachev01, Dimikson, Egorkincbl, ExesaLigno, Fckxorg, Geome try, Greezzee, Hakob, Konon454, Nechda, Ouvt02, Shishqa, Shugaley, Solovev, StasFomin, Sukhanovskiinl, TieBeTie, Виктор, Макарчук Алексей
Нет0
0%

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

Знаете ли вы Python?

  1. Да
  2. Нет

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

Знаете ли вы Jupyter-ноутбуки?

  1. Да
  2. Нет

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






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

Лекторы
Стас Фомин, [Иван Тунев]




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

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

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


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


Книга

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

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

?

Темы

Пройдено

Фокус

Не пройдено

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

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

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



Тренировка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Практика

2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

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

  • Win-Win!
  • Абсолютно практические задачи с собеседований.
    • LeetCode
    • CodeChef
    • SpojCode
    • Сотни решенных и нерешенных
  • Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
  • Нужно быть залогиненным
    • Скрыто из интернета
  • Изучайте Решенные практические задачи (Их там 558)
  • Надо решить 4 задачи из разных разделов. На Python.
    • Или взять бонусную задачу — «отл» автоматом.
2021-10-15 Practical Block 2021-11-03 15-02-30 image0.png

2021-10-15 Practical Block 2021-11-03 14-24-09 image0.png

(Их там 17)

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

(Их там 1)


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


Книга

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

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

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

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

File:book-advanced-algorithms.pdf

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

Видео

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

  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv1:23:15 — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:12:00 — временная и пространственная сложность алгоритмов.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:36:30 — NP-полнота и сводимости.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv0:00:22 — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv1:19:30 — метрическая задача коммивояжера, алгоритм Кристофидеса.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:03:31 — вероятностная проверка тождеств.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:37:40 — вероятностное округление для MAX-SAT


  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv0:03:59 — криптография, 4 курс
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:01:10 — Дерандомизация MAX-SAT
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:55:40 — Вероятностные классы сложности сложности RP/ZPP.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv2:02:34 — Вероятностные классы сложности BPP


  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv0:00:20 — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv0:00:30 — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv0:01:12 — BPP, полиномиальная иерархия, схемная сложность.

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

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




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

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

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