Задача о минимуме/максимуме скалярного произведения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Задача о минимуме/максимуме скалярного произведения''' - задача о нахождении минимальной…»)
 
Строка 14: Строка 14:
  
 
4. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex> таких что, <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность.
 
4. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex> таких что, <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность.
 +
 +
== Литература ==
 +
1. Романовский И. В. Дискретный анализ. — 3-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 320.

Версия 04:50, 23 ноября 2010

Задача о минимуме/максимуме скалярного произведения - задача о нахождении минимальной/максимальной суммы попарных произведений для двух заданных упорядоченных наборов чисел.

Теорема

Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности [math]x_1..x_m[/math] и убывающей последовательности [math]y_1..y_m[/math]. При сопоставлении возрастающим [math]x_1..x_m[/math] и [math]y_1..y_m[/math] достигается максимум.

док-во

1. Будем считать, что [math]x_i[/math] отсортирована по возрастанию.

2. Покажем, что если существуют пары чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math] такие что, [math]x_i \lt x_j[/math] и [math]y_i \lt y_j[/math], то скалярное произведение можно уменьшить, поменяв местами [math]y_i[/math] и [math]y_j[/math]. Так так [math](x_j - x_i)(y_j - y_i) \gt 0[/math], то [math]x_i y_i + x_j x_j \gt x_j y_i + x_i y_j[/math].

3.Проделав такую замену для всех [math]y_i \lt y_j[/math] получим отсортированную по убыванию последовательность [math]y_i[/math].

4. Аналогично для получения максимума во всех парах чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math] таких что, [math]x_i \lt x_j[/math] и [math]y_i \gt y_j[/math] нужно менять местами [math]y_i[/math] и [math]y_j[/math]. В результате получится отсортированная по возрастанию последовательность.

Литература

1. Романовский И. В. Дискретный анализ. — 3-е изд. — СПб.: Невский Диалект; БХВ-Петербург, 2003. — С. 320.