Wyniki wyszukiwania - BazTech

1

Grafy losowe

Rybarczyk K.

Wiadomości Matematyczne

|

2015

|

T. 51, Nr 1

7--24

PL

Uznaje się, że graf losowy po raz pierwszy został wykorzystany w 1947 w pracy Erdősa. Został on wtedy użyty do wyznaczenia oszacowania dolnego liczby Ramseya. Analiza własności grafów losowych, jako obiektów będących samodzielnym przedmiotem badań, została zapoczątkowana o wiele później dwiema pracami Erdősa i Rényiego, które ukazały się na przełomie lat pięćdziesiątych i sześćdziesiątych. Prace te wyznaczyły kierunki badań, charakter stawianych pytań dotyczących grafów losowych, a także pozostawiły wiele interesujących problemów otwartych, które nadal są inspiracją dla matematyków. Artykuł ten ma na celu przedstawić w sposób przystępny zagadnienia poruszane w teorii grafów losowych i kierunki jej rozwoju. Zaczniemy od trzech klasycznych modeli grafów losowych. Następnie zaprezentujemy podstawowe problemy rozpatrywane w pracach Erdősa i Rényiego i opiszemy, jak wpłynęły one na kierunki badań dotyczących grafów losowych. Później przedstawimy niektóre metody dowodowe wykorzystywane w teorii. Opiszemy także jeden z wielu przykładów zastosowań grafów losowych w innych dziedzinach nauki. Zakończymy przykładem nowego kierunku badań z pogranicza dziedzin matematyki, który jest ściśle powiązany z teorią grafów losowych.

2

The comparison of genetic algorithms which solve orienteering problem using complete and incomplete graph

Ostrowski K., Koszelew J.

Zeszyty Naukowe Politechniki Białostockiej. Informatyka

|

2011

|

Z. 8

61-77

EN

The purpose of this work was to compare two forms of genetic algorithm (complete and incomplete graph version) which solves Orienteering Problem (OP). While in most papers concerning OP graph is complete and satisfies triangle inequality, in our versions such assumptions may not be satisfied. It could be more practical as transport networks are graphs which do not have to satisfy those conditions. In such cases, graphs are usually complemented with fictional edges before they can be used by classic OP solving algorithms which operate on complete graphs. This paper answers the question: Is it better (in terms of results quality and time consumption) to transform graphs to classic OP form before running algorithm (complete graph version) or to solve OP on graphs without any assumptions and changes (incomplete graph version)? The computer experiment was conducted on the real transport network in Poland and its results suggest that it is worth checking both versions of the algorithm on concrete networks.

PL

Celem pracy było porównanie dwóch odmian algorytmu (wersja dla grafu pełnego i niepełnego) rozwiązujących Orienteering Problem (OP). W większości artykułów dotyczących OP graf jest pełny, a jego krawędzie spełniają nierówność trójkąta, natomiast w naszej wersji takie założenia mogą nie być spełnione. Może to być bardziej praktyczne ponieważ sieci transportowe są grafami, ktore nie muszą spełniać tych warunków. W takich przypadkach grafy są zazwyczaj uzupełniane fikcyjnymi krawędziami, a następnie działają na nich algorytmy rozwiązujące klasyczną wersje OP, które operują na grafie pełnym. Artykuł odpowiada na pytanie: czy pod względem jakości wyników i czasu obliczeń lepiej jest przekształcać graf do klasycznej formy OP przed uruchomieniem algorytmu w wersji dla grafu pełnego czy rozwiązywać OP na grafie niezmienionym i nie spełniającym dodatkowych założeń (wersja dla grafu niepełnego)? Eksperyment został przeprowadzony na prawdziwej sieci transportowej w Polsce, a jego wyniki sugerują, że warto sprawdzać obie wersje algorytmu na konkretnych sieciach.

3

Projektowanie topografii systemów VLSI. Cz. 1, Style i etapy projektowania, rozmieszczanie modułów

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 3

451-468

PL

