Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: nondeterministic algorithms

Sortuj według:

Ogranicz wyniki do:

A note on hardness of multiprocessor scheduling with scheduling solution space tree

Dwibedy Debasis, Mohanty Rakesh

Computer Science

2023

T. 24 (1)

53--74

We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.

Weryfikacja temporalnych własności algorytmów niedeterministycznych

Kacprzak M.

Zeszyty Naukowe Politechniki Białostockiej. Matematyka, Fizyka, Chemia

2001

Z. 20

37--53

W pracy zaprezentowany został system dowodowy dla logiki temporalnej czasu rozgałęzionego, nazwany Temporalną Logiką Procesów. Pozwala on na badanie statycznych i dynamicznych własności programów wyrażonych jako formuły temporalne rozważanego języka. Udowodniono mocne twierdzenie o pełności dla przedstawionego systemu formalnego.

This paper provides one of the versions of prepositional, branching time temporal logic, called Process Temporal Logic. It allows to verify static and dynamic properties of programs, which are expressed as temporal formulas. PTL system is presented with the infinitary axiomatic system and the proof of the completeness theorem. The majority of temporal logics treats a program as a separate object and not as a language element. The system shown in this article is different. Program is a part of expression which describes its quality just as in dynamic and algorithmic logic.