Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: subset sum

Sortuj według:

Ogranicz wyniki do:

Handling Non-determinism in Spiking Neural P Systems : Algorithms and Simulations

Carandang Jym Paul, Cabarle Francis George C., Adorna Henry Natividad, Hernandez Nestine Hope S., Martínez-del-Amor Miguel Ángel

Fundamenta Informaticae

2019

Vol. 164, nr 2-3

139--155

Spiking Neural P system is a computing model inspired on how the neurons in a living being are interconnected and exchange information. As a model in embrane computing, it is a non-deterministic and massively-parallel system. The latter makes GPU a good candidate for accelerating the simulation of these models. A matrix representation for systems with and without delay have been previously designed, and algorithms for simulating them with deterministic systems was also developed. So far, non-determinism has been problematic for the design of parallel simulators. In this work, an algorithm for simulating non-deterministic spiking neural P system with delays is presented. In order to study how the simulations get accelerated on a GPU, this algorithm was implemented in CUDA and used to simulate non-uniform and uniform solutions to the Subset Sum problem as a case study. The analysis is completed with a comparison of time and space resources in the GPU of such simulations.

Solving SUBSET SUM by Spiking Neural P Systems with Pre-computed Resources

Leporati A., Gutiérrez-Naranjo M.

Fundamenta Informaticae

2008

Vol. 87, nr 1

61-77

Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre–computed resources are given in advance, provided that their structure is “regular” and they do not contain neither “hidden information” that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as SUBSET SUM. In particular, we first propose a semi–uniform family of spiking neural P systems in which every system solves a specific instance of SUBSET SUM. Then, we exploit a technique used to calculate ITERATED ADDITION with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of SUBSET SUM of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.

Non-injectivity and knapsacks

Koskinen J.A.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

163-180

This paper is a cryptographically motivated study of the knapsack, its subset sum function and its inverse relation, the decipherment function. The novelty is that the subset sum function is not assumed to be injective. Instead, various forms of ``jectivity'' are introduced, distinguished by the amount of subsets that are allowed to have the same sum. Besides charting several general properties of knapsacks and the functions the paper reports on experiments that looked for dense knapsacks. Also a concrete construction of a relatively dense easily decipherable knapsack is presented.