Cours complet d’initiation à la programmation

Un algorithme est la description d'un enchaînement de calculs et de tâches élémentaires en vue de la réalisation d'un traitement automatique de données. Ces données doivent être représentées par des structures appropriées. L'algorithme peut ensuite être codé dans un langage de programmation pour donner un programme. La programmation regroupe ces activités : algorithmique, structuration de données et codage, les deux premières étant certainement les plus importantes.

Contrairement à ce que pourrait croire un novice, la tâche principale de la conception d'un programme n'est pas l'écriture de celui-ci dans un langage informatique donné.

La réalisation d'un programme se décompose en effet en plusieurs phases. De manière simplifiée, on présente ainsi la genèse d'un programme :

• établissement d'un cahier des charges : le problème posé ;
• analyse du problème et décomposition de celui-ci en sous-problèmes plus ou moins indépendants et plus simples à résoudre ;
• choix de structures de données pour représenter les objets du problème ;
• mise en œuvre des différents algorithmes à utiliser pour résoudre les sous-problèmes ;
• codage des algorithmes et création du programme dans un langage de programmation donné ;
• tests (et corrections) et validation auprès des utilisateurs.
  

Bien souvent, dans la pratique, ces étapes ne sont pas aussi nettement découpées. Les quatre premières sont certainement les plus importantes et on peut remarquer qu'elles sont indépendantes du langage de programmation choisi, qui n'intervient normalement qu'à la cinquième étape. La dernière étape est, elle aussi, très importante et ce serait une grave erreur de penser qu'elle ne fait pas partie du cycle de création d'un programme.

Pour un débutant en informatique, étudiant de surcroît, le cahier des charges consistera souvent en un énoncé d'exercice ou de problème proposé par un enseignant. Une première tâche, et elle est souvent plus difficile qu'on ne le croit, sera de comprendre cet énoncé ! Il faudra ensuite réfléchir à la résolution de ce problème et, ensuite seulement, le coder dans un langage. On peut donc le constater, une bonne partie du travail doit se faire avec un crayon et un papier ! Une erreur (méthodologique) des débutants est souvent, une fois l'énoncé lu (ou plus souvent simplement survolé), de se ruer sur leur clavier et de commencer à taper dessus (on ne sait d'ailleurs trop quoi) et seulement alors de commencer à réfléchir à la résolution du problème.

Il s'agit de poser les notions de base en programmation impérative :

• expressions et instructions ;
• constantes, variables et affectation. Variables locales ;
• types de données simples : nombres entiers ou non entiers, booléens, caractères et chaînes de caractères ;
• expressions et instructions conditionnelles ;
• répétition conditionnelle d'instructions (boucle tant que). Répétition non conditionnelle d'instructions (boucle pour) ;
• fonctions et procédures. Paramètres formels, paramètres effectifs.

Dans les deux cours qui suivent (API1 et API2) sont abordées les notions :

• tableaux ;
• enregistrements ;
• fichiers ;
• récursivité ;
• structures de données dynamiques ;
• programmation modulaire ;
• algorithmes de recherche et de tri ;
• complexité des algorithmes.

Il existe de très nombreux langages impératifs : C, Pascal, Ada, Python, Caml…

Pendant quelques années nous avons utilisé le langage Pascal. Mais l'expérience a montré que la lourdeur de la syntaxe de ce langage, ainsi que certaines de ses ambiguïtés, présentaient de réelles difficultés pour des étudiants débutant en programmation. Ce langage nécessitant une phase d'édition, puis une phase de compilation avant toute exécution, il devient très vite fastidieux de tester la moindre idée d'algorithme. Pour ces raisons nous avons décidé de changer de langage.

Nous nous sommes alors tournés vers Caml. Même si à la base ce langage est avant tout un langage fonctionnel, il offre aussi la possibilité de programmer dans un style impératif. Il dispose de plusieurs modes d'exécution :

• un mode interactif ;
• un mode compilé(1) qui permet de produire des exécutables autonomes.

Dans ce cours, le mode interactif est le seul mode abordé. La compilation pour produire des programmes exécutables autonomes sera abordée dans un autre cours.

Caml est un langage fonctionnel dans lequel les fonctions sont des valeurs du même ordre que toute autre valeur. En particulier, une fonction peut produire une autre fonction. Par exemple, la fonction plus définie ci-dessous est une fonction qui permet d'additionner deux nombres entiers.

# let plus a b = a + b ;;
val plus : int -> int -> int = <fun>

On peut le vérifier en appliquant la fonction plus aux deux entiers 2 et 5.

# plus 2 5 ;;
- : int = 7

Mais on peut aussi appliquer cette fonction à un seul entier, et la valeur produite par cette application donne une fonction qui, comme le montre le type indiqué par l'interprète du langage est une fonction qui à un entier associe un autre entier.

# let plus2 = plus 2 ;;
val plus2 : int -> int = <fun>

