ОБУЧЕНИЕ СТУДЕНТОВ ИСПОЛЬЗОВАНИЮ МЕТОДА ГАУССА ДЛЯ ЦЕЛОЧИСЛЕННЫХ МАТРИЦ ПРИ РЕАЛИЗАЦИИ НА КОМПЬЮТЕРЕ

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

Статья написана на основе части курса «анализ алгоритмов» для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных. Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса. Показаны проблемы, возникающие при обработке больших целых чисел, связанные с «нарезкой» цифр. Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга
Переведенное названиеTeaching students to use the Gauss method for integer matrices when implemented on a computer
Язык оригиналарусский
Страницы (с-по)90-95
Число страниц6
ЖурналКОМПЬЮТЕРНЫЕ ИНСТРУМЕНТЫ В ОБРАЗОВАНИИ
Номер выпуска3
DOI
СостояниеОпубликовано - 2019

Цитировать