Algorithmique impérative/Après

Cette partie introduit un ensemble de sujets d'ouverture possibles pour la poursuite de l'apprentissage.

Algorithmique

Comme nous l'avons vu, notamment sur le problème du tri des tableaux, il existe de multiples algorithmes connus dont l'étude est intéressante pour la culture de l'algorithmicien.

C'est l'objet du wikilivre Programmation Algorithmique.

Calculabilité et complexité

Vous allez sûrement vous poser cette question un jour : Peut-on écrire un algorithme qui... ?. Grande question, nos ordinateurs d'aujourd'hui dérivent de la Machine de Turing. Toute une branche des mathématiques est dédiée au problème de la Calculabilité.

Au fil des remarques dans les problèmes posés,nous avons abordé la notion d'efficacité d'un algorithme. Notamment dans le problème sur la somme des n premiers entiers où nous avons clairement constaté qu'il existait deux façons d'obtenir un résultat : l'une prenant beaucoup plus de ressources (en temps et en mémoire) que l'autre. Eh bien ce concept est formalisé : il est possible d'évaluer grâce aux mathématiques si un algorithme est plus efficace qu'un autre. Il s'agit de la complexité

Finalement, il s'agit de répondre à deux questions : peut-on obtenir un résultat en un temps fini (calculabilité) ? et si oui, dans quel ordre de grandeur de temps (complexité) ?

Algorithmique fonctionnelle

Nous avons étudié l'algorithmique impérative : cette précision est effectivement nécessaire. Une autre algorithmique existe. Elle pose d'autres bases de départ, d'autres concepts. Elle est plus complexe à apprendre et à comprendre que l'algorithmique impérative mais la puissance de ses axiomes permet d'éviter de nombreux problèmes.

Cet exemple exploite le concept de la récursion, fondamental dans cette algorithmique.

Algorithme itératif (impératif)	Algorithme récursif (fonctionnel)
Fonction factorielle(n : entier) Lexique i  : entier (* variable de boucle *) résultat : entier (* le résultat final qu'on retournera *) Début si i=0 alors résultat←1 sinon début résultat←1 (* on initialise le résultat *) pour i de 2 à n résultat←résultat*i finpour fin finsi Fin	Fonction factorielle(n : entier) Début si n<=1 alors 1 sinon n*factorielle(n-1) Fin

C'est un bon complément et une bonne suite à l'apprentissage de l'algorithmique impérative.

Structures de données

Nous n'avons jusqu'ici utilisé qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'éléments que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle le gestion dynamique de la mémoire (par opposition à statique).

Nous avons également vu qu'un tableau est générique : c'est-à-dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type.

Nous avons vu que les tableaux sont homogènes : c'est-à-dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certains éléments seraient des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.

Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.

Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes, les matrices, les rationnels, les arbres, l'ADN, la couleur, etc. Comment créer les éléments nécessaires au stockage de telle information quand un simple tableau ou un simple enregistrement ne suffisent plus ?

Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans le wikilivre Structures de données.

Théorie des langages

La langage algorithmique est composé de règles de syntaxe bien précises dont la raison peut paraître obscure. Les langages de programmation ont également de nombreuses règles d'écriture. Qu'est ce qui détermine qu'un langage peut être compris par un ordinateur ? Pourquoi ne peut-on pas tout simplement écrire nos algorithmes en français littéral ?

C'est l'objet de la théorie des langages.

Architecture des ordinateurs

Nos algorithmes sont implémentés dans un langage informatique puis compilés pour être transformés en un fichier binaire exécutable. Pourquoi le binaire ? Comment l'ordinateur peut-il simplement avec l'électricité stocker des données et effectuer des opération sur celles-ci ? Que fait exactement le compilateur ? Pourquoi un binaire compilé pour Linux ne fonctionne pas sous Windows ?

Une infinité de questions peut se poser sur le fonctionnement de l'ordinateur au-delà de l'écran. Il s'agit de l'Architecture des ordinateurs

Correction des algorithmes

De la même façon que pour la calculabilité et la complexité, une branche des mathématiques permet de prouver qu'un algorithme fonctionne. Il s'agit de la logique de Hoare

Conclusion

Il existe une multitude de domaines d'extension et de connaissances qui touchent à l'informatique en plus de l'algorithmique impérative. La plupart sont liées aux mathématiques. Chacune de ces matières suscitera plus ou moins votre curiosité...