Wyniki wyszukiwania - BazTech

1

Tight Lower Bound on Differential Entropy for Mixed Gaussian Distributions

Marconi Abdelrahman, Elghandour Ahmed H., Elbayoumy Ashraf D., Abdelaziz Amr

Journal of Telecommunications and Information Technology

|

2024

|

nr 2

23--31

EN

In this paper, a tight lower bound for the differential entropy of the Gaussian mixture model is presented. First, the probability model of mixed Gaussian distribution that is created by mixing both discrete and continuous random variables is investigated in order to represent symmetric bimodal Gaussian distribution using the hyperbolic cosine function, on which a tighter upper bound is set. Then, this tight upper bound is used to derive a tight lower bound for the differential entropy of the Gaussian mixture model introduced. The proposed lower bound allows to maintain its tightness over the entire range of the model's parameters and shows more tightness when compared with other bounds that lose their tightness over certain parameter ranges. The presented results are then extended to introduce a more general tight lower bound for asymmetric bimodal Gaussian distribution, in which the two modes have a symmetric mean but differ in terms of their weights.

2

On the Density of Spoof Odd Perfect Numbers

Tóth L.

Computational Methods in Science and Technology

|

2021

|

Vol. 27, No. 1

25--28

EN

We study the set S of odd positive integers n with the property 2n/σ(n) − 1 = 1/x, for positive integer x, i.e., the set that relates to odd perfect and odd “spoof perfect” numbers. As a consequence, we find that if D = pq denotes a spoof odd perfect number other than Descartes’ example, with pseudo-prime factor p, then q > 1012. Furthermore, we find irregularities in the ending digits of integers n ∈ S and study aspects of its density, leading us to conjecture that the quantity of numbers in S below k is ∼ 10 log(k).

3

Two-center of the Convex Hull of a Point Set : Dynamic Model, and Restricted Streaming Model

Sadhu Sanjib, Roy Sasanka, Nandi Soumen, Maheshwari Anil, Nandy Subhas C.

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 1

119--138

EN

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.

4

Lower and upper bounds for solutions of the congruence xm ≡ a(mod n)

Zakarczemny M.

Technical Transactions

|

2017

|

Vol. 11(114)

161--168

EN

Let n, m be natural numbers with n ≥ 2. We say that an integer a, (a, n) = 1, is the m-th power residue modulo n if there exists an integer x such that xm ≡ a(mod n). Let C(n) denote the multiplicative group consisting of the residues modulo n which are relatively prime to n. Let s(n, m, a) be the smallest solution of the congruence xm ≡ a(mod n) in the set C(n). Let t(n, m, a) be the largest solution of the congruence xm ≡ a(mod n) in the set C(n). We will give an upper bound for s(n, m, a) and a lower bound for t(n, m, a).

PL

Niech n, m będą liczbami naturalnymi, takimi że n ≥ 2. Powiemy, że liczba całkowita a, (a, n) = 1, jest m-tą resztą kwadratową modulo n, jeśli istnieje liczba całkowita x, taka że xm ≡ a(mod n). Niech C(n) będzie grupą multiplikatywną zawierającą reszty modulo n, względnie pierwsze z n. Oznaczmy przez s(n, m, a) najmniejsze rozwiązanie równania xm ≡ a(mod n) w zbiorze C(n). Oznaczmy przez t(n, m, a) największe rozwiązanie równania xm ≡ a(mod n) w zbiorze C(n). Podamy górne oszacowanie na s(n, m, a) oraz dolne na t(n, m, a).

5

Naming a Channel with Beeps

Chlebus B. S., De Marco G., Talo M.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 3

199--219

EN

We consider a communication channel in which the only available mode of communication is transmitting beeps. A beep transmitted by a station attached to the channel reaches all the other stations instantaneously. Stations are anonymous, in that they do not have any individual identifiers. The algorithmic goal is to assign names to the stations in such a manner that the names make a contiguous segment of positive integers starting from 1. We develop a Las Vegas naming algorithm, for the case when the number of stations n is known, and a Monte Carlo algorithm, for the case when the number of stations n is not known. The given randomized algorithms are provably optimal with respect to the expected time O(n log n), the expected number of used random bits O(n log n), and the probability of error.

6

A Lower Bound for the HBC Transversal Hypergraph Generation

Elbassioni K., Hagen M., Rauf I.

Fundamenta Informaticae

|

2014

|

Vol. 130, nr 4

409--414

EN

The computation of transversal hypergraphs in output-polynomial time is a long standing open question. An Apriori-like level-wise approach (referred to as the HBC-algorithm or MTminer) was published in 2007 by Hébert, Bretto, and Crémilleux [A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundamenta Informaticae, 80(4), 2007, 415–433] and was experimentally demonstrated to have very good performance on hypergraphs with small transversals. In this short note extending the paper by Hagen [Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157(7), 2009, 1460–1469], we prove a superpolynomial lower bound for the HBC-algorithm. This lower bound also shows that the originally claimed upper bound on the HBC-algorithm's running time is wrong.

7

On the Optimality of the Binary Algorithm for the Jacobi Symbol

Busch J.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 1-2

1-11

EN

We establish lower bounds on the complexity of computing the following number-theoretic functions and relations from piecewise linear primitives: (i) the Legendre and Jacobi symbols, (ii) pseudoprimality, and (iii) modular exponentiation. As a corollary to the lower bound obtained for (i), an algorithm of Shallit and Sorenson is optimal (up to a multiplicative constant).

8

The Shortest Common Superstring Problem and Viral Genome Compression

Ilie L., Popescu C.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

153-164

EN

Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is very close to the one achieved by modern computers.