title: ÐÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð° Ð²Ð¸Ð·ÑÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ Ð½ÐµÐºÐ¾ÑÐ¾ÑÑÑ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ Ð·Ð°Ð´Ð°Ñ Ð¿Ð¾Ð¸ÑÐºÐ°
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Application for visualization several reductions of search problems
Creators: name: ÐÑÐ·Ð½ÐµÑÐ¾Ð², ÐÐ²Ð°Ð½
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2022
Subjects: Ð·Ð°Ð´Ð°ÑÐ° Ð¿Ð¾Ð¸ÑÐºÐ°
np-Ð¿Ð¾Ð»Ð½Ð¾ÑÐ°
ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ðµ
java
javafx
Ð²Ð¸Ð·ÑÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹
search problem
np-completness
reduction
reductions visualization

description: ÐÐ°Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° ÑÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ñ Ð´Ð»Ñ Ð²Ð¸Ð·ÑÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ ÑÑÐ°Ð¿Ð¾Ð² ÑÑÐµÑ Ð²ÑÐ±ÑÐ°Ð½Ð½ÑÑ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ Ð¾Ð´Ð½Ð¸Ñ Ð·Ð°Ð´Ð°Ñ Ð¿Ð¾Ð¸ÑÐºÐ° (NPâÐ¿Ð¾Ð»Ð½ÑÑ Ð·Ð°Ð´Ð°Ñ) Ðº Ð´ÑÑÐ³Ð¸Ð¼: ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ðµ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¾ Ð²ÑÐ¿Ð¾Ð»Ð½Ð¸Ð¼Ð¾ÑÑÐ¸ Ðº Ð·Ð°Ð´Ð°ÑÐµ Ð¾ 3-Ð²ÑÐ¿Ð¾Ð»Ð½Ð¸Ð¼Ð¾ÑÑÐ¸,ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ðµ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¾ 3-Ð²ÑÐ¿Ð¾Ð»Ð½Ð¸Ð¼Ð¾ÑÑÐ¸ Ðº Ð·Ð°Ð´Ð°ÑÐµ Ð¾ Ð½ÐµÐ·Ð°Ð²Ð¸ÑÐ¸Ð¼Ð¾Ð¼ Ð¼Ð½Ð¾Ð¶ÐµÑÑÐ²Ðµ, ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ðµ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¾ Ð½ÐµÐ·Ð°Ð²Ð¸ÑÐ¸Ð¼Ð¾Ð¼ Ð¼Ð½Ð¾Ð¶ÐµÑÑÐ²Ðµ Ðº Ð·Ð°Ð´Ð°ÑÐµ Ð¾ Ð²ÐµÑÑÐ¸Ð½Ð½Ð¾Ð¼ Ð¿Ð¾ÐºÑÑÑÐ¸Ð¸. Ð Ð¿ÑÐ¾ÑÐµÑÑÐµ Ð²ÑÐ¿Ð¾Ð»Ð½ÐµÐ½Ð¸Ñ Ð´Ð°Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÑ ÑÐµÑÐ°Ð»Ð¸ÑÑ ÑÐ»ÐµÐ´ÑÑÑÐ¸Ðµ Ð·Ð°Ð´Ð°ÑÐ¸: ÐÐ·ÑÑÐµÐ½Ð¸Ðµ ÑÐµÐ¾ÑÐµÑÐ¸ÑÐµÑÐºÐ¾Ð¹ ÑÐ°ÑÑÐ¸ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ NP-Ð¿Ð¾Ð»Ð½ÑÑ Ð·Ð°Ð´Ð°Ñ. Ð ÐµÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ Ð·Ð°Ð´Ð°Ñ Ð¿Ð¾Ð¸ÑÐºÐ° Ð½Ð° ÑÐ·ÑÐºÐµ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸ÑÂ Java.Ð¡Ð¾Ð·Ð´Ð°Ð½Ð¸Ðµ Ð¾ÐºÐ¾Ð½ Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ñ Ð´Ð»Ñ Ð²Ð¸Ð·ÑÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ð¸ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ñ Ð·Ð°Ð´Ð°Ñ Ð¿Ð¾Ð¸ÑÐºÐ°. Ð¡Ð±Ð¾ÑÐºÐ° Ð¿ÑÐ¾ÐµÐºÑÐ° Ð´Ð»Ñ Ð´Ð¾ÑÑÐ°Ð²ÐºÐ¸ ÐºÐ¾Ð½ÐµÑÐ½Ð¾Ð¼Ñ Ð¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°ÑÐµÐ»Ñ. Ð ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ Ð´Ð°Ð½Ð½Ð¾Ð¹ ÑÐ°Ð±Ð¾ÑÑ Ð±ÑÐ»Ð° ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐ°Ð½Ð° Ð¿ÑÐ¾Ð³ÑÐ°Ð¼Ð¼Ð°, Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´ÑÑÐ°Ñ ÑÐºÐ°Ð·Ð°Ð½Ð½ÑÐµ Ð²ÑÑÐµ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ñ Ð¾Ð´Ð½Ð¾Ð¹ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¿Ð¾Ð¸ÑÐºÐ° Ðº Ð´ÑÑÐ³Ð¾Ð¹. ÐÑÐ»Ð° ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐ°Ð½Ð° Ð²Ð¸Ð·ÑÐ°Ð»Ð¸Ð·Ð°ÑÐ¸Ñ ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐ¾Ð² Ð²ÑÐ¿Ð¾Ð»Ð½ÐµÐ½Ð¸Ñ ÐºÐ°Ð¶Ð´Ð¾Ð³Ð¾ Ð¸Ð· ÑÑÐµÑ ÑÐ°Ð³Ð¾Ð² ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ Ð¿Ð¾Ð´ Ð½Ð¾Ð¼ÐµÑÐ°Ð¼Ð¸ 1 Ð¸ 2 Ð¾Ð´Ð½Ð¾Ð¹ Ð·Ð°Ð´Ð°ÑÐ¸ Ð¿Ð¾Ð¸ÑÐºÐ° Ðº Ð´ÑÑÐ³Ð¾Ð¹. ÐÐ»Ñ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ñ Ð¿Ð¾Ð´ Ð½Ð¾Ð¼ÐµÑÐ¾Ð¼ 3 Ð±ÑÐ»Ð¾ ÑÐ¿ÑÐ¾ÐµÐºÑÐ¸ÑÐ¾Ð²Ð°Ð½Ð¾ Ð¾ÐºÐ½Ð¾ Ð´Ð»Ñ Ð¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°ÑÐµÐ»Ñ, Ð½Ð¾ Ð²Ð·Ð°Ð¸Ð¼Ð¾Ð´ÐµÐ¹ÑÑÐ²Ð¸Ðµ Ñ Ð¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°ÑÐµÐ»ÑÑÐºÐ¸Ð¼Ð¸ Ð´Ð°Ð½Ð½ÑÐ¼Ð¸ Ð½Ðµ Ð½Ð°ÑÑÑÐ¾ÐµÐ½Ð¾.
description: 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.