排序方式: 共有16条查询结果,搜索用时 15 毫秒
1.
Cicalese F. Vaccaro U. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2002,48(4):933-938
We prove that the entropy is a supermodular and subadditive function on the lattice of all n-dimensional probability distributions, ordered according to the partial order relation defined by majorization among vectors 相似文献
2.
We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full
knowledge about the size and the topology of the network. We show that gossiping can be completed in
time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than
units of time. Moreover, we show a
schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules
by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log 3
n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log 2
n) time broadcasting schedule by Kowalski and Pelc.
A preliminary version of this paper appeared in the proceedings of ISAAC’06.
F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported
by the Research Council of Norway through the SPECTRUM project. 相似文献
3.
4.
Giada La Scalia Giuseppe Aiello Cristiana Rastellini Rosa Micale Luca Cicalese 《Expert systems with applications》2011,38(4):3091-3097
Pancreatic islet transplantation consists of replacing insulin-producing cells to restore normal glycemia in diabetic patients. This is a minimal invasive procedure that has been proved successful. Unfortunately unpredictability of islet transplant outcome remains a frustrating and costly issue limiting the clinical implementation of this procedure. Multiple variables are involved in the procedure and assessment is subjective to individual operators. The aim of this study was to generate a system expressing the probability of transplant success in relation to four classes of identified variables (donor, organ, isolation and recipient). We have proposed the utilization of Multi-Criteria Decision Making methods (MCDM) as a powerful tool for evaluating pancreatic islet transplant-related information with the goal to achieve optimal decision. Technique Ordered Preference by Similarity to the Ideal Solution (TOPSIS), one of the most widely used MCDM methods in decision support systems, was here utilized with modification to fit better in a medical system. In our modified method, we have utilized fuzzy logic in order to consider uncertain and vague data. 相似文献
5.
Cicalese F. Vaccaro U. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(4):633-637
We consider the problem of bounding the average length of an optimal (Huffman) source code when only limited knowledge of the source symbol probability distribution is available. For instance, we provide tight upper and lower bounds on the average length of optimal source codes when only the largest or the smallest source symbol probability is known. Our results rely on basic results of majorization theory and on the Schur concavity of the minimum average length of variable-length source codes for discrete memoryless sources. In the way to prove our main result we also give closed formula expressions for the average length of Huffman codes for several classes of probability distributions. 相似文献
6.
Ferdinando Cicalese 《Theory of Computing Systems》2014,54(4):578-594
We study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious. In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k>0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions. 相似文献
7.
8.
We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1,…,M}. Player Q has to find out x by asking questions of type: “which one of the sets A1,A2,…,Aq, does x belong to?”, where the sets A1,…,Aq constitute a partition of S. Player R answers “i” to indicate that the number x belongs to Ai. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [logqM]. The case q=2 and e1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qi, for any i1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qi, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions. 相似文献
9.
We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let qe(m) be the smallest integer q satisfying Berlekamp’s bound
. Then at least qe(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly qe(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly qe(m) questions—or equivalently, e-error correcting codes with 2m codewords of length qe(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, qe(m)−1 questions do not suffice to find the unknown number, and qe(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests. 相似文献
10.