Accès plus rapide que le navigateur!
31 relations: Algorithme d'approximation, Algorithme glouton, Algorithmique, APX (complexité), Cambridge University Press, Complexité en temps, David P. Williamson, Delbert Ray Fulkerson, Ensemble dominant, Espace euclidien, Espace métrique, Fonction objectif, Gerhard Woeginger, Graphe complet, Graphe planaire, Inégalité triangulaire, Jack Edmonds, K-médiane, K-moyennes, Marek Karpinski, NP-difficile, Optimisation combinatoire, Partitionnement de données, Problème algorithmique, Problème de décision, Problème de l'emplacement d'installations, Problème NP-complet, Problème P ≟ NP, Schéma d'approximation en temps polynomial, Théorie des graphes, Université de Californie à San Diego.
Algorithme d'approximation
En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation.
Nouveau!!: K-centre et Algorithme d'approximation · Voir plus »
Algorithme glouton
Un algorithme glouton (en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global.
Nouveau!!: K-centre et Algorithme glouton · Voir plus »
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.
Nouveau!!: K-centre et Algorithmique · Voir plus »
APX (complexité)
En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant.
Nouveau!!: K-centre et APX (complexité) · Voir plus »
Cambridge University Press
Cambridge University Press ou CUP (en français, Presses universitaires de Cambridge) est une maison d'édition universitaire britannique rattachée à l’université de Cambridge.
Nouveau!!: K-centre et Cambridge University Press · Voir plus »
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.
Nouveau!!: K-centre et Complexité en temps · Voir plus »
David P. Williamson
David Paul Williamson (né en 1967) est un mathématicien américain, professeur de recherche opérationnelle à l'université Cornell et rédacteur en chef du SIAM Journal on Discrete Mathematics.
Nouveau!!: K-centre et David P. Williamson · Voir plus »
Delbert Ray Fulkerson
Delbert Ray Fulkerson (-) est un mathématicien américain, coauteur de l'algorithme de Ford-Fulkerson.
Nouveau!!: K-centre et Delbert Ray Fulkerson · Voir plus »
Ensemble dominant
En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G.
Nouveau!!: K-centre et Ensemble dominant · Voir plus »
Espace euclidien
En mathématiques, un espace euclidien est un objet algébrique permettant de généraliser de façon naturelle la géométrie traditionnelle développée par Euclide, dans ses Éléments.
Nouveau!!: K-centre et Espace euclidien · Voir plus »
Espace métrique
En mathématiques et plus particulièrement en topologie, un espace métrique est un ensemble au sein duquel une notion de distance entre les éléments de l'ensemble est définie.
Nouveau!!: K-centre et Espace métrique · Voir plus »
Fonction objectif
comparaison de certains substituts de la fonction de perte Le terme fonction objectif, fonction économique ou fonction de coût, est utilisé en optimisation mathématique et en recherche opérationnelle pour désigner une fonction qui sert de critère pour déterminer la meilleure solution à un problème d'optimisation.
Nouveau!!: K-centre et Fonction objectif · Voir plus »
Gerhard Woeginger
Gerhard J. Woeginger, né le à Graz, en Autriche et mort le, est un mathématicien et informaticien autrichien.
Nouveau!!: K-centre et Gerhard Woeginger · Voir plus »
Graphe complet
En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête.
Nouveau!!: K-centre et Graphe complet · Voir plus »
Graphe planaire
Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre.
Nouveau!!: K-centre et Graphe planaire · Voir plus »
Inégalité triangulaire
En géométrie, l'inégalité triangulaire est le fait que, dans un triangle, la longueur d'un côté est inférieure à la somme des longueurs des deux autres côtés.
Nouveau!!: K-centre et Inégalité triangulaire · Voir plus »
Jack Edmonds
Jack R. Edmonds, né le, est un mathématicien et informaticien théoricien canadien, considéré comme l'un des contributeurs les plus importants dans le domaine de l'optimisation combinatoire.
Nouveau!!: K-centre et Jack Edmonds · Voir plus »
K-médiane
Le problème k-médiane, ou k-median en anglaisLa traduction en français provient de la traduction par Nicolas Shabanel de, voir.
Nouveau!!: K-centre et K-médiane · Voir plus »
K-moyennes
Le partitionnement en k-moyennes (ou en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire.
Nouveau!!: K-centre et K-moyennes · Voir plus »
Marek Karpinski
Marek Karpinski est un informaticien et mathématicien connu pour ses recherches en théorie d'algorithmes et leurs applications, en optimisation combinatoire, en théorie de la complexité et en fondations mathématiques d'informatique.
Nouveau!!: K-centre et Marek Karpinski · Voir plus »
NP-difficile
Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP.
Nouveau!!: K-centre et NP-difficile · Voir plus »
Optimisation combinatoire
L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité.
Nouveau!!: K-centre et Optimisation combinatoire · Voir plus »
Partitionnement de données
clustering'' hiérarchique. Le partitionnement de données (ou en anglais) est une méthode en analyse des données.
Nouveau!!: K-centre et Partitionnement de données · Voir plus »
Problème algorithmique
Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre.
Nouveau!!: K-centre et Problème algorithmique · Voir plus »
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».
Nouveau!!: K-centre et Problème de décision · Voir plus »
Problème de l'emplacement d'installations
Le problème d'emplacement d'installations (facilities location problem) est un problème de recherche opérationnelle et de géométrie algorithmique.
Nouveau!!: K-centre et Problème de l'emplacement d'installations · Voir plus »
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Nouveau!!: K-centre et Problème NP-complet · Voir plus »
Problème P ≟ NP
Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.
Nouveau!!: K-centre et Problème P ≟ NP · Voir plus »
Schéma d'approximation en temps polynomial
En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire.
Nouveau!!: K-centre et Schéma d'approximation en temps polynomial · Voir plus »
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.
Nouveau!!: K-centre et Théorie des graphes · Voir plus »
Université de Californie à San Diego
L'université de Californie à San Diego (communément appelée UCSD) fait partie de l'université de Californie.
Nouveau!!: K-centre et Université de Californie à San Diego · Voir plus »
Redirections ici:
K-centre métrique, Problème du k-centre métrique.
