Archive for November 2010

Три задачи с одним решением

Есть три задачи. Задача первая – решить матричное уравнение A x = b, где A – матрица, x – неизвестный вектор, а b – заданная правая часть, опять вектор. Коэффициенты – действительные числа.

Во второй задаче коэффициенты (и у матрицы и у векторов) – целые числа.

А в третьей задаче все то же самое, только коэффициенты целые положительные, и уравнение надо решить в целых положительных числах.

Накал пиздеца постепенно крепчает. Целые числа мы не всегда можем делить друг на друга. Впрочем, взяв пару чисел (a, b), мы можем вычесть из большего по модулю числа меньшее по модулю, и такая процедура редукции нам отлично заменит деление.

А целые положительные числа мы можем вычитать, только меньшее из большего.

Однако, алгоритм Гаусса решения линейных систем уравнений работает во всех трех случаях (на то он и Гаусс).

Умные дядьки про третью задачу пишут страшное, примерно такое: http://documents.kenyon.edu/math/CWendler.pdf Это страшные люди, разобраться в их алгебре практически невозможно.

Попытаюсь на пальцах.

Continue reading ‘Три задачи с одним решением’ »

Из штатного расписания

“n-way ассоциативный продьюсер”