Search results for: PROBLEMY NP-TRUDNE

• Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych

  Publication

  • K. Giaro
  • M. Kubale

  - Year 2005

  Szeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...

• Fault tolerant guarding of grids

  Publication

  • A. Kosowski
  • M. Małafiejski
  • P. Żyliński

  - Year 2006

  W 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.

  Full text to download in external service

• Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym

  Publication

  • A. Nadolski

  - Year 2006

  W 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.

• Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 3. Alicja i Bogdan remontują mieszkanie.

  Publication

  • M. Kubale
  • D. Niemczyk

  - Pismo PG - Year 2023

  Poniższe zagadki nawiązują z jednej strony do problemu kafelkowania płaszczyzny, który jest nierozstrzygalny, z drugiej do problemu rozkroju wstęgi, który jest NP-trudny. Jednakże przypadki szczególne, które tu rozważamy, nie są tak trudne i mogą być rozwiązane za pomocą algorytmów działających w czasie wielomianowym.

  Full text to download in external service

• Zachowanie poprzez sieciowanie w przedsiębiorczości społecznej w odpowiedzi na trudne otoczenie instytucjonalne – przypadek 5 spółdzielni socjalnych

  Publication

  • M. Starnawska

  - Problemy Zarządzania - Year 2014

  Celem niniejszego artykułu jest zobrazowanie procesów, jakimi są zachowania przedsiębiorców, zachodzących w przedsiębiorczości społecznej w odpowiedzi na trudne otoczenie instytucjonalne. Opisano zachowania przedsiębiorcze przedstawicieli pięciu spółdzielni socjalnych na podstawie pogłębionych wywiadów i obserwacji . Za pomocą metody ciągłego porównywania wyodrębniono 3 główne kategorie zachowań badanych przedsiębiorców, które...

  Full text available to download

• Sumacyjne kolorowanie grafów

  Publication

  • M. Małafiejski

  - Year 2002

  W tym rozdziale, oprócz szczegółowego zaprezentowania koncepcji sumy chroma-tycznej, jej własności oraz wyników z nią związanych, dokonano analizy zło-żoności problemu sumacyjnego kolorowania dla wybranych klas grafów, w szcze-gólności rozróżniono klasy grafów, dla których problem sumacyjnego kolorowa-nia można rozwiązać w czasie wielomianowym oraz przypadki NP-trudne.

• Michał Bernard Pietrzak dr hab.

  People

  Katedra Statystyki i Ekonometrii

            Michal Pietrzak is head of the Department of Statistics and Econometrics at the Faculty of Economics and Management, Gdańsk University of Technology, and Deputy Editor-in-Chief for Statistical Reviewing of the journals: Oeconomia Copernicana and Equilibrium. Quarterly Journal of Economics and Economic Policy. Until October 2021, he worked as an associate professor at the Faculty of Economic Sciences and Management, Nicolaus...

• Inferring perfect phylogenies with restrictions on character state transitions

  Publication

  • J. Truszkowski
  • K. Giaro

  - Year 2008

  Znana z klasycznej literatury metoda rekonstrukcji drzewa filogenetycznego zbioru gatunków na podstawie ich cech analizowanych w modelu doskonałej filogenezy często okazuje się niewystarczająca ze względu na założenia tego modelu, zmuszające do pominięcia znanych biologom informacji. W pracy definiujemy rozszerzenie umożliwiając wprowadzenie dla każdej cechy grafu skierowanego dopuszczalnych przejść ewolucyjnych pomiędzy jej stanami....

• Sieć SSWN w oczyszczalni ścieków

  Publication

  • A. Borowa
  • M. Brdyś
  • G. Ewald

  - Year 2008

  Modelowanie złożonych, dynamicznych, nieliniowych systemów z wieloma skalami czasu, do jakich należą biologiczne oczyszczalnie ścieków, jest wcišż poważnym wyzwaniem. Problemy związane z pomiarem sporej części stanu obiektu oraz duże koszty urządzeń pomiarowych utrudniają a wręcz uniemożliwiają korzystanie z modeli fizykalnych rozważanych systemów. Jest to szczególnie trudne, gdy potrzebujemy modelu do celów sterowania.

• Modele i metody kolorowania grafów. Część I

  Publication

  • M. Kubale

  - Przegląd Elektrotechniczny - Year 2010

  Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...