Wyniki wyszukiwania - BazTech

1

A note on 1-semi-greedy bases in p-Banach spaces with 0 < p ≤ 1

Berná Pablo M., García Andrea, González David

Demonstratio Mathematica

|

2024

|

Vol. 57, nr 1

art. no. 20240047

EN

The purpose of this article is to discuss about the so-called semi-greedy bases in p-Banach spaces. Specifically, we will review existing results that characterize these bases in terms of almost-greedy bases, and, also, we analyze quantitatively the behavior of certain constants. As new results, by avoiding the use of certain classical results in p-convexity, we aim to quantitatively improve specific bounds for bi-monotone 1-semi-greedy bases.

2

Filtering Decision Rules Driven by Sequential Forward and Backward Selection of Attributes: An Illustrative Example in Stylometric Domain

Zielosko Beata, Stańczyk Urszula, Jabloński Kamil

Annals of Computer Science and Information Systems

|

2023

|

Vol. 35

833--842

EN

The paper presents investigations concerning the decision rule filtering process controlled by the estimated relevance of available attributes. In the conducted study, two search directions were used, sequential forward selection and sequential backward elimination, applied after the knowledge discovery step to the rule sets inferred from a dataset. The steps of sequential search, along with two different strategies of rule selection, were governed by three rankings obtained for variables, all related to characteristics of data and rules that can be induced, as follows, (i) a ranking based on the weighting factor referring to the occurrence of attributes in generated decision reducts, (ii) the OneR ranking exploiting short rule properties, and (iii) the proposed ranking defined through the operation of greedy algorithm for rule induction. The three rankings were confronted and compared from the perspective of their usefulness for the selection of rules performed in the two directions. The resulting sets of rules were analysed with respect to the properties of the constituent decision rules and from the point of performance for all constructed rule-based classifiers. Substantial experiments were carried out in the stylometric domain, treating the task of authorship attribution as classification. The results obtained indicate that for all three rankings and search paths it was possible to obtain a noticeable reduction of attributes while at least maintaining the power of inducers, at the same time improving characteristics of rule sets.

3

Meta-heuristic approach based on genetic and greedy algorithms to solve flexible job-shop scheduling problem

Rezaeipanah Amin, Sarhangnia Fariba, Abdollahi Mohammad Javad

Computer Science

|

2021

|

T. 22 (4)

463--488

EN

Job-shop scheduling systems are one of the applications of group technology in industry, the purpose of which is to take advantage of the physical or operational similarities of products in their various aspects of construction and design. Additionally, these systems are identified as cellular manufacturing systems (CMS). In this paper, a meta-heuristic method that is based on combining genetic and greedy algorithms has been used in order to optimize and evaluate the performance criteria of the flexible job-shop scheduling problem. In order to improve the efficiency of the genetic algorithm, the initial population is generated by the greedy algorithm, and several elitist operators are used to improve the solutions. The greedy algorithm that is used to improve the generation of the initial population prioritizes the cells and the job in each cell and, thus, offers quality solutions. The proposed algorithm is tested over the P-FJSP dataset and compared with the state-of-the-art techniques of this literature. To evaluate the performance of the diversity, spacing, quality, and run-time criteria were used in a multi-objective function. The results of the simulation indicate the better performance of the proposed method as compared to the NRGA and NSGA-II methods.

4

A Reactive Search-Based Algorithm for Scheduling Multiprocessor Tasks on Two Dedicated Processors

Aïder Méziane, Baatout Fatma Zohra, Hifi Mhand

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

257--261

EN

In this paper, we propose a reactive search-based algorithm for solving the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is characterized by a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to determine the scheduling of all tasks minimizing the execution of the last assigned task. The proposed reactive search starts with a starting greedy solution. Next, a series of local operators combined with a tabu list are introduced in order to intensify the search process. The method is also reinforced with a drop and rebuild operator that is applied for diversifying the search process. Finally, the performance of the proposed method is evaluated on a set of benchmark instances, where its provided results are compared to those achieved by a recent method available in the literature. Encouraging results have been reached.

5

Interfejs do zdalnego sterowania ploterem z funkcją rozpoznawania obrazów

Kamiński M., Morawiec M.

Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej

|

2017

|

Nr 57

37--42

PL

Maszyny numeryczne takie jak obrabiarki CNC, plotery czy drukarki 3D są coraz powszechniejsze w użytku. Na Politechnice Gdańskiej przygotowano pracę magisterską [12], której rezultaty przedstawiono w niniejszym artykule. Ze względu na objętość referatu, przedstawiono jedynie wybrane aspekty budowy plotera, aplikacji na urządzenie mobilne oraz przegląd zastosowanych algorytmów optymalizacji pod kątem szybkości rysowania. Aplikacja funkcjonuje w systemie Android, a komunikuje się z maszyną za pomocą interfejsu bluetooth. Aplikacja oferuje także możliwość optymalizacji tras, zarówno tych rysowanych, jak i nierysowanych, pokonywanych przez ploter. Jest to problem komiwojażera bez powrotu, który rozwiązany może być poprzez algorytmy: zachłanny, genetyczny, wspinaczkowy lub symulowanego wyżarzania.