L'application de la fonction plus2 à un entier donne cet entier augmenté de 2.

# plus2 5 ;;
- : int = 7

Mathématiquement parlant, la fonction plus est donc une fonction dont l'ensemble de départ est l'ensemble des entiers kitxmlcodeinlinelatexdvp\mathbb{Z}finkitxmlcodeinlinelatexdvp et celui d'arrivée est l'ensemble des fonctions de kitxmlcodeinlinelatexdvp\mathbb{Z}finkitxmlcodeinlinelatexdvp dans kitxmlcodeinlinelatexdvp\mathbb{Z}finkitxmlcodeinlinelatexdvp.

Une autre façon de considérer la fonction qui à deux entiers associe la somme de ces deux entiers consiste à la définir comme une fonction dont l'ensemble de départ est l'ensemble des couples d'entiers kitxmlcodeinlinelatexdvp\mathbb{Z} \times \mathbb{Z}finkitxmlcodeinlinelatexdvp et celui d'arrivée est kitxmlcodeinlinelatexdvp\mathbb{Z}finkitxmlcodeinlinelatexdvp.

Les deux fonctions plus et add sont d'une certaine manière deux facettes de la même fonction : on dit que la première en est la version curryfiée et la seconde la version décurryfiée.

En Caml, on peut écrire très simplement la forme décurryfiée.

# let add (a,b) = a + b ;;
val add : int * int -> int = <fun>

L'application de cette fonction à deux entiers donne le résultat attendu.

# add (2,5) ;;
- : int = 7

Mais l'application à un seul entier n'est plus possible

# add (2) ;;
This expression has type int but is here used with type int * int

puisque l'interprète du langage attend qu'un couple d'entiers soit fourni à la fonction add.

En programmation, il est fréquent d'avoir à définir des fonctions ou procédures à deux (ou plus) paramètres. Dans la plupart des langages de programmation (C, Ada, Pascal…), lorsqu'une telle fonction a été définie, il n'est pas possible de l'appliquer avec un nombre d'arguments inférieur au nombre de paramètres précisé dans sa définition. Nous avons donc choisi, pour ce cours d'InitProg, de programmer toutes les fonctions ou procédures à plusieurs paramètres que nous rencontrerons sous leur forme décurryfiée(2). Cela a le double avantage :

• d'être syntaxiquement proche de ce qui se fait dans d'autres langages de programmation ;
• de ne pas permettre l'application partielle d'une fonction qui fournirait des valeurs fonctionnelles qui pourrait désorienter le programmeur débutant.

Ce cours est découpé de manière assez classique en introduction (que vous lisez actuellement), chapitres, annexes, et diverses tables (des figures, des matières…).

Les chapitres recouvrent les objectifs du programme. Ils sont tous suivis de quelques exercices.

Une annexe importante est celle présentant les fonctions du module Cartes. Ce module définit un environnement de travail qui permet de déplacer des cartes situées sur quatre tas d'un tas vers un autre. Cet environnement est utilisé durant les premières semaines du cours pour introduire progressivement les différentes structures de contrôle en programmation impérative, ainsi que les notions de fonctions et procédures. Le report en annexe de la présentation de ce module est délibéré afin de distinguer les objectifs du cours (présentés dans les divers chapitres) des moyens pour les atteindre.

Ce cours ne contient pas les sujets de TP qui seront proposés au fur et à mesure par l'intermédiaire du semainier du portail des UE d'informatique (http://www.fil.univ-lille1.fr/portail/ls1/initprog/) ou du site du cours sur Moodle (http://moodle.univ-lille1.fr/). Bien entendu, les TP font partie intégrante du cours et sont indispensables à une bonne compréhension.

Les algorithmes de résolution de problème sont décrits en « pseudocode » sous la forme

La traduction d'un algorithme en Caml, ainsi que les programmes sont présentés sous la forme

let fact (n) =
  let f = ref 1
  in
    for i = 1 to n do
      f := !f * i
    done;
    !f

Enfin, les dialogues avec l'interprète du langage sont décrits sous la forme

# let a = 5 ;;
val a : int = 5
# fact (5) ;;
- : int = 120

Lorsqu'une nouvelle structure syntaxique du langage est présentée pour la première fois, elle l'est sous la forme

let < identificateur > = < expression >

Pierre Allegraud, Fabrice Aubert, Alexandre Bilger, Julien Bosman, François Dervaux, Alexandre Feugas, Michel Fryziel, Sophie Jacquin, Laetitia Jourdan, Céline Kuttler, Jean-Luc Levaire,

Didier Mailliet, Nour-Eddine Oussous, Yosra Rekik, Romain Rouvoy, Mikaël Salson, Alexandre

Sedoglavic, Bayrem Tounsi, Cristian Versari, Christophe Vroland, Éric Wegrzynowski, Léopold

Weinberg, Hassina Zeghlache.