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».
 
  
<blockquote>
+
* Скачайте все видеолекции. Я специально скачал и выложил [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент], чтобы вы могли за раз скачать все. Скачайте и смотрите, используя видеоплеер VLC, и ускоряйте клавишей «]», пока не найдете темп, при котором вам не будет скучно (+ сэкономите время). Также там можно листать:
Например, вот 
+
;CTRL→, CTRL←: ±1 минута
* [[Жадный_алгоритм_в_задачах_о_покрытии]] — страница темы
+
;ALT→, ALT←: ±10 секунд (наиболее удобное, имхо).
* [[Жадный_алгоритм_в_задачах_о_покрытии/Задачи]] — подстраница задач
+
;SHIFT→, SHIFT←: ±3 секунды («ну-ка повтори, что сказал»)
* [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set]] — постановка задачи
+
;RIGHTALT→, RIGHTALT←: ±5мин.
* Решения:  
+
Стало скучновато, докладчик усыпляет?
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Александра-Мафусалова]]
+
]»: Добавьте ему 10% к скорости. И так раза три.
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение-Михаила-Кузнецова]]  
+
[»: Притормозить на -10%.
** [[Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set/Решение Владимира Игнатьева]]
+
</blockquote>
+
  
Все статьи в этой категории — задачи, которые можно пытаться решать.
+
Вперед! У вас впереди несколько дней, включая все выходные.
* [[:Category:Нерешенные задачи]].
+
Любая активность, даже попытки решения  — хорошо.
+
После того, как задача решена, она перейдет в архив:
+
* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения, решения предыдущего курса были открыты все три месяца.
+
  
Cтатьи-решения задач помечать вставляя строку
+
С понедельника следующей недели, мы запускаем онлайн-лекции, в которых рассмотрим недопрочитанные темы, и ответим на ваши вопросы по предыдущим.
+
<pre><nowiki>[[Category:На проверку]]</nowiki></pre> и подписываться на изменения («watch this page»).
+
  
Проверенное решение перейдет в [[:Category:Решения]] или, если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
+
Лекции будут проходить где-то днем, с 13:00-17:00, ибо по нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства. Более конкретная актуальная информация будет идти рассылкой по указанным вами почтовым адресам, и возможно с помощью Skype-чата.
Т.е. очередь решений на проверку → [[:Category:На проверку]], проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
+
  
Отдельно, пробуем новую инициативу те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
+
Технически это будет с нашей стороны:
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
+
* Трансляция звука, экрана, и, возможно, говорящих голов.
 +
* Вы задаете вопросы в чате.
  
Эти задачи заводим в [[:Category:Предложенные студентами задачи]]
+
Скорее всего, мы будем использовать Skype для трансляции звука и чата, и join.me для трансляции экрана, но возможны и варианты.
  
Любая активность по всем темам — найденные ошибки в книге, решенные задачи, предложенные задачи — все будет фиксироваться, и может привести к отличной оценке «автоматом» (либо упрощенной сдаче экзамена). Любая. Так что изучайте темы, в любом формате (решая ли задачи или вычитывая или даже придумывая новые — в любом случае активность будет зачтена и учтена). Да, это будут в таблице учета появлятся разные цифры, которые хитрым образом могут повлиять на оценку.
+
Прочитанная лекция будет оперативно монтироваться и публиковаться, так что если пропустили - то можно посмотреть потом, вы теряете только возможность оперативного общения.
Не беспокойтесь о них — просто изучайте материал, ширше и глубжке, и все будет ОК.
+
Хуже всего — ничего не делать.
+
----
+
  
Итак, к первой онлайн встрече, вы должны изучить следующий блок материалов:
+
Итак, текущий фокус — видеолекции. Скачиваем и смотрим!
* [[Жадный алгоритм в задачах о покрытии]]
+
Скачать очень полезно, ибо возможно этот сайт будет переезжать и будет местами недоступен.
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
+
На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.
* [[Жадный алгоритм в задаче о рюкзаке]]
+
Да, их можно смотреть и там, и даже скачать оттуда, но, думаю, торрентом быстрее.
* [[Динамическое программирование для задачи о рюкзаке]]
+
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
+
  
На самом деле, первый раз будет экспериментальным, так что хотя бы изучите материалы по жадным алгоритмам.
+
Запоминаем свои вопросы, если видите ошибку — фиксируйте.
  
Если возникают вопросы по этим темам — пишите их в комментарии к этому посту. Кстати, можете отвечать на вопросы сокурсников.
+
Дальше будут возможности решать задачи, находить ошибки в книгах и слайдах и прочие возможности асинхронной удобной коллаборации.
  
 +
Вопросы-замечания-предложения → mailto:stas-fomin@yandex.ru, теперь я буду отвечать оперативно.
  
Онлайн встреча будет в среду, {{!|11 декабря, 2013 года}}, {{@|в 12:20}} (решаем проблему с подключением) здесь, {{!|[http://discopal.ispras.ru/TV?useskin=cleanmonobook по ссылке]}}.
+
== Конспект консультации ==
  
{{SideBar|мы поняли, в пятницу у подавляющего большинства лекции весь день.}}
+
****Если не видно сверху картинки  попробуйте пегрузить страницу, или в левом нижнем углу верхнего окна понажимать на иконку включения.***
 +
*** Критичная проблема - может быть в корпоративной сети закрыт 1935.
 +
yatv.ru - зайдите, и попробуйте чтонибудь посмотреть. Если там не работает - увы. ***
 +
Для тех, у кого увы - будут записи.
  
По нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства.
+
Записи - это хорошо)
 +
У меня с планшета yatv.ru есть, а вот картинки здесь нет(
 +
просьба фиксировать ответы на вопросы в блокноте
  
Технически — это будет с нашей стороны:
+
:а когда экзамен?
* Трансляция звука, экрана, и, возможно, говорящих голов.
+
;О: 20 декабря МФТИ. Потом ИСП РАН 301. На экзамене можно пользоваться чем угодно. 2-3 попытки сдачи.
* Вы задаете вопросы в интерактивном чате-блокноте.
+
  
Какой именно сервис мы будем использовать для трансляции — в первый раз наверно это будет трансляция через yatv, далее возможны варианты (может быть каждый раз будем использовать новый сервис).
+
;В:минимальные требования на удвл 3, хор 5, отл 8.
Пока регистрироваться нигде не нужно.
+
;О:Требований нет. Надо делать всё! Исправлять оишбки, решать задачки, придумывать новые задачки.
  
Итак, текущий фокус — видеолекции и книга. Скачиваем, смотрим, читаем.
+
;В:А как понять, что сделали/нарешали/напридумывали достаточно для желаемой оценки?
На всякий случай — еще один адрес лекций, https://vimeo.com/channels/251742 — запомните букмарками.
+
;О: понятно будет ближе к дате экзаменов. По баллам (за решение, отмечание ошибок и т.д.) Часть получит автомат, среди еще части проведут лотерею
 +
 
 +
;В: Сколько человек обычно получают автомат и выигрывают лотерею?
 +
;ПО РАЗНОМУ
 +
 
 +
;В:Можно ли решать задачи, которые на проверке или нужно брать только новые ? О:Нельзя. Если задача решена, но не проверена, нужно взять другую задачу.
 +
 
 +
;В: а как тогда сверять? я должен смотреть на задачу, а потом выискивать ее в "на проверку"?
 +
;О: при просмотре "подстраниц" задачи там будут уже какие-то решения. Если среди них есть решения из категории "на проверку", значит кто-то её уже решал.
 +
 
 +
;В: В категории нерешенных задач есть задачи с решениями. Их можно решать? Или нужно смотреть есть ли они в категории на проверку?
 +
;О:
 +
 
 +
;В: А что делать, если мою задачу, которую я решила, потом кто-то еще решил? Будет учитываться, кто первый?
 +
;О: как учтутся оба решения. Но желательно так не делать.
 +
 
 +
;В: Будут новые задачки появляться? А то уже есть очень большой процент задач, которые решили всего около 5 человек. Такими темпами на всех не хватит+1
 +
;О: будут появляться новые задачи.
 +
 
 +
Ответьте на этот вопрос, пжлст (стрелочка вниз) !!!
 +
;В:Задачи надо предлагать вместе с решением? (я вопрос, который очень хочет ответа!)
 +
;В:При решении задач главное количество или разнообразие?
 +
;О: разнообразие, количество и сложность.
 +
 
 +
;В: А можно экзамен до Нового Года? Я думаю, все поддержат) Даже числа до 24 лучше Да)+4
 +
Или во второй половине января? -Там же ГОС 15го После госа) Нельзя же после госа. Действительно, могут возникнуть проблемы.
 +
Лишь бы не в новогодние праздники: когда есть уникальный шанс уехать куда подальше.+1
 +
;О: 20 декабря МФТИ. Потом в ИСП РАН комната 301
 +
 
 +
;В:Что такое A_index?
 +
;О: отражает вашу способность зарегестрироваться на ресурсе.
 +
 
 +
;В:А если A_index пуст?
 +
;хрен знает
 +
 
 +
;В:Можно как-то учесть сертификат coursera по алгоритмам? +1 или ШАДа? или аналогичный курс на ИСПе? или прослушанный курс в МГУ?
 +
;О: короче скорее нет, чем да. Можно подготовить теоретические вопросы симпатичные, или задачи (тестовые вопросы в quiz'ах на coursera по алгоритмам).
 +
 
 +
;В: А какого рода задачи будут приемлимыми? Можно же напридумывать элементарщины. Ну да. Просто известные задачи в некотором виденье
 +
;О:можно попробовать. Главное, чтобы было интересно!
 +
 
 +
;В: А можно ли смотреть чужие решения на проверку и говорить, что, дескать, товарищ не прав?
 +
;О: Круто! Так можно. Только без троллей, которые придираются к каждому символу (ну, извините)
 +
 
 +
;В: Задачи надо предлагать вместе с решением?
 +
;О: Короче, желательно с решением
 +
 
 +
;В:У меня вопрос по модифицированному жадному алгоритму.
 +
отвечено
 +
;В: Можно следующие онлайн встречи проводить каким-то другим способом? Чтобы тем, кто увы, они тоже были доступны
 +
НЕт, не придумал
 +
 
 +
;В: Какие ещё есть виды деятельности по курсу, кроме решение и предложения задач, нахождения ошибок?
 +
;О: я не знаю. Проверять чужие решения. Ошибки во всем, что угодно (слайды, книги, видео, смысл жизни). Можно предлагать интересные производственные задачи, которые своядтся к тому-то (банкинг, пересылка пакетов и тд и тп). Присылать такие вещи можно на почту (вроде как)
 +
;В:Насколько часто будут проходить вебинары?
 +
;завтра может быть
 +
 
 +
;В: вопросы, если они появляются, задавать вам по e-mail?
 +
;О: да
 +
давайте страничку FAQ по курсу +1 Ещё туда ответы на эти вопросы можно скопипастить
 +
 
 +
;В: Можно ли участие в каком-нибудь контесте зачесть в рамках курса?) http://russianaicup.ru ? или хакатоне?
 +
;О: главное польза в рамках курса, тогда мб
 +
 
 +
;В: Когда станет известно то кто получит автомат?
 +
;О: 20 декабря утром Сурово(
 +
 
 +
;В: А что именно будет на экзамене? Задачи/билеты с теорией/ещё что-то?
 +
;о:тест, вопросы по теме, всем можно пользоваться, задачи (именно опубликованне).
  
Запоминаем свои вопросы, если видите ошибку — фиксируйте.
 
Дальше будут возможности решать задачи, находить ошибки в книгах и слайдах и прочие возможности асинхронной удобной коллаборации.
 
  
Вопросы-замечания-предложения → комментариями к этому посту или по [mailto:stas-fomin@yandex.ru почте], теперь я буду отвечать оперативно.
+
{{wl-publish: 2012-11-21 15:56:46 +0400 | StasFomin }}
{{wl-publish: 2013-12-10 22:39:29 +0400 | StasFomin }}
+

Версия 09:57, 11 декабря 2013

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


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

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

Напоминаю:

  • Проверьте Курс лекций «Эффективные алгоритмы», есть ли вы в таблице зарегистрированных студентов — последний шанс зарегистрироваться до понедельника, и проверьте указаны ли у вас Skype-логин (если вы хотите посещать онлайн-лекции), Discopal-логин, ну и главное — email. Если видите в списке вашего друга/товарища/знакомого без email — достучитесь до него, пусть пришлет email.


  • Скачайте все видеолекции. Я специально скачал и выложил торрент, чтобы вы могли за раз скачать все. Скачайте и смотрите, используя видеоплеер VLC, и ускоряйте клавишей «]», пока не найдете темп, при котором вам не будет скучно (+ сэкономите время). Также там можно листать:
CTRL→, CTRL←
±1 минута
ALT→, ALT←
±10 секунд (наиболее удобное, имхо).
SHIFT→, SHIFT←
±3 секунды («ну-ка повтори, что сказал»)
RIGHTALT→, RIGHTALT←
±5мин.

Стало скучновато, докладчик усыпляет?

«]»
Добавьте ему 10% к скорости. И так раза три.
«[»
Притормозить на -10%.

Вперед! У вас впереди несколько дней, включая все выходные.

С понедельника следующей недели, мы запускаем онлайн-лекции, в которых рассмотрим недопрочитанные темы, и ответим на ваши вопросы по предыдущим.

Лекции будут проходить где-то днем, с 13:00-17:00, ибо по нашему опыту, большинство старшекурсников в это время находится в офисах, за клавиатурой, с наушниками, понятное дело с интернетом, и вполне сможет участвовать, так сказать, без отрыва от производства. Более конкретная актуальная информация будет идти рассылкой по указанным вами почтовым адресам, и возможно с помощью Skype-чата.

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

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

Скорее всего, мы будем использовать Skype для трансляции звука и чата, и join.me для трансляции экрана, но возможны и варианты.

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

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

Запоминаем свои вопросы, если видите ошибку — фиксируйте.

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

Вопросы-замечания-предложения → mailto:stas-fomin@yandex.ru, теперь я буду отвечать оперативно.

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

        • Если не видно сверху картинки попробуйте пегрузить страницу, или в левом нижнем углу верхнего окна понажимать на иконку включения.***
      • Критичная проблема - может быть в корпоративной сети закрыт 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 декабря утром Сурово(
В
А что именно будет на экзамене? Задачи/билеты с теорией/ещё что-то?
о
тест, вопросы по теме, всем можно пользоваться, задачи (именно опубликованне).