Обучение студентов использованию метода Гаусса для целочисленных матриц при реализации на компьютере

  • Татьяна Матвеевна Косовская Санкт-Петербургский государственный университет, Университетский пр., д. 28, Старый Петергоф, 198504, Санкт-Петербург, Россия
Ключевые слова: Метод Гаусса, вычислительная сложность, вычисления с большими целыми числами

Аннотация

Статья написана на основе части курса "анализ алгоритмов" для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных. Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса. Показаны проблемы, возникающие при обработке больших целых чисел, связанные с ‘нарезкой" цифр. Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга.

Биография автора

Татьяна Матвеевна Косовская, Санкт-Петербургский государственный университет, Университетский пр., д. 28, Старый Петергоф, 198504, Санкт-Петербург, Россия

Доктор физико-математических наук, доцент, профессор кафедры информатики математико-механического факультета СПбГУ, kosovtm@gmail.com

Литература

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).

Опубликован
2019-09-30
Как цитировать
Косовская, Т. М. (2019). Обучение студентов использованию метода Гаусса для целочисленных матриц при реализации на компьютере. Компьютерные инструменты в образовании, (3), 90-95. https://doi.org/10.32603/2071-2340-2019-3-90-95
Выпуск
Раздел
Компьютер в учебном процессе