Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
29 octobre 2009 4 29 /10 /octobre /2009 15:46



On désigne par algorithmique l’ensemble des activités logiques qui relèvent des algorithmes ; en particulier, en informatique, cette discipline désigne l'ensemble des règles et des techniques qui sont impliquées dans la définition et la conception des algorithmes. Le mot vient du nom du mathématicien Al Khuwarizmi (latinisé au Moyen Âge en Algoritmi), qui, au IXe siècle écrivit le premier ouvrage systématique sur la solution des équations linéaires etquadratiques. Dans le cas général, l’algorithmique s’effectue au moyen de calculs.

Il est parfois fait usage du mot algorithmie, bien que ce dernier ne figure pas dans la plupart des dictionnaires.

Définition

Un algorithme est un processus systématique de résolution, par le calcul, d'un problème permettant de présenter les étapes vers le résultat à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En d'autres termes, un algorithme est un énoncé d’une suite d’opérations permettant de donner la réponse à un problème. Si ces opérations s’exécutent en séquence, on parle d’algorithme séquentiel. Si les opérations s’exécutent sur plusieurs processeurs en parallèle, on parle d’algorithme parallèle. Si les tâches s’exécutent sur un réseau de processeurs on parle d’algorithme réparti ou distribué.

Historique

Antiquité

Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l’époque des Babyloniens, pour des calculs concernant le commerce et les impôts.

L’algorithme le plus célèbre est celui qui se trouve dans le livre 7 des Éléments d'Euclide. Il permet de trouver le plus grand diviseur commun, ou PGCD, de deux nombres. Un point particulièrement remarquable est qu’il contient explicitement une itération et que les propositions 1 et 2 démontrent (maladroitement pour nos contemporains) sa convergence.

Étude systématique

L’algorithmique a été systématisée par le mathématicien perse Al Khuwarizmi (né vers 780 - mort vers 850), auteur d’un ouvrage (souvent traduit par L’algèbre et le balancement) qui décrit des méthodes de calculs algébriques (en plus d'introduire le zéro des Indiens).

Le savant arabe Averroès (1126-1198) évoque une méthode de raisonnement où la thèse s’affine étape par étape (itérativement) jusqu’à une certaine convergence et ceci conformément au déroulement d’un algorithme. À la même époque, au XIIe siècle, le moine Adelard de Bath a introduit le terme latin de algorismus (par référence au nom de Al Khuwarizmi). Ce mot donne algorithme en français en 1554.

Au XVIIe siècle, on pourrait entrevoir une certaine allusion à la méthode algorithmique chez René Descartes dans la méthode générale proposée par le Discours de la méthode (1637), notamment quand, en sa deuxième partie, le logicien français propose de « diviser chacune des difficultés que j’examinerois, en autant de parcelles qu’il se pourroit, et qu’il seroit requis pour les mieux résoudre. » Sans évoquer explicitement les concepts de boucle ou d’itération, l’approche de Descartes prédispose la logique à accueillir le concept de programme, mot qui naît en français en 1677.

L’utilisation du terme algorithme a été remarquable chez Ada Lovelace, fille de Lord Byron et assistante de Charles Babbage (1792-1871).

Vocabulaire

Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.

Un algorithme énonce une résolution sous la forme d’une série d’opérations à effectuer. La mise en œuvre de l’algorithme consiste en l’écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d’un programme informatique.

Les informaticiens utilisent fréquemment l’anglicisme implémentation pour désigner cette mise en œuvre. L’écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n’a ici aucun rapport avec lacryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L’algorithme devra être plus ou moins détaillé selon le niveau d’abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l’expérience du cuisinier.

Exemples d’algorithmes

Il existe un certain nombre d’algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se référera aux articles suivants pour de plus amples détails :

Complexité algorithmique


Les principales notions mathématiques dans le calcul du coût d’un algorithme précis sont les
notions de domination(notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d’informations (enbits, en nombre d’enregistrements, etc.) manipulée dans l’algorithme. En algorithmique on trouve souvent des complexités du type :

Notation Type de complexité
O(1) complexité constante (indépendante de la taille de la donnée)
O(log(n)) complexité logarithmique
O(n) complexité linéaire
O(nlog(n)) complexité quasi-linéaire
O(n2) complexité quadratique
O(n3) complexité cubique
O(np) complexité polynomiale
O(nlog(n)) complexité quasi-polynomiale
O(2n) complexité exponentielle
O(n!) complexité factorielle

Sans entrer dans les détails mathématiques, le calcul de l’efficacité d’un algorithme (sa complexité algorithmique), consiste en la recherche de deux quantités importantes. La première quantité est l’évolution du nombre d’instructions de base en fonction de la quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de données à trier), que l’on privilégiera sur le temps d'exécution mesuré en secondes (car ce dernier dépend de la machine sur laquelle l'algorithme s'exécute). La seconde quantité estimée est la quantité de mémoire nécessaire pour effectuer les calculs. Baser le calcul de la complexité d’un algorithme sur le temps ou la quantité effective de mémoire qu’un ordinateur particulier prend pour effectuer ledit algorithme ne permet pas de prendre en compte la structure interne de l’algorithme, ni la particularité de l’ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d’accès aux données, l’exécution de l’algorithme (qui peut faire intervenir le hasard) ou son organisation de la mémoire, le temps d’exécution et la quantité de mémoire ne seront pas les mêmes.

Il existe également un autre aspect de l'évaluation de l'efficacité d'un algorithme : les performances en moyenne de cet algorithme. Elle suppose d'avoir un modèle de la répartition des données de l'algorithme, tandis que la mise en œuvre des techniques d'analyse implique des méthodes assez fines de combinatoire et d'évaluation asymptotique, utilisant en particulier les séries génératrices et des méthodes avancées d'analyse complexe. L'ensemble de ces méthodes sont regroupées sous le nom de combinatoire analytique.

On trouvera dans l’article sur la théorie de la complexité des algorithmes d’autres évaluations de la complexité qui vont en général au-delà des valeurs proposées ci-dessus et qui répartissent les problèmes (plutôt que les algorithmes) en classes de complexité.

Quelques indications sur l’efficacité des algorithmes

Souvent, l’efficacité d’un algorithme n’est connue que de manière asymptotique, c’est-à-dire pour de grandes valeurs du paramètre n. Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace. Ainsi, pour trier un tableau de 30 lignes (c’est un paramètre de petite taille), il est inutile d’utiliser un algorithme évolué comme le Tri rapide (l’un des algorithmes de tri les plus efficaces en moyenne) : l’algorithme de tri le plus trivial sera suffisamment efficace.

Entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l’occupation mémoire est la plus faible. L’analyse de la complexité algorithmique peut également servir à évaluer l’occupation mémoire d’un algorithme. Enfin, le choix d’un algorithme plutôt qu’un autre doit se faire en fonction des données que l’on s’attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l’on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l’applique à une liste de valeurs déjà triée. Il n’est donc pas judicieux de l’utiliser si on prévoit que le programme recevra en entrée des listes déjà presque triées.

Un autre paramètre à prendre en compte est la localité de l’algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu’une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de swapping).

