Wyniki wyszukiwania - BazTech

1

Multiprocessor Scheduling Problem with Release and Delivery Times

Grigoreva Natalia

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

263--269

EN

The multiprocessor scheduling problem is defined as follows: tasks have to be executed on several parallel identical processors. For each task we know release time, processing time and delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The objective is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by giving priority to the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. It is proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.

2

An Exact Two-Phase Method For Optimal Camera Placement In Art Gallery Problem

Alihodzic Adis, Delalic Sead, Hasic Damir

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

215--222

EN

It is well-known that determining the optimal number of guards which can cover the interior of a simple nonconvex polygon presents an NP-hard problem. The optimal guard placement can be described as a problem which seeks for the smallest number of guards required to cover every point in a complex environment. In this paper, we propose an exact twophase method as well as an approximate method for tackling the mentioned issue. The proposed exact approach in the first phase maps camera placement problem to the set covering problem, while in the second phase it uses famous state-of-the-art CPLEX solver to address set covering problem. The performance of our combined exact algorithm was compared to the performance of the approximate one. According to the results presented in the experimental analysis, it can be seen that the exact approach outperforms the approximate method for all instances.

3

Best approximation in quotient probabilistic normed space

Sen M., Nath S., Tripathy B. C.

Journal of Applied Analysis

|

2017

|

Vol. 23, nr 1

53--57

EN

In this article, we study the best approximation in quotient probabilistic normed space. We define the notion of quotient space of a probabilistic normed space, then prove some theorems of approximation in quotient space are extended to quotient probabilistic normed space.

4

ACBC-Adequate Association and Decision Rules Versus Key Generators and Rough Sets Approximations

Kryszkiewicz M.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 1/2

65--85

EN

In this paper, we propose an ACBC-evaluation formula, which delivers a flexible way of formulating different kinds of criteria for association and decision rules. We prove that rules with minimal antecedents that fulfill ACBC-evaluation formulae are key generators, which are patterns of a special type. We also show that a number of types of rough set approximations of decision classes can be expressed based on ACBC-evaluation formulae. We prove that decision rules preserving respective approximations of decision classes are rules that satisfy an ACBC-evaluation formula and that antecedents of such optimal decision rules are key generators, too. A number of properties related to particular measures of association rules and key generators are derived.

5

A Relational Logic for Spatial Contact Based on Rough Set Approximation

Düntsch I., Orłowska E., Wang H.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 1/2

191--206

EN

In previous work we have presented a class of algebras enhanced with two contact relations representing rough set style approximations of a spatial contact relation. In this paper, we develop a class of relational systems which is mutually interpretable with that class of algebras, and we consider a relational logic whose semantics is determined by those relational systems. For this relational logic we construct a proof system in the spirit of Rasiowa-Sikorski, and we outline the proofs of its soundness and completeness.

6

Spaced Seed Design Using Perfect Rulers

Egidi L., Manzini G.

Fundamenta Informaticae

|

2014

|

Vol. 131, nr 2

187--203

EN

A widely used class of approximate pattern matching algorithms work in two stages, the first being a filtering stage that uses spaced seeds to quickly discards regions where a match is not likely to occur. The design of effective spaced seeds is known to be a hard problem. In this setting, we propose a family of lossless spaced seeds for matching with up to two errors based on mathematical objects known as perfect rulers. We analyze these seeds with respect to the tradeoff they offer between seed weight and the minimum length of the pattern to be matched. We identify a specific property of rulers, namely their skewness, which is closely related to the minimum pattern length of the derived seeds. In this context, we study in depth the specific case of Wichmann rulers and investigate the generalization of our approach to the larger class of unrestricted rulers. Although our analysis is mainly of theoretical interest, we show that for pattern lengths of practical relevance our seeds have a larger weight, hence a better filtration efficiency, than the ones known in the literature.

7

On the Accuracy of Rough Approximations of Regular Languages

Torres G. M.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 4

533--545

EN

In this paper we attempt to measure the accuracy of approximations of regular languages by languages in +−varieties (as defined by Eilenberg). These approximations are upper approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given +−variety. In our approach, the accuracy of an approximation is measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i, j-definite and k-testable approximations.

8

An Analysis of Probabilistic Approximations for Rule Induction from Incomplete Data Sets

Clark P. G., Grzymala-Busse J. W., Hippe Z. S.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 3

365--379

EN

The main objective of our research was to test whether the probabilistic approximations should be used in rule induction from incomplete data. For our research we designed experiments using six standard data sets. Four of the data sets were incomplete to begin with and two of the data sets had missing attribute values that were randomly inserted. In the six data sets, we used two interpretations of missing attribute values: lost values and “do not care” conditions. In addition we used three definitions of approximations: singleton, subset and concept. Among 36 combinations of a data set, type of missing attribute values and type of approximation, for five combinations the error rate (the result of ten-fold cross validation) was smaller than for ordinary (lower and upper) approximations; for other four combinations, the error rate was larger than for ordinary approximations. For the remaining 27 combinations, the difference between these error rates was not statistically significant.

