Дискретная оптимизация 2018 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== О курсе == Курс читается для студентов 3-го курса [https://cs.hse.ru/ami ПМИ ФКН ВШЭ] в 4 модуле. '''Л…»)
 
Строка 9: Строка 9:
 
=== Полезные ссылки ===
 
=== Полезные ссылки ===
  
−
Репозиторий с материалами:
+
Репозиторий с материалами: TODO
−
Канал в телеграм для объявлений:
+
Канал в телеграм для объявлений: https://t.me/joinchat/AAAAAFD1-ZdchZS1FoOduA
−
Чат с преподавателями, где можно задавать вопросы (не флудить): https://t.me/lsml18
+
−
 
+
−
Таблица с оценками: ?
+
−
 
+
−
Оставить отзыв на курс: ?
+
−
 
+
  
 +
Таблица с оценками: TODO
 +
Оставить отзыв на курс: TODO
  
 
== Семинары ==
 
== Семинары ==
Строка 25: Строка 21:
 
! Группа !! Преподаватель !! Учебный ассистент !! Страница !! Расписание
 
! Группа !! Преподаватель !! Учебный ассистент !! Страница !! Расписание
 
|-
 
|-
−
| МОП 151 || Лахтанов Иван || ? || ? || ?
+
| МОП 151 || Лахтанов Иван || - || ? || ?
 
|-
 
|-
−
| МОП 152 || Колесниченко Игнат || ? || ? || ?
+
| МОП 152 || Колесниченко Игнат || - || http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat || Вторник 15.10-16.30
 
|-
 
|-
−
| АПР 153  || Суханов Николай || ? || ? || ?
+
| АПР 153  || Суханов Николай || - || ? || ?
 
|-
 
|-
−
| АДИС 154 || Савченко Руслан || ? || ? || ?
+
| АДИС 154 || Савченко Руслан || - || ? || ?
 
|-
 
|-
−
| РС 155 || Ахмедов Максим || ? || ? || ?
+
| РС 155 || Ахмедов Максим || - || ? || ?
 
|-  
 
|-  
−
| ТИ 156 || Саакян Вильям || ? || ? || ?
+
| ТИ 156 || Саакян Вильям || - || ? || ?
 
|-  
 
|-  
 
|}
 
|}
  
−
Ассистенты: ??
 
  
 
=== Консультации ===
 
=== Консультации ===
Строка 47: Строка 42:
 
=== Правила выставления оценок ===
 
=== Правила выставления оценок ===
  
−
В курсе предусмотрено несколько форм контроля знания:
+
В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.
−
* Практические домашние работы на Python
+
−
* Письменный экзамен
+
  
−
Итоговая оценка вычисляется на основе оценки за работу в семестре и оценки за экзамен:
+
Итоговая оценка вычисляется исходя из оценок за домашние задания
  
−
O<sub>итоговая</sub> = 0.7 * O<sub>накопленная</sub> + 0.3 * О<sub>экз</sub>
+
O<sub>итоговая</sub> = 0.33 * O<sub>ДЗ1</sub> + 0.33 * О<sub>ДЗ2</sub> + 0.34 * О<sub>ДЗ3</sub>
  
−
Оценка за работу в семестре вычисляется по формуле
+
Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).
−
 
+
−
O<sub>накопленная</sub> = 0.35 * O<sub>дз1</sub> + 0.35 * О<sub>дз2</sub> + 0.3 * О<sub>работа_на_семинаре</sub>
+
−
 
+
−
Необходимым условием для получения автомата является накопленная оценка, равная 8 или выше.
+
  
 
=== Правила сдачи заданий ===
 
=== Правила сдачи заданий ===
−
 
−
На каждое домашнее задание каждому студенту отводится ~2 недели беспрерывной работы ресурсов в облаке Azure.
 
−
Лучше останавливать машины, как написано в инструкции, когда вы их не используете, так всем точно хватит ресурсов.
 
  
 
Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.
 
Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.
Строка 70: Строка 56:
 
При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.
 
При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.
  
−
При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён (при этом получить дополнительные баллы за призовые места на конкурсе можно только при участии в общий срок). Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.
+
При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.
  
 
== Лекции ==
 
== Лекции ==
−
Из 2017:
 
  
−
'''Лекция 1''' (3 апреля). Онлайн-обучение и линейные модели [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture1.pdf Слайды]]
+
'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.
  
