Discussion :

[zouhour]

Bonjour,
Est ce que quelqu'un peux m'informer sur la notion d'Algorithmes Combinatoires, c'est trés urgent.



Merci

[PRomu@ld]

Le sujet est très vaste.

Mais saches que si c'est pour te faire une bibliographie, internet regorge de ressources à ce sujet.

[FrancisSourd]

Dans le cadre de la complexité, si on a n entiers valant au plus K, on dit qu'un algorithme est polynomial s'il s'exécute en O(P(n log K)) où P est un polynôme.

On dit qu'un algorithme est combinatoire s'il s'exécute en O(P(n)) lorsqu'on suppose que les opérations arithmétique de base se font en O(1).

Par exemple, on peut montrer que la programmation linéaire peut être résolue en temps polynomial par différents algorithmes (points intérieurs, ellipsoide) mais le nombre d'itérations lors de l'exécution de ces algorithmes dépend de log K. Ces algos ne sont donc pas combinatoires.

Inversement, les algorithmes de flots, de tris, d'arbres couvrants sont combinatoires. Quand on dit que le tri est en O(n log n) ce n'est pas tout à fait exacte: en effet comparer deux nombres de l'ordre de K=2^150 se fait avec log K=150 opérations élémentaires. La "vraie" complexité de ces algos dépend donc bel et bien de log K. En pratique, comme log K ne dépasse pas les 64 bits, on l'oublie et on profite du fait que la comparaison de deux registres se fait, électroniquement, de manière parallèle.