2013-12-11 — Семинар-консультация по приближенным алгоритмам с гарантированной оценкой точности

Материал из DISCOPAL
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
 
Итак, мы вполне ожидали, что за прошедшее время, все желающие
 
Итак, мы вполне ожидали, что за прошедшее время, все желающие
* зарегистрировались на курс — на [[Курс лекций «Эффективные алгоритмы»]] полный список, хотя, к сожалению, некоторые не осилили выполнить пяток простых пунктов из [[Блог:Advanced_Algorithms/Запись_на_осенний_семестр-2013_«Эффективных_алгоритмов»]].
+
* зарегистрировались на курс — на [[Курс лекций «Эффективные алгоритмы»]] полный список, хотя, к сожалению, некоторые не осилили выполнить пяток простых пунктов из квеста [[Блог:Advanced_Algorithms/Запись_на_осенний_семестр-2013_«Эффективных_алгоритмов»]], увы, им не будет приходить уведомления об онлайн-консультациях и прочие анонсы.
 +
** Проверьте, что вы или ваши друзья не в их числе — если вам не пришло почтовое уведомление об этом посте, значит, либо вы не указали почту, либо не подтвердили ее, либо не подписались на этот блог.
 
* вы ознакомились видеолекциями/слайдами/[[:File:Book-advanced-algorithms.pdf|книгой]].
 
* вы ознакомились видеолекциями/слайдами/[[:File:Book-advanced-algorithms.pdf|книгой]].
 
  
 
На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра.
 
На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра.
 
Sad but true.
 
Sad but true.
 +
  
 
Так вот. Самое время стартовать на полной передаче!
 
Так вот. Самое время стартовать на полной передаче!
  
Напоминаю:
+
Мы будем использовать метод flipped classroom, когда лекции вы сможете прослушать дома, в удобное время, а онлайн встречу использовать именно для разбора вопросов и решения задач.
* Проверьте [[Курс лекций «Эффективные алгоритмы»]], есть ли вы в таблице зарегистрированных студентов — последний шанс зарегистрироваться до понедельника, и проверьте указаны ли у вас Skype-логин (если вы хотите посещать онлайн-лекции), Discopal-логин, ну и главное — email. Если видите в списке вашего друга/товарища/знакомого без email — достучитесь до него, пусть пришлет email.
+
Да, изначально планировались и лекции по новым темам, но увы, не вышло, такие дела. Так что темы будут старые, проверенные прошлыми годами, по которым все есть в печатной и видеоформе.
  
 +
Вы можете
 +
* читать [[:Файл:Book-advanced-algorithms.pdf|электронную книгу]] (адаптирована для чтения с экрана, крупные экранные шрифты, гиперссылки и т.п.), бумажную версию можно найти в библиотеке МФТИ.
 +
* смотреть видео лекций → приложены к каждой теме, просто пройдите по ссылке темы.
 +
* листать слайды, запоминая ключевые моменты. Особо продвинутым возможно достаточно слайдов.
 +
* решать задачи по каждой теме — задачи к каждой теме по ссылки «Подстраницы». Если задача еще не решена, т.е.  в категории [[:Category:Нерешенные задачи]]. Подстраница «BBB» страницы «AAA» — это страница с именем «BBB/AAA».
  
* Скачайте все видеолекции. Я специально скачал и выложил [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент], чтобы вы могли за раз скачать все. Скачайте и смотрите, используя видеоплеер VLC, и ускоряйте клавишей «]», пока не найдете темп, при котором вам не будет скучно (+ сэкономите время). Также там можно листать:
+
<blockquote>
;CTRL→, CTRL←: ±1 минута
+
Например, вот 
;ALT→, ALT←: ±10 секунд (наиболее удобное, имхо).
+
* [[Жадный_алгоритм_в_задачах_о_покрытии]] — страница темы
;SHIFT→, SHIFT←: ±3 секунды («ну-ка повтори, что сказал»)
+
* [[Жадный_алгоритм_в_задачах_о_покрытии/Задачи]] — подстраница задач
;RIGHTALT→, RIGHTALT←: ±5мин.
+
* [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set]] — постановка задачи
Стало скучновато, докладчик усыпляет?
+
* Решения:  
]»: Добавьте ему 10% к скорости. И так раза три.
+
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Александра-Мафусалова]]
[»: Притормозить на -10%.
+
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Михаила-Кузнецова]]  
 +
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение Владимира Игнатьева]]
 +