−
'''Лекция 2''' (10 апреля). Введение в Apache Spark [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture2.pdf Слайды]]
+
== Семинары ==
  
−
'''Лекция 3''' (17 апреля). Рекомендательные системы [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture3.pdf Слайды]]
+
'''Семинар 1''' (2-7 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.
−
 
+
−
'''Лекция 4''' (24 апреля). Градиентный бустинг [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture4.pdf Слайды]]
+
−
 
+
−
'''Лекция 5''' (15 мая). Введение в TensorFlow [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture5.pdf Слайды]]
+
−
 
+
−
'''Лекция 6''' (22 мая). Сверточные сети [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture6.pdf Слайды]]
+
−
 
+
−
'''Лекция 7''' (29 мая). Рекуррентные сети [[https://github.com/ZEMUSHKA/lsml_hse/blob/master/lecture7.pdf Слайды]]
+
−
 
+
−
'''Лекция 8''' (5 июня). MinHash, LSH и понижение размерности [[https://github.com/ZEMUSHKA/lsml_hse/ Материалы 8 лекции]]
+
  
 
== Практические задания ==
 
== Практические задания ==
−
Из 2017:
 
  
−
'''Задание 1.''' Рекомендательная система на Apache Spark
+
== Полезные материалы ==
 +
===Рекомендуемая литература  ===
  
−
Дата выдачи: 17.04.2017 23:59MSK
+
  * "B.Korte, J.Vygen – Combinatorial optimization" – подробная книга по теории комбинаторной оптимизации (http://www.or.uni-bonn.de/~vygen/co.html).
 +
  * "V. Vazirani – Approximation Algorithms" – одна из лучших книг по приближенным алгоритмам.
 +
  * "H. Papadimitriou – Combinatorial Optimization: Algorithms and Complexity" – классический учебник по комбинаторной оптимизации.
 +
  * "Where are the hard knapsack problems?" [David Pisinger] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
 +
  * ((https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf "Heuristics for the Traveling Salesman Problem" [Christian Nilsson]))  - краткое но насыщенное описание эвристик для задачи о коммивояжёре.
 +
  * "Handbook of Constraint Programming" [F. Rossi, P. van Beek and T. Walsh] - справочник по программированию в ограничениях.
 +
  * "Handbook of Metaheuristics" [Michel Gendreau, Jean-Yves Potvin] - справочник с описанием эвристических алгоритмов оптимизации.
  
−
Дедлайн: 10.05.2016 23:59MSK
+
===Полезные ссылки  ===
  
−
Условие: https://docs.google.com/document/d/1LMs8QBpD60qLPvrxPcav5I3tb9PJZkx4t8JuFoH_YOA/edit?usp=sharing
+
  * ((http://dopt.s3-website-us-east-1.amazonaws.com/003/viz/tsp/ Визуализатор маршрута коммивояжёра)) (вершины подаются в 0-индексации)
−
В условие будут добавляться комментарии, следите за обновлениями.
+
  * Курс по дискретной оптимизации на ((https://www.coursera.org/course/optimization Coursera)). Содержит хорошие видео-лекции по Constraint Programming и Local Search.
  
−
'''Задание 2 и 3.''' Сверточные сети в TensorFlow
+
===Материалы иного рода. ===
  
−
Дата выдачи: 23.05.2017 23:59MSK
+
Библиотеки для решения задач оптимизации:
−
 
+
  *  ((https://developers.google.com/optimization/ Google Optimization Tools)) (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. (((http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/documentation_hub.html Более полная документация)))
−
Дедлайн 2 задания: 04.06.2017 23:59MSK
+
  * ((http://numberjack.ucc.ie/ Numberjack)) (Python)
−
 
+
  * ((http://choco-solver.org/ Choco)) (Java)
−
Дедлайн 3 задания: 14.06.2017 23:59MSK (жесткий)
+
  * ((http://www.gecode.org/index.html Gecode)) (C++)
−
 
+
  * ((http://www.minizinc.org/ MiniZinc)) (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).
−
Условие: https://docs.google.com/document/d/1EN-0jAjC5ZAaE-7dR5oWDAOPZYh7lsBE0n_C3yP0q5U/edit?usp=sharing
+
−
 
+
−
== Экзамен ==
+
−
 
+
−
Дата: ?
+
−
 
+
−
Место: ?
+
−
 
+
−
Вопросы к экзамену: https://docs.google.com/document/d/1xtQv7vIfo2b7ZOvnw5U7SB2gatAFHUs5Xf65a8ps7k4/edit?usp=sharing
+
−
 
+
−
== Полезные материалы ==
+
−
===Книги===
+
−
# Ron Bekkerman, Mikhail Bilenko, John Langford. Scaling up Machine Learning: Parallel and Distributed Approaches, Cambridge University Press, 2011.
+
−
# Jure Leskovec, Anand Rajaraman, Jeff Ullman. Mining of Massive Datasets, Cambridge University Press, 2014.
+
−
# Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning (Adaptive Computation and Machine Learning series), The MIT Press, 2016.
+
−
# Sandy Ryza, Uri Laserson, Sean Owen, Josh Wills. Advanced Analytics with Spark: Patterns for Learning from Data at Scale, O'Reilly Media, 2015.
+

Версия 15:23, 4 апреля 2018

О курсе

Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ в 4 модуле.

Лектор: Игнат Колесниченко

Лекции ПМИ проходят по вторникам, 13:40 - 15:00, ауд. 622.

Полезные ссылки

Репозиторий с материалами: TODO Канал в телеграм для объявлений: https://t.me/joinchat/AAAAAFD1-ZdchZS1FoOduA

Таблица с оценками: TODO Оставить отзыв на курс: TODO

Семинары

Группа Преподаватель Учебный ассистент Страница Расписание
МОП 151 Лахтанов Иван -  ?  ?
МОП 152 Колесниченко Игнат - http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat Вторник 15.10-16.30
АПР 153 Суханов Николай -  ?  ?
АДИС 154 Савченко Руслан -  ?  ?
РС 155 Ахмедов Максим -  ?  ?
ТИ 156 Саакян Вильям -  ?  ?


Консультации

Консультации с преподавателями и учебными ассистентами (если иное не оговорено на странице семинаров конкретной группы) по курсу проводятся по предварительной договорённости ввиду невостребованности регулярных консультаций.

Правила выставления оценок

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = 0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

Правила сдачи заданий

Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.

При обнаружении плагиата оценки за домашнее задание обнуляются всем задействованным в списывании студентам, а также подаётся докладная записка в деканат. Следует помнить, что при повторном списывании деканат имеет право отчислить студента.

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

Лекции

Лекция 1 (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

Семинары

Семинар 1 (2-7 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

Практические задания

Полезные материалы

Рекомендуемая литература

 * "B.Korte, J.Vygen – Combinatorial optimization" – подробная книга по теории комбинаторной оптимизации (http://www.or.uni-bonn.de/~vygen/co.html).
 * "V. Vazirani – Approximation Algorithms" – одна из лучших книг по приближенным алгоритмам.
 * "H. Papadimitriou – Combinatorial Optimization: Algorithms and Complexity" – классический учебник по комбинаторной оптимизации. 
 * "Where are the hard knapsack problems?" [David Pisinger] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
 * ((https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf "Heuristics for the Traveling Salesman Problem" [Christian Nilsson]))  - краткое но насыщенное описание эвристик для задачи о коммивояжёре.
 * "Handbook of Constraint Programming" [F. Rossi, P. van Beek and T. Walsh] - справочник по программированию в ограничениях.
 * "Handbook of Metaheuristics" [Michel Gendreau, Jean-Yves Potvin] - справочник с описанием эвристических алгоритмов оптимизации.

Полезные ссылки

 * ((http://dopt.s3-website-us-east-1.amazonaws.com/003/viz/tsp/ Визуализатор маршрута коммивояжёра)) (вершины подаются в 0-индексации)
 * Курс по дискретной оптимизации на ((https://www.coursera.org/course/optimization Coursera)). Содержит хорошие видео-лекции по Constraint Programming и Local Search.

Материалы иного рода.

Библиотеки для решения задач оптимизации: 

 *  ((https://developers.google.com/optimization/ Google Optimization Tools)) (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. (((http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/documentation_hub.html Более полная документация)))
 * ((http://numberjack.ucc.ie/ Numberjack)) (Python)
 * ((http://choco-solver.org/ Choco)) (Java)
 * ((http://www.gecode.org/index.html Gecode)) (C++)
 * ((http://www.minizinc.org/ MiniZinc)) (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).
Источник — «http://wiki.cs.hse.ru/index.php?title=Дискретная_оптимизация_2018&oldid=27453»