Программа визуализации некоторых сведений задач поиска: выпускная квалификационная работа бакалавра: направление 02.03.02 «Фундаментальная информатика и информационные технологии» ; образовательная программа 02.03.02_02 «Информатика и компьютерные науки»

Кузнецов, Иван Алексеевич

Details

	Table	Card	RUSMARC

Title:	Программа визуализации некоторых сведений задач поиска: выпускная квалификационная работа бакалавра: направление 02.03.02 «Фундаментальная информатика и информационные технологии» ; образовательная программа 02.03.02_02 «Информатика и компьютерные науки»
Creators:	Кузнецов Иван Алексеевич
Scientific adviser:	Герасимов Александр Сергеевич
Organization:	Санкт-Петербургский политехнический университет Петра Великого. Институт компьютерных наук и технологий
Imprint:	Санкт-Петербург, 2022
Collection:	Выпускные квалификационные работы; Общая коллекция
Subjects:	задача поиска; np-полнота; сведение; java; javafx; визуализация сведений; search problem; np-completness; reduction; reductions visualization
Document type:	Bachelor graduation qualification work
File type:	PDF
Language:	Russian
Level of education:	Bachelor
Speciality code (FGOS):	02.03.02
Speciality group (FGOS):	020000 - Компьютерные и информационные науки
DOI:	10.18720/SPBPU/3/2022/vr/vr22-3038
Rights:	Доступ по паролю из сети Интернет (чтение, печать, копирование)
Record key:	ru\spstu\vkr\19749

Allowed Actions: –

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Данная работа посвящена реализации программы для визуализации этапов трех выбранных сведений одних задач поиска (NP‑полных задач) к другим: сведение задачи о выполнимости к задаче о 3-выполнимости,сведение задачи о 3-выполнимости к задаче о независимом множестве, сведение задачи о независимом множестве к задаче о вершинном покрытии. В процессе выполнения данной работы решались следующие задачи: Изучение теоретической части сведений NP-полных задач. Реализация сведений задач поиска на языке программирования Java.Создание окон программы для визуализации сведения задач поиска. Сборка проекта для доставки конечному пользователю. В результате данной работы была разработана программа, производящая указанные выше сведения одной задачи поиска к другой. Была разработана визуализация результатов выполнения каждого из трех шагов сведений под номерами 1 и 2 одной задачи поиска к другой. Для сведения под номером 3 было спроектировано окно для пользователя, но взаимодействие с пользовательскими данными не настроено.

This work aimed to the implementation of a program for visualizing the stages of three selected reductions of some search problem (NP‑complete problem) to other: reduction of satisfiability problem into 3-satisfiability problem, reduction of 3-satisfiability problem into independent set problem, reduction of independent set problem into vertex cover problemIn the process of developing this work, the following tasks were solved: Research theoretical part of reductions of NP-complete problems. Develop Java program to complete the reductions. Design application windows for visualization of search problem reductions. Build project for delivery to final user. As a result, a program was developed that completes the above reductions of one search problem into another. A visualization of the results of performing each of the three steps of reductions from one search problem into another, under numbers 1 and 2, was developed. For reduction number 3, a window was designed for the user, but interaction with user data was not developed.

Document access rights

	Network		User group		Action
	ILC SPbPU Local Network		All
	Internet		Authorized users SPbPU
	Internet		Anonymous

Usage statistics

Access count: 2
Last 30 days: 0
Detailed usage statistics