9

Proof Methods for Corecursive Programs

Gibbons J., Hutton G.

Fundamenta Informaticae

|

2005

|

Vol. 66, nr 4

353--366

EN

Recursion is a well-known and powerful programming technique, with a wide variety of applications. The dual technique of corecursion is less well-known, but is increasingly proving to be just as useful. This article is a tutorial on the four main methods for proving properties of corecursive programs: fixpoint induction, the approximation (or take) lemma, coinduction, and fusion.

10

A View on Rough Set Concept Approximations

Bazan J., Nguyen H.S., Szczuka M.

Fundamenta Informaticae

|

2004

|

Vol. 59, nr 2,3

107--118

EN

The concept of approximation is one of the most fundamental in rough set theory. In this work we examine this basic notion as well as its extensions and modifications. The goal is to construct a parameterized approximation mechanism making it possible to develop multi-stage multi-level concept hierarchies that are capable of maintaining acceptable level of imprecision from input to output.

11

Self-tuning control under input variance constraint

Królikowski A., Kubiak T., Lemos J.M.

Systems Science

|

2003

|

Vol. 29, nr 1

135-149

EN

In this paper, a variance-constrained self-tuning control is considered for a plant given by discrete-time ARMAX model. A minimization of a quadratic cost function under constraint is approached by LQG and stochastic approximation (SA) methods, as well as by MUSMAR, a predictive adaptive controller based on multiple identifiers. The optimization algorithms obtained are simulated for unstable plant model and different structures of the controller.

12

Research for fuzzy Duoma debt model and its fuzzy solution

Bing-Yuan C.

Systems Science

|

2003

|

Vol. 29, nr 3

81-93

EN

Debt model is generalized first in this paper; and then an extensively used fuzzy debt model is built by a concept of inverse image defined by fuzzy functions. Third, a proof is demonstrated of the existence of fuzzy solutions as well as dependence upon initial values and parameters of solutions. Fourth, a series of solving methods is advanced with problems discussed on this system's stability. And finally, Duoma debt model with a triangle fuzzy function is solved.

13

Expert schemes for the obtaining of discrete models for LTI systems using real sampling and parameter identification

De La Sen M., Garrido A.J., Barambones O., Maseda F.J.

Systems Science

|

2003

|

Vol. 29, nr 2

95-112

EN

In this paper, we present an expert network scheme designed to obtain discrete transfer functions for LTI systems under real sampling of finite duration rather than an instantaneous ideal one. For this purpose, the expert network handles two different identification methods to derive parametric discrete models techniques of reduced mathematical complexity from measured input-output data series. One of the methods is based on a typically used least-squares minimization, while the other one is based on the Leverrier's algorithm; that is, using a data series of the impulse response of the system to identify a parametric discrete model. These techniques are of particular practical interest when the continuous-time system is unknown or when dealing with discrete-time systems whose analytical expression becomes very complex due, for instance, to the use of finite duration real sampling. The expert network improves the discretization process implementing a biestimation mechanism that switches to the model that provides a better performance at each estimation instant considered for different values of the hold order.

14

Application of uncertain variables to a project management under uncertainty

Bubnicki Z.

Systems Science

|

2003

|

Vol. 29, nr 2

65-79

EN

The paper concerns task and resource allocation in a complex of operations which may be considered as a part of the knowledge-based project management system. The brief overview of concepts and results concerning the allocation problem under uncertainty described by uncertain variables is presented. An application of two-level decomposition of the complex and the allocation taking into account uncertain and random parameters in the description of the operations are discussed. Two simple examples illustrate the approach presented.

15

Application of uncertain and random variables to knowledge-based pattern recognition

Bubnicki Z., Szala M.

Systems Science

|

2003

|

Vol. 29, nr 3

37-52

EN

The paper is concerned with recognition problems based on relational knowledge representations with two kinds of unknown parameters: uncertain parameters characterized by certainty distributions given by an expert and random parameters described by probability distributions. After a short presentation of uncertain variables and their application to the knowledge-based recognition under uncertainty, the different versions in two formulations of the recognition problem are discussed. In the first formulation two unknown parameters (uncertain and random) in the relation describing the set of object to be recognized are considered. The second formulation concerns the case with one unknown parameter in the knowledge representation, described by a certainty distribution with a random parameter or by a probability distribution with an uncertain parameter. Simple examples illustrate the presented approach. The application of so called C-uncertain variables and the description of the recognition system with three-level uncertainty are included.

16

An affine Gaussian process approach for nonlinear system identification

