Définition : Algorithmique¶

L'algorithmique est l'étude et la conception d'algorithmes. C'est-à-dire l'analyse des algorithmes afin d'en déterminer leur efficacité et leur fiabilité. Ainsi que la production de systèmatisme permettant de résoudre des problèmes.

Que permet l'algorithmique?¶

L'étude de l'algorithmique permet de répondre aux questions du type:

L’algorithme proposé se termine-t-il?
Le résultat est-il celui attendu ?
Le temps d'éxécution de mon algorithme est-il raisonnable?
La quantité de mémoire nécessaire au bon fonctionnement de mon algorithme est-elle raisonnable?
Est-il possible d'écrire un algorithme qui produirait le même résultat en étant plus rapide ou moins gourmand en mémoire?

Définition: Algorithme¶

Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes.

Il se compose de trois phases: 1. L'entrée des données 2. Le traitement des données 3. La sortie des données

En pratique l’algorithmique va nous permettre de prouver qu’un algorithme est correct (se termine et produit une réponse conforme à ce qui est attendu), de comparer différents algorithmes avec les mêmes spécifications (complexité) et nous fournir des exemples d’algorithmes et de modélisation de problème.

Les algorithmes existaient bien avant l’informatique. Par exemple : l’algorithme d’Euclide a plus de 2000 ans. Le nom algorithme vient du savant arabe Al-Khwârizmî (IXème siècle)

Donald Knuth dans un ouvrage nommé "The Art of Computer Programming" donne en 1968 cinq caractéristiques fondamentales aux algorithmes :

finitude : « un algorithme doit toujours se terminer après un nombre fini d’étapes » ;
définition précise : « chaque étape d'un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambiguïté pour chaque cas » ;
entrées : « quantités qui lui sont données avant qu'un algorithme ne commence. Ces entrées sont prises dans un ensemble d'objets spécifié » ;
sorties : « quantités ayant une relation spécifiée avec les entrées » ;
rendement : « toutes les opérations que l'algorithme doit accomplir doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon ».

Algorithmes fondamentaux¶

Un algorithme est une méthode pour résoudre un problème comme trier un tableau, la recherche d'un élément particulier, etc. Bien que vous utiliserez uniquement le langage Python, un algorithme ne dépend ni du langage dans lequel il va être implémenté ni de comment il va être implémenté.

Preuves d'algorithmes¶

Parcours séquentiel d'un tableau¶

Recherche par dichotomie¶

Tri par sélection et tri par insertion.¶

Notion de complexité¶

La complexité est l'étude des coûts d'un algorithme, c'est-à-dire de son temps d'exécution ou de la place qu'il va utiliser en mémoire en fonction de la taille des données. Nous ne parleront que de complexité en temps.