Plus longue sous-séquence commune

En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique. La généralisation à un nombre arbitraire de suites est un problème NP-difficile : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences. Exemple Pour les deux séquences de caractères suivantes :

« abcde »,
« ceij », la plus longue sous-séquence commune est « ce ».

Dans ce problème, il est nécessaire que les éléments communs soient dans le même ordre dans les différentes séquences, mais pas qu’ils soient obligatoirement consécutifs : « e » n’est pas consécutif à « c » dans la première séquence. Algorithme par force brute On constate par dénombrement qu'il existe 2^n sous-séquences pour une chaîne de longueur n. Les essayer toutes par force brute pour trou

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (15)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (4)

Concepts associés

Chargement

Cours associés (3)

Cours associés

Chargement

Séances de cours associées (18)

Séances de cours associées

Chargement

Entity Search with NECESSITY

Nicolas Bonvin, Ekaterini Ioannou, Anshul Jain, Zoltán Miklós, Saket Sathe, Gleb Skobeltsyn

Loosely structured heterogeneous information spaces are typically created by merging data from a variety of different applications and information sources. A common problem these information spaces need to address is that various data describe the same real-word entities (e.g., conferences, organizations). In this demo, we introduce necessity, an efficient and scalable entity store. necessity is able to handle a large number of entities and at the same time provide an efficient and highly accurate entity search functionality for heterogeneous and partially structured queries that follow the vision of dataspaces.

2009

Chargement

Learn to synthesize and synthesize to learn

Hazim Kemal Ekenel, Mohammad Saeed Rad, Jean-Philippe Thiran

Attribute guided face image synthesis aims to manipulate attributes on a face image. Most existing methods for image-to-image translation can either perform a fixed translation between any two image domains using a single attribute or require training data with the attributes of interest for each subject. Therefore, these methods could only train one specific model for each pair of image domains, which limits their ability in dealing with more than two domains. Another disadvantage of these methods is that they often suffer from the common problem of mode collapse that degrades the quality of the generated images. To overcome these shortcomings, we propose attribute guided face image generation method using a single model, which is capable to synthesize multiple photo-realistic face images conditioned on the attributes of interest. In addition, we adopt the proposed model to increase the realism of the simulated face images while preserving the face characteristics. Compared to existing models, synthetic face images generated by our method present a good photorealistic quality on several face datasets. Finally, we demonstrate that generated facial images can be used for synthetic data augmentation, and improve the performance of the classifier used for facial expression recognition.

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Chargement

Learn to synthesize and synthesize to learn

Hazim Kemal Ekenel, Mohammad Saeed Rad, Jean-Philippe Thiran

2019

Chargement

MATH-302: Functional analysis I

Concepts de base de l'analyse fonctionnelle linéaire: opérateurs bornés, opérateurs compacts, théorie spectrale pour les opérateurs symétriques et compacts, le théorème de Hahn-Banach, les théorèmes de l'application ouverte et du graphe fermé.

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-421: Machine learning for behavioral data

Computer environments such as educational games, interactive simulations, and web services provide large amounts of data, which can be analyzed and serve as a basis for adaptation. This course will cover the core methods of user modeling and personalization, with a focus on educational data.

Programmation dynamique

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'épo

Distance d'édition sur les arbres

En informatique théorique, en biochimie et aussi dans des applications, en vision par ordinateur par exemple, la distance d'édition d'arbres (en anglais tree edit distance) est une mesure qui évalue,

Diff

diff est une commande Unix qui permet de comparer deux fichiers et d’en afficher les différences. Son utilisation typique consiste à calculer les changements entre une version d’un fichier et une ver