Search results for: EKSTRAPOLACJA WIELOMIANOWA
-
Szybka realizacja splotu z wykorzystaniem resztowej reprezentacji wielomianów.
PublicationPrzedstawiono możliwość realizacji splotu dwóch sygnałów dyskratnych z wykorzystaniem resztowej reprezentacji wielomianów oraz omówiono możliwośc budowy cyfrowego układu scalonego do tego celu. Podstawy teoretyczne zilustrowano przykładem obliczeniowym oraz podano schemat budowy układu mnożącego zrealizowanego z powszechnie dostępnych układówe automatycznych.
-
Nieliniowa ekstrapolacja chwili zgodności fazowej napięć synchronizowanych obiektów elektroenergetycznych z wykorzystaniem funkcji wymiernej
PublicationPrzedstawiono metodę nieliniowej ekstrapolacji chwili zgodności fazowej napięć synchronizowanych obiektów elektroenergetycznych z wykorzystaniem funkcji wymiernej. Opisano dotychczas stosowane metody wyznaczania chwil koincydencji fazowej, wskazując na ich niedogodności. Zawarto opis algorytmu wyznaczania chwili zgodności fazowej wg proponowanej metody z wykorzystaniem funkcji wymiernej, ilustrując go przykładem. Zaprezentowano...
-
W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo
Publicationw artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1, ..., jn, czas przetwarzania zadania i wynosi pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u,...
-
Zmiana szybkości próbkowania z użyciem filtrów ułamkowoopóźniających projektowanych oknem offsetowanym z pomocą aproksymacji wielomianowej
PublicationW pracy przedstawiono problem realizacji algorytmu zmiany szybkości próbkowania z użyciem filtrów ułamkowoopóźniających. Zaproponowano tutaj zastąpić filtry optymalne, filtrami projektowanych metodą okien offsetowanych. Uzyskujemy w ten sposób rozwiązanie pozbawione silnych listki występujące w paśmie zaporowym filtru zbiorczego jednak pojawia się problem realizacji offsetowania okna prototypowego, które zapropono-wano realizować...
-
An efficient algorithm for mobile guarded guards in simple grids
PublicationW pracy rozważono problem strzeżenia ortogonalnych krat dwuwymiarowych przez mobilne straże strzeżone. Podano algorytmy wielomianowe m.in. dla przypadku krat prostych i dla przypadku krat bez przeszkód w kierunku poziomym (pionowym).
-
A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publication.
-
Representation of the Poisson kernel for Jacobi and Hahn polynomials
PublicationW pracy przedstawiono dowód twierdzenia o reprezentacji jąder Poissona dla wielomianów Jacobiego wypukłą kombinacją nieujemnych jąder typu Durrmeyera. Podobne rezultaty uzyskano dla jąder Poissona dla dyskretnych wielomianów Hahna.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Generalized adaptive notch filters with frequency debiasing for tracking of polynomial phase systems
PublicationGeneralized adaptive notch filters are used for identification/tracking of quasi-periodically varying dynamic systems and can be considered an extension, to the system case, of classical adaptive notch filters. For general patterns of frequency variation the generalized adaptive notch filtering algorithms yield biased frequency estimates. We show that when system frequencies change slowly in a smooth way, the estimation bias can...
-
Optymalizacja wzmocnień obserwatora prędkości maszyny indukcyjnej
PublicationPrzedstawiono obserwator prędkości oparty na rozszerzonym modelu maszyny indukcyjnej i nieliniowych sprzężeniach zwrotnych. Zaproponowano dobór wzmocnień obserwatora metodą optymalizacji rojem cząstek. Otrzymano zależności umożliwiające zastosowanie sieci neuronowej lub wielomianów do strojenia wzmocnień obserwatora. Pokazano, że proste zależności wielomianowe wystarczają do strojenia wzmocnień obserwatora w zależności od prędkości...
-
Analiza porównawcza metod predykcji chwili zgodności fazowejw automatycznym synchronizatorze prądnic = Comparison of the methods of prediction time phase coincidence in automatic synchronizer of power generators
PublicationW artykule porównano dokładność wybranych metod realizacji warunku fazowego podczas synchronizacji obiektów elektroenergetycznych. Do porównania wybrano trzy metody: liniową, wielomianową oraz metodę adaptacyjnej synchronizacji prądnic z ekstrapolacją funkcją wymierną. Badania przeprowadzono dla różnych warunków pracy. Przyjęto stałą różnicę częstotliwości napięć synchronizowanych obiektów, różnicę częstotliwości zmieniającą się...
-
Comparison the Accuracy of the Extrapolation Methods of the Time Phase Coincidence in Synchronization of Power Generating Units
PublicationW artykule opisano metody ekstrapolacji chwili zgodności fazowej napięć łączonych obiektów elektroenergetycznych. Przeprowadzono analizę porównawczą wybranych metod ekstrapolacji w równych warunkach pracy oraz przedstawiono najistotniejsze wyniki badań.
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublicationW pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać...
-
The maximum edge-disjoint paths problem in complete graphs
PublicationRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
A polynomial algorithm for finding T-span of generalized cacti.
PublicationW pracy opisano wielomianowy algorytm wyznaczający optymalne T-pokolorowania dla uogólnionych kaktusów.
-
Connected searching of weighted trees
PublicationW artykule rozważamy problem spójnego przeszukiwania drzew obciążonych. Autorzy w [L. Barriere i inni, Capture of an intruder by mobile agents, SPAA'02 (2002) 200-209] twierdzą, że istnieje wielomianowy algorytm dla problemu obliczania optymalnej strategii przeszukiwania obciążonego drzewa. W niniejszej pracy pokazano, że problem ten jest obliczeniowo trudny nawet dla wierzchołkowo-obciążonych drzew (wagi krawędzi równe 1) oraz...
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublicationRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
Krzysztof Jan Kaliński prof. dr hab. inż.
PeopleKrzysztof J. Kaliński completed his MSc study at Gdańsk University of Technology (GUT) Faculty of Production Engineering (1980, result – get a first). He obtained PhD at GUT Faculty of Machine Building (1988, result – get a first), DSc at GUT Faculty of Mechanical Engineering (ME) (2002, result – get a first), and professor’s title – w 2013 r. In 2015 r. he became full professor, and since 2019 - professor.His research area includes:...
-
The complexity of equitable vertex coloring graphs
PublicationW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
-
Metoda szacowania nośności granicznych pali Vibro na podstawie quasi-liniowych krzywych osiadania
PublicationBadanie zgodności procedur próbnego obciążenia statycznego oraz metod interpretacji według PN-83/B-02482 i aktualnej normy PN-EN:1997-1:2008. Propozycja empirycznej metody ekstrapolacji quasi-liniowych krzywych osiadania pali Vibro na podstawie wyznaczonej nośności granicznej.
-
Kolorowanie końcówkowe multidrzew
PublicationW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Aproksymacyjny model tarcia
PublicationW pracy przedstawiono problem aproksymacji danych pomiarowych z eksperymentu tribologicznego. W celu uzyskania opisu zależności współczynnika tarcia od liniowej prędkości ślizgania i nacisków zastosowano dwa podejścia: aproksymacja wielomianowa i wykorzystanie sztucznej sieci neuronowej. W rezultacie prowadzonych prac ustalono, podejście neuronowe jest korzystniejsze.
-
Complex multiplier based on the polynomial residue number system
PublicationPrzedstawiono próbę zaprojektowania mnożnika zespolonego 4x4 opartego na algorytmie Skavantzosa i Stouraitisa. W algorytmie stosuje siękodowanie liczb n-bitowych jako wielomianów stopnia 7 w pierścieniu wielomianów modulo (x^8-1) z n/4-bitowymi współczynnikami. Mnożenie zespolone jest wykonywane jako 8-punktowy splot cykliczny. Podanoopóżnienie i złożoność sprzętową jak również porównanie ze standardowym.rozwiązaniem.
-
Kolorowanie grafów obciążonych i jego zastosowanie w problemie przydziału częstotliwości
PublicationReferat omawia jeden z modeli dla problemu przydziału częstotliwości, oparty o kolorowanie grafów obciążonych. Podana została złożoność obliczeniowa modelu i wielomianowy algorytm 4-kolorowania grafów w tym modelu.
-
Fault tolerant guarding of grids
PublicationW pracy rozważano problem strzeżenia krat dwuwymiarowych przez dwa niezależne zespoły straży. Wykazano, że zagadnienie minimalizacyjne jest NP-trudne i zaproponowano dla niego wielomianowy algorytm 6/5-przybliżony.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublicationRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
Neural Network Application for Recognition of Geometry Degradation of Power Cycle Components
PublicationPrzedyskutowano problem rozpoznawania degradacji geometrycznej. Skuteczne zastosowanie wybranego typu sieci neuronowej (SSN) jest prezentowane w referacie. SSN wykrywająca typy degradacji geometrycznej wykazała wysoką jakość. Pokazano pewną możliwość ekstrapolacji takich SSN. Pokazano możliwość wykrywania typów degradacji geometrycznej nawet w przypadku pozyskiwania niepełnych danych pomiarowych.
-
Koncepcja cyfrowego przetwornika napięcie-częstotliwość
PublicationDokonano przeglądu przetworników analogowych wielkości fizycznych na sygnał impulsowy modulowany częstotliwościowo. Przedstawiono propozycję cyfrowego przetwornika napięcie-częstotliwość. Opisano algorytm działania przetwornika, w którym odstęp między impulsami sygnału częstotliwościowego wyznaczany jest z ekstrapolacji z dwóch próbek napięcia z przetwornika analogowo-cyfrowego. Podano zalety i wady takiego rozwiązania.
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublicationNiniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.
-
Apparent molar volumes of divalent transition metal chlorides and perchlorates in dimethyl sulfoxide solutions.
PublicationZmierzono gęstości roztworów nadchloranów i chlorków dwuwartościowych metali szeregu Mn(II)-Zn(II) w dimetylosulfotenku. Wyznaczone na drodze ekstrapolacji cząstkowe objętości molowe nadchloranów rozdzielono na udziały jonowe. Przeanalizowano wpływ pola ligandów na cząstkowe objętości molowe kationów. Przedstawiono związek między wartościami pozornych objętości molowych a stanami koordynacyjnymi soli w DMSO.
-
Interval wavelength assignment in all-optical star networks
PublicationArtykuł omawia zwarte końcówkowe kolorowanie grafów, które jest matematycznym modelem dla problemu przydziału częstotliwości w sieciach optycznych. W artykule przedstawiono wielomianowe algorytmy wyznaczania zwartej końcówkowej liczby chromatycznej dla pełnych grafów k-dzielnych, drzew i podkubicznych grafów dwudzielnych.
-
Szeregowanie zadań uwarunkowanych czasowo
Publicationw pracy przedstawiono wyniki badań nad problemami szeregowania zadań uwarunkowanych czasowo. dla problemu 1|pi=a+bisi|σci przedstawiono nowe heurystyki, przypadek wielomianowy oraz w pełni wielomianowy schemat. wprowadzono koncepcję eliminacji zdominowanych fragmentów harmonogramu, oraz pokazano jak wykorzysta¢ ją do konstrukcji algorytmu dokładnego dla tego problemu, a także jak przy jej pomocy przyspieszy¢ inne algorytmy. następnie...
-
Connected searching of weighted trees
PublicationW pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.
-
On hydrodynamic forces acting on the ship in large motions.
PublicationPraca zapoznaje czytelnika ze współczesnym stanem dynamiki statku w nieliniowym ujęciu, ukierunkowanym na unikanie zbyt daleko idących komplikacji w rozwiązaniu. Nieliniowość dotyczy przede wszystkim sił Fronda-Kryłowa oraz sił tłumienia po wejściu pokładu do wody, czy też oporu stępek przechyłowych. Do pozostałych sił towarzyszących i dyfrakcyjnych stosuje się ekstrapolację podejścia liniowego.
-
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
PublicationW pracy rozważano złożoność obliczeniową problemu szeregowania w cylindrycznym systemie przepływowym. Skonstruowano algorytm wielomianowy dla problemu dwumaszynowego oraz wykazano, iż zagadnienie staje się NP-trudne przy szeregowaniu na trzech procesorach, bądź na dwóch, przy dodatkowym wymuszeniu braku obustronnych przestojów.
-
Rozpoznawanie typu degradacji geometrycznej układu łopatkowego turbin parowych
PublicationPrzedyskutowano problem rozpoznawania typów degradacji geometrycznej układów łopatkowych turbin parowych. Zaproponowano wybrany typ sztucznej sieci neuronowej SSN. SSN rozpoznająca typy degradacji geometrycznej wykazuje wysoką jakość wykrywania tych degradacji. Zaobserwowano też pewien potencjał do ekstrapolacji w tych typach SSN. Zastosowana SSN dobrze identyfikuje typy degradacji, zarówno dla pełnych jak i niepełnych danych pomiarowych.
-
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.
-
Pomiar on-line zmiennej częstotliwości metodą cyfrową
PublicationW cyfrowym pomiarze częstotliwości on-line dysponujemy informacją o długościach przedziałów międzyimpulsowych poprzedzających chwilę próbkowania. W artykule porównano pomiar częstotliwości na podstawie ostatniego przedziału i metodę wykorzystującą ekstrapolację z dwóch ostatnich przedziałów. Wykonano analizę dla liniowej i sinusoidalnej zmiany częstotliwości. Zaproponowano metodę, w której sposób wyznaczenia częstotliwości zależy...
-
Adaptacyjna metoda synchronizacji prądnic w systemie elektroenergetycznym
PublicationW artykule przedstawiono nowo opracowaną, adaptacyjną metodę synchronizacji prądnic w systemie elektroenergetycznym. Metoda ta w porównaniu z metodami dotychczas stosowanymi posiada szereg zalet, do których z pewnością należy zaliczyć: skrócenie czasu trwania procesu synchronizacji, inny aniżeli dotychczas sposób sterowania napięciem i prędkością kątową synchronizowanego obiektu, zwiększona dokładność ekstrapolacji (funkcją wymierną)...
-
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
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 kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Energy optimisation in resilient self-stabilizing processes
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 kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
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 kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublicationProblem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować przy pomocy hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy jak przy pomocy modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania, oraz jak rozwiązać problemy dwukryterialne.
-
Problemy opóźnień wynikających z czasu obliczeń w cyfrowym przetwarzaniu napięcie częstotliwość
PublicationPrzedstawiono rozwiązanie cyfrowego przetwornika napięcie-częstotliwość. Opisano algorytm działania przetwornika, w którym odstęp między impulsami sygnału częstotliwościowego wyznaczany jest z ekstrapolacji z dwóch próbek napięcia (pierwszej i drugiej, pierwszej i ostatniej lub przedostatniej i ostatniej). Porównano błędy przetwornika dla opisanych metod. Przedstawiono problem zwiększenia wartości błędów w wyniku opóźnień związanych...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Błędy cyfrowej rejestracji prędkości obrotowej z wykorzystaniem przetwornika obrotowo-impulsowego
PublicationPrzedstawiono zasadę działania przetwornika obrotowo-impulsowego w zastosowaniu do pomiaru prędkości obrotowej. Omówiono metody rejestracji on-line sygnału impulsowego z przetwornika obrotowo-impulsowego. W metodach tych prędkość obrotowa wyznaczana jest na podstawie ostatniego przedziału miedzyimpulsowego lub na podstawie dwóch ostatnich przedziałów miedzyimpulsowych z ekstrapolacji. Dla sinusoidalnej zmiany prędkości udowodniono,...
-
Interval edge-coloring of graphs.
PublicationRozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.
-
Odporne na zakłócenia impulsowe algorytmy estymacji parametrycznej w zastosowaniach.
PublicationOmówiono wykorzystanie metod estymacji parametrycznej w diagnostyce. Rozważano zastosowanie algorytmu LA w dynamicznym ważeniu wolno poruszających się pojazdów gdy przeciążenie wagi doprowadza do istotnego zafałszowania danych pomiarowych. Rozwiązano zadanie rekonstrukcji sygnału ciągłego metodą wielomianowej aproksymacji jego próbek.
-
The PRNS butterfly in the FPGA technology
PublicationW publikcaji zaprezentowano koncepcję realizacji motylka konwesji wejściowej w Wielomianowym Systemie Resztowym (Polynoamil Residue Number System, PRNS). Omówiono wykorzystanie reprezentacji liczb w systemie diminished-1 w prezentowanym rozwiązaniu oraz przedstawiono wynik syntezy ukłądu w środowisku Xilinx ISE.