Diese Arbeit betrachtet das Cograph Editing Problem im Kontext der Rekonstruktion phylogenetischer Bäume. Insbesondere muss dafür ein Cograph rekonstruiert werden, der durch Rauschen verzerrt wurde. Liu et al. zeigten, dass Cograph Editing NP-vollständig ist. Damit ist das Problem für große Graphen wahrscheinlich nicht in realistischer Zeit korrekt lösbar. Diese Arbeit stellt daher eine Greedy-Heuristik für die Lösung des Cograph Editing Problems vor. Dabei werden Editieroperationen als günstig betrachtet, wenn sie die Anzahl an induzierten P4 in dem Graphen minimieren. Es wird ein on-line Algorithmus zur Berechnung dieser Heuristik vorgestellt und analysiert. Anschließend wird ein Greedy-Algorithmus formuliert, der eine heuristische Lösung des Cograph Editing Problems in O(|V|^4) Zeit und unter Nutzung von O(|V|^2) Speicher berechnet. Eine Implementierung dieses Greedy-Algorithmus wird auf zufällig generierten Testdaten untersucht. Parallel dazu wird auch eine Implementierung für die korrekte Lösung des Cograph Editing Problems getestet. Dabei werden die Qualität der Ergebnisse und die Laufzeit gemessen und verglichen. Hier zeigte sich, dass der Greedy-Algorithmus bei der Rekonstruktion von durch Rauschen verzerrter Cographen vergleichbar gute Ergebnisse erzielen konnte.

Étant donné G = (V, E) un graphe non orienté connexe et un entier positif β (n), où n est le nombrede sommets de G, le problème du séparateur (VSP) consiste à trouver une partition de V en troisclasses A, B et C de sorte qu'il n'y a pas d'arêtes entre A et B, max {| A |, | B |} est inférieur ou égal àβ (n) et | C | est minimum. Dans cette thèse, nous considérons une modélisation du problème sous laforme d'un programme linéaire en nombres entiers. Nous décrivons certaines inégalités valides et etdéveloppons des algorithmes basés sur un schéma de voisinage.Nous étudions également le problème du st-séparateur connexe. Soient s et t deux sommets de Vnon adjacents. Un st-séparateur connexe dans le graphe G est un sous-ensemble S de V \ {s, t} quiinduit un sous-graphe connexe et dont la suppression déconnecte s de t. Il s'agit de déterminer un stséparateur de cardinalité minimum. Nous proposons trois formulations pour ce problème et donnonsdes inégalités valides du polyèdre associé à ce problème. Nous présentons aussi une heuristiqueefficace pour résoudre ce problème. / Given G=(V,E) a connected undirected graph and a positive integer β(n), where n is number ofvertices, the vertex separator problem (VSP) is to find a partition of V into three classes A,B and Csuch that there is no edge between A and B, max{|A|,|B|}less than or equal β(n), and |C| isminimum. In this thesis, we consider aninteger programming formulation for this problem. Wedescribe some valid inequalties and using these results to develop algorithms based onneighborhood scheme.We also study st-connected vertex separator problem. Let s and tbe two disjoint vertices of V, notadjacent. A st-connected separator in the graph G is a subset S of V\{s,t} such that there are no morepaths between sand tin G[G\S] and the graph G[S] is connected . The st-connected vertex speratorproblem consists in finding such subset with minimum cardinality. We propose three formulationsfor this problem and give some valid inequalities for the polyhedron associated with this problem.We develop also an efficient heuristic to solve this problem.

This diploma thesis deals with using of explicit semantic analysis for detection similarities in source codes in the context of plagiarism. For building a semantic interpreter 40 829 Wikipedia articles were used and the analysis was tested on 25 specially created documents using plagiarism techniques and 5 downloaded documents. The dataset was consisted of five languages: Java, Javascript, PHP, C++ and Python. Another dataset of 15 documents was used for testing random matches. It was demonstrated that the analysis is capable for the given dataset do detect similarities among different languages. Greedy String Tiling algorithm was used to refine the results and together with the explicit semantic analysis is implemented in the system Anton.

