INFO719 : rappels et compléments de programmation

Ce wiki est un complément de cours pour le cours « info-719 : rappels et compléments de programmation ». La participation au wiki est fortement encouragée.

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style PrenomNom...)

Je vous conseille d'aller lire ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques

Nouvelles

• 1 septembre 2009 à 11:13 (CEST) création de la page

Organisation des séances

Sauf cas particulier, toutes les séances de cours et de TD seront en fait des séances de cours/TD.

• Hyvernat 8 septembre 2009 à 10:01 (CEST) cours 1 : rappels historiques, Python première partie
• Hyvernat 8 septembre 2009 à 10:01 (CEST) TPD 1 : exemples, quelques programmes du TD1

Supports de TD et TP

• TD1, format pdf

---

---

Introduction

Rappels historiques

Vous pouvez partir de cette page pour avoir un peu plus de détails...

La préhistoire : le calcul

• le boulier chinois
• la pascaline de Pascal, inventée en 1641/42 : elle ne permet de faire que des additions (et des soustractions
• Leibniz rajoute la multiplication à la pascaline (1673)
• les "moulins à chiffres" de Charles Babbage (1834-36), malheureusement jamais construits...
• la "tabulating business machine" de Hollerith permet d'automatiser les calculs pour le recensement de la population américaine. Ceci donnera ensuite la société "international business machine" (IBM).
• l'apparition du relais électromécanique (1900) d'une fréquence de 100 Hz, permet la construction du Harvard Mark I en 1944

Les programmes et instructions

• les orgues de Barbarie
• les métiers à tisser de Vaucanson et Jacquard (1801)

Les ordinateurs "modernes"

• l'invention du tube à vide permet le développements d'ordinateurs entièrement électroniques : l'ENIAC en est le premier exemplaire (1946) ; il pèse environ 30 tonnes...
• la machine de Turing (ordinateur théorique)
• le Manchester Mark I (1948) et l'EDVAC (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
• l'UNIVAC I est le premier ordinateur commercialisé, en 1951.

Les langages de programmation modernes

D'après ce site, qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

• années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à porter. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
• FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
• LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
• ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
• Pascal (1975).
• C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
• Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
• ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
• Smalltalk (fin des année 1983), début de la programmation objet.
• 1983 : ADA.
• années '90 : Python (version 1.0 en 1994).
• années '90 : Java (version 1.0 en 1996).

Je vous conseille d'aller voir le graphique suivant : Computer Languages Timeline (ou découpé en pages A4).

Le langage Python : première partie

Python et les autres langages

Il existe de nombreux langages de programmations. Certains des plus connus et utilisés sont probablement Java et C / C++.

Le langage Python est également très présent car il permet d'écrire assez facilement des petits programmes pour effectuer des taches relativement complexes. (Les programmeurs de Google utilisent beaucoup Python.) Python est un langage libre et gratuit, disponible pour la plupart des ordinateurs (PC Windows, PC Linux / Unix, Macintosh, ...)

Python est, en première approximation, un langage interprété. Cela signifie qu'il n'y a pas d'étape de compilation, mais que l'utilisateur doit disposer d'un interprète Python sur sa propre machine. (Javascript, PHP ou Perl sont d'autres exemples de langages interprétés.)

Ceci est a contraster avec les langages compilés (C/C++, Pascal, ADA) ou le programmeur utilise le compilateur pour produire un fichier exécutable. L'utilisateur final n'a besoin de rien pour exécuter le programme (mais il doit avoir un ordinateur compatible avec le fichier exécutable). L'intérêt est que le programme peut plus facilement être optimisé pour une famille d'ordinateurs. Les langages compilés sont en général plus rapides que les langages interprétés...

La troisième famille de langage est celle des langage utilisant du code intermédiaire : le programme est compilé en un fichier binaire optimisé, et l'utilisateur doit avoir une « machine virtuelle » pour pouvoir exécuter le programme. JAVA est un tels langage.

Remarque : Python possède un mécanisme de code intermédiaire, mais celui ci est relativement transparent pour le programmeur.

Un des avantages de Python est qu'il intègre la « programmation objets » (comme en JAVA). Nous ne parlerons que très peu de cet aspect, que vous retrouverez au second semestre dans le cours d'info-803.

Utilisation de Python

Dans les salles machines, vous pouvez tester Python sous Linux (voir ici) en ouvrant un terminal (Application → Accessoires → Terminal) et en tapant python ou ipython après l'invite de commande. Vous devriez voir quelque chose comme

