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

Текущая версия на 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 КПМ

Материалы:

Файл:book-advanced-algorithms.pdf — историческое — книга, видео и все-такое.
Интернет + ИИ

Содержание

1 Квесты

Квесты

Входной квест

Визуализация алгоритмов

Опциональные квесты

Бонус-опциональные

для избранных — согласовывается некая тема, связанная и с алгоритмами, сложностью и областью научно-практических интересов студента.
- Категория:Проекты
Байпас, для тех, кому все это не интересно, и нужен тупо «уд» — придумаем или согласуем индивидуально.
- Совсем просто не будет, иначе это неэтично по отношению к другим курсам по выбору.
- Те, кто не стартанет вовремя, и проснется в ноябре-декабре — останется этот путь
- «Переэкзаменовщикам» — наверно тоже.

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

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

Содержание

Квесты

Навигация

Просмотры

Персональные инструменты

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-<!-- * [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]] -->
+__FORCETOC__
-* [[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Еженедельная тренировка]]
+{{SideBar|
+{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/12/sort=wlp_talk_updated}}
+|style=max-width:35%
+}}
 Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.
-<!--
+* [https://логос.испран.рф/mipt-course-03/hard-problems.svg Темы-цели курса]
-Семестровый курс по выбору<ref>К экзамену допускаются только студенты, зарегистрировавшиеся до 10 октября [mailto:stas-fomin@yandex.ru email].</ref>
+* [https://алгоритмы.испран.рф/public/course-effg.drawio.svg Путь прохождения]
-для студентов 6-го курса ФУПМ МФТИ.
+* [https://0x1.tv/Fcromt Методологический подход] (кому интересно почему так, а не иначе).
--->
+* [[Blog:Advanced_Algorithms/2024-09-08_Презентация_курса_«на_осень_2024»|Прошлогодняя презентация курса]]
-;Лекторы: д.ф.-м.н. [mailto:nnkuz@ispras.ru Н.Н. Кузюрин], [mailto:stas-fomin@yandex.ru С.А. Фомин]
+----
+Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [{{active-telegram-group-link}} группе].
+;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]
 Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
 {{:Как зарегистрироваться на курс}}
-<poll>
-UNSAFE_ID=aa-20171022
-ALTERNATIVE
-OPEN_RESULTS
-OPEN_VOTERS
-AUTHORIZED
-ALLOW_REVOTE
-END_POLL 2017-10-01
-Записываемся на курс «Advanced Algorithms-2017»?
-Да
-Нет
-</poll>
-<!--
-Прием экзамена, вторник, 2016-12-27, 11:30, [http://www.ispras.ru ИСПРАН], 301 аудитория.
 <poll>
-UNSAFE_ID=2016-12-23-exam
+UNSAFE_ID=aa-20250901
 ALTERNATIVE
 OPEN_RESULTS
@@ Строка 36: / Строка 29: @@
 AUTHORIZED
 ALLOW_REVOTE
-END_POLL 2016-12-23
+END_POLL 2025-10-30
-Будете на экзамене 2016-12-23, 10:45?
+Записываемся на курс «Advanced Algorithms-2025»?
 Да
 Нет
 </poll>
-* Если не набереться четырех студентов — возможно этот прием будет отменен.
+* Первое установочное занятие будет 4 сентября, в 18-30 в 903 КПМ
-Процесс сдачи будет включать:
-* Фильтрацию входящих тестами (если совсем не готов —  не тратим время друг друга).
-* Вопросы по теме («почему так»), или те самые задачи, которые вы решали.
+Материалы:
-Время последующих сдач пока не известно.
+* [[:Файл:book-advanced-algorithms.pdf]] — историческое — книга, видео и все-такое.
--->
+* Интернет + ИИ
-Вводное занятие проведено — всем изучать материалы на
-[[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое.
-Ближайшая встреча — 29 октября, готовим темы из раздела [[#Фокус]]
-Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам.
-<!-- Возможно, если будут новые темы, будут удаленные лекции (которых попробуем и также записать и зафиксировать). -->
-Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [https://vk.com/discopal группе].
-<!--
-{{!|Важное:}} Деканат внезапно захотел список студентов <s>прямо сейчас</s> уже вчера. Так что просьба, определится быстрее и записаться как указано выше на курс ASAP.
--->
 ----
-<!--
+=== Квесты ===
-Зафиксирована запись следующих участников:
+;Входной квест:
+* [[Визуализация алгоритмов]]
+;Опциональные квесты:
-Печально, что несложные несколько пунктов инструкции оказались невывыполнимы для многих (не осилили даже пункт «На своей личной странице, написать хотя бы ФИО и группу»).
+* [[Моделирование бизнес-задач]]
--->
+* [[Моделирование труднорешаемых задач]]
+* [[Разбор статей]]
+* [[НаучныйПоиск]]
-<!--
+;Бонус-опциональные:
+* для избранных — согласовывается некая тема, связанная и с алгоритмами, сложностью и областью научно-практических интересов студента.
-SELECT user_name, user_real_name, user_email FROM `user` WHERE user_name IN (select poll_user from poll_vote WHERE poll_id='Xc12c3daeb861942efc77a234744170c') and user_id IN (select wl_user from watchlist where wl_title = "Advanced_Algorithms")
+** [[:Категория:Проекты]]
+* Байпас, для тех, кому все это не интересно, и нужен тупо «уд» — придумаем или согласуем индивидуально.
-Итак, записались:
+** Совсем просто не будет, иначе это неэтично по отношению к другим курсам по выбору.
+** Те, кто не стартанет вовремя, и проснется в ноябре-декабре — останется этот путь
-Списки переданы и зафиксированы в учебной части.
+** «Переэкзаменовщикам» — наверно тоже.
--->
-* Проблемы → [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_6FZElcGVLNjEtY3lfOHhkdkRQWTI1aUktUUE&single=true&gid=9&output=html" id="1695919049" frameborder="0" height="800" width="100%"></iframe></div></div>
-</div>
-</center></html>
-В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса.
-В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.
-Если вы в зеленой группе — вы кандидат на «отлично автоматом».
-«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
-= Темы =
-Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соответствующего PDF-файла.
-== Фокус ==
-Темы к ближайшему занятию.
-* [[Несложно о сложности. Примеры алгоритмов]]
-* [[Формально об алгоритмах. Вычислительные модели]]
-* [[Временная и пространственная сложность алгоритмов]]
-* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
-== Непройденные темы ==
-* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
-* [[Жадный алгоритм в задачах о покрытии]]
-* [[Жадный алгоритм покрытия для почти всех исходных данных]]
-* [[Приближенный алгоритм для метрической задачи коммивояжера]]
-* [[Жадный алгоритм в задаче о рюкзаке]]
-* [[Динамическое программирование для задачи о рюкзаке]]
-* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
-* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
-* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
-* [[Полиномиальный в среднем алгоритм для SAT]]
-* [[Вероятностная проверка тождеств]]
-* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
-* [[MAX-SAT: вероятностное округление]]
-* [[MAX-CUT: вероятностное округление]]
-* [[MAX-SAT: дерандомизация]]
-<!-- * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] -->
-<!-- * [[PCP и аппроксимируемость]] -->
-<!-- {:Дерандомизация Люби} -->
-<!-- * [[Параллельный алгоритм Люби для максимального по включению независимого множества]] -->
-= Тренировка =
-[[Special:MediawikiQuizzer/Эффективные алгоритмы|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
-Тест будет на экзамене, чтобы отсеять совсем невменяемых.
-== Задачи ==
-Все статьи в этой категории — задачи, которые можно пытаться решать.
-* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.
-Решать надо создавая для решения ''подстраницу'' страницы с задачей, и ссылаясь в решении на задачу.
-;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
-Cтатьи-решения задач помечать вставляя строку
-<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
-и подписываться на изменения («watch this page»).
-Любая активность, даже попытки решения  — хорошо.
-После того, как задача решена, она перейдет в архив:
-* [[:Category:Решенные задачи]].
-Проверенное решение перейдет в [[:Category:Решения]] или,
-если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
-Т.е. очередь решений на проверку → [[:Category:На проверку]] (там сейчас {{!|{{PAGESINCATEGORY: На проверку}}}} задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
-Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
-Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
-Эти задачи заводим в
-[[:Category:Предложенные студентами задачи]]
-Все статьи в этой категории — задачи, которые можно пытаться решать.
-* [[:Category:Нерешенные задачи]].
-Любая активность, даже попытки решения  — хорошо.
-После того, как задача решена, она перейдет в архив:
-* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения.
-Cтатьи-решения задач помечать вставляя строку
-<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
-и подписываться на изменения («watch this page»).
-Проверенное решение перейдет в [[:Category:Решения]] или,
-если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
-= Видеолекции =
-* [[/Лекции осеннего семестра 2011]]
-** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
-* [[/Лекции осеннего семестра 2012]]
-* [[Курс_лекций_«Сложность_алгоритмов»_(ИСПРАН,_3_курс_МФТИ)/Лекции_весеннего_семестра_2013]]
-== Книга ==
-Специальная верстка для чтения с ноутбуков и КПК:
-* альбомная ориентация
-* крупные беззасечные шрифты
-Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
-Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
-[[:File: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/>