Wiki - Факультет компьютерных наук - Вклад [ru]

О факультете

2017-05-21T08:46:32Z

Alakhno: Добавлена ссылка на вторую часть курса "Методы оптимизации" (дискретная оптимизация).

__NOTOC__

== Учебные курсы факультета компьютерных наук==

=== Курсы за 2016/17 учебный год ===
{| class="wikitable"
|-
! 1 курс !! 2 курс !! 3-4 курс !! майноры
|-
|

[[Математический анализ на ПМИ_2016/2017 | Математический анализ на ПМИ (пилотный поток)]]

[[Линейная алгебра и геометрия_2016/2017 | Линейная алгебра и геометрия на ПМИ]]

[[Дискретная_математика_1_2016/2017 | Дискретная математика-1 на ПМИ]]

[[Основы и методология программирования_2016/2017_пилотный_поток | Основы и методология программирования на ПМИ (пилотный поток)]]

[[Основы и методология программирования_2016/2017 | Основы и методология программирования на ПМИ (основной поток)]]

[[Алгоритмы_и_структуры_данных_на_ПМИ_(пилотный_поток) | Алгоритмы и структуры данных на ПМИ (пилотный поток)]]

[[Алгоритмы_и_структуры_данных_на_ПМИ_(основной_поток) | Алгоритмы и структуры данных на ПМИ (основной поток)]]

[[Алгебра_на_ПМИ_2016/2017 | Алгебра на ПМИ]]

[http://hsealgebra17.wikidot.com/ Алгебра на ПИ]

||

[[Математический анализ_2016/2017 | Математический анализ-3 на ПМИ (основной поток)]]

[[Математически_анализ_3_на_ПМИ_(пилотный_поток) | Математический анализ-3 на ПМИ (пилотный поток)]]

[[DM_2_2016_2017 | Дискретная математика-2 на ПМИ (основной поток)]]

[[Дискретная математика_2_2016/2017 | Дискретная математика-2 на ПМИ (пилотный поток)]]

[[Алгоритмы и структуры данных_2_2016/2017 | Алгоритмы и структуры данных – 2 на ПМИ (основной поток)]]

[[Теория вероятностей_2016/2017 | Теория вероятностей на ПМИ (основной поток)]]

[[Теория_вероятностей_2016/2017_(пилотный_поток) | Теория вероятностей на ПМИ (пилотный поток)]]

[[Архитектура_компьютеров_и_операционные_системы_2016/2017 | Архитектура компьютеров и операционные системы]]

[[Факультатив_теория_вычислений_2016/2017 | Факультатив теория вычислений на ПМИ]]

[[Дополнительные_главы_теории_вероятностей_(факультатив,_2017) | Дополнительные главы теории вероятностей (факультатив)]]

[[Дифференциальные_уравнения_(2_курс,_2016/2017) | Дифференциальные уравнения]]

[[Математическая_статистика_2016/2017_(пилотный_поток) | Математическая статистика на ПМИ (пилотный поток)]]

||

[[НИС_Машинное_обучение_и_приложения_2016/2017 | НИС Машинное обучение и приложения на ПМИ]]

[[Машинное_обучение_1 | Машинное обучение 1 на ПМИ]]

[[Машинное_обучение_2 | Машинное обучение 2 на ПМИ]]

[[Прикладной_статистический_анализ_данных | Прикладной статистический анализ данных на ПМИ]]

[[Численные_методы_в_анализе_данных | Численные методы в анализе данных на ПМИ]]

[http://www.machinelearning.ru/wiki/index.php?title=Статистика_случайных_процессов_(курс_лекций,_ФКН_ВШЭ) Вероятностные модели и статистика случайных процессов на ПМИ]

[http://www.machinelearning.ru/wiki/index.php?title=Opt Методы оптимизации на ПМИ (специализации МОП и РС)]

[[Методы_оптимизации_(весна_2017)|Методы оптимизации 2 (дискретная оптимизация)]]

[[НИС_Распределенные_системы_(осень_2016) | НИС Распределенные системы]]

[[Анализ и верификация алгоритмов биржевой торговли | Анализ и верификация алгоритмов для систем биржевой торговли ]]

[[Программирование_на_графических_процессорах | Программирование на графических процессорах]]

[[ЯРПО | Языки разработки ПО (курс по выбору) на ПМИ]]

[[Data analysis (Software Engineering) 2017 | Data analysis на ПИ]]

[[Базы данных 2 | Базы данных 2 ]]

[[Компьютерные сети 2 | Компьютерные сети 2]]

[[Машинное_обучение_на_больших_данных | Машинное обучение на больших данных на ПМИ]]

||

[[Современные_методы_машинного_обучения_(курс_майнора) | Современные методы машинного обучения (курс майнора)]]

[[Майнор_Интеллектуальный_анализ_данных/Введение_в_программирование_2016/2017 | Введение в программирование (курс майнора)]]

[[Майнор Интеллектуальный анализ данных/Введение в анализ данных | Введение в анализ данных (курс майнора)]]

[[Майнор Интеллектуальный анализ данных/Прикладные задачи анализа данных| Прикладные задачи анализа данных (курс майнора)]]

|}

{|width=100%
|style="vertical-align:top;"|



=== Курсы за 2015/16 учебный год ===
{|
|-
| [[Технологии программирования|Технологии программирования на ПМИ]]
|-
|[[ОиМП-2015|Основы и методология программирования на ПМИ]]
|-
|[[Алгоритмы и структуры данных 2016]]
|-
|[[Линейная алгебра и геометрия_2015/2016 | Линейная алгебра и геометрия на ПМИ]]
|-
|[[Алгебра_2015/2016 | Алгебра на ПМИ]]
|-
|[http://hsealgebra.wikidot.com/ Алгебра на ПИ]
|-
|[[Компьютерные системы]]
|-
|[[Математический анализ на ПМИ_2015/2016 | Математический анализ на ПМИ]]
|-
|[[Факультатив_Матпрактикум | Матпрактикум (факультатив) на ПМИ]]
|-
|[[Data analysis (Software Engineering)]] 
|-
|[[Майнор Интеллектуальный анализ данных/Введение в программирование|Введение в программирование (курс майнора) на ПМИ]]
|-
|[[Майнор Интеллектуальный анализ данных/Введение в анализ данных/2015-2016|Введение в анализ данных (курс майнора) на ПМИ]]
|-
|[[НИС Машинное обучение и приложения|НИС Машинное обучение и приложения на ПМИ]]
|-
|[[Архитектура компьютеров и системное программирование (ПМИ_4, 2015/2016)|Архитектура компьютеров и системное программирование (4 курс)]]
|-
|[[Дифференциальные уравнения (2 курс, 2015/2016)| Дифференциальные уравнения]]
|-
|[[Введение в VBA|Введение в VBA]]
|}

|style="vertical-align:top;"|



=== Курсы за 2014/15 учебный год ===
{|
|-
|[[Основы и методологии программирования]] 
|-
|[[Алгоритмы и структуры данных 2015 | Алгоритмы и структуры данных]] 
|-
|[[Анализ данных (Программная инженерия)]] 
|-
|[[Алгебра_2014/2015 | Алгебра]] 
|-
|[[Magolego_sna_2015| MAGoLEGO Social Network Analysis]]
|}

==== Проектная работа ====
{|
|-
|[[Проектная работа]] 
|-
|[[Учебная практика 1 курс (2016)]]
|-
|[[Проектная работа 2 курс (2016)]]
|}


|}

== Мероприятия факультета компьютерных наук ==
=== Summer School 2015 ===
[[Introduction to Natural Language Processing|Introduction to Natural Language Processing]]
#[[Lecture 1. Introduction|Introduction]]
#[[Lecture 2. Tokenization and word counts|Tokenization and word counts]]
#[[Lecture 3. POS tagging. Key word and phrase extraction|POS tagging. Key word and phrase extraction]]
#[[Lecture 4. Parsing|Parsing]]
#[[Lecture 5. Language sources|Language sources]]
#[[Lecture 6. Synonyms and near-synonyms detection|Synonyms and near-synonyms detection]]
#[[Lecture 8. Suffix trees for NLP|Suffix trees for NLP]]
#[[NLP References|References]]

== Архив ==
* [[Учебная практика 1 курс (2015)]]

Методы оптимизации (весна 2017)

2017-05-19T07:29:22Z

Alakhno:

== Аннотация ==
Вики-страница посвящена второй части курса методов оптимизации, посвящённой дискретной (комбинаторной) оптимизации.
== Персоналии ==
* Лектор: Максим Бабенко
* Семинаристы: Максим Ахмедов, Александр Дайняк, Алексей Лахно, Руслан Савченко

== Лекции ==
=== Лекция 04.04 ===
* Постановка задачи о паросочетании наибольшей мощности/веса
* Постановка задачи линейного программирования (LP).
* Целочисленная линейная программа, кодирующая задачу о паросочетании. Линейная релаксация.
* Пример того, что для $K_3$ у решений соответствующей линейной релаксации нет комбинаторного смысла. [Почему оптимум такой? Заход в двойственность.]
* Понятие препятствия и сертификата. Пример: s-t-барьер как сертификат несуществования (комбинаторное препятствие для существования) s-t-пути в неориентированном графе. В ориентированных графах s-t-разрезы.
* Теорема Холла о совершенных паросочетаниях. Построение препятствия.
* Формула Татта-Бержа (в формате критерия существования совершенного паросочетания в произвольном графе) в сторону "критерий не выполнен => совершенного паросочетания не существует".

=== Лекция 11.04 ===
* Формы задач ЛП, их эквивалентность
* Элиминация переменных
* Полиэдры, политопы, вершины
* Критерий вершины
* Тотально унимодулярные матрицы, целочисленность полиэдра
* Тотальная унимодулярность в задаче о двудольном паросочетании
=== Лекция 18.04 ===
* Слабая двойственность для задачи ЛП
* Сильная двойственность (формулировка)
* Построение двойственной ЛП для задачи в общей форме
* Прямая и двойственная ЛП для задачи о двудольном паросочатении, целочисленность двойственных решений, теорема Кёнига—Эгервари
* Конусы: конечнопорожденные и полиэдральные
* Отделимость от конусов, лемма Фаркаша
=== Лекция 25.04 ===
* Доказательство теоремы о сильной двойственности
* Дополняющая нежесткость
* Задача о кратчайших путях, формулировка в терминах линейного программирования
* Потенциалы и приведенные длины

=== Лекция 16.05 ===
* Критерий консервативности длин в терминах наличия допустимых потенциалов
* Primal-dual алгоритм для случая неотрицательных длин
* Сведение случая длин общего вида к последовательности подзадач для неотрицательных длин
* Задача о покрытии множества, формулировка в виде ЛП
* Детерминированное округление решений: d-приближение для покрытия максимальной толщины d
* Рандомизированное округление решений: O(log n)-приближение для общего случая

== Домашние задания ==
* [https://drive.google.com/file/d/0B5XaFkH0dkxeUm8zM3B5SFY2UkE/view?usp=sharing Первое задание (теоретическое)]
* [https://drive.google.com/file/d/0B5XaFkH0dkxeUkxrRDVjUWhUajg/view?usp=sharing Второе задание (практическое)]
* Третье задание (теоретическое)

==Правила вычисления итоговой оценки за курс==

"Итоговая_оценка" = 0.8 * "Накопленная_итоговая" + 0.2 "Экзамен"

"Накопленная_итоговая " = 0.625 * "Накопленная_непрерывная" + 0.375 * "Накопленная_дискретная"

"Накопленная_непрерывная" выставляется по итогам 3-го модуля преподавателями курса по непрерывной оптимизации.

За 4-й модуль выставляется отдельная оценка "Накопленная_дискретная" и проводится экзамен.
На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).

"Итоговая_оценка" округляется ближайшему целому (.5 округляется к единице).

В 4-м модуле в курсе есть три домашних задания, которые оцениваются от 0 до 10.

"Накопленная_дискретная"" = 0.35 * ("дом_1" + "дом_2" + "дом_3").

"Накопленная_дискретная" округляется до [0,10] в большую сторону.
Если до округления "Накопленная_дискретная" >= 10, то она округляется до 10.