Wyniki wyszukiwania - BazTech

1

Digraph-building method for finding a set of minimal realizations of 2-D dynamic systems

Markowski K. A., Hryniów K.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2018

|

Vol. 66, nr 5

589--597

EN

This paper presents a digraph-building method designed to find the determination of realization of two-dimensional dynamic system. The main differences between the method proposed and other state-of-the-art solutions used include finding a set of realizations (belonging to a defined class) instead of only one realization, and the fact that obtained realizations have minimal size of state matrices. In the article, the proposed method is described, compared to state-of-the-art methods and illustrated with numerical examples. To the best of authors’ knowledge, the method shown in the paper is superior to all other state-of-the-art solutions both in terms of number of solutions and their matrix size. Additionally, MATLAB function for determination of realization based on the set of state matrices is included.

2

Model przydziału zasobów do zadań w przedsiębiorstwie transportowym

Izdebski M., Jacyna M.

Logistyka

|

2012

|

nr 4

PL

W artykule zdefiniowano ogólny problem przydziału, wyjaśniono pojęcie skojarzenia w grafie dwudzielnym a następnie opisano problem przydziału w przedsiębiorstwie transportowym. Wyznaczono model matematyczny przydziału, funkcję optymalizacyjną.

EN

This article defines a general assignment problem and explains definition of a matching in a bipartite graph. This paper describes an assignment problem of tasks to resources in the transport company. This article contains the mathematical allocation model of tasks, function optimization with constrains.

3

Analog Circuits Sizing Using the Fixed Point Iteration Algorithm with Transistor Compact Models

Javid F., Iskander R., Durbin F., Louerat M.-M.

International Journal of Microelectronics and Computer Science

|

2012

|

Vol. 3, nr 1

7-14

EN

This paper presents an algorithm, based on the fixed point iteration, to solve for sizes and biases using transistor compact models such as BSIM3v3, BSIM4, PSP and EKV. The proposed algorithm simplifies the implementation of sizing and biasing operators. Sizing and biasing operators were originally proposed in the hierarchical sizing and biasing methodology [1]. They allow to compute transistors sizes and biases based on transistor compact models, while respecting the designer's hypotheses. Computed sizes and biases are accurate, and guarantee the correct electrical behavior as expected by the designer. Sizing and biasing operators interface with a Spice-like simulator, allowing possible use of all available compact models for circuit sizing and biasing over different technologies. A bipartite graph , that contains sizing and biasing operators, is associated to the design view of a circuit, it is the design procedure for the given circuit. To illustrate the effectiveness of the proposed fixed point algorithm, a folded cascode OTA is efficiently sized with a 130nm process, then migrated to a 65nm technology. Both sizing and migration are performed in a few milliseconds.

4

Endomorphism monoid of diamond product of two common complete bipartite graphs

Jiarasuksakun T., Rutjanisarakul T., Thongjua W.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2010

|

Vol. 15

59--66

EN

An endomorphism of a graph G = (V, E) is a mapping f : V → V such that for all x, y ∈ V if {x, y} ∈ E, then {f (x),f (y)}∈ E. Let End(G) be the class of all endomorphisms of graph G. The diamond product of graph G = (V, E) (denoted by G ◊ G) is a graph defined by the vertex set V (G ◊ G) = End(G) and the edge set E (G ◊ G) ={{f, g} ⊂ End(G)|{f(x), g(x)} ∈ E for all x ∈ V}. Let Km,n be a complete bipartite graph on m + n vertices. This research aims to study the algebraic property of V (Km,n ◊ Km,n) = End(Km,n) after we have found that Km,n ◊ Km,n is also a complete bipartite graph on mmnn + nmmn vertices. The result shows that all of its vertices (endomorphisms) form a noncommutative monoid.

5

Alternatywna metoda rozwiązywania kwadratowego zagadnienia przydziału

Schiff K.

Logistyka

|

2010

|

nr 2

PL

Kwadratowy problem przydziału polega na takim umieszczeniu fabryk (obiektów) w lokalizacjach, aby całkowity koszt wyrażony jako suma iloczynów odległości między obiektami i strumieni towarów przepływających między tymi obiektami był jak najmniejszy. Artykuł ten przedstawia nowy sposób modelowania problemu przy wykorzystaniu grafów dwudzielnych i nowy sposób rozwiązania problemu, krok po kroku, polegający na znalezieniu maksymalnego dopasowania o minimalnej wadze z uwzględnieniem fizycznego umiejscowienia fabryk (obiektów) w lokalizacjach.

EN

A new method for quadratic assignment problem is presented. The problem is modeled by a bipartite graph. Hungarian method is used for finding the solution: the assignment with minimum costs is found, but this solution must take into consideration of real objects localizations.

6

Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

Kosowski A., Kuszner Ł.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

75-81

PL

W artykule podano algorytm rozproszonego, samostabilizującego się kolorowania grafów. Rozważamy spójny system niezależnych, asynchronicznych węzłów, z których każdy posiada tylko i wyłącznie lokalną wiedzę o systemie. Bez względu na stan początkowy system powinien osiągnąć pożądany stan globalny, wykonując w każdym z węzłów algorytm dany w postaci zbioru reguł. Zgodnie z naszą wiedzą przedstawiony algorytm jest pierwszym samostabilizującym algorytmem dokładnego kolorowania grafów dwudzielnych, działającym w wielomianowej liczbie ruchów.

EN

In the paper a distributed self-stabilizing algorithm for graph coloring is given. We consider a connected system of autonomous asynchronous nodes, each of which has only local information about the system. Regardless of the initial state, the system must achieve a desirable global state by executing a set of rules assigned to each node. Our method based on spanning trees is applied to give the first (to our knowledge) self-stabilizing algorithms working in a polynomial number of moves, which color bipartite graphs with exactly two colors.