Projektowanie układów VLSI wymaga stosowania systemów projektowania wspomaganych komputerowo. Niniejsza praca jest pierwszą częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. Opisano różne style topografii oraz przykłady układów dla poszczególnych stylów. Następnie, przedstawiono etapy projektowania topografii: podział, planowanie układu, rozmieszczenie, trasowanie połączeń oraz weryfikacja. Planowanie układu zostało szczegółowo omówione, ze względu na podobieństwa łączące ten etap z rozmieszczaniem. Przedstawiono problem rozmieszczania modułów. Omówiono sposoby estymacji długości połączeń. Opisano metody minimalizacji opóźnień w układzie. Przedstawiono stosowane metody rozmieszczania modułów.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. This paper the first part of the survey of the cell placement techniques for digital VLSI circuits. Design styles used in VLSI circuits are described. Layouts of Standard Cell, Gate Array, Sea-of-Gates and Field Programmable Gate Array are presented. Then the physical design flow, which includes partitioning, becouse this stage is similar to the placement problem. The cell placement problem and placement techniques are describes. VLSI cell placement phase of the physical design process. Cell placement, which is a ver difficult optimization problem, has proved to be a np. - compete. The goail of the VLSI cell placement is to arrange all the cells on a placement carrier while minimizing an objective or cost function. The most commonly used objectives of the placement are to minimize the total estimated wire length and the interconnect congestion, and to meet the timing requirements for critical nets. Commonly used wire length estimates for the cell placement are presented. The timing driven placement methods are described. The algorithms used for the cell placement are presented.

4

Estymacja długości połączeń w układach VLSI

Kos A., Nagórny Z.

Elektronika : konstrukcje, technologie, zastosowania

|

2005

|

Vol. 46, nr 11

47-49

PL

Znane są różne sposoby estymacji długości połączeń w układach VLSI. Nie zawsze istnieje zgodność między wartością estymowanej długości połączeń a rzeczywistą długością połączeń po ich wyznaczeniu. Przedstawiono sposób wyznaczenia współczynników korygujących wartość estymowanej długości połączeń, w zależności od liczby końcówek w danym węźle układu elektronicznego. Określono wartości współczynników dla dwóch sposobów estymacji długości połączeń: half-perimeter oraz grafu pełnego. Wartości współczynników wyznaczono na podstawie porównania estymowanej długości połączeń bez współczynników z długością wyznaczoną na podstawie zmodyfikowanego algorytmu Prima, który jest stosowany do prowadzenia połączeń w układach VLSI. Przedstawiono rezultaty rozmieszczania modułów, uzyskane z zastosowaniem otrzymanych współczynników.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. The physical design phases are described: floorplanning, placement and routing. The cell placement is a very important phase of the physical design process. The most commonly used objective of the placement is to minimize the total wire length. Placement algorithms use a wire length estimate to minimize the total wire length, because each intermediate configurations routing takes too much time. The most commonly used methods to estimate the total wire length are halfperimeter and complete graph measures. There is not a good correlation between these estimations and the actual total wire length after routing. In this paper a method to adjust the halfperimeter and complete graph measures using correction factors is presented. The correction factor of the net wire length estimate is a function of the number of net terminals. The actual net wire length is calculated by using a modified Prim algorithm and the Lee algorithm.

5

Wielomiany koherencyjne dla grafów zwykłych

Paszkiewicz A.

Biuletyn Wojskowej Akademii Technicznej

|

2001

|

Vol. 50, nr 1

149-164

PL

W pracy przedstawiono wielomiany opisujące prawdopodobieństwa spójności grafów zwykłych i pełnych do stopnia 17. Opracowany program komputerowy pozwala wyznaczyć te wielomiany dla stopni wyrażających się wielkimi liczbami naturalnymi. Zebrano wielomiany koherencyjne dla wszystkich niezomorficznych grafów zwykłych o liczbie wierzchołków do 6 włącznie.

EN

There are presented polynomials describing probabilities of connectness of ordinary and full graphs of degree up to 17. Moreover there exists complete computer program allowing us to appoint such polynomials for degrees expressed by huge natural numbers. All coherential polynomials for all ordinary graphs with up to 6 vertexes are collected in the article.