Детальная информация
Название | Реализация двух алгоритмов решения систем строгих и нестрогих линейных неравенств: выпускная квалификационная работа бакалавра: направление 02.03.02 «Фундаментальная информатика и информационные технологии» ; образовательная программа 02.03.02_02 «Информатика и компьютерные науки» |
---|---|
Авторы | Шоберг Георгий Анатольевич |
Научный руководитель | Герасимов Александр Сергеевич |
Организация | Санкт-Петербургский политехнический университет Петра Великого. Институт компьютерных наук и кибербезопасности |
Выходные сведения | Санкт-Петербург, 2024 |
Коллекция | Выпускные квалификационные работы; Общая коллекция |
Тематика | системы строгих и нестрогих линейных неравенств; решение систем линейных неравенств; метод исключений Фурье-Моцкина; systems of strict and nonstrict linear inequalities; solution of systems of linear inequalities; Fourier–Motzkin elimination method |
Тип документа | Выпускная квалификационная работа бакалавра |
Тип файла | |
Язык | Русский |
Уровень высшего образования | Бакалавриат |
Код специальности ФГОС | 02.03.02 |
Группа специальностей ФГОС | 020000 - Компьютерные и информационные науки |
DOI | 10.18720/SPBPU/3/2024/vr/vr24-5298 |
Права доступа | Доступ по паролю из сети Интернет (чтение, печать, копирование) |
Дополнительно | Новинка |
Ключ записи | ru\spstu\vkr\33629 |
Дата создания записи | 29.08.2024 |
Разрешенные действия
–
Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети
Действие 'Загрузить' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети
Группа | Анонимные пользователи |
---|---|
Сеть | Интернет |
Данная работа посвящена реализации метода исключений Фурье-Моцкина и полиномиального алгоритма проверки совместности и решения систем строгих и нестрогих линейных неравенств в рациональных числах. В ходе данной работы решались следующие задачи: 1. Провести обзор известных алгоритмов решения данной задачи и смежных задач, а также их реализаций. 2. Модифицировать метод исключений Фурье-Моцкина для работы с системами строгих и нестрогих линейных неравенств и расширить его до их решения. 3. Выявить полиномиальный алгоритм проверки совместности строгих и нестрогих линейных неравенств и расширить его до их решения. 4. Реализовать выбранные алгоритмы. 5. Протестировать реализованные алгоритмы и экспериментально сравнить их работу с другими реализациями. В работе приводится формальное описание модификации метода исключений Фурье-Моцкина для работы с системами, содержащими строгие неравенства, а также расширение данного метода и полиномиального алгоритма проверки совместности систем строгих и нестрогих линейных неравенств для решения таких систем. В результате работы данные алгоритмы были реализованы на языке Java, в виде позволяющем работать с рациональными числами произвольной точности.
The given work is devoted to the implementation of the Fourier-Motzkin elimination method and polynomial algorithm for checking the consistency and solving systems of strict and nonstrict linear inequalities in rational numbers. In the course of this work the following tasks were solved: 1. Review the known algorithms for solving this problem and related problems, as well as their implementations. 2. Modify Fourier-Motzkin elimination method of exceptions to work with systems of strict and nonstrict linear inequalities and extend it to their solution. 3. Identify a polynomial algorithm for checking the consistency of strict and nonstrict linear inequalities and extend it to their solution. 4. Implement the selected algorithms. 5. Test the implemented algorithms and experimentally compare their performance with other implementations. The paper provides a formal description of the modification of Fourier-Motzkin elimination method to work with systems containing strict inequalities, as well as an extension of this method and polynomial algorithm for checking the consistency of systems of strict and nonstrict linear inequalities to solve such systems. As a result, these algorithms were implemented in Java language, in a form that allows to work with rational numbers of arbitrary precision.
Место доступа | Группа пользователей | Действие |
---|---|---|
Локальная сеть ИБК СПбПУ | Все |
|
Интернет | Авторизованные пользователи СПбПУ |
|
Интернет | Анонимные пользователи |
|
Количество обращений: 1
За последние 30 дней: 1