EN

The topic is to build a CNC machine working as a plotter, and also create an application running on the Android operating system, which processes images, optimizes the code and allows to control the built machine. The examination is an estimation which of the methods used in this thesis is optimal and gives the best results in this type of problem, which is choosing the shortest path of the salesman problem. The purpose of the paper is to obtain the code processed by the numerical machine in the shortest possible time, which will be carried out in a short period of time with the proper accuracy of the work. Another important aspect is the implementation of an intuitive user interface that does not cause problems with support. The optimization methods used produce satisfactory results that are more or less practical depending on the problem. The effect in the form of drawn images is at a high level of accuracy. After many hours of working with the CNC machine using the created application, it can be seen that this is a useful set for both people who want to create their own images as well as for those seeking education in this field. The great advantage is that the design is very easily expandable so that it can acquire new, very useful features for a small amount of extra work in the form of adding new functionality.

6

Optymalizacja częściowych reguł asocjacyjnych względem liczby pomyłek

Zielosko B., Robaszkiewicz M.

Studia Informatica

|

2016

|

Vol. 37, nr 1

187--198

PL

Artykuł przedstawia optymalizację częściowych reguł asocjacyjnych generowanych przez algorytm zachłanny względem liczby pomyłek (błędnych zaklasyfikowań). Zaproponowana optymalizacja ma na celu: (i) uzyskanie reguł o stosunkowo dobrej jakości, które w kolejnych etapach badań zostaną wykorzystane do budowy klasyfikatorów, (ii) zmniejszenie liczby konstruowanych reguł, co ma znaczenie z punktu widzenia reprezentacji wiedzy. Praca przedstawia wyniki eksperymentalne dla zbiorów danych umieszczonych w Repozytorium Uczenia Maszynowego.

EN

In the paper, an optimization of partial association rules relative to number of misclassifications is presented. The aims of proposed optimization are: (i) construction of rules with small number of misclassifications, what is important from the point of view of construction of classifiers, (ii) decreasing the number of rules, what is important from the point of view of knowledge representation. The paper contains experimental results for data sets from UCI Machine Learning Repository.

7

A Minimum-Spanning-Tree-Inspired Algorithm for Channel Assignment in 802.11 Networks

Dolińska I., Jakubowski M., Masiukiewicz A., Rządkowski G., Piórczyński K.

International Journal of Electronics and Telecommunications

|

2016

|

Vol. 62, No. 4

379--388

EN

Channel assignment in 2.4 GHz band of 802.11 standard is still important issue as a lot of 2.4 GHz devices are in use. This band offers only three non-overlapping channels, so in crowded environment users can suffer from high interference level. In this paper, a greedy algorithm inspired by the Prim’s algorithm for finding minimum spanning trees (MSTs) in undirected graphs is considered for channel assignment in this type of networks. The proposed solution tested for example network distributions achieves results close to the exhaustive approach and is, in many cases, several orders of magnitude faster.

8

Approximation of Reset Thresholds with Greedy Algorithms

Ananichev D. S., Gusev V. V.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

221--227

EN

The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.

9

Sieci kognitywne MANET

Gajewski P., Łopatka J., Suchański M.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2014

|

nr 6

132--137

PL

Dokonano przeglądu zagadnień związanych z tworzeniem kognitywnych, mobilnych sieci doraźnych - MANET CR. Opisano dotychczasowe wyniki realizacji projektów związanych z opracowaniem i standaryzacją sieci radia kognitywnego - CR. Scharakteryzowano wybrane kognitywne rozwiązania dla mobilnych sieci doraźnych, głównie na podstawie wyników projektu CORASMA (Cognitive Radio for Spectrum Management) Europejskiej Agencji Obrony - EDA. Opisano przykład zastosowania algorytmu zachłannego dla rozproszonego zarządzania widmem w wojskowej sieci z grupowaniem węzłów. W zakończeniu omówiono drogę do uzyskania kognitywnej sieci radiowej dla potrzeb obronności kraju.

EN

In this paper a survey of the cognitive radio (CR) techniques for Mobile Ad Hoc Networks (MANET CR) is presented. The main results of up to now projects concerning development and standardization CR networks are described. The chosen solutions for MANET CR are also characterized. Here we mainly discuss the results of EDA project CORASMA, in which the greedy algorithm for frequency distributed management have been proposed for clustered MANET CR. The way to CR networks for national security is shown in the context of national and international activities in this area.

10

A Greedy Algorithm for Construction of Decision Trees for Tables with Many-Valued Decisions : A Comparative Study

Azad M., Chikalov I., Moshkov M., Zielosko B.

Fundamenta Informaticae

|

2013

|

Vol. 128, nr 1-2

1--15

EN

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction.

11

Greedy Algorithms for Construction of Approximate Tests for Decision Tables with Many-Valued Decisions

