Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Concept

Tri topologique

En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Exemple de tri topologique Soit G=(S,A) un graphe orienté avec S={1,2,3,4,5,6,7,8,9} et A={(1,2),(1,8),(2,8),(2,3),(3,6),(4,3),(4,5),(5,6),(9,8)}. Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6. En effet, chaque sommet apparaît bien avant ses successeurs. Il n'y a pas unicité de l'ordre. Algorithme Pour un graphe représenté en mémoire sous une forme facile à parcourir, par exemple par listes d'adjacence, le calcul d'un tri topologique est simple. Il

À 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

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Résumé

Source officielle

À propos de ce résultat

Publications associées (21)

Publications associées

Chargement

Personnes associées (5)

Personnes associées

Chargement

Unités associées (3)

Unités associées

Chargement

Concepts associés (13)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (14)

Séances de cours associées

Chargement

Coalgèbres d'Alexander-Whitney

Théophile Naïto

The goal of this work is to study Alexander-Whitney coalgebras (first defined in [HPST06]) from a topological point of view. An Alexander-Whitney coalgebra is a coassociative chain coalgebra over Z with an extra algebraic structure : the comultiplication must respect the coalgebra structure up to an infinite sequence of homotopies (this sequence is part of the data of the Alexander-Whitney coalgebra structure). Alexander-Whitney coalgebras are interesting for topologists because the normalized chain complex C(K) of a simplicial set K is endowed with an Alexander-Whitney coalgebra structure. This theorem is proved for the first time here (generalising a result proven in [HPST06]). This theorem gives the hope that the Alexander-Whitney coalgebra structure of C(K) contains interesting information that can be used to solve topological problems. This hope is strengthened by the success already obtained in the work of several topologists. Among others, [HPST06], [HL07], [Boy08], and [HR] use the Alexander-Whitney coalgebra structure of the normalized chains of a simplicial set in an essential way to solve topological problems. This thesis begins with some background material. In particular, the definition of a DCSH morphism between two coassociative chain coalgebras is recalled in complete detail. For example, signs are determined with great precision. Next we devote a chapter to the definition of Alexander-Whitney coalgebras and to their importance in topology. In the following chapter we begin the conceptual study of Alexander-Whitney coalgebras. A global study of these objects had not yet been carried out even if the Alexander-Whitney coalgebra structure has been studied and used in order to answer some specific questions. With the aim of studying Alexander-Whitney coalgebras in a nice setting, we develop an operadic description of these coalgebras in the following chapter. More precisely, we show that there is an explicit operad AW such that the coalgebras over this operad are exactly the Alexander-Whitney coalgebras. Furthermore, AW is shown to be a Hopf operad, so that the category formed by the Alexander-Whitney coalgebras is actually a monoidal category. These results are proven in a reasonably general framework. In fact, we associate an operad to each bimodule (over the associative operad) of a certain type, such that we get AW if this bimodule is well chosen. In particular, these results enable us to study Alexander-Whitney coalgebras from the standpoint of operads. This strategy is recognised to be successful in various mathematical situations, and especially in algebraic topology. Moreover, we develop a minimal model notion in the setting of right module over a chosen operad (which has to satisfy some reasonable conditions), with the aim of applying this result to the special case of the Alexander-Whitney coalgebras. This is possible because coalgebras over some fixed operad P can be seen as right modules over P. And the category of right modules over P has some nice features which do not appear to hold in the category of P-coalgebras. The inspiration for this part of our work comes from the notion of minimal model developed in the framework of rational homotopy theory. The two following facts show that it is reasonable to try to adapt some ideas of rational homotopy theory to the category of Alexander-Whitney coalgebras. A. There is a theorem that says that studying topological spaces up to rational equivalences is, essentially, equivalent to studying cocommutative chain coalgebras over the field of rational numbers. This is false if the ring of integers replaces the field of rational numbers, but Alexander-Whitney coalgebras are "almost" cocommutative in the sense which is explained in this thesis. B. It could be that the Alexander-Whitney coalgebra structure of the normalized chains of a simplicial set is weak enough to allow explicit computations. At least, it is clear that the Alexander-Whitney coalgebra structure on the normalized chains is far from being an E∞-structure (such a structure determines the homotopy type of the considered simplicial set, at least under some conditions). The chapter about minimal models in the framework of right modules over an operad includes an existence theorem and a discussion of the unicity of this model. In the second part of this chapter, we construct an explicit path-object in the model category of right modules over an operad. This path-object is then used to investigate the topologically relevant information that could stem from the minimal model in the case of the operad AW. Finally, we present and examine some interesting open questions about Alexander-Whitney coalgebras. These questions give a nice outlook on future research in this area.

EPFL2009

Chargement

Thurston equivalence of topological polynomials

Springer, Kluwer Academic Publishers2006

Chargement

Hierarchical Multi-Stream Posterior Based Speech Recognition System

Samy Bengio, Hervé Bourlard, Hamed Ketabdar

In this paper, we present initial results towards boosting posterior based speech recognition systems by estimating more informative posteriors using multiple streams of features and taking into account acoustic context (e.g., as available in the whole utterance), as well as possible prior information (such as topological constraints). These posteriors are estimated based on ``state gamma posterior'' definition (typically used in standard HMMs training) extended to the case of multi-stream HMMs.%, resulting in new features. This approach provides a new, principled, theoretical framework for hierarchical estimation/use of posteriors, multi-stream feature combination, and integrating appropriate context and prior knowledge in posterior estimates. In the present work, we used the resulting gamma posteriors as features for a standard HMM/GMM layer. On the OGI Digits database and on a reduced vocabulary version (1000 words) of the DARPA Conversational Telephone Speech-to-text (CTS) task, this resulted in significant performance improvement, compared to the state-of-the-art Tandem systems.

2005

Chargement

Graphe orienté acyclique

En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie.

Lexique de la théorie des graphes

NOTOC A ; Acyclique : graphe ne contenant pas de cycle. ; Adjacence : une liste d'adjacence est une structure de données constituée d'un tableau dont le i-ème élément co

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets

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-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

DH-405: Foundations of digital humanities

This course gives an introduction to the fundamental concepts and methods of the Digital Humanities, both from a theoretical and applied point of view. The course introduces the Digital Humanities circle of processing and interpretation, from data acquisition to new understandings.