$ python
Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41) 
[GCC 4.3.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>

Vous pouvez maintenant tester des petits programmes directement.

Lorsque vous écrivez un programme conséquent, il est important de le sauver dans un fichier. Vous pouvez soit utiliser votre éditeur de texte favori (Gedit, Emacs, Xemacs, Vim, ...) pour écrire vos programmes et utiliser le terminal pour les exécuter :

$ python mon_programme.py

Une autre possibilité (recommandée si vous n'êtes pas sûrs de vous) est d'utiliser l'environnement Python « Idle ». Vous pouvez accéder à Idle par les menus : Applications → Programmation → IDLE ???). Vous vous retrouvez alors avec une fenêtre Python Shell qui permet de tester l'exécution de programmes (ou morceaux de programmes), et vous pouvez également éditer un programme (File → New Window ou File → Open). La touche F5 dans la fenêtre d'édition permet de faire passer votre programme dans la fenêtre Python Shell, et donc de le tester.

Parmi les choses à faire pour configurer Idle, je vous conseille de mettre l'option Default Source Encoding à Locale-defined. (Menu : Options → Configure IDLE → General.

Un tout petit peu de syntaxe

La syntaxe de Python est différente de JAVA ou Pascal, mais en général plus simple. Deux points importants sont :

• on n'utilise pas le point-virgule « ; » pour séparer les instructions : on change simplement de ligne
• on n'utilise pas les accolades (« {} ») ou les « begin end » pour faire des blocs, mais on change simplement l'indentation
• une ligne contenant une instruction de contrôle (if, else, for, while, ...) se termine par un « : »

Voici des exemples de code Python pour les structures usuelles :

• commentaires :

<source lang="python">

# si une ligne commence par un '#', alors c'est un commentaire

</source>

• conditionnelles :

<source lang="python"> if n <= 0 and n < 10:

   print "C'est un chiffre"

elif 10 <= n and n < 100:

   print "C'est un nombre à deux chiffres"

elif n >= 100:

   print "C'est un nombre à beaucoup de chiffres"
   print "(au moins trois)"

else:

  print "Erreur : c'est probablement un nombre négatif..."

</source>

• boucles for :

<source lang="python"> for i in range(100): # c'est pour faire une boucle de 0 à 99...

   r = i*i
   print r

print "C'est fini..." </source>

• boucles while :

<source lang="python"> d = 0 tmp = n while (tmp > 0):

   tmp = tmp/10      # la division entre des nombres entiers donne le quotient (division entière)
   d = d + 1

print "Il faut %i chiffres pour écrire %i." % (d,n) </source>

Python possède de nombreux mécanismes pour faciliter la programmation. Nous verrons plusieurs d'entre eux au fur et à mesure du cours et des TD/TP.

Remarque importante : pour pouvoir utiliser les accents, en dehors de l'environnement Idle, il faut mettre la ligne suivante au début de votre programme

# -encoding: utf8-

ou

# -encoding: latin1-

Rappels d'algorithmique

Dans la suite, les algorithmes sont écrits en utilisant le langage Python. Il est normalement possible de copier coller le code dans un fichier pour l'exécuter...

Un exemple

Exercice : écrire une fonction appartient qui prend 2 arguments :

• un tableau t
• un nombre n

et qui vérifie si le nombre n apparaît dans le tableau t. Tester cette fonction sur quelques exemples.

Pour résoudre ce problème, il faut :

• définir une fonction. La syntaxe est

<source lang="python"> def nom_fonction (argument1, argument2, ...):

 ...
 ...
 ...

</source>

• tester l'égalité de deux valeurs. La syntaxe est val1 == val2
• obtenir la taille du tableau. La syntaxe est len(t)

On peut donc écrire la fonction comme suit : <source lang="python"> def appartient(t, n):

 dedans = False
 for i in range(len(t)):   # range(m) génère la liste 0, 1, 2, ..., m-1
   if t[i] == n:
     dedans = True
 return(dedans)

</source>

Cette version n'est pas très bonne car elle continue même si elle a trouvé n au tout début du tableau. Une version un peu meilleure et plus élégante serait la suivante : <source lang="python"> def appartient(t, n):

 """Cette fonction teste si le nombre "n" apparaît dans le tableau "t"."""
 for e in t:
   if e == n:
     return(True)
 return(False)     # si on sort de la boucle, c'est qu'on n'a pas trouvé le nombre "n"

</source>

Les avantages de cette versions sont :

• la fonction possède une documentation : le texte entre les """. Ce texte doit apparaître juste après la ligne « def ... ». Il n'est pas obligatoire, mais fortement conseillé,
• on parcours le tableau t directement avec for e in t:, ce qui est plus lisible,
• on s'arrête dés qu'on a trouvé n.

Pour tester la fonction, on peut, dans l'environnement interactif, déclarer un tableau contenant des entiers en progression arithmétique grâce à la fonction range :

>>> range(10)      # avec un seul argument "n", tous les nombres de 0 à "n-1"
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(5,15)    # avec deux arguments "i" et "n", tous les nombres de "i" à "n-1"
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> range(0,43,2)  # avec trois arguments "i", "n" et "r", les nombres de "i" jusqu'à "n-1" (au plus) par incrément de "r"
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42]
>>> range(100,90,-1)
[100, 99, 98, 97, 96, 95, 94, 93, 92, 91]
>>> appartient(range(10), 5)
True
>>> appartient(range(10), 15)
False
>>> appartient(range(800,-123,-2), 8)
True
>>> appartient(range(800,-123,-5), 8)
False

Remarque : pour tester simplement si un élément appartient à une liste, il est plus judicieux d'utiliser le mot clé in de Python :

>>> 3 in range(0,10000)
True
>>> 3 not in range(0,1000)
False
>>> 3 in range(2,100,2)
False

Quelques exercices

• cf TD1.
• je vous conseille également de faire quelques exercices dans la première partie du livre "Building Skills in Python" : "Language Basics". (Voir les références pour un lien vers le livre...)

Compléments de cours, références

• la page officiel du langage Python
• la documentation des bibliothèques standards
• un livre gratuit de Steven F. Lott sur le langage Python : Building Skills in Python (accès direct)