2013-12-11 — Семинар-консультация по приближенным алгоритмам с гарантированной оценкой точности
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
** Проверьте, что вы или ваши друзья не в их числе — если вам не пришло почтовое уведомление об этом посте, значит, либо вы не указали почту, либо не подтвердили ее, либо не подписались на этот блог. | ** Проверьте, что вы или ваши друзья не в их числе — если вам не пришло почтовое уведомление об этом посте, значит, либо вы не указали почту, либо не подтвердили ее, либо не подписались на этот блог. | ||
* вы ознакомились видеолекциями/слайдами/[[:File:Book-advanced-algorithms.pdf|книгой]]. | * вы ознакомились видеолекциями/слайдами/[[:File:Book-advanced-algorithms.pdf|книгой]]. | ||
− | |||
На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра. | На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра. | ||
Строка 16: | Строка 15: | ||
* смотреть видео лекций → приложены к каждой теме, просто пройдите по ссылке темы. | * смотреть видео лекций → приложены к каждой теме, просто пройдите по ссылке темы. | ||
* листать слайды, запоминая ключевые моменты. Особо продвинутым возможно достаточно слайдов. | * листать слайды, запоминая ключевые моменты. Особо продвинутым возможно достаточно слайдов. | ||
− | * решать задачи по каждой теме — задачи к каждой теме по ссылки «Подстраницы». Подстраница «BBB» страницы «AAA» — это страница с именем «BBB/AAA». | + | * решать задачи по каждой теме — задачи к каждой теме по ссылки «Подстраницы». Если задача еще не решена, т.е. в категории [[:Category:Нерешенные задачи]]. Подстраница «BBB» страницы «AAA» — это страница с именем «BBB/AAA». |
+ | Например, вот | ||
+ | * [[Жадный_алгоритм_в_задачах_о_покрытии]] — страница темы | ||
+ | * [[Жадный_алгоритм_в_задачах_о_покрытии/Задачи]] — подстраница задач | ||
+ | * [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set]] — постановка задачи | ||
+ | * Решения: | ||
+ | ** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Александра-Мафусалова]] | ||
+ | ** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Михаила-Кузнецова]] | ||
+ | ** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение Владимира Игнатьева]] | ||
− | Итак, к первой онлайн встрече, вы должны следующий блок материалов: | + | Все статьи в этой категории — задачи, которые можно пытаться решать. |
+ | * [[:Category:Нерешенные задачи]]. | ||
+ | Любая активность, даже попытки решения — хорошо. | ||
+ | После того, как задача решена, она перейдет в архив: | ||
+ | * [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения, решения предыдущего курса были открыты все три месяца. | ||
+ | |||
+ | Cтатьи-решения задач помечать вставляя строку | ||
+ | |||
+ | <pre><nowiki>[[Category:На проверку]]</nowiki></pre> и подписываться на изменения («watch this page»). | ||
+ | |||
+ | Проверенное решение перейдет в [[:Category:Решения]] или, если возникнут вопросы-возражения в [[:Category:Проблемы в решении]]. | ||
+ | Т.е. очередь решений на проверку → [[:Category:На проверку]], проверяйте, что ваши решения в правильной категории (а то их так и не проверят...). | ||
+ | |||
+ | Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). | ||
+ | Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач. | ||
+ | |||
+ | Эти задачи заводим в [[:Category:Предложенные студентами задачи]] | ||
+ | |||
+ | Любая активность по всем темам — найденные ошибки в книге, решенные задачи, предложенные задачи — все будет фиксироваться, и может привести к отличной оценке «автоматом» (либо упрощенной сдаче экзамена). Любая. Так что изучайте темы, в любом формате (решая ли задачи или вычитывая или даже придумывая новые — в любом случае активность будет зачтена и учтена). | ||
+ | Хуже всего — ничего не делать. | ||
+ | ---- | ||
+ | |||
+ | Итак, к первой онлайн встрече, вы должны изучить следующий блок материалов: | ||
* [[Жадный алгоритм в задачах о покрытии]] | * [[Жадный алгоритм в задачах о покрытии]] | ||
* [[Жадный алгоритм покрытия для почти всех исходных данных]] | * [[Жадный алгоритм покрытия для почти всех исходных данных]] | ||
− | |||
* [[Жадный алгоритм в задаче о рюкзаке]] | * [[Жадный алгоритм в задаче о рюкзаке]] | ||
* [[Динамическое программирование для задачи о рюкзаке]] | * [[Динамическое программирование для задачи о рюкзаке]] | ||
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | ||
+ | |||
+ | На самом деле, первый раз будет экспериментальным, так что хотя бы изучите материалы по жадным алгоритмам. | ||
Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников. | Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников. | ||
− | Первая онлайн встреча будет в пятницу, 6 декабря, 2013 года, в | + | Первая онлайн встреча будет в пятницу, <b>6 декабря, 2013 года, в 13:00</b>, здесь, на этой же странице — тут будут ссылки |
По нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства. | По нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства. |
Версия 09:13, 5 декабря 2013
Итак, мы вполне ожидали, что за прошедшее время, все желающие
- зарегистрировались на курс — на Курс лекций «Эффективные алгоритмы» полный список, хотя, к сожалению, некоторые не осилили выполнить пяток простых пунктов из квеста Блог:Advanced_Algorithms/Запись_на_осенний_семестр-2013_«Эффективных_алгоритмов», увы, им не будет приходить уведомления об онлайн-консультациях и прочие анонсы.
- Проверьте, что вы или ваши друзья не в их числе — если вам не пришло почтовое уведомление об этом посте, значит, либо вы не указали почту, либо не подтвердили ее, либо не подписались на этот блог.
- вы ознакомились видеолекциями/слайдами/книгой.
На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра. Sad but true.
Так вот. Самое время стартовать на полной передаче!
Мы будем использовать метод flipped classroom, когда лекции вы сможете прослушать дома, в удобное время, а онлайн встречу использовать именно для разбора вопросов и решения задач.
Вы можете
- читать электронную книгу (адаптирована для чтения с экрана, крупные экранные шрифты, гиперссылки и т.п.), бумажную версию можно найти в библиотеке МФТИ.
- смотреть видео лекций → приложены к каждой теме, просто пройдите по ссылке темы.
- листать слайды, запоминая ключевые моменты. Особо продвинутым возможно достаточно слайдов.
- решать задачи по каждой теме — задачи к каждой теме по ссылки «Подстраницы». Если задача еще не решена, т.е. в категории Category:Нерешенные задачи. Подстраница «BBB» страницы «AAA» — это страница с именем «BBB/AAA».
Например, вот
- Жадный_алгоритм_в_задачах_о_покрытии — страница темы
- Жадный_алгоритм_в_задачах_о_покрытии/Задачи — подстраница задач
- Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set — постановка задачи
- Решения:
Все статьи в этой категории — задачи, которые можно пытаться решать.
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:
- Category:Решенные задачи — кстати, полезно смотреть чужие решения, решения предыдущего курса были открыты все три месяца.
Cтатьи-решения задач помечать вставляя строку
[[Category:На проверку]]и подписываться на изменения («watch this page»).
Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении. Т.е. очередь решений на проверку → Category:На проверку, проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
Эти задачи заводим в Category:Предложенные студентами задачи
Любая активность по всем темам — найденные ошибки в книге, решенные задачи, предложенные задачи — все будет фиксироваться, и может привести к отличной оценке «автоматом» (либо упрощенной сдаче экзамена). Любая. Так что изучайте темы, в любом формате (решая ли задачи или вычитывая или даже придумывая новые — в любом случае активность будет зачтена и учтена). Хуже всего — ничего не делать.
Итак, к первой онлайн встрече, вы должны изучить следующий блок материалов:
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм покрытия для почти всех исходных данных
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
На самом деле, первый раз будет экспериментальным, так что хотя бы изучите материалы по жадным алгоритмам.
Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников.
Первая онлайн встреча будет в пятницу, 6 декабря, 2013 года, в 13:00, здесь, на этой же странице — тут будут ссылки
По нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства.
Технически — это будет с нашей стороны:
- Трансляция звука, экрана, и, возможно, говорящих голов.
- Вы задаете вопросы в интерактивном чате-блокноте.
Какой именно сервис мы будем использовать для трансляции — в первый раз наверно это будет трансляция через yatv, далее возможны варианты (может быть каждый раз будем использовать новый сервис). Пока регистрироваться нигде не нужно.
Итак, текущий фокус — видеолекции и книга. Скачиваем, смотрим, читаем. На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.
Запоминаем свои вопросы, если видите ошибку — фиксируйте. Дальше будут возможности решать задачи, находить ошибки в книгах и слайдах и прочие возможности асинхронной удобной коллаборации.
Вопросы-замечания-предложения → комментариями к этому посту или по почте, теперь я буду отвечать оперативно.