</blockquote>
  
Вперед! У вас впереди несколько дней, включая все выходные.
+
Все статьи в этой категории — задачи, которые можно пытаться решать.
 +
* [[:Category:Нерешенные задачи]].
 +
Любая активность, даже попытки решения  — хорошо.
 +
После того, как задача решена, она перейдет в архив:
 +
* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения, решения предыдущего курса были открыты все три месяца.
  
С понедельника следующей недели, мы запускаем онлайн-лекции, в которых рассмотрим недопрочитанные темы, и ответим на ваши вопросы по предыдущим.
+
Cтатьи-решения задач помечать вставляя строку
 +
 +
<pre><nowiki>[[Category:На проверку]]</nowiki></pre> и подписываться на изменения («watch this page»).
  
Лекции будут проходить где-то днем, с 13:00-17:00, ибо по нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства. Более конкретная актуальная информация будет идти рассылкой по указанным вами почтовым адресам, и возможно с помощью Skype-чата.
+
Проверенное решение перейдет в [[:Category:Решения]] или, если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
 +
Т.е. очередь решений на проверку → [[:Category:На проверку]], проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
 +
 
 +
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
 +
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
 +
 
 +
Эти задачи заводим в [[:Category:Предложенные студентами задачи]]
 +
 
 +
Любая активность по всем темам — найденные ошибки в книге, решенные задачи, предложенные задачи — все будет фиксироваться, и может привести к отличной оценке «автоматом» (либо упрощенной сдаче экзамена). Любая. Так что изучайте темы, в любом формате (решая ли задачи или вычитывая или даже придумывая новые — в любом случае активность будет зачтена и учтена). Да, это будут в таблице учета появлятся разные цифры, которые хитрым образом могут повлиять на оценку.
 +
Не беспокойтесь о них — просто изучайте материал, ширше и глубжке, и все будет ОК.
 +
Хуже всего — ничего не делать.
 +
----
 +
 
 +
Итак, к первой онлайн встрече, вы должны изучить следующий блок материалов:
 +
* [[Жадный алгоритм в задачах о покрытии]]
 +
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
 +
* [[Жадный алгоритм в задаче о рюкзаке]]
 +
* [[Динамическое программирование для задачи о рюкзаке]]
 +
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 +
 
 +
На самом деле, первый раз будет экспериментальным, так что хотя бы изучите материалы по жадным алгоритмам.
 +
 
 +
Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников.
 +
 
 +
 
 +