Azad M., Chikalov I., Moshkov M., Zielosko B.

Fundamenta Informaticae

|

2012

|

Vol. 120, nr 3/4

231-242

EN

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. We consider bounds on the precision of this algorithm relative to the cardinality of tests.

12

Approximate algorithm for β -decision rule optimization

Zielosko B., Moshkov M.

Studia Informatica

|

2011

|

Vol. 32, nr 2A

329-335

EN

In the paper greedy algorithm for construction of β decision rules and algorithm for construction of β -complete systems of decision rules are studied. Obtined bounds on accuracy of the considered algorithms are presented.

PL

W artykule został przedstawiony algorytm zachłanny dla konstruowania β -reguł decyzyjnych oraz dla konstruowania β -kompletnych systemów reguł decyzyjnych. Zostały zaprezentowane granice dokładności wyników uzyskiwanych za pomocą rozważanych algorytmów.

13

A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions

Kwarciak K., Formanowicz P.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2011

|

Vol. 59, nr 1

111-115

EN

In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge is a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.

14

Algorytm zachłanny dla konstruowania częściowych reguł asocjacyjnych

Zielosko B.

Studia Informatica

|

2010

|

Vol. 31, nr 2A

225-236

PL

W artykule przedstawiono sposób konstruowania częściowych reguł asocjacyjnych z wykorzystaniem algorytmu zachłannego. Podejście to jest odmienne od znanego algorytmu A priori i jego modyfikacji, wykorzystujących zbiory częste. Przedstawione wyniki badań oraz rezultaty z przeprowadzonych eksperymentów pokazują, że algorytm zachłanny pozwala konstruować stosunkowo małą liczbę krótkich, częściowych reguł asocjacyjnych o dobrej jakości, które pokrywają wszystkie obiekty danego systemu informacyjnego.

EN

The paper presents greedy algorithm for partial association rule construction. This approach is different from the known algorithm Apriori and its modifications based on frequent itemsets. Theoretical and experimental results show, that the greedy algorithm constructs relatively small number of short partial association rules which have good accuracy and cover all objects from given information system.

15

Greedy Algorithm with Weights for Decision Tree Construction

Moshkov M.Ju.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 3

285-292

EN

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

16

Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

Wyrwoł B.

Elektronika : konstrukcje, technologie, zastosowania

|

2010

|

Vol. 51, nr 9

21-23

PL

Kolorowanie grafów znajduje zastosowanie wszędzie tam, gdzie konieczny jest podział zbioru na rozłączne podzbiory wg określonego kryterium jakie spełniają lub nie elementy zbioru. Większość algorytmów kolorowania realizowana jest zwykle na drodze programowej. W sytuacji, kiedy dużą rolę odgrywają uwarunkowania czasowe, konieczna jest realizacja sprzętowa z wykorzystaniem dedykowanego układu. W artykule przedstawiony został zachłanny algorytm kolorowania wierzchołków grafu oraz jego sprzętowa implementacja w układzie programowalnym FPGA. Dodatkowo omówiona została metoda reprezentacji danych opisujących strukturę grafu i przykład wykorzystania sprzętowego modułu kolorowania grafu, wspomagającego proces dekompozycji lingwistycznej, w systemie wnioskowania przybliżonego.

EN

Graph coloring algorithms are used wherever it is necessary to divide set on disjoint subsets according to specified criteria or not they meet the elements of the set. Most of the coloring algorithms are usually implemented as a computer or microcontroller program. To reduce computing time of the coloring result it is necessary to implement hardware using a dedicated chip. The paper presents graph greedy vertex algorithm and its hardware implementation in an FPGA chip. It describes also a graph data structure and finally implementation of the graph coloring module in the fuzzy hierarchical inference system. It is used in linguistic decomposition process of the knowledge base in the stage of the partitioning the rule base.

17

Greedy Algorithm for Construction of Partial Association Rules

Moshkov M.Ju., Piliszczuk M.

Fundamenta Informaticae

|

2009

|

Vol. 92, nr 3

259-277

EN

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

18

Greedy Algorithm for Attribute Reduction

Zielosko B., Piliszczuk M.

Fundamenta Informaticae

|

2008

|

Vol. 85, nr 1-4

549-561

EN

In the paper the accuracy of greedy algorithm for construction of partial tests (superreducts) and partial decision rules is considered. Results of experiments with greedy algorithm are described.

19

Evolutionary and greedy exploration of the space of decision trees

Biedrzycki R., Arabas J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

61-68

EN

This paper addresses the issue of the decision trees induction. We define the space of all possible trees and try to find good trees by searching that space. We compare performance of an evolutionary algorithm and standard, problem-specific algorithms (ID3, C4.5).

20

Dijkstra's algorithm revisited: the dynamic programming connexion

Sniedovich M.

Control and Cybernetics

|

2006

|

Vol. 35, no. 3

599-620

EN

Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic programming should be (at least) alluded to in a proper exposition/teaching of the algorithm.