Search
Search results for: GRAFY%20KUBICZNE
-
Nowa wizja dla gdańskiej Wyspy Spichrzów
PublicationArtykuł obejmuje analize proponowanych obecnie rozwiązań w zakresie zagospodarowania obszaru gdańskiej Wyspy Spichrzów. Omówiono w nim koncepcję stworzoną przez S. Fiszera jako syntezy prac warsztatowych, prowadzonych w ciągu ostatniego roku przez firmę GRAY International.
-
Dynamics of Field Line Mappings in Magnetic Flux Tubes
PublicationWe study the topological constraints on the dynamics of magnetic field lines in flux tubes. Our approach is based on the application of the topological invariant: fixed point index. We consider periodic flux tubes and find various restrictions on the field lines that come from the sequence of fixed point indices of iterations. We also analyze the case of a tube with a cylindrical obstacle, deducing some special dynamical properties...
-
Paired bondage in trees
PublicationW pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.
-
Kolorowanie hipergrafów
PublicationHipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.
-
Robustness of the Rotor-router Mechanism
PublicationW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Przeanalizowano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera w przypadku wystąpienia zaburzeń w grafie: usunięcie krawędzi, dodanie krawędzi, lokalna zamiana portów
-
Detekcja obiektów graficznych i ekstrakcja ich parametrów
PublicationW rozdziale przedstawiono wybrane metody wykrywania obiektów na obrazach, a także sposoby ich opisywania za pomocą parametrów umożliwiających późniejszą klasyfikację. Zaprezentowano algorytmy analizy obrysu obiektu (podział linii brzegowej na tokeny, wykorzystanie symetrii) oraz analizy tekstury (NxM-gramy, lokalne wzorce, filtry Gabora), omówiono także wykrywanie obiektów metodą AdaBoost.
-
Distributed largest-first algorithm for graph coloring.
PublicationW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
Rozproszone kolorowanie grafów
PublicationW pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.
-
Żywice epoksydowe i poliuretany - wzajemne oddziaływania modyfikujące. Cz. II. Przenikające się sieci polimerowe (IPN).
PublicationNa podstawie przeglądu literatury przedstawiono sposoby wzajemnej modyfikacji żywic epoksydowych (EP) i poliuretanów (PUR) prowadzące do tworzenia przenikających się sieci polimerowych (IPN) oraz szczepionych sieci polimerowych(graf-IPN).Podstawowym celem modyfikacji EP jest poprawa ich elastyczności...
-
Compact scheduling of zero-one time operations in multi-stage systems.
PublicationRozważamy szeregowanie zwarte na maszynach dedykowanych z zero-jedynkowymi operacjami w modelu otwartym, przepływowym i mieszanym. Harmonogramy zostały zmodelowane przy pomocy pokolorowań krawędzi grafu konfliktów z pewnymi dodatkowymi ograniczeniami. Dowodzimy NP-trudności problemów w przypadku ogólnym oraz prezentujemy przegląd znanych wielomianowych algorytmów szeregujących dla systemów o specyficznej budowie.
-
Images of apples for the use of the Viola-Jones method. Data set no. 2 - grey scale
Open Research DataThe database contains pictures of apples made at different angles, from different sides and containing different varieties. In this way, two bases of apple images were created (each database contains 1,100 images). This set is data set no. 2 - grey scale: processed images in shades of gray. The photos were prepared for the best possible detection process...
-
Ordinal pattern statistics for the assessment of heart rate variability
PublicationThe recognition of all main features of a healthy heart rhythm (the so-called sinus rhythm) is still one of the biggest challenges in contemporary cardiology. Recently the interesting physiological phenomenon of heart rate asymmetry has been observed. This phenomenon is related to unbalanced contributions of heart rate decelerations and accelerations to heart rate variability. In this paper we apply methods based on the concept...
-
Differentiating patients with obstructive sleep apnea from healthy controls based on heart rate-blood pressure coupling quantified by entropy-based indices
PublicationWe introduce an entropy-based classification method for pairs of sequences (ECPS) for quantifying mutual dependencies in heart rate and beat-to-beat blood pressure recordings. The purpose of the method is to build a classifier for data in which each item consists of two intertwined data series taken for each subject. The method is based on ordinal patterns and uses entropy-like indices. Machine learning is used to select a subset...
-
Ordinal Pattern Statistics for RR Intervals during Head-Up Tilt Test in Patients with the History of Vasovagal Syncope
PublicationWe apply ordinal pattern analysis to quantify differences in distribution of patterns of length 3 and 4 in basal state and during head-up tilt test (HUTT) in patients with the history of syncope and positive (HUTT(+)) or negative (HUTT(-)) responses to the test. We identify the patterns related to prevalence of sympathetic or parasympathetic cardiac modulation as well as describe the relations between the response to the test and...
-
Ustalenie prędkości zderzenia w oparciu o zakres uszkodzeń samochodu z wykorzystaniem metod energetycznych – badania pilotażowe
PublicationW artykule przedstawiono omówienie możliwości technicznych mierzenia profi lu odkształcenia samochodu powypadkowego przy użyciu specjalnie do tego celu zaprojektowanego i wykonanego przyrządu pomiarowego. Przyrząd ten zastosowany w metodzie grafi cznej wyznaczania wartości pracy deformacji, powoduje zwiększenie wykorzystania metod energetycznych jako niezwykle istotnych w praktyce opiniowania szczególnie trudnych i złożonych zdarzeń...
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublicationW pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.
-
Complixity results on open shop scheduling to minimize total cost of operations
PublicationW pracy zaprezentowano serię rezultatów dotyczących złożoności obliczeniowejproblemu szeregowania w systemie otwartym z kryterium łącznego kosztu opera-cji. W ogólności problem jest NP-trudny nawet w przypadku 1-procesorowym.Dlatego zaprezentowano możliwie wiele przypadków szczególnych, które są wie-lomianowe. Są one funkcją długości operacji i struktury grafu konfliktów po-między zadaniami.
-
Wspomagana komputerowo weryfikacja określonego poziomu nienaruszalności bezpieczeństwa sil z wykorzystaniem autorskiej aplikacji ProSIL
PublicationW referacie przedstawiono oprogramowanie Pro SIL wspomagające zarządzanie bezpieczeństwem funkcjonalnym. Program ProSIL składa się z trzech modułów wspomagających: określanie wymaganego poziomu SIL (moduł ProSILen) weryfikację SIL (moduł ProSILer) oraz przeprowadzenie analizy warstw zabezpieczeń metodą LOPA. W aplikacji ProSIL zaimplementowano opracowaną w trakcie badań metodykę analizy bezpieczeństwa funkcjonalnego w projektowaniu...
-
Cost minimisation in unbounded multi-interface networks
PublicationW pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublicationLiczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
-
Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym.
PublicationW pracy rozważamy kombinatoryczny problem MERST polegający na szukaniu, dla danego grafu, drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Dla ogólnych grafów problem MERST jest NP-trudny. W pracy zaproponowano nową funkcję dobroci dla pewnego przybliżonego algorytmu rozwiązującego powyższy problem i przeprowadzono doświadczenia komputerowe w celu porównania nowej z wcześniej znaną funkcją dobroci.
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublicationW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
An interactive system for mobile robot navigation
PublicationW pracy przedstawiono interaktywny system do zdalnego sterowania robotem mobilnym zbudowany przy użyciu języka VRML. System jest wspomagany przez algorytm wyznaczania optymalnej trajektorii ruchu robota mobilnego poruszającego się w obecności przeszkód statycznych. Otoczenie reprezentowane jest przez graf nieskierowany. W metodzie wykorzystano algorytm Dijkstry.
-
Preparation of Well-Compatibilized PP/PC Blends and Foams Thereof
PublicationThe performance of polypropylene-poly(ethylene brassylate) block and graft copolymers and a polypropylene-polycaprolactone graft copolymer as compatibilizers for polypropylene-rich polypropylene/bisphenol A polycarbonate (PP/PC, 80/20 wt/wt) blends was elucidated. The copolymers were synthesized either by metal-catalyzed ring-opening polymerization or transesterification of a presynthesized polyester, initiated by hydroxyl-functionalized...
-
Dedicated scheduling of tasks to minimize mean flow time
PublicationThis paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.
-
Directed laplacian kernels for link analysis
PublicationPrzedstawiono zastosowanie algorytmów opartych o funkcje jądra do problemu analizy linków i cytowań. Zaproponowano nowe funkcje jądra zbudowane na operatorze Laplace'a dla grafów skierowanych. Odzwierciedlają one powiązanie pomiędzy węzłami grafu jako funkcję długości łączących je ścieżek oraz istotności odwiedzanych po drodze węzłów. Eksperymenty z nowymi funkcjami jądra przeprowadzono na zbiorze cytowań pobranych z publikacji...
-
Total restrained bondage in graphs
PublicationPodzbiór D zbioru wierzchołków grafu nazywamy zewnętrznie totalnym dominującym w grafie, jeśli każdy wierzchołek spoza D ma sąsiada zarówno w D jak i poza D. Moc najmniejszego zbioru o tej własności nazywamy liczbą dominowania zewnętrznie totalnego. W artykule badamy wpływ usuwania krawędzi na liczbę dominowania zewnętrznie totalnego, czyli liczbę zewnętrznego totalnego zniewolenie w grafach.
-
Ograniczone (p1, p2,...,pk) kolorowanie wierzchołków grafów.
PublicationProblem ograniczonego (p1,...,pk) kolorowania grafów polega na poszukiwaniu odpowiedzi na pytanie, czy istnieje takie pokolorowanie wierzchołków grafu , że krotności użycia poszczególnych barw są równe ustalonym progom p1,...,pk. W ogólnym przypadku problem ten, jako uogólnienie klasycznego kolorowania grafów pozostaje NP-zupełnym. W pracy przedstawiamy wyniki dotyczące ograniczonego kolorowania split grafów, kografów oraz...
-
Periodic expansion in determining minimal sets of Lefschetz periods for Morse–Smale diffeomorphisms
PublicationWe apply the representation of Lefschetz numbers of iterates in the form of periodic expansion to determine the minimal sets of Lefschetz periods of Morse–Smale diffeomorphisms. Applying this approach we present an algorithmic method of finding the family of minimal sets of Lefschetz periods for Ng, a non-orientable compact surfaces without boundary of genus g. We also partially confirm the conjecture of Llibre and Sirvent (J Diff...
-
Dold sequences, periodic points, and dynamics
PublicationIn this survey we describe how the so-called Dold congruence arises in topology, and how it relates to periodic point counting in dynamical systems.
-
Generalized Dold sequences on partially-ordered sets
PublicationDold sequences constitute an important class of integer sequences that play an important role in combinatorics, number theory, topology and dynamical systems. We generalize the notion of Dold sequence for the case of partially ordered sets and describe their properties. In particular we give two alternative descriptions of generalized Dold sequences: by some class of elementary sequences as well as by different...
-
Computations of the least number of periodic points of smooth boundary-preserving self-maps of simply-connected manifolds
PublicationLet $r$ be an odd natural number, $M$ a compact simply-connected smooth manifold, $\dim M\geq 4$, such that its boundary $\partial M$ is also simply-connected. We consider $f$, a $C^1$ self-maps of $M$, preserving $\partial M$. In [G. Graff and J. Jezierski, Geom. Dedicata 187 (2017), 241-258] the smooth Nielsen type periodic number $D_r(f;M,\partial M)$ was defined and proved to be equal to the minimal number of $r$-periodic points...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Optimal and safe control planning with the use of discrete optimization
PublicationW opracowaniu zaproponowano metodę projektowania optymalnych i tolerujących uszkodzenia systemów sterowania opartych na wykorzystaniu algorytmów optymalizacji dyskretnej. Publikacja przedstawia potencjalne wady i zalety metody. Główna idea proponowanego algorytmu sprowadza się do wykorzystania struktury grafu przepływowego w celu stworzenia reprezentacji dynamiki własnej danego procesu. Poszukiwana trajektoria optymalna, jeśli...
-
Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych
PublicationHipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...
-
Euler tour lock-in problem in the rotor-router model
PublicationW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Porównano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera dla różnych klas grafów, prowadząc rozważania w kontekście teorii gier. Przydział początkowych portów i wskaźników w modelu jest traktowany jako rozgrywka pomiędzy graczem...
-
Topologia algebraiczna 2022/23
e-Learning CoursesCelem przedmiotu jest zapoznanie studentów z podstawowymi pojęciami i twierdzeniami z zakresu topologii algebraicznej.
-
Teoria punktów stałych [2022/2023] (Matematyka, WFTiMS)
e-Learning CoursesTeoria punktów stałych WFTIMS, Matematyka
-
Detection methods of dynamic spammer's behavior
PublicationPoczta elektroniczna ze względu na swoją naturę jest bardzo podatna na zjawisko spamu. Oddzielanie spamu od dobrych wiadomości jest zadaniem żmudnym i pracochłonnym. Dlatego jest rzeczą istotną opracowanie skutecznej metody walki ze spamem uwzględniającej nie tylko aktualne metody działania spamerów, ale również wzięcie pod uwagę dynamicznych aspektów zmieniających się stale ich zachowań.Artykuł opisuje metodę klasyfikacji wiadomości...
-
Entropy Measures in the Assessment of Heart Rate Variability in Patients with Cardiodepressive Vasovagal Syncope
PublicationSample entropy (SampEn) was reported to be useful in the assessment of the complexity of heart rate dynamics. Permutation entropy (PermEn) is a new measure based on the concept of order and was previously shown to be accurate for short, non-stationary datasets. The aim of the present study is to assess if SampEn and PermEn obtained from baseline recordings might differentiate patients with various outcomes of the head-up tilt test...
-
Cost minimization in wireless networks with a bounded and unbounded number of interfaces
PublicationPraca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne. Rozważono zarówno wariant, w którym liczba interfejsów komunikacyjnych jest parametrem stałym (narzuconym...
-
Total outer-connected domination numbers of trees
PublicationNiech G=(V,E) będzie grafem bez wierzchołków izolowanych. Zbiór wierzchołków D nazywamy zbiorem dominującym totalnym zewnętrznie spójnym jeżli każdy wierzchołek grafu ma sąsiada w D oraz podgraf indukowany przez V-D jest grafem spójnym. Moc najmniejszego zbioru D o takich własnościach nazywamy liczbą dominowania totalnego zewnątrznie spójnego. Praca m.in. zawiera dolne ograniczenie na liczbę dominowania totalnego zewnętrznie spójnego...
-
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Packing [1,Delta]-factors in graphs of small degree
PublicationRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
Eksperymenty z zastosowanie algorytmów genetycznych do problemu kolorowania grafów
PublicationNiniejsza praca przedstawia wykorzystanie algorytmów genetycznych (AG) do problemu kolorowania wierzchołków grafu (GCP). Przeprowadzono szereg symulacji mających na celu porównanie skuteczności operatorów krzyżownia, mutacji i selekcji oraz sposobu generacji i parametrów populacji. Uzyskane wyniki pokazały znaczną przewagę operatorów korzystających z wiedzy o problemie nad operatorami losowymi. Dla wybranej konfiguracji algorytmu...
-
Harmoniczne kolorowanie grafów
PublicationW rozdziale omówiono tzw. harmoniczne kolorowanie grafów, które jest odmia-ną klasycznego kolorowania wierzchołków grafów. Podano najważniejsze własno-ści tego sposobu kolorowania grafów i jego potencjalne zastosowanie w radio-komunikacji lotniczej i projektoaniu funkcji mieszających. Podano równieżtzw. algorytm degresywny, który koloruje każdy graf za pomocą liczby kolorównie przekraczającej w dwójnasób harmonicznej liczby...
-
Metoda szybkiego wyznaczania par węzłowo rozłącznych tras dla ochrony transmisji unicast
PublicationW celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże, złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. W pracy prezentujemy nowe podejście wyznaczania par rozłącznych tras bazujące na transformacji grafu sieci w meta strukturę. Wyniki badań odnośnie czasu wyznaczania tras...
-
Topological-numerical analysis of a two-dimensional discrete neuron model
PublicationWe conduct computer-assisted analysis of a two-dimensional model of a neuron introduced by Chialvo in 1995 [Chaos, Solitons Fractals 5, 461–479]. We apply the method of rigorous analysis of global dynamics based on a set-oriented topological approach, introduced by Arai et al. in 2009 [SIAM J. Appl. Dyn. Syst. 8, 757–789] and improved and expanded afterward. Additionally, we introduce a new algorithm to analyze the return times...
-
Periodic points of latitudinal maps of the $m$-dimensional sphere
PublicationLet f be a smooth self-map of the m-dimensional sphere Sm. Under the assumption that f preserves latitudinal foliations with the fibres S1, we estimate from below the number of fixed points of the iterates of f. The paper generalizes the results obtained by Pugh and Shub and by Misiurewicz.
-
Shub’s conjecture for smooth longitudinal maps of S^m
PublicationLet f be a smooth map of the m-dimensional sphere Sm to itself, preserving the longitudinal foliation. We estimate from below the number of fixed points of the iterates of f , reduce Shub’s conjecture for longitudinal maps to a lower dimensional classical version, and prove the conjecture in case m = 2 and in a weak form for m = 3.