Enfin, il existe certains algorithmes dont la complexité est dite amortie. Cela signifie que, pour certaines exécutions de l’algorithme (cas marginaux), la complexité de l’algorithme sera très supérieure au cas moyen. Bien sûr, on n’utilise la notion de complexité amortie que dans les cas où cette réaction est très marginale.

Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l’on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d’une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu’on appelle une heuristique. Le but d’une heuristique n'est donc pas d'essayer toutes les combinaisons possibles afin de trouver celle répondant au problème, mais de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable. C’est ainsi que les programmes de jeu d’échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l’expérience d’un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus informatiques non répertoriés dans leur base, en s’appuyant sur des ressemblances avec des virus connus.

Applications

 

.

Partager cet article

Repost 0
Published by CHOMOLANGMA
commenter cet article

commentaires

☼ Zorbax ☼

  • : CHOMOLANGMA
  • CHOMOLANGMA
  • : Réflexions sur le sens de la vie. Diversités culturelles et médiatiques.
  • Contact

ON EST QUAND???

Bonjour, nous sommes le

☼ Qui Cherche Trouve ☼

♫♪♪♫♪♫♪♫♪

Poussieres De Savoir ☼

POUSSEZ PAS !!!

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcSH1bqV_MZbKff7r4KH0YXDgokYKnPMVcS17_NVF7KeFFQmHvTYYQ

 

 

Depuis le 2 octobre 2008 ma paroisse a compté de fidèles :

 


Compteur Global


 

 

 

 

 

☼ Merci à vous tous ☼

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcRspNEZw03K2txVYJaQojtGiQPv2Ef2hRp76vnThpM_Xhg74AeH

 

 

   Et aussi, bien sûr, à notre superbe équipe  !!!!!!!...

 


☼ En Alcove ☼

