Wyniki wyszukiwania - BazTech

1

Development issues in algorithms for system level self-diagnosis

Mashkov V., Smolarz A., Lytvynenko V.

Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska

|

2016

|

nr 1

26--28

EN

The paper deals with the problem of developing probabilistic algorithm for system level self-diagnosis. The main goal of the suggested algorithm is to minimize the mean time of its executing. The algorithm is based on the computing of the posterior probability of fault-free state of each system unit. Final decision about unit’s state is made on the chosen decision rule. The execution of the probabilistic algorithm is elucidated with the help of simple example and then explained for the case of more complex systems.

PL

Artykuł opisuje problem projektowania probabilistycznego algorytmu autodiagnostyki na poziomie systemu. Głównym celem proponowanego algorytmu jest minimalizacja średniego czasu wykonania. Algorytm oparty jest na obliczeniach prawdopodobieństwa a posteriori bezawaryjnego stanu każdej jednostki systemu. Decyzja o stanie jednostki podejmowana jest na podstawie wybranej reguły decyzyjnej. Działanie algorytmu probabilistycznego zostało opisane na prostym przykładzie, a następnie wyjaśnione dla przypadku bardziej złożonych systemów.

2

The average time complexity of probabilistic algorithms for finding generators in finite cyclic groups

Adamski T., Nowakowski W.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2015

|

Vol. 63, nr 4

989--996

EN

Generators of finite cyclic groups play important role in many cryptographic algorithms like public key ciphers, digital signatures, entity identification and key agreement algorithms. The above kinds of cryptographic algorithms are crucial for all secure communication in computer networks and secure information processing (in particular in mobile services, banking and electronic administration). In the paper, proofs of correctness of two probabilistic algorithms (for finding generators of finite cyclic groups and primitive roots) are given along with assessment of their average time computational complexity.

3

Numerical estimation of the quantum factorization effectiveness

Zawadzki P.

Theoretical and Applied Informatics

|

2010

|

Vol. 22, No. 1

63-72

EN

The quantum factorization is probably the most famous algorithm in quantum computation. The algorithm succeeds only when some random number with an even order relative to factorized composite integer is fed as the input to the quantum order finding algorithm. Moreover, post processing of the quantum measurement recovers the correct order only for some subset of possible values. It is well known that numbers with even orders are found with probability not less than 1=2. However, numerical simulation proves that probability of such event exhibits grouping on some discrete levels above that limit. Thus, one may conclude that usage of the lowest estimate leads to underestimation of the successful factorization probability. The understanding of the observed grouping requires further research in that field.

PL

Algorytm kwantowej faktoryzacji liczb stał się jednym z głównych czynników stymulujących rozwój informatyki kwantowej. Algorytm ten, zaproponowany przez Shora [1], bazuje na redukcji problemu rozkładu na czynniki do problemu wyznaczenia rzędu liczby (1) w arytmetyce modularnej. Wyznaczanie rzędu liczb przy użyciu klasycznych komputerów ma złożoność wykładniczą, a więc nie przynosi żadnych korzyści w stosunku do standardowych algorytmów faktoryzacji, jednak komputery kwantowe umożliwiają jednoczesne wykonanie obliczeń dla wielu danych wejściowych (11) co prowadzi do obniżenia złożoności obliczeniowej problemu. Wprowadzenie losowego czynnika oraz właściwości kwantowego pomiaru prowadzą do probabilistycznego charakteru algorytmu. Prawdopodobieństwo niepowodzenia związane z niepewnością wyniku kwantowego pomiaru może być dowolnie zminimalizowane (14), jednak prawdopodobieństwo niepowodzenia klasycznego algorytmu rozwinięcia na ułamki łańcuchowe oraz wybrania czynnika nie spełniającego warunków algorytmu faktoryzacji są znaczne. Wyniki komputerowej symulacji wspomnianych prawdopodobieństw dla liczb złożonych stanowiących iloczyn dwóch liczb pierwszych, a więc o postaci wykorzystywanej w systemach kryptograficznych, przedstawiono odpowiednio na rys. 2 i rys. 3. Prawdopodobieństwo niepowodzenia wyznaczenia parzystego rzędu liczby na podstawie prawidłowego pomiaru kwantowego jest stosunkowo wysokie i jest bezpośrednim skutkiem właściwości funkcji totient Eulera (18). Powodzenie tego kroku może by´c zwiększone poprzez testowanie prawidłowości wielokrotności liczby otrzymanej z estymacji, jednak wpływu działań tego typu nie rozważano ze względu na mnogość dostępnych scenariuszy działania. Prawidłowy wybór czynnika x w równaniu (1) ma kluczowe znaczenie dla powodzenia dalszej części algorytmu. W literaturze [7] przyjmuje się, że prawdopodobieństwo właściwego wyboru x jest zawsze większe od 1=2. Jednak komputerowe symulacje dowodzą, że dla wielu liczb złożonych prawdopodobieństwo to znacznie przewyższa dolny kres, a w niektórych przypadkach jest bliskie 1. Można więc wnioskować, że funkcjonujące dotąd oceny skuteczności kwantowej faktoryzacji są znacznie zaniżone. Wyraźnie widoczne na rys. 3 grupowanie się wartości wspomnianego prawdopodobieństwa wokół dyskretnych poziomów sugeruje istnienie pewnej wewnętrznej zależności wynikającej z właściwości czynników tworzących liczbę złożoną. Wyniki tego typu nie były dotąd prezentowane w literaturze i wymagają dalszych badań.

