Algorithmique et programmation (Licence)

Cours algorithmique et programmation (Licence), tutoriel & guide de travaux pratiques en pdf.

Quelques éléments d’algorithmiques

1. Séquentialité : descendre l’escalier puis prendre à droite, puis tout droit jusqu’à la sortie, puis traverser la route, puis…
La séquentialité permet de décrire l’éxécution consécutives d’instructions.
2. Sous-programmes : préparer 250 grammes de pâte brisée ; regarder le produit des deux chiffres sur la table de multiplication ; …
Transformation d’un bloc d’instructions en une instruction (réutilisable). Note : usage de paramètres.
3. Test : si vous voulez de la haute définition, choisissez un enregistrement sans perte.
4. Boucle : prendre la 4ème porte à droite ; mélangez jusqu’à obtenir une préparation homogène ; répéter l’opération pour chaque chiffre du nombre à multiplier. Répétition d’instructions beaucoup de fois, ou un nombre inconnu de fois.
Ce qui manque pour un algorithme
1. De la rigueur :
– pas de justification aux actions → éxécution bête ;
– aucune ambiguité possible ;
– exécution reproductible.
2. Des données à manipuler : nombres (entiers, flottants), chaînes, …
3. Un langage strict :
– le français est naturellement ambigu…
– … et beaucoup trop complexe…
– … et beaucoup trop vaste.

Pourquoi le tri ?

Problème très classique en algorithmique :
1. utilisation fréquente ;
2. ne demande pas de données complexes (tableaux de nombres) ;
3. plusieurs solutions, des plus simples au plus complexes…
4. avec des avantages et des inconvénients.
Question pour la résolution du problème : comment feriez-vous ?

Algorithme de tri

1. On choisit le plus grand (pour un tri par ordre décroissant) de l’ensemble à trier ;
2. on le range en haut du tableau et on l’enlève de l’ensemble à trier ;
3. si l’ensemble n’est pas vide, on reprend à l’étape 1.
Ce tri est appelé un tri par sélection (la première étape, la plus centrale dans ce tri, étant une « sélection » du plus grand élément).

Ecriture du tri par sélection

Pour écrire l’algorithme (ou le programmer), chacune des étapes doit être détaillées.
1. La première étape est elle-même un problème algorithmique (recherche du plus grand élément d’un ensemble). Elle demande encore une analyse (comment feriez-vous ?), peut-être d’autant plus difficile que cela semble simple. Cette décomposition d’un problème algorithmique en sous-problèmes est appelée analyse descendante.
2. Les étapes deux et trois sont des opérations élémentaires dépendantes du langage algorithmique (ou de programmation) utilisé. Savoir écrire ces étapes sans difficulté est avant tout une question de pratique, avec quelques choix à faire :
– comment représenter les données (variables, tableaux, …) ?
– quelles structures du langage utiliser (boucles, fonctions, …) ?
−→ difficultés de deux ordres :
1. comment résoudre un problème (question « stratégique ») ;
2. comment écrire les étapes élémentaires (question « tactique »). « Science » algorithmique

Avantage du tri par sélection

1. utilise peu de déplacements de données. Inconvénients du tri par sélection :
1. sur un ordinateur, les déplacements de données ne sont en général par un problème ;
2. utilise beaucoup de comparaisons → plutôt lent.
L’algorithmique, en tant que discipline, est la « science » (ou la branche de la science informatique) qui cherche des algorithmes pour résoudre des problèmes, et détermine leurs avantages et leurs inconvénients.

Langage algorithmique

Traditionnellement, on écrit les algorithmes dans un langage algorithmique (aussi appelé « pseudo-code »). C’est-à-dire un machin formalisé en simili-langage naturel. Par exemple :
lire a affecter 0 à s pour i allant de 1 à 10 faire affecter i+s à s afficher s
Le langage algorithmique est essentiellement un langage de programmation sans certains détails techniques utilisés par l’ordinateur (par exemple, les déclarations de variables).

« Approches » de l’algorithmique

Il existe plusieurs approches dans la rédaction des algorithmes (et des programmes) :
impérative, fonctionnelle, orientée objet, déclarative, …
A savoir : toutes ces approches permettent de résoudre les mêmes problêmes. Aucun n’est plus « expressif » qu’un autre (par exemple, tous les langages permettent de programmer un tri par sélection). Les différences sont donc des questions de commodités.
Dans ce cours nous présenterons la forme « classique » de la programmation impérative.

Et les programmes ?

Langages de programmation : C, Basic, Java, Pascal, Caml, etc. et tous leurs dérivés…
Plusieurs milliers de langages de programmation ont été créés.
Fonctionnalités différentes, approches différentes, capacités différentes…
Choix du C : langage impératif classique, encore largement utilisé, avec de nombreux dérivés, libre.