Чему вы научитесь
Курс состоит из двух семестров. В каждом семестре нужно решить три задачи, по одной из каждой темы.
Темы первого семестра:
- Поиск в графе 1 – явное применение алгоритмов поиска в ширину и глубину для решения задачи.
2. Поиск в графе 2 – применения тех же алгоритмов для проверки различных свойств графов.
3. Пути в сетях – задачи на алгоритм Дейкстры, алгоритм Форда-Беллмана, нахождение кратчайшего пути в ациклическом графе.
Темы второго семестра:
- Минимальный остов – применение алгоритма Ярника-Прима-Дейкстры и алгоритма Борувки-Краскала.
2. Максимальный поток и паросочетания – алгоритм Форда-Фалкерсона, алгоритм Куна.
3. Задачи на разные темы – построение графовой модели, применение различных алгоритмов, в том числе из предыдущих тем.
Все задачи на курсе общедоступны, но для каждого студента формируется индивидуальный набор обязательных задач. Номер задачи в теме определяется следующим образом:
\( N = (Q - 1) \mod M + 1 \) , где
\( N \) – номер задачи в теме
\( Q \) – номер студента в группе
\( M \) – количество задач в теме
Например, в теме 10 задач, тогда студент с номером 12 получает задачу с номером \( (12-1) \mod 10 + 1 = 2 \)$\lt math xmlns="http://www.w3.org/1998/Math/MathML"\gt<mo stretchy="false">(</mo><mn>12</mn><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mspace width="0.667em"></mspace><mi>mod</mi><mspace width="thinmathspace"></mspace><mspace width="thinmathspace"></mspace><mn>10</mn><mo>+</mo><mn>1</mn><mo>=</mo></math>$
355
