Algorithme de Tarjan : Différence entre versions
De Sciencinfolycee
(8 révisions intermédiaires par 3 utilisateurs non affichées) | |||
Ligne 5 : | Ligne 5 : | ||
|SiloRole=auteur; | |SiloRole=auteur; | ||
|SiloLangue=fre | |SiloLangue=fre | ||
− | |Résumé=Présentation de l'algorithme de Tarjan. | + | |Résumé=Présentation de l'algorithme de Tarjan : du nom de son inventeur Robert Tarjan, il permet de déterminer les composantes fortement connexes d'un graphe orienté. Il est de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux. |
− | |Catégorie= | + | |Catégorie=Algorithmes classiques |
− | |Mots-clés contrôlés= | + | |Mots-clés contrôlés=théorie des graphes; graphe orienté; algorithme de Tarjan; Tarjan, Robert E. : 1948-; |
|SiloTypeDocumentaire=texte | |SiloTypeDocumentaire=texte | ||
|SiloTypologieGenerale=article | |SiloTypologieGenerale=article | ||
Ligne 13 : | Ligne 13 : | ||
|SiloStructure=atomique | |SiloStructure=atomique | ||
|SiloNiveauAgregation=1.Le plus petit niveau (grain) | |SiloNiveauAgregation=1.Le plus petit niveau (grain) | ||
− | |Format= | + | |Format=PDF |
|SiloTypePedagogique=cours / présentation | |SiloTypePedagogique=cours / présentation | ||
|SiloPublicCible=enseignant | |SiloPublicCible=enseignant |
Version actuelle datée du 17 février 2012 à 16:04
Section Description | |
---|---|
URL | http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/tarjan.pdf |
Titre | Algorithme de Tarjan |
Auteur(s) | Pichardie, David |
Fonction(s) | auteur |
Notes | |
Section Analyse | |
Langue | fre |
Résumé | Présentation de l'algorithme de Tarjan : du nom de son inventeur Robert Tarjan, il permet de déterminer les composantes fortement connexes d'un graphe orienté. Il est de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux. |
Sélection(s) thématique(s) | Algorithmes classiques |
Mots-clés normalisés | théorie des graphes ; graphe orienté ; algorithme de Tarjan ; Tarjan, Robert E. : 1948- |
Proposition autres mots-clés | |
Type documentaire | texte |
Typologie Générale | article |
Date de publication | 2010/11/02 |
Structure du document | atomique |
Niveau d'agrégation | 1.Le plus petit niveau (grain) |
Exigences techniques | |
Section Pédagogie | |
Type pédagogique | cours / présentation |
Public cible | enseignant |
Utilisation pédagogique | |
Section Relation | |
Type de la relation | est une partie de |
URL de la relation | http://www.irisa.fr/celtique/pichardie/teaching/L3/ALGO/ |
Section Droits | |
Droits du document | |
Section processus de validation (workflow) | |
Intervenants | Thierry; Diane Rives (indexation); DB |
Statut du workflow | publiée |
Signaler cette ressource. Si ce lien de signalement ne fonctionne pas (ouverture intempestive d'un mailer alors que vous utilisez un webmail) c'est qu'il vous manque l'extension idoine dans votre navigateur (par exemple l'extension send-mail pour firefox); c'est une bonne occasion de l'installer.