The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in t...
详细信息
The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in terms of a simple transformation of binary trees, but its use in nontrivial problems is usually prevented by the absence of a computationally efficient algorithm. Since recent attempts to discover such an algorithm continue to be unsuccessful, we address the complementary problem of designing an approximation to the nni metric. Such an approximation should be well-defined, efficient to compute, comprehensible to users, relevant to applications, and a close fit to the nni metric; the challenge, of course, is to compromise these objectives in such a way that the final design is acceptable to users with practical and theoretical orientations. We describe an approximation algorithm that appears to satisfy adequately these objectives. The algorithm requires O(n) space to compute dissimilarity between binary trees withn labeled leaves; it requires O(n logn) time for rooted trees and O(n 2 logn) time for unrooted trees. To help the user interpret the dissimilarity measures based on this algorithm, we describe empirical distributions of dissimilarities between pairs of randomly selected trees for both rooted and unrooted cases.
作者：
BONNET, MMACCHI, OCNRS
ECOLE SUPER ELECTSIGNAUX & SYST LABF-91190 GIF SUR YVETTEFRANCE
AnalyseDeux algorithmes pour annuleur d’écho par filtrage adaptatif sont comparés à l’aide de plusieurs paramètres : résidu d’écho, complexité des calculs en précision finie ...
详细信息
Analyse
Deux algorithmes pour annuleur d’écho par filtrage adaptatif sont comparés à l’aide de plusieurs paramètres : résidu d’écho, complexité des calculs en précision finie et vitesse de convergence. Il s’agit de l’algorithme classique du gradient et de l’un de ses dérivés : l’algorithme du signe de l’erreur. Les auteurs montrent qu’en utilisant un bruit auxiliaire contrôlé, l’algorithme du signe a un comportement semblable à celui de l’algorithme du gradient en ce qui concerne le résidu d’écho et la longueur des mots binaires. Il est nettement supérieur à l’algorithme du gradient en ce qui concerne la complexité globale. Le problème de la vitesse de convergence plus faible peut être résolu par des techniques simples d’initialisation. Des simulations illustrent les résultats théoriques.
AnalyseOn envisage le décodage pondéré, à vraisemblance maximale mot par mot, des codes q-aires linéaires en blocs. Tous les mots d’un tel code sont représentés par un diagramme en ...
详细信息
Analyse
On envisage le décodage pondéré, à vraisemblance maximale mot par mot, des codes q-aires linéaires en blocs. Tous les mots d’un tel code sont représentés par un diagramme en treillis, précisément défini grâce à la représentation du code par un polynôme à plusieurs indéterminées. On définit en fonction des probabilités a priori une « cote » associée aux chemins en les nœuds du treillis, qui est une fonction non croissante du niveau de nœud et telle que le mot qui atteint la plus grande cote au dernier niveau de nœud (cote finale) est le meilleur pour le critère de vraisemblance maximale. Le décodage peut alors utiliser l’algorithme de Viterbi mais, si la cote finale d’un chemin particulier est connue, les nœuds du treillis de cote supérieure peuvent seuls appartenir au meilleur chemin. De plus, dès que l’on trouve un chemin meilleur que le chemin initialement considéré, sa cote finale sert de nouveau seuil pour la cote des nœuds, au-dessous duquel il n’y a plus à en tenir compte. Le seuil initial adopté est la cote finale du chemin spécifié par le résultat de la décision ferme sur les k premiers symboles, k étant la dimension du code. On montre de plus que son calcul fait intervenir celui du syndrome. On examine la stratégie d’exploration des autres chemins. On montre qu’un classement des symboles par fiabilité décroissante rend minimal le volume de calcul nécessaire en moyenne. Pour terminer, des moyens de simplifier davantage au détriment de l’optimalité sont brièvement décrits.
Consider a computer system in which different types of serially reusable resources are shared by several classes of processes. We assume that each process in a process class has the same known maximum claim (i.e., the...
详细信息
Consider a computer system in which different types of serially reusable resources are shared by several classes of processes. We assume that each process in a process class has the same known maximum claim (i.e., the maximum resource requirement), but that the actual sequence of requests is unknown. Our resource manager uses the "expedient policy" in granting requests for resources, under the constraint that at most K (a constant) processes can reside in the system at any time.
We present here several basic methodologies used in the design of control parts of microprocessors and discuss their classification with respect to the qualities of their design. All these different methodologies are ...
详细信息
We present here several basic methodologies used in the design of control parts of microprocessors and discuss their classification with respect to the qualities of their design. All these different methodologies are brought out by decoding existing integrated circuits. Afterwards each one of these methodologies was used to redesign a new control part for the MC 6800 microprocessor, its operation part remaining unchanged. In this way, we obtained a set of normalized solutions so that the real efficiency of each method could be estimated in terms of the cost of hardware and design time. The performance expressed by the cycle time of each control part was also calculated leading to the complete, valid classification of different design styles. Lastly, the evolution of the design efficiency versus the circuit complexity was studied.
The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are eno...
详细信息
The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource units to satisfy the request. The question of whether or not there exists a polynomial algorithm for predicting deadlock in a “claim-limited” serially reusable resource system has been open. An algorithm employing a network flow technique is presented for this purpose. Its running time is bounded by O(mn1.5) if the system consists of n processes sharing m types of serially reusable resources.
Práce se zabývá problémem třídění polí, který patří mezi známé problémy informatiky. Definuje pojmy třídění, algoritmus a složitost algoritmů. Po...
详细信息
Práce se zabývá problémem třídění polí, který patří mezi známé problémy informatiky. Definuje pojmy třídění, algoritmus a složitost algoritmů. Popisuje vybrané algoritmy pro třídění od nejjednodušších po vybrané složitější konstrukce. Nakonec jsou algoritmy porovnány v závislosti na počtu operací a době trvání celého procesu.
暂无评论