L'objet de cette thèse est l'analyse et le traitement automatique de grands volumes de données audio. Plus particulièrement, on s'intéresse à l'archivage, tâche qui regroupe, au moins, deux problématiques: la compression des données, et l'indexation du contenu de celles-ci. Ces deux problématiques définissent chacune des objectifs, parfois concurrents, dont la prise en compte simultanée s'avère donc difficile. Au centre de cette thèse, il y a donc la volonté de construire un cadre cohérent à la fois pour la compression et pour l'indexation d'archives sonores. Les représentations parcimonieuses de signaux dans des dictionnaires redondants ont récemment montré leur capacité à remplir une telle fonction. Leurs propriétés ainsi que les méthodes et algorithmes permettant de les obtenir sont donc étudiés dans une première partie de cette thèse. Le cadre applicatif relativement contraignant (volume des données) va nous amener à choisir parmi ces derniers des algorithmes itératifs, appelés également gloutons. Une première contribution de cette thèse consiste en la proposition de variantes du célèbre Matching Pursuit basées sur un sous-échantillonnage aléatoire et dynamique de dictionnaires. L'adaptation au cas de dictionnaires temps-fréquence structurés (union de bases de cosinus locaux) nous permet d'espérer une amélioration significative des performances en compression de scènes sonores. Ces nouveaux algorithmes s'accompagnent d'une modélisation statistique originale des propriétés de convergence usant d'outils empruntés à la théorie des valeurs extrêmes. Les autres contributions de cette thèse s'attaquent au second membre du problème d'archivage: l'indexation. Le même cadre est cette fois-ci envisagé pour mettre à jour les différents niveaux de structuration des données. Au premier plan, la détection de redondances et répétitions. A grande échelle, un système robuste de détection de motifs récurrents dans un flux radiophonique par comparaison d'empreintes est proposé. Ses performances comparatives sur une campagne d'évaluation du projet QUAERO confirment la pertinence de cette approche. L'exploitation des structures pour un contexte autre que la compression est également envisagé. Nous proposons en particulier une application à la séparation de sources informée par la redondance pour illustrer la variété de traitements que le cadre choisi autorise. La synthèse des différents éléments permet alors d'envisager un système d'archivage répondant aux contraintes par la hiérarchisation des objectifs et des traitements. / The main goal of this work is automated processing of large volumes of audio data. Most specifically, one is interested in archiving, a process that encompass at least two distinct problems: data compression and data indexing. Jointly addressing these problems is a difficult task since many of their objectives may be concurrent. Therefore, building a consistent framework for audio archival is the matter of this thesis. Sparse representations of signals in redundant dictionaries have recently been found of interest for many sub-problems of the archival task. Sparsity is a desirable property both for compression and for indexing. Methods and algorithms to build such representations are the first topic of this thesis. Given the dimensionality of the considered data, greedy algorithms will be particularly studied. A first contribution of this thesis is the proposal of a variant of the famous Matching Pursuit algorithm, that exploits randomness and sub-sampling of very large time frequency dictionaries. We show that audio compression (especially at low bit-rate) can be improved using this method. This new algorithms comes with an original modeling of asymptotic pursuit behaviors, using order statistics and tools from extreme values theory. Other contributions deal with the second member of the archival problem: indexing. The same framework is used and applied to different layers of signal structures. First, redundancies and musical repetition detection is addressed. At larger scale, we investigate audio fingerprinting schemes and apply it to radio broadcast on-line segmentation. Performances have been evaluated during an international campaign within the QUAERO project. Finally, the same framework is used to perform source separation informed by the redundancy. All these elements validate the proposed framework for the audio archiving task. The layered structures of audio data are accessed hierarchically by greedy decomposition algorithms and allow processing the different objectives of archival at different steps, thus addressing them within the same framework.

No description available.

No description available.

No description available.

No description available.

No / Greedy and contention-based forwarding schemes were proposed for mobile ad hoc networks (MANETs) to perform data routing hop-by-hop, without prior discovery of the end-to-end route to the destination. Accordingly, the neighboring node that satisfies specific criteria is selected as the next forwarder of the packet. Both schemes require the nodes participating in the selection process to be within the area that confronts the location of the destination. Therefore, the lifetime of links for such schemes is not only dependent on the transmission range, but also on the location parameters (position, speed and direction) of the sending node and the neighboring node as well as the destination. In this paper, we propose a new link lifetime prediction method for greedy and contention-based routing which can also be utilized as a new stability metric. The evaluation of the proposed method is conducted by the use of stability-based greedy routing algorithm, which selects the next hop node having the highest link stability.

The purpose of this research was to provide a better understanding of handbooks and to establish criteria guidelines for handbook selection and use. Content analysis utilizing the library as fieldwork identified 15 handbooks for MsWs meeting selection criteria for this study. Coding and diagramming of over 2000 pages resulted in identification of 15 themes which grouped into 3 types of relationships: personal (to self and God), familial (to husband and children), and congregational (to the church). Six of these themes were recognized as distinctive to the life of the MsW. Three time frames (1940 to 1960, 1960 to 1980, and 1980 to 1998) were established, and handbooks were found to be consistent with the social context of their respective era. An unfolding picture of the life of the MsW as portrayed by key informants revealed a shift in emphasis, with earlier handbooks portraying a lifeworld revolving around role fulfillment, and later handbooks emphasizing development as a person. A lack of learning opportunities for MsWs was noted throughout the eras. A 30+ page appendix of metaphors indicates that MsWs use their gift of reasoning through word pictures. The authors taught lived world truth as they perceived it. This study indicated clues as to appropriateness of content in handbooks and safeguards to be taken in reading them for self-directed learning or other training purposes. The implication is that handbooks are adult education by default. Two original products resulting from this research were a schemata of the process of using handbooks as a format for learning and selection criteria guidelines for choosing a handbook. The process may be utilized in self-directed learning (individual or guided) and within other educational settings, and the guidelines may be adapted to handbooks for other populations. This research should encourage related studies to broaden the knowledge base of understanding handbooks and recognizing their place in training, utilizing field research using literature sources, and assisting MsWs with learning how to effectively manage their myriad roles and relationships. / Ed. D.