4

Efektywne szukanie stacji w sieciach o topologii kraty

Rajba P.

Przegląd Elektrotechniczny

|

2009

|

R. 85, nr 4

108-115

PL

W pracy przedstawiono problem znajdowania najbardziej odległych sąsiadów dla wybranej stacji w sieci radiowej, w której stacje (z nadajnikami o jednakowej mocy) sa˛ rozmieszczone na kracie, tj. w punktach o współrzędnych całkowitych. Zaprezentowany algorytm działa w czasie O(R), gdzie R jest zasięgiem stacji.

EN

In this paper we present the problem of finding the farthest neighbours for a selected station in a radio network. The stations (with transmitters having identical range) are localized on a grid, i.e. the vertices have integer origins. The presented algorithm completed its work in time L(R), where R is a radius of the station.

5

The recognition algorithm for the probabilistic decision system with the different quality of the expert knowledge

Woźniak M.

Journal of Applied Computer Science

|

2003

|

Vol. 11, nr 2

99-108

EN

Paper deals with the knowledge acquisition process for the probabilistic expert systems. We assume that the knowledge base of the decision support system is delivered from the unreliable sources. In the paper we propose the idea of the knowledge quality management and we present the modification of the probabilistic rule-based decision algorithm (based on the Bayes formulae).

6

Determining transition probabilities in probabilistic algotithms

Borowska A.

Zeszyty Naukowe Politechniki Białostockiej. Informatyka

|

2002

|

Z.1

7-19

EN

The main problem of the paper is related to the algebraic method for determining transition probabilities in probabilistic algorithms interpreted in finite structures. The correctness of this method is based on a lemma stating that the determinant of a matrix (being of a special form) is different from zero. The paper contains two proofs of this lemma, formulated without a proof in [3].

PL

Poniższa praca zawiera dwa dowody lematu opublikowanego w pracy [3] bez dowodu. Algebraiczny fakt rozważany w lemacie jest punktem wyjściowym dla metody wyznaczania prawdopodobieństw przejść w iteracyjnych algorytmach probabilistycznych interpretowanych w skończonych dziedzinach. Dotyczy on niezerowości wyznacznika macierzy o pewnej specyficznej postaci.

7

Different approaches applied to the contextual medical decision problem

Kurzyński M., Puchała E., Woźniak M.

Journal of Medical Informatics & Technologies

|

2001

|

Vol. 2, Part. 1

MI147--MI153

EN

In many diagnostic problems there exist dependencies between successive states object and applied control. This situation is typical for the medical decision task, i.e. the recognition of the human acid-base state. We will present neural networks, probabilistic and fuzzy approach applied to the medical decision problem with context.

8

Modelowanie niepewności w pewnym problemie szeregowania zadań

Bożejko W., Wodecki M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2001

|

T. 5, z. 1/2

103-112

PL

W pracy przedstawiamy przykład stosowania metod probabilistycznych oraz teorii zbiorów rozmytych do modelowania niepewnych danych. Oba sposoby reprezentacji niedeterministycznych parametrów porównujemy na przykładzie jednomaszynowego problemu minimalizacji sumy kar zadań nie wykonanych w terminie. Na bazie powszechnie obecnie stosowanej metaheurystyki tabu search skonstruowano algorytmy rozwiązywania rozpatrywanego problemu szeregowania zadań. Na podstawie otrzymanych wyników obliczeniowych można stwierdzić, że najbardziej odporne na zaburzenie danych są rozwiązania wyznaczone przez algorytm probabilistyczny (niepewne dane są zmiennymi losowymi).

EN

We show some samples of probablistic methods and fuzzy sets application to model uncertainly data in some scheduling problems. We compare both methods of undeterministic parameters representation on the one - machine problem of minimalization the total weighted number of late jobs. On base of taboo search metaheuristic (commonly currently applied) we construct algorithms to solve scheduling problem as described above. On the basis of computational results we can affirm that the most resistant to data disturbance is solution created by probabilistic algorithm (uncertainly data are random variables).