Курс «Эффективные алгоритмы» для МФТИ — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показаны 263 промежуточные версии 11 участников)
Строка 1: Строка 1:
 +
__FORCETOC__
 +
 
{{SideBar|
 
{{SideBar|
−
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/3/sort=wlp_talk_updated}}
+
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/12/sort=wlp_talk_updated}}
 
|style=max-width:35%
 
|style=max-width:35%
 
}}
 
}}
−
 
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
 
Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
  
−
Семестровый курс по выбору<ref>К экзамену допускаются только студенты, зарегистрировавшиеся до декабря [mailto:stas-fomin@yandex.ru email].</ref>
+
* [https://логос.испран.рф/mipt-course-03/hard-problems.svg Темы-цели курса]
−
для студентов 6-го курса ФУПМ МФТИ.
+
* [https://алгоритмы.испран.рф/public/course-effg.drawio.svg Путь прохождения]
−
 
+
* [https://0x1.tv/Fcromt Методологический подход] (кому интересно почему так, а не иначе).
−
 
+
* [[Blog:Advanced_Algorithms/2024-09-08_Презентация_курса_«на_осень_2024»|Прошлогодняя презентация курса]]
−
;Лекторы: д.ф.-м.н. [mailto:nnkuz@ispras.ru Н.Н. Кузюрин], [mailto:stas-fomin@yandex.ru С.А. Фомин]
+
−
 
+
−
В 2012 году, курс проходит дистанционно.
+
−
 
+
−
Желающим посещать курс, надо зарегистрироваться:
+
−
* Зарегистрироваться на http://discopal.ispras.ru
+
−
* Прислать email/выбранный логин на http://discopal.ispras.ru/Skype-логин → [mailto:stas-fomin@yandex.ru Стасу Фомину]
+
−
* Проверить, что появились в списке (см. ниже).
+
−
 
+
−
 
+
−
<!-- * [[Календарь_лекций]] -->
+
−
 
+
−
<html><center>
+
−
</p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZElcGVLNjEtY3lfOHhmVHZPdGJZOXI3WHc&single=true&gid=9&output=html" id="1695919049" frameborder="0" height="800" width="100%"></iframe></div></div></div>
+
−
</center></html>
+
−
 
+
−
В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса.
+
−
В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.
+
−
 
+
−
Если вы в зеленой группе — вы кандидат на «отлично автоматом».
+
−
 
+
−
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
+
−
 
+
−
 
+
−
 
+
−
 
+
−
= Тренировка =
+
−
 
+
−
[[Special:MediawikiQuizzer/Эффективные алгоритмы|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
+
−
Тест будет на экзамене, чтобы отсеять совсем невменяемых.
+
−
 
+
−
= Задачи =
+
−
Все статьи в этой категории — задачи, которые можно пытаться решать.
+
−
* [[:Category:Нерешенные задачи]].
+
−
Любая активность, даже попытки решения  — хорошо.
+
−
После того, как задача решена, она перейдет в архив:
+
−
* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения.
+
−
 
+
−
Т.е. в некотором смысле задачи одноразовые, посмотрим, сможем ли мы обеспечить достаточное количество задач.
+
−
<blockquote>
+
−
Увы, не смогли. Поэтому идем на жертвы — задачи можно решать повторно, если вы в текущий момент не видите открытого решения к задаче (т.е. уже проверено и скрыто).
+
−
</blockquote>
+
−
 
+
−
Cтатьи-решения задач помечать вставляя строку
+
−
+
−
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
+
−
и подписываться на изменения («watch this page»).
+
−
 
+
−
Проверенное решение перейдет в [[:Category:Решения]] или,
+
−
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
+
−
 
+
−
Т.е. очередь решений на проверку → [[:Category:На проверку]], проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
+
−
 
+
−
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
+
−
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
+
−
 
+
−
Эти задачи заводим в
+
−
[[:Category:Предложенные студентами задачи]]
+
−
 
+
−
 
+
−
 
+
−
 
+
−
= Лекции =
+
−
* [[/Лекции осеннего семестра 2011]]
+
−
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
+
−
 
+
−
* [[/Лекции осеннего семестра 2012]]
+
  
−
= Темы =
+
----
  
−
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
+
Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [{{active-telegram-group-link}} группе].
  
−
* [[Несложно о сложности. Примеры алгоритмов]]
+
;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]
−
* [[Формально об алгоритмах. Вычислительные модели]]
+
−
* [[Временная и пространственная сложность алгоритмов]]
+
−
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
+
−
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
+
−
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
+
−
* [[PCP и аппроксимируемость]]
+
−
* [[Жадный алгоритм в задачах о покрытии]]
+
−
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
+
−
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
+
−
* [[Жадный алгоритм в задаче о рюкзаке]]
+
−
* [[Динамическое программирование для задачи о рюкзаке]]
+
−
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
+
−
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
+
−
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
+
−
* [[Полиномиальный в среднем алгоритм для SAT]]
+
−
* [[Вероятностная проверка тождеств]]
+
−
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
+
−
* [[MAX-SAT: вероятностное округление]]
+
−
* [[MAX-SAT: дерандомизация]]
+
−
<!-- {:Дерандомизация Люби} -->
+
−
* [[MAX-CUT: вероятностное округление]]
+
−
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]
+
  
−
== Книга ==
+
Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 +
{{:Как зарегистрироваться на курс}}
  
−
Специальная верстка для чтения с ноутбуков и КПК:
 
−
* альбомная ориентация
 
−
* крупные беззасечные шрифты
 
  
−
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
+
<poll>
 +
UNSAFE_ID=aa-20250901
 +
ALTERNATIVE
 +
OPEN_RESULTS
 +
OPEN_VOTERS
 +
AUTHORIZED
 +
ALLOW_REVOTE
 +
END_POLL 2025-10-30
 +
Записываемся на курс «Advanced Algorithms-2025»?
 +
Да
 +
Нет
 +
</poll>
 +
* Первое установочное занятие будет 4 сентября, в 18-30 в 903 КПМ
  
−
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
+
Материалы:
 +
* [[:Файл:book-advanced-algorithms.pdf]] — историческое — книга, видео и все-такое.  
 +
* Интернет + ИИ
  
−
[[File:book-advanced-algorithms.pdf|512px]]
 
  
−
== Примечания и ссылки ==
 
−
* Рекомендуется прочитать хотя бы [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 первые лекции] по введению в Python и научные вычисления.
 
  
−
<references/>
+
----
 +
=== Квесты ===
 +
;Входной квест:
 +
* [[Визуализация алгоритмов]]
 +
;Опциональные квесты:
 +
* [[Моделирование бизнес-задач]]
 +
* [[Моделирование труднорешаемых задач]]
 +
* [[Разбор статей]]
 +
* [[НаучныйПоиск]]
 +
;Бонус-опциональные:
 +
* для избранных — согласовывается некая тема, связанная и с алгоритмами, сложностью и областью научно-практических интересов студента.
 +
** [[:Категория:Проекты]]
 +
* Байпас, для тех, кому все это не интересно, и нужен тупо «уд» — придумаем или согласуем индивидуально.
 +
** Совсем просто не будет, иначе это неэтично по отношению к другим курсам по выбору.
 +
** Те, кто не стартанет вовремя, и проснется в ноябре-декабре — останется этот путь
 +
** «Переэкзаменовщикам» — наверно тоже.

Текущая версия на 12:58, 4 сентября 2025



Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.

Вопросы пишите на почту, или задавайте в группе.

Преподаватель
С.А. Фомин

Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:

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


Записываемся на курс «Advanced Algorithms-2025»?

Да10
100%
Anastasia voznyuk, Degkir, Ekaterina Dudenko, Godknows, Nikita Okhotnikov, PM, StasFomin, Volivan239, Whadohlob, Анна Савчук
Нет0
0%

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

  • Первое установочное занятие будет 4 сентября, в 18-30 в 903 КПМ

Материалы:


Содержание

Квесты

Входной квест
Опциональные квесты
Бонус-опциональные
  • для избранных — согласовывается некая тема, связанная и с алгоритмами, сложностью и областью научно-практических интересов студента.
  • Байпас, для тех, кому все это не интересно, и нужен тупо «уд» — придумаем или согласуем индивидуально.
    • Совсем просто не будет, иначе это неэтично по отношению к другим курсам по выбору.
    • Те, кто не стартанет вовремя, и проснется в ноябре-декабре — останется этот путь
    • «Переэкзаменовщикам» — наверно тоже.
Источник — «https://discopal.ispras.ru/index.php?title=Курс_«Эффективные_алгоритмы»_для_МФТИ&oldid=36216»