ALGORITHMIQUE
L'algorithmique est une partie fondamentale en informatique.Elle est bien distincte de la programmation.
Un algorithme répond à une question , résout un problème ou encore réalise une tâche de façon automatique et en un nombre finis d'étapes.
Par exemple , en arithmétique comment savoir si un nombre est premier.L'algorithme (la méthode) qui sera proposé devra répondre oui ou non et cela quel que soit l'entier considéré.
A un problème posé ,un algorithme proposé. Charge à celui qui l'a conçu de démontrer qu'il se termine , qu'il réalise bien ce qu'il est censé faire et d'en calculer la
complexité pour savoir s'il peut être utilisé dans la pratique. Il sera amené à le corriger ou à l'améliorer.
Le travail de conception , de démonstration puis de calcul de complexité est théorique et s'appuie souvent sur des notions et des raisonnements mathématiques.
Il en est ainsi lors de recherche d'invariants de boucle et de leur démonstration par récurrence.
Ce travail se fait sur "papier" au contraire de la programmation qui se fait sur machine. Les deux sont liès et complémentaires .
Il y a de nombreux algorithmes sur les structures de données:
Sur les tableaux et de manière analogue sur les chaînes de caractères:recherche d'un élèment dans un tableau trié , tri d'un tableau
(ils seront étudiés en classe). Algorithmes de tri
Sur les graphes: parcours en largeur , en profondeur , plus court chemin (utilisé dans la couche réseau du modèle TCP IP) etc..
Sur les arbres binaires: parcours préfixe, postfixe , recherche d'élèment etc..(utilisé dans le codage de Huffman)
Ce sera l'occasion d'utiliser des fonctions récursives , dichotomiques et de voir quelques relations de récurrence sur leur complexité.
Par exemple la recherche d'un élèment dans un tableau trié est en O(n) ou encore la complexité du tri fusion est en O(nlog(n))
où n est la taille du tableau.
La notion de complexité est riche , elle fait appel aux mathématiques (récurrence , probabilités pour la complexité en moyenne ) mais
aussi à des questions encore ouvertes comme savoir si les problèmes NP et P sont les mêmes. ( Le cryptage RSA utilisé lors
d'échanges de données repose sur le fait que l'on ne dispose pas d'algorithme "rapide" de décomposition d'entiers .
Il s'agit dans ce cas de grands entiers).
TD TP:
n°1
ANNEXES
Retour vers la page précédente