Онлайн встреча будет в среду, {{!|11 декабря, 2013 года}}, {{@|в 12:20}} (решаем проблему с подключением) здесь, {{!|[http://discopal.ispras.ru/TV?useskin=cleanmonobook по ссылке]}}.
 +
 
 +
{{SideBar|мы поняли, в пятницу у подавляющего большинства лекции весь день.}}
 +
 
 +
По нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства.
  
 
Технически — это будет с нашей стороны:
 
Технически — это будет с нашей стороны:
 
* Трансляция звука, экрана, и, возможно, говорящих голов.
 
* Трансляция звука, экрана, и, возможно, говорящих голов.
* Вы задаете вопросы в чате.
+
* Вы задаете вопросы в интерактивном чате-блокноте.
  
Скорее всего, мы будем использовать Skype для трансляции звука и чата, и join.me для трансляции экрана, но возможны и варианты.
+
Какой именно сервис мы будем использовать для трансляции — в первый раз наверно это будет трансляция через yatv, далее возможны варианты (может быть каждый раз будем использовать новый сервис).
 +
Пока регистрироваться нигде не нужно.
  
Прочитанная лекция будет оперативно монтироваться и публиковаться, так что если пропустили - то можно посмотреть потом, вы теряете только возможность оперативного общения.
+
Итак, текущий фокус — видеолекции и книга. Скачиваем, смотрим, читаем.
 
+
Итак, текущий фокус — видеолекции. Скачиваем и смотрим!
+
Скачать очень полезно, ибо возможно этот сайт будет переезжать и будет местами недоступен.
+
 
На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.
 
На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.
Да, их можно смотреть и там, и даже скачать оттуда, но, думаю, торрентом быстрее.
 
  
 
Запоминаем свои вопросы, если видите ошибку — фиксируйте.
 
Запоминаем свои вопросы, если видите ошибку — фиксируйте.
 
 
Дальше будут возможности решать задачи, находить ошибки в книгах и слайдах и прочие возможности асинхронной удобной коллаборации.
 
Дальше будут возможности решать задачи, находить ошибки в книгах и слайдах и прочие возможности асинхронной удобной коллаборации.
  
Вопросы-замечания-предложения → mailto:stas-fomin@yandex.ru, теперь я буду отвечать оперативно.
+
Вопросы-замечания-предложения → комментариями к этому посту или по [mailto:stas-fomin@yandex.ru почте], теперь я буду отвечать оперативно.
 +
 
 +
== Видео консультации ==
 +
Пока драфт и немного обрезано, вечером починю.
 +
{{Vimeoembed|81585142|800|500}}
  
 
== Конспект консультации ==
 
== Конспект консультации ==
Строка 136: Строка 179:
  
  
{{wl-publish: 2012-11-21 15:56:46 +0400 | StasFomin }}
+
{{wl-publish: 2013-12-10 22:39:29 +0400 | StasFomin }}

Текущая версия на 10:00, 11 декабря 2013

Итак, мы вполне ожидали, что за прошедшее время, все желающие

На самом деле, мы знаем, что большинство обычно, к учебе активно приступают только в конце семестра. Sad but true.


Так вот. Самое время стартовать на полной передаче!

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

Вы можете

  • читать электронную книгу (адаптирована для чтения с экрана, крупные экранные шрифты, гиперссылки и т.п.), бумажную версию можно найти в библиотеке МФТИ.
  • смотреть видео лекций → приложены к каждой теме, просто пройдите по ссылке темы.
  • листать слайды, запоминая ключевые моменты. Особо продвинутым возможно достаточно слайдов.
  • решать задачи по каждой теме — задачи к каждой теме по ссылки «Подстраницы». Если задача еще не решена, т.е. в категории Category:Нерешенные задачи. Подстраница «BBB» страницы «AAA» — это страница с именем «BBB/AAA».

Например, вот

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

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

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

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

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

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

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

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

Любая активность по всем темам — найденные ошибки в книге, решенные задачи, предложенные задачи — все будет фиксироваться, и может привести к отличной оценке «автоматом» (либо упрощенной сдаче экзамена). Любая. Так что изучайте темы, в любом формате (решая ли задачи или вычитывая или даже придумывая новые — в любом случае активность будет зачтена и учтена). Да, это будут в таблице учета появлятся разные цифры, которые хитрым образом могут повлиять на оценку. Не беспокойтесь о них — просто изучайте материал, ширше и глубжке, и все будет ОК. Хуже всего — ничего не делать.


Итак, к первой онлайн встрече, вы должны изучить следующий блок материалов:

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

Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников.


Онлайн встреча будет в среду, 11 декабря, 2013 года, в 12:20 (решаем проблему с подключением) здесь, {{{1}}}.

мы поняли, в пятницу у подавляющего большинства лекции весь день.

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

Технически — это будет с нашей стороны:

  • Трансляция звука, экрана, и, возможно, говорящих голов.
  • Вы задаете вопросы в интерактивном чате-блокноте.

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

Итак, текущий фокус — видеолекции и книга. Скачиваем, смотрим, читаем. На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.

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

Вопросы-замечания-предложения → комментариями к этому посту или по почте, теперь я буду отвечать оперативно.

Видео консультации

Пока драфт и немного обрезано, вечером починю.

Конспект консультации

        • Если не видно сверху картинки попробуйте пегрузить страницу, или в левом нижнем углу верхнего окна понажимать на иконку включения.***
      • Критичная проблема - может быть в корпоративной сети закрыт 1935.

yatv.ru - зайдите, и попробуйте чтонибудь посмотреть. Если там не работает - увы. *** Для тех, у кого увы - будут записи.

Записи - это хорошо) У меня с планшета yatv.ru есть, а вот картинки здесь нет( просьба фиксировать ответы на вопросы в блокноте

В
а когда экзамен?
О
20 декабря МФТИ. Потом ИСП РАН 301. На экзамене можно пользоваться чем угодно. 2-3 попытки сдачи.
В
минимальные требования на удвл 3, хор 5, отл 8.
О
Требований нет. Надо делать всё! Исправлять оишбки, решать задачки, придумывать новые задачки.
В
А как понять, что сделали/нарешали/напридумывали достаточно для желаемой оценки?
О
понятно будет ближе к дате экзаменов. По баллам (за решение, отмечание ошибок и т.д.) Часть получит автомат, среди еще части проведут лотерею
В
Сколько человек обычно получают автомат и выигрывают лотерею?
ПО РАЗНОМУ
В
Можно ли решать задачи, которые на проверке или нужно брать только новые ? О:Нельзя. Если задача решена, но не проверена, нужно взять другую задачу.
В
а как тогда сверять? я должен смотреть на задачу, а потом выискивать ее в "на проверку"?
О
при просмотре "подстраниц" задачи там будут уже какие-то решения. Если среди них есть решения из категории "на проверку", значит кто-то её уже решал.
В
В категории нерешенных задач есть задачи с решениями. Их можно решать? Или нужно смотреть есть ли они в категории на проверку?
О
В
А что делать, если мою задачу, которую я решила, потом кто-то еще решил? Будет учитываться, кто первый?
О
как учтутся оба решения. Но желательно так не делать.
В
Будут новые задачки появляться? А то уже есть очень большой процент задач, которые решили всего около 5 человек. Такими темпами на всех не хватит+1
О
будут появляться новые задачи.

Ответьте на этот вопрос, пжлст (стрелочка вниз) !!!

В
Задачи надо предлагать вместе с решением? (я вопрос, который очень хочет ответа!)
В
При решении задач главное количество или разнообразие?
О
разнообразие, количество и сложность.
В
А можно экзамен до Нового Года? Я думаю, все поддержат) Даже числа до 24 лучше Да)+4

Или во второй половине января? -Там же ГОС 15го После госа) Нельзя же после госа. Действительно, могут возникнуть проблемы. Лишь бы не в новогодние праздники: когда есть уникальный шанс уехать куда подальше.+1

