Wyniki wyszukiwania - BazTech

1

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.

2

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.

3

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.

4

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.

5

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.

6

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.

7

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.

8

Efektywność algorytmów dynamicznego kolorowania grafów - zastosowania w sieciach optycznych WDM

Borowiecki P., Sidorowicz E.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 144

135-142

PL

W pracy tej formułujemy problem dynamicznego kolorowania grafów, analizujemy efektywność algorytmu zachłannego First-Fit (w skrócie FF) oraz wskazujemy na jego zastosowanie w problemie przydziału długości fali w sieciach optycznych WDM. W szczególności podajemy dolne i górne oszacowania dobroci algorytmu FF. Wskazujemy istnienie klas grafów G, dla których różnica pomiędzy wartością rozwiązania generowanego przez algorytm FF(G) a wartością optymalną OPT(G) może być dowolnie duża. Z drugiej strony dowodzimy, że dla dowolnego grafu G używanego przez nas w problemie przydziału długości fali zawsze zachodzi FF(G) < 20PT(G).

EN

Within this paper we introduce a problem of dynamie graph coloring and analyze effectiveness of greedy algorithm First-Fit (FF for short). We point out an important application of a new model to wavelength assignment problem in WDM networks. In particular, we give lower and upper bounds on the performance ratio of FF. We prove that for some classes of graphs G, the difference between the solution value FF(G) and optimum value OPT(G) may be arbitrarily large. On the other hand, for all graphs, that we used in the wavelength assignment problem FF(G) < 20PT(G) holds.

9

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).

10

Algorytm zachłanny dla pewnego problemu szeregowania zadań czasowo-zależnych

Gawiejnowicz S., Kurc W., Pankowska L.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

139-150

PL

W pracy jest rozważany jednomaszynowy problem szeregowania zadań czasowo-zależnych. Czas wykonywania pj zadania j jest funkcją czasu t rozpoczęcia tego zadania, pj(t) = 1 + alfa jt, gdzie alfa j > O dla j = O, 1, ... ,n. Zadania są niepodzielne, niezależne, nie ma czasów gotowości ani linii krytycznych, a kryterium optymalności uszeregowania jest łączny czas zakończenia wykonywania zadań. Dla danego ciągu współczynników alfa j, j = O, 1, ... ,n definiowana jest sygnatura, której własności stanowią podstawę do skonstruowania algorytmu zachłannego.

EN

A single machine time-dependent scheduling problem is considered. The processing time pj of job j is a function of the starting time t of the job, pj(t) = 1 + alfa jt, where alfa j > 0 for j = 0, 1, ... ,n. Jobs are non-preemptable and independent, there are neither ready times nor deadlines, and the criterion of optimality is the total completion time. On the ground of properties of a signature for a given sequence of coefficients alfa j, j = 0,1, ... ,n a greedy algorithm for the problem is constructed.

11

Prowadzenie połączeń przez kanał dla problemów MID-DCRP

Chmiel K.

Studia z Automatyki i Informatyki

|

1998

|

T. 23

53-82

PL

W pracy rozważana jest podklasa problemów o maksymalnej gęstości międzykolumnowej (MID-DCRP) klasy problemów gęstych DCRP. Przebadana została struktura tej klasy z punktu widzenia charakterystyki rozwiązania (Is, II, Ip), gdzie Is oznacza liczbę ścieżek, a II i Ip liczbę odpowiednio, lewych i prawych kolumn dodatkowych. Na tej podstawie wskazany został wielomianowy algorytm, prowadzący do optymalnego rozwiązania przy dwustopniowym kryterium liczby ścieżek i liczby kolumn.

EN

In the paper the class of maximum intercolumn density dense channel routing problems (MID-DCRP) is considered. The structure of the class with respect to the solution characteristic (Is, II, Ip) is investigated, where Is denotes the number of tracks and II, Ip denote the number of left and right additional columns, respectively. Presented results indicate a polynomial time algorithm, leading to the optimal solution in terms of the two level criterion: number of tracks - number of columns.