Qu'est-ce-que les algorithme exponentielle?

[invite0b5c32d7]

Bonjour à tous.

Je voudrais savoir ce qu'est les algorithme exponentielle.

Je l'aies entendu en regardant la télévision et je suis une personne de nature curieuse.

Si vous avez des liens pdf et autre je serais ravi de les lire.

Merci
-----

[invite4492c379]

Hello,

Je suppose que tu parles des algorithmes à complexité exponentielle. On mesure l'efficacité d'un algorithme en fonction de la «taille» des données en entrée. Par exemple si tu disposes d'un algo qui trie un tableau d'entier on appellera taille le nombre de cellules dans ce tableau par exemple. Pour le cas du voyageur de commerce qui consiste à trouver un chemin qui relie toutes les villes on peut considérer le nombre de ville et le nombre de routes qui relient ces villes.
L'efficacité mesurée est souvent le temps que met l'algo à résoudre le problème, mais on peut aussi considérer la place mémoire utilisée.
On dispose de plusieurs catégories d'algo :

* linéaire, si on double la taille des entrées, le temps sera doublé
par exemple charcher un nombre dans tableau trié avec un méthode naïve est en O(n), c'est ainsi que c'est noté.Tu prends un tableau deux fois plus grand, tu metteras deux fois plus de temps

* polynomial, si on multiplie la taille des entrée par n, le temps sera proportionnel à n^k (si k=1 on a les algo linéaires).
par exemple la multiplication qu'on apprend à l'école a une complexité en O(n²). Si tu mets un temps t pour multiplier un nombre de n chiffres avec lui-même, tu mettrras en gros 4 fois plus de temps pour multiplier un nombre de 2n chiffres avec lui-même.

* exponentiel, si tu ajoutes seulement une donnée à un ensemble de n données alors le temps sera multiplié par k. Par exemple si trouver le cours chemin entre 4 villes te prend 1s, pour 5 villes cela prendra 2s, pour 6 il te faudra 4s ... 10 villes 17 minutes ... 15 villes 9 heures ... 20 villes 12 jours ... 25 villes 1 ans ... 30 villes 34 ans

Tu vois qu'en fait les algorithmes de complexité exponentielle ne sont utilisable que pour des problèmes de petite taille. Malheureusement il existe des problèmes pour lesquels nous ne connaissons que des algo de complexité exponentielle.

Quel est ton niveau pour que je te donne des références adaptées ?

[erik]

Salut,

Tu trouveras sur la page Complexité algo quelques précisions supplémentaires et notamment ce tableau : Comparatif complexité algo

[invite0b5c32d7]

mon niveau est débutant, je connais même pas les bases de la programmation. J'étudis en autodidacte le XHTML, CSS, PHP et MYSQL qui prends déjà pas mal de temps mais j'avance vite.

Je voudrais savoir s'il y a un ordre d'apprentissage, une liste logique pourmieux apprendre l programmation?

[A voir en vidéo sur Futura]

[invite4492c379]

Re-,

oui et non

Ce qui est important n'est pas le langage en soi. Ce qui est important est d'avoir de solides bases en algorithmique, avoir des connaissances en conception. Programmer commence toujours avec un crayon, du papier et évidemment de la cervelle

Tu peux trouver des tutoriels pour apprendre un peu tout ça. Par curiosité, pourquoi ces choix ?

[invite0b5c32d7]

Bien j'adore l'informatique et je voudrais savoir créer des logiciels, programme très complexes et j'espère en faire mon métier.

[invite6a2167ab]

Bonsoir quinnmallory,

Effectivement, les problèmes de complexité des algorithmes sont vraiment, à mon avis, sources de questions passionnantes. Ceci dit, quand tu dis "j'adore l'informatique et je voudrais savoir créer des logiciels, programme très complexes", à l'usage tu découvriras sans doute quelque chose d'encore plus agréable : créer des logiciels et des programmes très simples. Parce que, si tu veux que les gens utilisent les programmes que tu crées, il faut que ces programmes soient suffisamment simples... Après, c'est sûr, si tu bosses sur le système de pilotage automatique d'un Airbus, le programme sera complexe, ne serait-ce que par sa taille ; mais si la part sur laquelle tu travailles est trop compliquée pour que tes collègues puissent la comprendre et s'en servir, ton travail n'aura servi à rien !

Bonne soirée.