Gregorcic G., Lightbody G.

Systems Science

|

2003

|

Vol. 29, nr 2

47-63

EN

The traditional Gaussian Process model is not analytically invertible. In order to use the Gaussian Process model for Internal Model Control, numerical approaches have to be used to find the inverse of the model. The numerical search for the inverse of each sample increases the already large computational load. To reduce the computation load an Affine Local Gaussian Process Model Network, as a combination of traditional Local Model Network and non-parametrical Gaussian Process Prior approach, is proposed in this paper. A novel algorithm for structure optimisation is introduced and exact inverse of the proposed network is derived. An Affine Local Gaussian Process Model Network and its inverse are illustrated on a simulated example.

17

Frequency analysis of nonlinear dynamical systems and the control of vibration

Banks S. P., Tomas-Rodriguez M.

Archives of Control Sciences

|

2003

|

Vol. 13, no. 3

269-279

EN

In this paper we shall consider nonlinear vibrating systems which can be written in form x= A(x)+B(x)u. We shall introduce a sequence of linear, time-varying approximations which can be studied in the frequency domain. A spectral optimal control theory will be developed.

18

Some introductory remarks on modeling of the electromagnetic phenomena

Krawczyk A., Kotowski R.

Journal of Technical Physics

|

2002

|

Vol. 43, no 4

417-418

19

Motional finite element simulation of magnetic brakes and solid rotor induction machines

De Gersem H., Hameyer K.

Journal of Technical Physics

|

2002

|

Vol. 43, no 4

389-397

EN

The torques of a magnetic brake and a solid rotor induction machine, fed by sinusoidal voltage sources, are simulated by a motional finite element method. Oscillatory solutions occurring for motional models with elevated velocities, are prevented by adaptive mesh refinement relying upon intermediate solutions stabilised by upwinded finite element test functions. A relaxed successive approximation deals with the non-linear material properties. The connections of the conductors and windings within the finite element model to external loads, impedances and supplies are represented by an electric circuit and added to the system of equations. The technical examples indicate the advantages of the motional formulation.

20

Aproksymacja i stabilizacja odporna wielowymiarowych układów liniowych stacjonarnych ze skupionymi, współmiernymi opóźnieniami

Kozera W.

Studia / Wyższa Szkoła Morska w Szczecinie

|

1999

|

nr 31

1-179

PL

Istnienie opóźnień w procesach transportu, mieszania, spalania, ewolucji, fluktuacji ekonomicznych, biurokracji sprawia, że aby efektywnie sterować tymi procesami należy uwzględnić opóźnienia w ich modelach matematycznych. W niniejszej pracy przedstawiono oryginalne metody skończenie wymiarowej aproksymacji równań różniczkowo-różnicowych, opisujących wielowymiarowe układy liniowe stacjonarne ze skupionymi opóźnieniami, za pomocą zwyczajnych równań różniczkowych lub różnicowych. Ułatwia to znacznie analizę oraz syntezę tych układów. Ponadto zaproponowano sposoby wyznaczania łatwych do realizacji technicznej stabilizujących sprzężeń zwrotnych ciągłych i dyskretno-ciągłych (hybrydowych), odpornych na niedokładności modelowania. Można je łatwo uogólnić na przypadek syntezy kompensatorów odpornych takżena niepewności strukturalne wynikające np. ze zmian parametrów, bądź nieliniowości układu oraz spełniające szereg dodatkowych wymagań jakościowych (kompensatory wielozadaniowe). Prezentowane metody zostały zweryfikowane na licznych, odpowiednio dobranych przykładach, a uzyskane wyniki świadczą o ich dużej efektywności. Praca zawiera jedynie własne rozwiązania autora rozpatrywanych zagadnień, które porównano z ważniejszymi, praktycznymi rozwiązaniami znanymi z literatury.

EN

Due to time delays in processes of transport, mixing, burning, evolution, economic fluctuation, bureaucracy etc., the effective control of these processes requires accounting for these delays in mathematical models of the processes. This work presents original methods of finite-dimensional approximations of differential-difference equations describing multivariable linear time-invariant systems with commensurate delays. These approximations are performed bymeans of ordinary differential of difference equations. This substantially facilitates the analysis and synthesis of the systems. Moreover, presented are ways of determining stabilizing continuous and discrete-continnuous (hybrid) robust control laws attenuating the unstructured uncertainties of modelling, easy for technical realization. They can be readily generalized to cover the synthesis of robust compensators attenuating also structured uncertainties resulting e.g. either from parameter variations or nonlinear disortion of the system and satisfying a number of additional performance specifications (multipurpose compensators). The described methods have been verified by many relevant examples. The results prove high effectiveness of the methods. The work contains only the author's solutions of the problems and compares them with major practical solutions found in the literature on the subject.