☼♥☼♥☼


 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcTJQdwhuv8K2KE2fv7sAcLYqokJ6fOwOos7DPEsrBY_tOyjkmt9

 

 

 

 

  http://t2.gstatic.com/images?q=tbn:ANd9GcTwbpFmC0lwUUqRVtxAgfCeDB97ON6I9jGDIVmmGwpa1bg_oeiS8w



 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcQJFhyxpCtvTfrKTTq2Dnraqndo0k6KOOvR5B49c424W-RXGsXk

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQ4lkR76RVvxlM2Pg0xGQLGN-vJ1IC1AeiO9YFoy0C2maJDnAlsEA

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcS3s1MTNys4JJ2XciWuydUFkX2s3uxVNEo4XLmDXWkNuzNwaF-I

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcRpmq_X4KGoOioCJ7IGFovNaZR1dl5V9wdd73SKUZoyRXImy8hQsA

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcT6vugj46xpPFClJ40ZcN_g83W39aPcCsnryaBlwulPqhMuSmHABA

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcS0rnZSUpbcqus_ag8-saWRw8BVp-nHBjwhG0FGGsPrBMTVGsKfUA

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcRiQjNvzjX7IEkfQYGG-KxW9pOVJoLjsP43P-wRgoCo6bmRIFfQ

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcSTia4A3P4_qwGWtAAvhY4S2BKgtk6tR_QCD3_DTBLqQwkYTLP7

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcRPAWH7AgJ7gN7ej2rrAa90b9jK2nWJtRcdmCSJLXifbDqpzt-GAQ

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcSnH3SFCsuDblli6D1AJMGBIO3SduYE7QocfhaOPh2CbcgSaTJm3g

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcS_x5rZOKIoXBMbTrRfiBoXYGA8_aG1puNXFnPK-vFSJb8S0TB-

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcT5xPsHZoCoc3Y10UzSIfZBJ1VM5yTf0rOp0z02qzAq29ZylEqp

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcSJYo3dfiA7rWKtAhGDKlIvNQBBfXfxpskBzCjE2VA_WnhL03zQ

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcRrs5cw6eknmiTVBcESn97krqvfndk10XJq35s-mUIxnoXepsHU2w

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcTtPoMny2WLrgyLYUkv0xzCHZ3BSe7txlE-Xe2XSz1rA4IRBQ-8

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcTzDbIU4QatTLNRgPQwPUcMDO8BtCGQMAkP46aQAp05yXC1m0y84g

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcS_sSIdV_qG7YiVCrY6Fze69BhzpdENouF0zUUp4OV8__EbU9Ad

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQ9uJqfoOS-LjhgtT3qLp4AH34AojcYXzS6ifUoduwpXl2xR4cu

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcSBBpAVI8uqqXKRXeWLnFO9do5ObFZm7YxgxrJ7-EbHR2oDqLo0vQ

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcRDpZXNSZZorQeUMLz3DTA9hEU2rI_bxr_LT9c4T9nvHvAWTZjCGQ

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQJxvHFLqQeIleqlsCzYw3aqr-0Y6eKQMVnyaA5me5hdAxIljVU

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcSC9dHlJXHSlla_xZ5T9EZytHwAWT-qbU_d19dTtxAXrGNihAXKlQ

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcR9uI2iDGC9O3GMDlf8NsxtxQx-Qp8sqHmOc5rb-zkptdYl27ct

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcRbZ3vVwEjZT_vYCN_egFTIwdBz6fqNL0Pg-y_Q61vxrmzGOpx_

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcQJ2rE3MpU2-7BbpUlr6UqYo4BmnNs_dvTC88BMslWtXGy7xpm4

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcQEpgxQwBFunGDiUIemTa46VNveEHAu-uA8FY-TsPaLWXJFd2s0

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQTdXbqeHRkSO7KlYa4OkUya7gTOtG1LddYFWDuhmMG8TTBud38

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcTNv54UJcOf0QWIB4OraEz3h5BSPwvVpIDgtJO-zq0-MNAH1T-r

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQQ4msZqs5YGyEvDc4xIBtl0glm2rQZ7LsilbzRNUFi1QmhSgwd

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcRadP8tzRToSi6YgV25tgPSiZuZH-m01ykcCd-vsvFtJOoai2ucTw

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQWsJatoxZ24v32bG85ut1XPEPG4Fa5l6ApTX9VfC1X3_fQlO6t

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcSATYwKzSKWCjMx6cjBGrTkiC8C_lyJBimQ86hhDpKGyeWCgRFU5Q

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcRkni6wj2PqLxVIQnGL2w-Hh0Qdu5Q2vEiKSUXAJ7TKh9ePWQBm

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcQzo44WmwLEIvLwTyzq_jnCtqqHX6X_CIYel1kbk7vcUHUp-ieN

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcQJijg5RyUyd3NObMK9uNkIduA32k3nPJwfiuvaWrAi2Td5vyXO

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcSLXSS07G9gseceN7SeCwGRL0C6ij_75lYGEnDN1qwb_bEl9bGs

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcSgjOBb-AqrP0ZXPZSVl55yswE6dnD4uny-n0Xh-9mAuwm1GUq3

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcSZAb3DktAXiGznQlZB9az_nvD6AoLygDkDTstPDm_WBfLnJ3ltQg

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcRXwcTaTVudGTxMwVFFrGw1Z-j9x9D9inLKamTPCwUThDbPuEYpeA

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcTU6wtRoYw9X2-MMykBLzlVjXeRgi5rqzD5ck22QxWwI8h7QeNUQA

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcRpMUOK13Ots0UnbeCQLds3ixSZxNY9gFOfm65Bvc-pf6ZKAlWbzg

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQhH-RzSe9GF29vGoZwod2tN7O-9mFfpWJX4bLt78JtJYMqI8w1rA

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQxu-I9t3HJlWQ3e6bM41HAOc8j3Smoe-ahJN9OTRyzd6vOUOVF

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQYkezUKlW0ttRviIW9f6NJHBcjJ-sUE4XMIic0ka6qkCguqsqWEQ

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcSLwoIa5Xuj4eEFEX5vzJFqlL0GIrwjAUDCWbZgf6ni2O6MUMuwHg

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcSmu_lhCfJa5L3JKT73eNWm5-DVlMMhgQ2zjDd5kmbF9S0PDwt0

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcTl9CWad5AcZHOfC-RgTWPbODkKY_C0DW3MZXkDUucqfvfZLDvJvQ

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcSSorC-n_GApivF90u5JfsOvUI44_E6pQ_gYw3Zv_SawrJlQ7U_OA

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcSHehPIU8WfymVyIehhOVdWyZ9Iby-7WygiZdxRqYoB6-t4uxfc

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcTHknIkIppczoDGtgqaDVGpF5vzTnPgO0XzesL14bXWKIidntgi

 

 

 

