Заключение

По результатам разработанных модификаций удалось получить выигрыш во времени работы алгоритма Григорьева. Ожидалось, что получится найти менее очевидные преобразования, чем поиск тропической суммы не всей строки, а только её ненулевой части, которые могли бы также оказать влияние на время, что сделать не получилось. Наиболее полезный, на мой взгляд, результат – это внесение в программу Побежимова [12] дополнений, позволяющих проверять матрицу на невырожденность. Сама по себе проверка является очень тяжелой вычислительной операцией, но в дальнейшем она может быть усовершенствована до итеративного вычисления через перманент матрицы меньшего размера – именно такая идея была описана Д.Ю. Григорьевым [2] при оценке сложности алгоритма.

Список литературы

1. Сорокин, В. Н. Разработка методов и алгоритмов решения многомерных минимаксных задач тропической оптимизации: дис. … канд. физ.-мат. наук : 01.01.07 / В.Н. Сорокин — СПб., 2018. С. 4-5 // https://disser.spbu.ru/files/disser2/disser/KqM3N92JNH.pdf

2. Grigoriev D. Complexity of solving tropical linear systems = Сложность решения систем тропических линейных систем / D. Grigoriev // CNRS, Math´ematiques, Universit´e de Lille Villeneuve d’Ascq, 59655, France

3. Давыдов, А. П. Оценки сложности алгоритма Григорьева для решения тропических линейных систем / А. П. Давыдов // Зап. научн. сем. ПОМИ, 2012, том 402, 69–82

4. Литвинов, Г. Л. Деквантование Маслова, идемпотентная и тропическая математика: краткое введение / Г.Л. Литвинов // Зап. научн. сем. ПОМИ, 2005, том 326, 145–182

5. [Электронный ресурс] http://amoebas.sfu-kras.ru/?page_id=234 — Тропические полиномы и их графики

6. [Электронный ресурс] http://amoebas.sfu-kras.ru/?page_id=17 — Функция Иенсена-Ронкина

7. [Электронный ресурс] https://e-maxx.ru/algo/linear_systems_gauss — Метод Гаусса решения системы линейных уравнений

8. [Электронный ресурс] http://www.cleverstudents.ru/systems/solving_systems_Gauss_method.html — Метод Гаусса: описание алгоритма решения системы линейных уравнений, примеры, решения.

9. Волков Е. А. Численные методы: Учеб. Пособие для вузов. — 2-е изд., испр. — М.: Наука. Гл. ред. физ.-мат. лит., 1987. — 248 с.

10. [Электронный ресурс] https://planetmath.org/hessenbergmatrix ­— Hessenberg matrix = матрицы Хессенберга

11. [Электронный ресурс] https://www.wikiwand.com/en/Tridiagonal_matrix — Tridiagonal matrix = Трёхдиагональная матрица

12. [Электронный ресурс] https://github.com/arlekin147/TropicalMathematic — Репозиторий А. А. Побежимова с программной реализацией алгоритма Григорьева

13. Прасолов В. В. П70 Задачи и теоремы линейной алгебры. — 2-е изд. — М., 2008

14. Уилкинсон Дж. X. Алгебраическая проблема собственныx значений. Изд-во "Наука", 1970. - 565 с.

15. Алексеева О. Г. Методические указания по экономическому обоснованию выпускных квалификационных работ бакалавров: Метод. Указания / О.Г. Алексеева // СПб.: Изд-во СПбГЭТУ “ЛЭТИ”, 2013. с.

16. Приказ № ОД/0539 от 27.09.2019 «Об увеличении уровня оплаты труда работникам университета и об изменении размеров минимальных должностных окладов и должностных окладов по профессионально-квалификационным группам, с учетом повышающих коэффициентов по квалификационным уровням» // СПбГЭТУ «ЛЭТИ»

17. Положение об оплате труда работников университета (редакция, действующая с 01.10.2019) // [Электронный ресурс] URL: https://etu.ru/sveden/files/Pologhenie_ob_oplate_truda_2019.pdf

18. Налоговый кодекс Российской Федерации (часть вторая) от 05.08.2000 N 117-ФЗ (ред. от 23.04.2018) (с изм. и доп., вступ. в силу с 01.05.2018)

19. О Классификации основных средств, включаемых в амортизационные группы (с изменениями на 28 апреля 2018 года): постановление Правительства Рос. Федерации от 01.01.2002 № 1 // Официальный интернет-портал правовой информации. 2018. № 526. С. 001–020.

20. Конспект лекции Д. Ю. Григорьева «Рекуррентные тропические последовательности» / Н. Лукашов, В. Смирнова, А. Беляева // [Электронный ресурс] URL: https://cloud.mail.ru/public/2VV8/4YYzVKkiG