О
20 декабря МФТИ. Потом в ИСП РАН комната 301
В
Что такое A_index?
О
отражает вашу способность зарегестрироваться на ресурсе.
В
А если A_index пуст?
хрен знает
В
Можно как-то учесть сертификат coursera по алгоритмам? +1 или ШАДа? или аналогичный курс на ИСПе? или прослушанный курс в МГУ?
О
короче скорее нет, чем да. Можно подготовить теоретические вопросы симпатичные, или задачи (тестовые вопросы в quiz'ах на coursera по алгоритмам).
В
А какого рода задачи будут приемлимыми? Можно же напридумывать элементарщины. Ну да. Просто известные задачи в некотором виденье
О
можно попробовать. Главное, чтобы было интересно!
В
А можно ли смотреть чужие решения на проверку и говорить, что, дескать, товарищ не прав?
О
Круто! Так можно. Только без троллей, которые придираются к каждому символу (ну, извините)
В
Задачи надо предлагать вместе с решением?
О
Короче, желательно с решением
В
У меня вопрос по модифицированному жадному алгоритму.

отвечено

В
Можно следующие онлайн встречи проводить каким-то другим способом? Чтобы тем, кто увы, они тоже были доступны

НЕт, не придумал

В
Какие ещё есть виды деятельности по курсу, кроме решение и предложения задач, нахождения ошибок?
О
я не знаю. Проверять чужие решения. Ошибки во всем, что угодно (слайды, книги, видео, смысл жизни). Можно предлагать интересные производственные задачи, которые своядтся к тому-то (банкинг, пересылка пакетов и тд и тп). Присылать такие вещи можно на почту (вроде как)
В
Насколько часто будут проходить вебинары?
завтра может быть
В
вопросы, если они появляются, задавать вам по e-mail?
О
да

давайте страничку FAQ по курсу +1 Ещё туда ответы на эти вопросы можно скопипастить

В
Можно ли участие в каком-нибудь контесте зачесть в рамках курса?) http://russianaicup.ru ? или хакатоне?
О
главное польза в рамках курса, тогда мб
В
Когда станет известно то кто получит автомат?
О
20 декабря утром Сурово(
В
А что именно будет на экзамене? Задачи/билеты с теорией/ещё что-то?
о
тест, вопросы по теме, всем можно пользоваться, задачи (именно опубликованне).