Тема: Feedback
Спасибо за проделаную роботу! Прочитал практически все алгоритмы :-) И нашел несколько ошибок(опечаток):
В функции Эйлера, доказательство мультипликативности:
если x взаимнопросто с a, то не следует, что x mod a = 1 (например x=7, a=4 (7 mod 4 = 3) или x=8, a=5 (8 mod 5 = 3))
В алгоритме Штор-Вагнера, Доказательство:
"наиболее сильно сильно связанную"
лишнее слово "сильно".
"то обозначим предпоследнюю добавленную вершину через s, а предпоследнюю — через t."
Наверное, "последнюю через t".
"но не ещё не были учтены в"
лишнее "не"
В алгоритме Куна:
Увеличивающей цепью ... назовём цепь,
Наверное, "назовём чередующуюся цепь".
Матрица Татта:
"Напомним, что паросочетание "
Нету продолжения(((
"некоторого полинома относительно переменных-элементов этой матриц"
Наверное, "матрицы".
Центры тяжести многоугольников и многогранников:
"Мы считаем, что масса распределена по фигуре однородна"
Наверное, "распределенная" или "однородно".
Нахождение площади объединения треугольников. Метод вертикальной декомпозиции:
"найдём все точки пересечения всех отрезков (образующих треугольники), и отсортируем найденные точки"
Наверное, следует упомянуть о том, что отсортировать надо по X.
Нахождение вписанной окружности в выпуклом многоугольнике методом "сжатия сторон":
"больше сдвигать стороны мы не сможет"
Наверное, "сможем".
Z-функция строки и её вычисление:
Пример 2: aaabaab; z[4] должно быть 2 а не 3.
"Применения эти будут во многом аналогичным применениям \alohref=prefix_function{префикс-функции}."
опечатка в ссылке на префикс функцию.
Суффиксный массив. Наибольший общий префикс двух подстрок: способ с дополнительной памятью
Наверное, не за О(1), а за О(log(N)).
Sqrt-декомпозиция:
"которая позволяет некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за"
не хватает слова "выполнять".
"Рассмотрим ещё одну интересную вариацию идею"
Наверное, "вариацию идеи".
Дерево отрезков:
Усложнённые версии дерева отрезков:
мы должны просто по двум таким пары
Наверное, "парам".
Присвоение на отрезке
"западывающее" обновление
запаздывающее
Декартово дерево (treap, дерамида):
"Merge (T1, T2) ... (все значения в первом меньше значений во втором)"
Возможно, следует указать "(все значения Y в первом меньше значений Y во втором)"
Задача Иосифа
"чем рассмотренная выше динамика" - на самом деле, динамики выше нет.
И несколько пожеланий/предложений:
В алгоритме Диница:
обязательно ли запускать несколько dfs'ов? Такой вариант вроде б должен быстрее работать (и коду меньше):
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
int rest=flow;
for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]], to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs (to, min (rest, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
rest-=pushed;
if (!rest)
return flow;
}
}
return flow-rest;
}
int dinic() {
int flow = 0;
while (bfs()) {
memset (ptr, 0, n * sizeof ptr[0]);
flow+=dfs(s,INF);
}
return flow;
}
Если нет, то укажите, пожалуйста на ошибку.
Пересечение окружности и прямой:
возможно, лучше формулы переделать в TeX.
Префикс-функция. Алгоритм Кнута-Морриса-Пратта:
Сжатие строки - может просто вставить ссылку на соответствующую статью?
Может в книге сделать текст пошире?