http://t0.gstatic.com/images?q=tbn:ANd9GcQ2gFiEiRrnRVPCVmgC8fP4RV_b4Cyut6pHRWot2zotTH_isSgx

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcRMnyl4ZznB4yj9tFflGmUrm8zxq1VAfdzbHlagdVlYHHs5AqI2Xw

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcSABiNYE2Ig0ORn0Dp6LWBs8FU1-eDuUfhJpaBhY3dBILcGkw7Y

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQX6x3fLQO-eGD7Sdc__AFLjGRztfSRzdOgtJe_w_XI_qKOl_cQ

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcQWAfv06yKnlGGke983sE24US_BbpZ0xgnAp3yIh3eXvCRrRfxtgg

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcSguscboVOMXCDflSARG5UefcNGLsGZylvXKHJGK4ldNdG1xYiR

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcTVsXwe7MG_AOX5rUiFD0hVw9aHeILEWPB_3WS5456jt040weKpxQ

 

 

 

http://t2.gstatic.com/images?q=tbn:ANd9GcS14rgGXof16mpTbvNq37y9tGIxf38V3B4j5iFLZChBi8qMo0cC

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcRk338QqS34hcxTHah2whOwSbnEtO-yxxKutL5KPMcrWPKtCTUf

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcTQg04AvSsLnhDeWWl4-qLzPD5EX7xzuOAVEiswXHB9n5gRBOxj

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcQC715gVGqLwXFM7U94WtdKlMrAiHbkqIvJl2WJ6h_JMsUMfL622g

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcR4ku7jfXybpiE3fm21gXSpihSd_rjwxvIac8kqkj5TkIg3rLODrg

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcThGLPUz7SfnoPUPrFttXiSBuS3NYmV99axgZzgYDofBuo_RpfcUg

 

 

 

http://t3.gstatic.com/images?q=tbn:ANd9GcSqsjlV84iSMlkqfRlTaGiWfn6_nyGg91BQcNLZbGrRnn0-j3S4

 

 

 

http://t1.gstatic.com/images?q=tbn:ANd9GcSwkrLsv_IQh2wUOQ1DkYx-HwxeUOLNEtv8yCh59CnX_HbW5H3q

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

☼ Quoi & Où ☼