Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: time and space complexity

Sortuj według:

Ogranicz wyniki do:

Trade-Offs Between Time, Space, Cooperation, and Communication Complexity for CD Grammar Systems

Cojocaru L.

Fundamenta Informaticae

2011

Vol. 107, nr 4

345-378

In this paper we investigate the communication and cooperation phenomenon in Cooperating Distributed Grammar Systems (henceforth CDGSs). In this respect, we define several complexity structures and two complexity measures, the cooperation and communication complexity measures. These measures are studied with respect to the derivation modes and fairness conditions under which CDGSs may work. We deal with trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with regular, linear, and context-free components. Cooperation and communication processes in CDGSs with regular and linear components are of equal complexity. The two (equal) cooperation and communication complexity measures are either constant or linear, as functions of lengths of words in the generated language. The same result holds for the cooperation and communication complexity of q-fair languages generated by CDGSs with regular and linear components. For the case of non-constant communication (cooperation) the time and space used by a nondeterministicmultitape Turingmachine to recognizeweakly q-fair languages are linear, as is the communication (cooperation) complexity. For CDGSs with context-free components the cooperation and communication complexity may be different. These measures are either linear or logarithmic functions, in terms of lengths of words in the generated language. In order to find trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with context-free components we study asymptotic behavior of growth functions characteristic to these measures. We prove that languages generated by CDGSs with context-free components are accepted by nondeterministicmultitape Turing machines either in quadratic time, linear space, and with cooperation complexity that varies from logarithmic to linear, or in polynomial or exponential time and space, and linear cooperation complexity.

A new Bayesian tree construction : method with decreased time complexity

Kłopotek M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2001

Nr 927

1-11

Bayesian networks have many practical applications due to their capability to represent joint probability distribution in many variables in a compact way. There exist efficient reasoning methods for Bayesian networks. Many algorithms for learning Bayesian networks from empirical data have been developed. A well-known problem with Bayesian networks is the practical limitation for the number of variables for which a Bayesian network can be learned in reasonable time. A remarkable exception here is the Chow/Liu algorithm learning tree-like Bayesian networks. However, its quadratic time and space complexity in the number of variables may prove also prohibitive for high dimensional data. The paper presents a novel algorithm overcoming this limitation for the tree-like class of Bayesian networks. The new algorithm space consumption grows linearly with the number of variables n while the execution time is proportional to n ln (n), hence both are better than those of Chow/Liu algorithm. This opens new perspectives in construction of Bayesian networks from data containing tens of thousands and more variables, e.g. in automatic text categorization.

Sieci bayesowskie mają wiele praktycznych zastosowań związanych z ich zdolnością do zwartej reprezentacji rozkładów prawdopodobieństwa w wielu zmiennych. Istnieją efektywne metody wnioskowania w sieciach bayesowskich. Opracowano wiele algorytmów uczenia sieci z danych. Znanym problemem sieci bayesowskich są ograniczenia co do ilości zmiennych, dla których algorytmy uczące działają w rozsądnym czasie. Wyjątkiem jest tu algorytm Chow/Liu generujący drzewiaste sieci bayesowskie. Niestety, jego kwadratowa złożonośc obliczeniowa w liczbie zmiennych jest poważnym ograniczeniem dla wielu nowych zastosowań wielowymiarowych. W pracy przedstawiony jest nowy algorytm uczenia sieci drzewiastych z danych, który ma liniowe zużycie pamięci, a jednocześnie czas jego wykonania jest proporcjonalny do n ln(n). Zarówno złożoność czasowa jak i przestrzenna przewyższa parametry algorytmu Chow/Liu. Stwarza to nowe perspektywy zastosowań w sytuacjach, gdy trzeba tworzyć sieci liczące dziesiątki tysięcy i więcej węzłów, np. automatycznej kategoryzacji tekstów.