7

O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

Giaro K., Janczewski R.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 136

67-73

PL

Problem przydziału częstotliwości to zagadnienie, które formułuje się zazwyczaj następująco: na pewnym obszarze znajduje się grupa nadajników radiowych, którym trzeba przydzielić częstotliwości w taki sposób, żeby nie zakłócały się podczas nadawania i aby szerokość wykorzystanego przez nie pasma częstotliwości była minimalna. Zagadnienie to modeluje się zazwyczaj na gruncie teorii grafów za pomocą trzech pojęć: grafów interferencji, kontrastowych pokolorowań i T-rozpiętości. Niniejszy artykuł poświęcony jest złożoności obliczeniowej tego modelu; zawiera jego dokładny opis, dowód tego, że wyznaczanie T-rozpiętości i optymalnych pokolorowań kontrastowych jest NP-trudne nawet dla grafów dwudzielnych oraz wielomianowy algorytm wyznaczający optymalne pokolorowania kontrastowe dla tzw. częściowych k-drzew.

EN

Frequency assignment problem (FAP) can be formulated as follows: there is a group of transmitters situated in a certain region of a plane; a channel is to be assigned to each of them in such a way that there is no interference during transmitting and the span of used frequency band is minimal. The paper is devoted to the computational complexity of the graph-theoretical model of FAP based on three notions: interference graphs, T-colorings and the T-span. We describe the model, prove that the problem of computing the T-span is NP-hard even for bipartite graphs and present a polynomial time algorithm for finding optimal T-coloring for the socalled partial k-trees.

8

Zwarte kolorowanie małych grafów dwudzielnych. Eksperymenty komputerowe

Giaro K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 131

75-83

PL

Rozważamy pewien stosunkowo nowy model kolorowania krawędziowego grafów zwany zwartym kolorowaniem. Polega on na przypisaniu krawędziom grafu liczb naturalnych w taki sposób, by kolorowanie to było legalne oraz kolory krawędzi incydentnych do dowolnego wierzchołka tworzyły zwarte przedziały. Okazuje się, że nie wszystkie grafy można kolorować w sposób zwarty. Praca prezentuje w skrócie podstawowe własności zwartego kolorowania. Dalsza część opisuje przebieg kilku doświadczeń komputerowych mających na celu weryfikację pewnych hipotez dotyczących zwartego kolorowania na małych grafach dwudzielnych.

EN

In this paper we consider some relatively new model of edge coloring called compact. It consists in ascribing natural numbers to the edges of a graph in such a way that obtained coloring is legal and colors of edges incident to any vertex constitute compact intervals. It occurs that not all graphs can by colored in this way. This article shortly describes basic properties of compact coloring and presents a few computer experiments performed to verify on small bipartite graphs some hypotheses concerning compact coloring.

9

O problemie przydziału częstotliwości, awartych T-pokolorowaniach i grafach dwudzielnych

Janczewski R.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 131

85-93

PL

Tytułowy problem przydziału częstotliwości to następująco sformułowane zagadnienie: na pewnym obszarze znajduje się grupa nadajników radiowych, którym trzeba przydzielić częstotliwości w taki sposób, aby nie zakłócały się podczas nadawania. Tak postawiony problem staje się trudny dopiero w momencie, gdy interesuje nas nie tyle jego rozwiązanie, co znalezienie rozwiązania spełniającego pewne dodatkowe warunki, np. minimalizującego szerokość wykorzystanego pasma częstotliwości. W niniejszej pracy zajmujemy się sytuacjami, w których tytułowy problem ma rozwiązanie korzystające z pasma częstotliwości o minimalnej szerokości i równocześnie wykorzystuje wszystkie częstotliwości pośrednie (znajdujące się pomiędzy najmniejszą a największą z wykorzystanych częstotliwości). Przypominamy teoriografowy model Hale'a dla rozważanego zagadnienia związany z grafami interferencji oraz r-pokolorowaniami, i formułujemy w języku teorii grafów szereg warunków równoważnych z istnieniem rozwiązania o opisanych wcześniej własnościach.

EN

The frequency assignment problem can be defined as follows: there are several transmitters situated in a certain region of a plane; assign channels to them (one transmitter receives one channel) in such a way that interference during transmitting is avoided. It is easy to find a solution to this problem. The problem becomes hard only when we are interested in finding solutions that satisfy some additional requirements, e.g. minimize the span of frequency band. In the paper we investigate these cases in which the problem has a solution that uses a frequency band of minimal span and uses all intermediate channels, i.e. these channels which lie between the smallest and the largest channel used. We recall graph-theoretic model of the problem due to Hale and state in graph-theoretic terms several conditions that are equivalent to the existence of solutions satisfying requirements described earlier.

10

Minimalizacja średniego czasu obsługi zadań w systemie równoległego przydziału zasobów

Małafiejski M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

273-285

PL

W pracy, obok podsumowania dotychczasowych wyników dotyczących problemu minimalizacji średniego czasu przepływu zadań w systemie równoległego przydziału zasobów, zaprezentowano własności sumy multichromatycznej, w szczególności nowe oszacowania. Ponadto zaproponowano rozszerzenie klasycznej notacji trójpolowej w celu uwzględnienia nowych wyników dotyczących złożoności wybranych problemów szeregowania zadań na podstawie wybranych klas grafów konfliktowych.

EN

In the paper we consider the problem of scheduling multiprocessor tasks on dedicated processors. The author extends the notation alfa / beta / gamma to take into consideration new results concerning the complexity of the problem restricted to the special families of conflicting graphs. Moreover, some new properties of the multichromatic sum aare presented.