PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 29

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  hypergraph
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available Subdivision of hypergraphs and their colorings
Iradmusa Moharram N.
Opuscula Mathematica
|
2020
|
Vol. 40, no. 2
271--290
EN
In this paper we introduce the subdivision of hypergraphs, study their properties and parameters and investigate their weak and strong chromatic numbers in various cases.
2
Content available Algorytm selekcji wykorzystujący teorię hipergrafów
Stefanowicz Ł., Wiśniewski R., Adamski M.
Pomiary Automatyka Kontrola
|
2014
|
R. 60, nr 7
516--518
PL
Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.
EN
The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one.
3
Content available remote Reduction of the Memory Size in the Microprogrammed Controllers
Adamski M., Barkalov A., Wiśniewski R., Lipiński J.
Przegląd Elektrotechniczny
|
2013
|
R. 89, nr 11
114-117
EN
The method of reduction of the control memory size in the microprogrammed controllers is proposed in the article. The idea is based on the hypergraph theory. The concurrent microoperations are encoded together thus the total volume of the memory is reduced. In order to receive the proper microinstruction, an additional module – microinstruction decoder is also prepared. The idea of the proposed method is illustrated by an example. Moreover, the result of performed experimental investigations is presented, as well.
PL
W artykule zaproponowano metodę redukcji pojemności pamięci sterowników mikroprogramowanych. Metoda bazuje na teorii hipergrafów. Mikrooperacje parami kompatybilne są kodowane wspólnie, dzięki czemu redukcji ulega całkowita pojemność pamięci sterownika mikroprogramowanego. Do struktury układu wprowadzono dodatkowy moduł, dekodera mikroinstrukcji. Jednostka ta jest odpowiedzialna za odkodowanie pierwotnych danych. Idea proponowanej metody zilustrowano przykładem. Ponadto, przeprowadzono także badania eksperymentalne, których celem była weryfikacja skuteczności proponowanej metody. Wyniki badań pokazują, że pierwotna pamięć sterownika jest redukowana średnio o 21%.
4
Content available remote Analiza tablic decyzyjnych z wykorzystaniem monotonicznego rachunku sekwensów
Tkacz J., Adamski M.
Przegląd Elektrotechniczny
|
2013
|
R. 89, nr 6
256--259
PL
W artykule przedstawiono nowatorski sposób analizy systemów regułowych z wykorzystaniem symbolicznego wnioskowania w monotonicznej logice sekwentów Gentzena. Badany system dyskretny jest opisywany w postaci tablicy decyzyjnej. Celem analizy systemu jest usunięcie zbytecznych kolumn w tablicy decyzyjnej oraz nieistotnych symboli zmiennych logicznych w jej poszczególnych wierszach. Efektywny aparat wnioskowania w logice formalnej umożliwia sprawne wyznaczanie transwersal krawędzi hipergrafu rozróżnialności.
EN
The paper presents a new methodology for symbolic reduction of multivalued decision tables, currently intensively used for compact behavioral specifications of logic controllers. As an example the well known problem of simplification of a set of several logic rules with many variables is chosen. As a completely new, original solution, the formal automated reasoning based on Gentzen propositional calculus together with hypergraph theory are jointly used. The clique-transversal symbolic calculation is performed by means of effective reasoning in Gentzen calculus.
5
Content available Zastosowanie hipergrafów w procesie selekcji implikantów prostych
Wiśniewski R., Stefanowicz Ł.
Pomiary Automatyka Kontrola
|
2013
|
R. 59, nr 11
1195--1197
PL
W referacie przedstawiona została nowa koncepcja selekcji implikantów prostych w procesie dwupoziomowej minimalizacji funkcji logicznych. Aktualnie znane metody selekcji bazują na połączeniu metod dokładnych z przybliżonymi. W artykule zaproponowana została nowatorska metoda selekcji, która w całości opiera się na algorytmach dokładnych, poprzez zastosowanie teorii hipergrafów. Najbardziej istotną zaletą proponowanego rozwiązania jest wielomianowa złożoność obliczeniowa całej operacji selekcji, która w przypadku ogólnym ma złożoność wykładniczą.
EN
: In the paper a new idea for the selection of prime implicants is proposed. The method is based on the two-level minimization process of the Boolean functions, according to the Quine-McCluskey approach. Initially, the set of prime implicants for the logic function ought to be calculated. Next, the selection process is applied to achieve the minimal formula. Such an operation is a typical covering problem and in general case it has exponential computational complexity. In the paper we propose a new prime implicants selection method. An idea is based on the hypergraph theory. The prime implicants table is formed as a selection hypergraph. If the selection hypergraph belongs to the Exact Transversal Hypergraph class (xt-class), the solution may be obtained in a polynomial time, which is not possible in a general case. The proposed method is illustrated by an example. All necessary steps are shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function.
6
Content available Towards al-based distributed lighting control systems
Wojnicki I., Sędziwy A., Kotulski L.
Automatyka / Automatics
|
2012
|
Vol. 16, no. 2
189-198
EN
The paper discusses an approach which is targeted at obtaining maximal benefits of contemporary advanced lighting systems. The benefits are expressed in terms of improved energy efficiency (i.e. lower power consumption) or citizens ąuality of life. Applying proposed solution one could use intelligent control methods which functionality goes far beyond simple preset lighting scenarios as it is present in existing commercial systems. The main problem tackled here is a high complexity of control algorithms related to a size of a state space compound of lighting profiles, fixtures' working parameters and varying environment conditions. The proposed method, designed for solving this issue, is using decom-posable graph representations of the environment under control, and multiagent system deployed on it. An important component of the system is a rule-based engine, adapting lighting control parameters to actual environment needs.
PL
Artykuł przedstawia podejście nastawione na maksymalizację korzyści płynących z zastosowania zaawansowanych systemów oświetlenia tj. poprawę wydajności energetycznej (np. zmniejszenie poboru energii) oraz polepszenie jakości życia. Proponowane rozwiązanie, bazujące na koncepcji inteligentnego sterowania, udostępnia funkcje dotychczas niespotykane w oferowanych komercyjnie produktach. Problemem, w przypadku systemów oświetlenia, jest duża złożoność obliczeniowa algorytmów sterujących. Związane jest to z rozbudowaną przestrzenią stanów dla takiego systemu reprezentującą różne profile oświetlenia, parametry pracy punktów świetlnych oraz warunki środowiska. Zaproponowane podejście rozwiązuje ten problem poprzez zastosowanie dekomponowalnej reprezentacji grafowej oraz środowiska wieloagentowego przetwarzającego takie grafy. Istotnym elementem rozwiązania jest system regułowy określający parametry sterowania dla poszczególnych punktów świetlnych w zależności od zapotrzebowania.
7
Content available Wyznaczanie optymalnego oświetlenia wspomagane metodami formalnymi
Sędziwy A.
Pomiary Automatyka Robotyka
|
2011
|
R. 15, nr 12
135-136
PL
W niniejszym artykule przedstawiam kierunki swoich badań oraz motywację ich podjęcia. Dotyczą one budowy formalnego modelu wspierającego tworzenie inteligentnych systemów projektowania i sterowania oświetleniem ulicznym.
EN
The article presents my recent work and its future direction including their motivation and background. Developing formal methods underlying intelligent systems of design and control of street lighting are in my research area.
8
Content available Zastosowanie teorii hipergrafów w procesie analizy systemów dyskretnych opisanych sieciami Petriego
Adamski M., Wiśniewska M.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 8
945-947
PL
W artykule zaprezentowane zostały nowe metody wspomagające proces analizy systemów dyskretnych opisanych sieciami Petriego. Relacje w prototypowanym systemie dyskretnym są odwzorowane hiper-grafem. Dzięki temu projektowany, wbudowany, rekonfigurowany sterownik logiczny może zostać poddany efektywniejszemu procesowi analizy z wykorzystaniem nowych algorytmów, związanych z traktowanymi łącznie teoriami hipergrafów i sieci Petriego. Wykorzystano między innymi takie procedury jak dopełnienie, dualizm, transwersale, transwersale dokładne oraz kolorowanie hipergrafu. W artykule w sposób nieformalny wykorzystano autorskie twierdzenia, wspomagające cały proces projektowania sterowników. Szczególną uwagę zwrócono na nowe sposoby analizy systemów dyskretnych, opisanych sieciami Petriego, takie jak częściowa weryfikacja poprawności specyfikacji sterownika na podstawie struktury hipergrafu współbieżności oraz zastosowanie transwersal do-kładnych w procesie wyodrębniania powiązanych ze sobą procesów sekwencyjnych.
EN
In the paper application of the hypergraph theory to analysis of discrete-systems described by means of Petri Nets is proposed. The relations between local states are represented by hypergraph vertices whose edges correspond to the global states. Therefore, the analysis of a prototype system can be performed by more effective operations supported by the hypergraph theory as well as the Petri net theory (such as dualism, hypergraph complement, transversals, exact transversals, hypergraph colouring). In the paper the authors propose application of the concurrency hypergraph to the analysis of a discrete-system. Such a structure refers to the traditional concurrency graph, however it keeps information about global states of the analysed system. Moreover, the concurrency hypergraph has some unique properties, which can lead to reduction in the computational complexity of some algorithms of the analysis. All minimal transversals in the concurrency hypergraph are also exact transversals. Therefore, such a hypergraph can be applied also to the decomposition process of a discrete-system, which is described by a Petri Net. After the analysis, a controller described by a Petri Net can be decomposed into concurrent sub-nets (concurrent automata). Each exact transversal of the concurrency hypergraph refers to the concurrent automata. The proposed solution allows significantly reducing the computational complexity to a polynomial. The traditional methods, based on the coloring of a concurrency graph are exponential time algorithms, thus they are defined to be NP-complete.
9
Content available Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów
Wiśniewska M., Adamski M., Wiśniewski M.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 6
675-678
PL
Redukcja pojemności pamięci jest istotnym etapem w procesie projektowania systemów dyskretnych. Często pojemność prototypowanej pamięci przekracza rozmiar docelowego bloku pamięci (np. w układach programowalnych FPGA). Najczęściej stosowanym rozwiązaniem jest redukcja rozmiaru mikroinstrukcji w projektowanym systemie. Algorytm bazuje na wyznaczeniu, a następnie selekcji klas kompatybilności poszczególnych mikrooperacji. W artykule zaprezentowane zostaną 2 autorskie algorytmy selekcji klas kompatybilności. Metody opierają się o wykorzystanie teorii hipergrafów (zastosowanie pokrycia wierzchołkowego). Proponowane rozwiązania zostaną gruntownie przeanalizowane oraz porównane z metodą tradycyjną, bazują na przekształceniach macierzowych.
EN
The problem of memory size reduction is a very important part of design process of discrete systems. The prototyped memory size very often exceeds the size of memory blocks offered by programmable devices (in example FPGAs). One of the most popular solutions to this problem is memory size reduction. The reduction process is based on selection of the compatibility classes of microoperations. Three methods of selection of compatibility classes are presented in the paper. The first one is a well-known method of selection, to which the fast reduction algorithm is applied. The algorithm bases on the matrix operations, which can also be represented as reduction of the hypergraph incidence matrix. In each step some vertices and edges are reduced. The reduced matrix holds the final result. The two other solutions introduced in the paper are based on the idea of computation of the minimal transversal (vertices covering) of hypergraphs. Proper microop-erations are represented by the hypergraph vertices, while compatibility classes are described by the hyperedges. Therefore, any method of hypergraph transversal calculation can be applied to achieve the selection. In the paper the authors propose and analyse the effectiveness of backtracking and greedy algorithms. The proposed solutions are compared with the traditional method, which is based on transformation of the hypergraph incidence matrix. The obtained results of experiments are analysed and discussed in detail.
10
Content available Dekompozycja sterowników współbieżnych z zastosowaniem transwersal dokładnych hipergrafu
Wiśniewska M., Adamski M., Wiśniewski R.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 8
851-853
PL
W artykule zaprezentowany został nowatorski sposób dekompozycji cyfrowych sterowników współbieżnych opisanych z wykorzystaniem sieci Petriego na podsieci typu automatowego. W proponowanym rozwiązaniu relacje pomiędzy miejscami sieci Petriego określone za pomocą hipergrafu współbieżności. W odróżnieniu od dotychczas stosowanych rozwiązań, w artykule zaproponowano autorską koncepcję wyznaczania zbiorów niewspółbieżnych, która bazuje na obliczeniu transwersal dokładnych w hipergrafie współbieżności.
EN
In the paper a new decomposition method of a control system into concurrent automata is presented. The control unit is described as a Petri Net which is further decomposed into concurrent subnets. The main idea of the proposed method is application of exact transversals to the decomposition algorithm. Contrary to the traditional solutions, the authors propose the application of a concurrency hypergraph instead of a standard concurrency graph. The concurrent subnets are found by calculation of exact transversals in the hypergraph. The selection of concurrent automata is also performed with application of exact transversals. Such a solution allows achieving the optimal results (the fewest number of concurrent automata). The proposed concurrency hypergraph has some unique properties. First of all, it is defined to be an exact hypergraph. Therefore, each exact transver-sal in such a hypergraph refers to the concurrent automata. Moreover, all minimal transversals of the hypergraph are also exact transversals. Finally, computation and selection of all exact transversals can be performed in polynomial-time, and this is the most important advantage of the proposed method. The traditional solutions are based on the coloring of a concurrency graph, thus the complexity is NP-complete. All steps that are required in order to perform the decomposition of a controller described by a Petri Net are shown. The proposed method is compared with the traditional solution. Finally, the preliminary results of experiments are presented and discussed.
11
Content available Autorski system wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego
Wiśniewska M.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 8
948-950
PL
W referacie przedstawiono autorski system komputerowy wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego. System sterujący zostaje opisany za pomocą sieci Petriego, na podstawie której określany jest graf lub hipergraf współbieżności. Macierz incydencji hipergrafu współbieżności stanowi dane wejściowe systemu Hippo. Aplikacja oferuje przeprowadzenie dekompozycji z zastosowaniem operacji bazujących na teorii hipergrafów różnymi metodami i umożliwia wybór najlepszej z nich.
EN
The dedicated CAD system Hippo for automatic decomposition of Petri Nets into concurrent automata is presented. At the beginning the reachability graph is calculated for the Petri Net which may be easily represented by a concurrency graph or a hypergraph. Such structures are input for main decomposition process. There are several methods for decomposition of Petri Nets. The most popular one is based on the colouring of the concurrency graph, however recently, a few new algorithms based on hypergraph theory have appeared. Contrary to a concurrency graph, application of a concurrency hypergraph to the decomposition of Petri Net enables using new and fast methods. The solution can be found by colouring of a concurrency hypergraph, calculating its complement or finding exact transversals. Especially, the last method is most interesting, because it allows reducing the computational complexity to a polynomial. In the paper the decomposition process is presented in detail. There are several ways of decomposition presented (based on colouring graphs/hypergraphs), calculating hypergraph complement or finding its exact transversals. Each of the presented method was implemented in Hippo. The decomposition process is automated. As the input of the Hippo system, a description of a concurrency graph or hypergraph is required. Based on this structure and a selected decomposition method, Hippo finds and prints results. The obtained results are presented in graphical and text form.
12
Content available Automatyczny system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów
Wiśniewska M.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 7
726-728
PL
W artykule zaprezentowany został autorski system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów. Narzędzie Hippo składa się ze zbioru bibliotek, realizujących najważniejsze operacje z zakresu teorii grafów i hipergrafów (m. in. kolorowanie, pokrycie, dopełnienie, dualizm, itd.), które zostały zrealizowane pod kątem ich zastosowania w dekompozycji systemów dyskretnych. Głównym zadaniem systemu jest usprawnienie oraz automatyzacja procesu dekompozycji systemów dyskretnych stosowanych m.in. w projektowaniu zaawansowanych układów cyfrowych (redukcja rozmiaru pamięci, selekcja klas kompatybilności, minimalizacja funkcji logicznych, dekompozycja automatów cyfrowych). Opracowany system Hippo umożliwia przeprowadzenie automatycznego procesu dekompozycji z zastosowaniem różnych algorytmów (zarówno grafowych, jak i hipergrafowych), w efekcie pozwalając wybrać użytkownikowi najkorzystniejsze rozwiązanie.
EN
In the paper a dedicated CAD system Hippo for automatic decomposition of discrete systems is presented. The tool consists of a set of libraries. Each library was designed as a separate module to solve the particular problem from the field of the graph and hypergraph theories (among others: vertex coloring, vertex covering, transversal computation, dualism, computation of the graph and hypergraph complement). The main task of the system is to improve the process of decomposition of discrete systems (for example: reduction of the microinstruction length, selection of the compatibility classes, decomposition of concurrent automata). The Hippo system consists of eight main modules:- complement -calculation of graph/hypergraph complement;- coloring - five methods of coloring of graph and hypergraph (four greedy and one backtracking);- transversal - four methods of transversals computation (fast reduction algorithm, greedy, backtracking, mixed fast reduction and greedy);- exact transversals - the calculation of the exact transversals is based on the Knuth DLX algorithm, the main advantage of such a solution is polynomial computational time in case of exact hypergraphs;- dualism (only for hypergraphs) - calculates the dual hypergraph;- converting graph to hypergraph;- converting hypergraph to graph;- conversion of the graph/hypergraph description to the TeX format.In the paper particular libraries are described in detail. Moreover, the stand-alone application (Hippo) is shown. Finally, an example of automatic decomposition of the discrete system is presented. All steps and required operations are described.
13
Content available Zastosowanie transwersali hipergrafów w minimalizacji pojemności pamięci systemów dyskretnych
Wiśniewska M., Wiśniewski R., Adamski M.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 7
777-779
PL
Algorytm redukcji pojemności pamięci systemów dyskretnych bazuje na wyznaczeniu i selekcji klas kompatybilności poszczególnych mikrooperacji. Proces selekcji klas kompatybilności jest zaliczany do problemów z klasy NP-trudnych. W artykule zaprezentowano metodę selekcji klas kompatybilności opierającą się o wyznaczenie transwersali hipergrafów. Proponowane rozwiązanie zostało gruntownie przeanalizowane oraz porównane z metodami tradycyjnymi, bazującymi na przekształceniach macierzowych.
EN
The problem of memory size minimisation is a very important part of the design process of a discrete system. Very often the volume of the prototyped memory exceeds the size of memory blocks offered by programmable devices (like FPGAs or CPLDs). One of the most popular solution to this problem is memory size minimisation. The reduction of the memory is achieved thanks to selection of the compatibility classes of the microoperations. Such a problem is NP-hard, therefore many various algorithms have been developed. Most of them are based on the graph and matrix theories. In the paper there is proposed a method for memory size reduction in which the hypergraph theory is applied. A hypergraph permits to store and reduce information about the compatibility classes in comparison with the traditional graphs. The memory size minimisation is reached thanks to the computation of its transversal (vertices cover). Any known transversal algorithm can be used in order to calculate the selection of compatibility classes. Four different covering methods of hypergraphs are presented and compared. All steps that are required in order to perform the microinstruction length reduction of discrete systems are shown. The proposed method is compared with the traditional solution. Finally, the detailed results of experiments are presented and discussed.
14
Content available Domination hypergraphs of certain digraphs
Sonntag M., Teichert H. M.
Opuscula Mathematica
|
2010
|
Vol. 30, no. 2
179-191
EN
If D = (V,A) is a digraph, its domination hypergraph DH(D) = (V, E) has the vertex set V and e ⊆ V is an edge of DH(D) if and only if e is a minimal dominating set of D. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.
15
Zastosowanie kolorowania hipergrafów w procesie dekompozycji równoległej automatów współbieżnych
Wiśniewska M., Wiśniewski R.
Metody Informatyki Stosowanej
|
2010
|
nr 2 (23)
151-157
PL
W referacie zapręzentowano metodę dekompozycji sieci Petriego na podsieci typu automatowego, opartą o kolorowanie hipergrafu osiągalności. Zaprezentowano szczegółowe wyniki przeprowadzonych badań, w których proponowane rozwiązanie porównano z klasycznymi metodami opartymi o kolorowanie grafów osiągalności. Wyniki eksperymentów pokazały, że prezentowany algorytm jest znacznie szybszy od dotychczas stosowanych rozwiazań (nawet 1600 razy w przypadku sieci zawierających 200 miejsc).
EN
In the article a decomposition method of concurrent automata is presented. The main advantage of the presented method is the availability of hypergraph theory usage instead of graph one. Hypergraph contains all information about the relations between hyperedges while in graph all cliques have to be found. Furthermore, the process of finding concurrent automata can be more effective because of hypergraph coloring usage. The computation of the hypergraph coloring is less complex than adequate graph coloring. Let us point out that the results of both solutions, either hypergraph and graph coloring are here the same.
16
Redukcja binarnych tablic decyzyjnych z wykorzystaniem automatycznego wnioskowania
Adamski M., Tkacz J., Wrzesińska B.
Metody Informatyki Stosowanej
|
2010
|
nr 3 (24)
5-12
PL
W artykule przedstawiono sposób redukcji binarnych tablic decyzyjnych z wykorzystaniem systemu komputerowego dowodzenia twierdzeń w zdaniowym rachunku Gentzena [1, 4]. Binarna tablica decyzyjna przedstawia słabo określoną funkcję logiczną wielu zmiennych [6, 7]. Przykładową tablicę zaczerpnięto z książki [5], ze względu na zamieszczony w niej pełny i systematyczny opis wszystkich kroków minimalizacji funkcji i stopniowo uzyskiwanych rezultatów częściowych. Proponowany sposób minimalizacji symbolicznej postaci funkcji logicznej umożliwia w stosunkowo sprawny sposób otrzymywanie rezultatów dokładnych, wraz z formalnym dowodem ich gwarantowanej poprawności.
EN
The paper presents a new methodology for symbolic reduction of binary decision tables, currently intensively used for compact behavioral specifications of logic controllers. As an example the well known problem of simplification of a set of boolean relations with many variables and large sets of don’t care condition is chosen. They described also a special class of Boolean function called weakly specified or strongly unspecified. As a completely new, original solution, the formal automated reasoning based on Gentzen propositional calculus together with hypergraph theory are jointly used. The clique-transversal symbolic calculation is performed by means of effective reasoning in Gentzen calculus, giving the formal proof of all transformations.
17
Content available remote Reduction of the Microinstruction Length in the designing process of Microprogrammed Controllers
Wiśniewska M., Wiśniewski R., Adamski M.
Przegląd Elektrotechniczny
|
2009
|
R. 85, nr 7
203-206
EN
The problem of the microinstruction length reduction is a very important part of the designing process of the microprogrammed controllers. Such a problem is NP-hard, therefore many various algorithms have been developed. Almost all proposed ideas are based on the traditional graph theory and its modifications (heuristics, stochastic, etc.). In the paper, we propose the method of microinstruction length reduction, where the hypergraph theory is applied. A hypergraph permits to store and reduce the information about the compatibility classes in comparison with traditional graphs. The microinstruction length reduction is reached thanks to the calculation of the dual hypergraph and computation of its minimum transversal (minimal vertices cover). All steps that are required in order to perform the microinstruction length reduction of microprogrammed controllers will be shown. The proposed method will be illustrated by way of example and compared with the traditional solution, based on the graph theory.
PL
Problem redukcji rozmiaru mikroinstrukcji jest ważnym etapem w procesie projektowania sterowników mikroprogramowanych. Jest to problem NP-trudny, dlatego też powstało wiele metod poszukujących rozwiązania. Zdecydowana większość zaproponowanych algorytmów bazuje na tradycyjnej teorii grafów. W artykule zaprezentowano nowatorską metodę redukcji rozmiaru mikroinstrukcji sterowników mikroprogramowanych, częściowo opierającą się na rozwiązaniach klasycznych. Metoda bazuje na wykorzystaniu teorii hipergrafów do wyznaczenia klas kompatybilności dla poszczególnych mikrooperacji. Mikrooperacje, które są parami kompatybilne mogą zostać zakodowane z wykorzystaniem mniejszej liczby bitów. Dzięki temu rozmiar pamięci układu mikroprogramowanego może zostać w znacznym stopniu zmniejszony. Zaproponowane rozwiązanie bazuje na wyznaczeniu hipergrafu dualnego, a następnie znalezieniu jego minimalnej transwersali (minimalnego pokrycia wierzchołkowego). Idea metody zostanie zilustrowana przykładem. Pokazane zostaną wszystkie kroki, jakie są niezbędne do zaprojektowania zmodyfikowanego układu pamięci. Zaproponowana metoda zostanie porównana z rozwiązaniami klasycznymi, bazującymi na teorii grafów.
18
Content available Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych
Wiśniewska M.
Pomiary Automatyka Kontrola
|
2009
|
R. 55, nr 8
575-577
PL
Problem redukcji rozmiaru mikroinstrukcji jest ważnym etapem w procesie projektowania sterowników mikroprogramowanych. Jest to problem NP-trudny, dlatego też powstało wiele metod poszukujących rozwiązania. Zdecydowana większość zaproponowanych algorytmów bazuje na tradycyjnej teorii grafów. W artykule przedstawiono nową metodę redukcji rozmiaru mikroinstrukcji pamięci sterowników mikroprogramowanych. Algorytm bazuje na reprezentacji klas kompatybilności mikrooperacji z zastosowaniem teorii hipergrafów, a redukcja rozmiaru mikroinstrukcji obliczana jest na podstawie najmniejszej transwersali hipergrafu.
EN
A microprogrammed controller (also called microprogrammed control unit) consisting of two main parts is one of realizations of the control unit. The first part is responsible for addressing microinstructions that are kept in the control memory. The role of the second part is to hold and generate adequate microinstructions. Typically, the control memory is implemented as a ROM or RAM memory. Many controllers have a long microinstruction width. It may cause serious problems in the prototyping process. If the design is realized as a System-On-Programmable-Chip (SoPC), the memory can be implemented with dedicated memory blocks of Field Programmable Gate Arrays (FPGAs). However, if the microinstruction length exceeds the length of the dedicated memory block offered by an FPGA, the controller's memory ought to be decomposed. In case of controllers implemented as a System-On-Chip (SoC), the memory is treated as an independent module. It means that each additional bit in the microinstruction width increases the total cost of the memory and the whole device. Therefore, the microinstruction length reduction is a very important part of the designing process of the microprogrammed controllers in a digital system. In the paper, we propose the method of microinstruction length reduction, where the hypergraph theory is applied. The microinstruction length reduction is reached thanks to the calculation of the dual hypergraph and computation of its minimum transversal (minimal vertices cover).
19
Content available remote Metodyka ustalania kolejności montażu z użyciem hipergrafu, grafu skierowanego i macierzy stanów
Suszyński M., Ciszak O., Żurek J.
Archiwum Technologii Maszyn i Automatyzacji
|
2009
|
Vol. 29, nr 4
103-111
PL
W artykule przedstawiono metodę wyznaczania kolejności montażu wyrobu z wykorzystaniem hipergrafu i grafu skierowanego. Matematyczną reprezentację digrafu struktury wyrobu opisano za pomocą macierzy stanów oraz macierzy grafu. Do wyszukiwania najlepszej kolejności montażu jednostek montażowych wykorzystano algorytm Dijkstry. Artykuł kończą wnioski z przeprowadzonych badań.
EN
The paper presents a method of product assembly sequence with the use of digraph and directed graph. The mathematic representation of product structure digraph has been displayed with employment of state matrix and graph matrix. Searching for the best solutions within the order of assembly units was conducted with Dijkstry algorythm application. The final part of the analysis presents the results of the study.
20
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
Obszarski P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
79-84
PL
Problem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować za pomocą hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy, jak za pomocą modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania oraz jak rozwiązać problemy dwukryterialne.
EN
Problem of scheduling multiprocessor tasks on dedicated machines can be modeled by hypergraphs. There are a few classes of hypergraphs for which polynominal time algorithms for scheduling with total cost criterion are known. Our aim is to show that other criteria and also bicriterial problems can be solved by the use of total cost criterion.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.