Обучение студентов использованию метода Гаусса для целочисленных матриц при реализации на компьютере
Аннотация
Статья написана на основе части курса "анализ алгоритмов" для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных. Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса. Показаны проблемы, возникающие при обработке больших целых чисел, связанные с ‘нарезкой" цифр. Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга.
Литература
T. M. Kosovskaya and N. K. Kosovskii, “About polynomial algorithms for solution of diophantine systems of linear equations and comparisons,” in Proc. of VIII International seminar Descrete mathematics and its applications, Moscow, 2004, pp. 72–74 (in Russian).
A. Schrijver, Theory of linear and integer programming, Wiley, 1998.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: Freeman, 1979.
S. M. Okulov, Programming in algorithms, Moscow: BINOM, 2007 (in Russian).
Материал публикуется под лицензией:
