Table des matières
30 relations: Algorithme, Algorithme de Ford-Fulkerson, Algorithme de poussage/réétiquetage, Algorithme probabiliste, Algorithmique, Classe de complexité, Complexité en temps, Contraction d'arête, Coupe (théorie des graphes), Coupe minimum, Degré (théorie des graphes), E (nombre), Georgia Institute of Technology, Graphe non orienté, Lexique de la théorie des graphes, Liste d'adjacence, Matrice d'adjacence, NC (complexité), Principe de contraction, Problème de flot maximum, Pseudo-code, Rajeev Motwani, Sanjeev Arora, Taux d'expansion (théorie des graphes), Terminaison d'un algorithme, Théorème flot-max/coupe-min, Théorie des graphes, Université de Patras, Université de Princeton, Université Paris-Diderot.
Algorithme
triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes.
Voir Algorithme de Karger et Algorithme
Algorithme de Ford-Fulkerson
Exemple d'exécution de l'algorithme de Ford-Fulkerson. L'animation affiche le graphe résiduel correspondant à chaque itération. En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème de flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle.
Voir Algorithme de Karger et Algorithme de Ford-Fulkerson
Algorithme de poussage/réétiquetage
Lalgorithme push-relabel (traduit en français par algorithme de poussage/réétiquetage), aussi appelé algorithme de Goldberg-Tarjan, est l'un des algorithmes les plus efficaces pour calculer un flot maximum dans un réseau.
Voir Algorithme de Karger et Algorithme de poussage/réétiquetage
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard.
Voir Algorithme de Karger et Algorithme probabiliste
Algorithmique
Organigramme de programmation représentant l'algorithme d'Euclide. Lalgorithmique est l'étude et la production de règles et techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution d'un problème permettant de décrire précisément des étapes pour résoudre un problème algorithmique.
Voir Algorithme de Karger et Algorithmique
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource.
Voir Algorithme de Karger et Classe de complexité
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.
Voir Algorithme de Karger et Complexité en temps
Contraction d'arête
En théorie des graphes, une contraction d'arête est une opération sur un graphe.
Voir Algorithme de Karger et Contraction d'arête
Coupe (théorie des graphes)
En théorie des graphes, une coupe d'un graphe est une partition des sommets en deux sous-ensembles.
Voir Algorithme de Karger et Coupe (théorie des graphes)
Coupe minimum
En théorie des graphes et en informatique théorique, une coupe minimum (« coupe min », en anglais: ou) d'un graphe est une coupe contenant un nombre minimal d'arêtes.
Voir Algorithme de Karger et Coupe minimum
Degré (théorie des graphes)
Un graphe G non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est \Delta(G).
Voir Algorithme de Karger et Degré (théorie des graphes)
E (nombre)
1, e. Le nombre est la base des logarithmes naturels, c'est-à-dire le nombre défini par.
Voir Algorithme de Karger et E (nombre)
Georgia Institute of Technology
Le Georgia Institute of Technology, connu aussi sous le nom de Georgia Tech ou GT, est une université de recherche mixte publique, et située à Atlanta (Géorgie), aux États-Unis.
Voir Algorithme de Karger et Georgia Institute of Technology
Graphe non orienté
Exemple de graphe non orienté à 5 sommets. En théorie des graphes, un graphe non orienté G.
Voir Algorithme de Karger et Graphe non orienté
Lexique de la théorie des graphes
; Acyclique: graphe ne contenant pas de cycle.
Voir Algorithme de Karger et Lexique de la théorie des graphes
Liste d'adjacence
Pour chaque sommet, la liste d'adjacence est représentée en jaune. En algorithmique, une liste d'adjacence est une structure de données utilisée pour représenter un graphe.
Voir Algorithme de Karger et Liste d'adjacence
Matrice d'adjacence
En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à sommets est une matrice de dimension dont l'élément non diagonal est le nombre d'arêtes liant le sommet au sommet.
Voir Algorithme de Karger et Matrice d'adjacence
NC (complexité)
En théorie de la complexité, un domaine de l'informatique théorique, NC (pour) est une classe de complexité faisant intervenir le parallélisme.
Voir Algorithme de Karger et NC (complexité)
Principe de contraction
Dans la théorie des probabilités et statistique fondamentales, et plus précisément dans la théorie de principe de grandes déviations, le principe de contraction est un théorème qui établit que la mesure image d'un espace de probabilité vérifiant le principe de grandes déviations par une application continue vérifiera également le principe de grandes déviations.
Voir Algorithme de Karger et Principe de contraction
Problème de flot maximum
Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum.
Voir Algorithme de Karger et Problème de flot maximum
Pseudo-code
En programmation, le pseudo-code, également appelé LDA (pour Langage de Description d'Algorithmes) est une façon de décrire un algorithme en langage presque naturel, sans référence à un langage de programmation en particulier.
Voir Algorithme de Karger et Pseudo-code
Rajeev Motwani
Rajeev Motwani (राजीव मोटवानी; -) était un professeur et chercheur en informatique théorique à l'Université Stanford.
Voir Algorithme de Karger et Rajeev Motwani
Sanjeev Arora
Sanjeev Arora (né en à Jodhpur) est un chercheur en informatique théorique indien connu pour son travail en théorie de la complexité et en algorithmique.
Voir Algorithme de Karger et Sanjeev Arora
Taux d'expansion (théorie des graphes)
En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe Shlomo Hoory, Nathan Linial et Avi Widgerson.
Voir Algorithme de Karger et Taux d'expansion (théorie des graphes)
Terminaison d'un algorithme
La terminaison est une propriété fondamentale des algorithmes.
Voir Algorithme de Karger et Terminaison d'un algorithme
Théorème flot-max/coupe-min
Le théorème flot-max/coupe-min (ou en anglais) est un théorème important en optimisation et en théorie des graphes.
Voir Algorithme de Karger et Théorème flot-max/coupe-min
Théorie des graphes
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.
Voir Algorithme de Karger et Théorie des graphes
Université de Patras
L’université de Patras (Πανεπιστήμιο Πατρών) fut créée en 1964.
Voir Algorithme de Karger et Université de Patras
Université de Princeton
L'université de Princeton (Princeton University) aussi appelée Princeton est une université américaine privée située dans la ville de Princeton (New Jersey), aux États-Unis.
Voir Algorithme de Karger et Université de Princeton
Université Paris-Diderot
L'université Paris-DiderotNom d'usage dont s'est doté l'établissement par délibération de son conseil d'administration.
Voir Algorithme de Karger et Université Paris-Diderot