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
• TD2, format pdf
• lien vers la page de téléchargement de la bibliothèque PIL pour windows (prenez la version 1.1.6 pour Python 2.6)
• lien vers le TP0
• lien vers le TP1 (au format texte)
• lien vers le TP2 (au format texte)

Compléments de TP

TP0

correction possible du TP0

TP1

Voila la fonction rectangle que vous pouvez utiliser dans le TP1 : <source lang="python">

1. 1. 1. fonction rectangle du TP0

def rectangle(im, geom, couleur=(255,255,255)):

   """dessine un rectangle « horizontal » de couleur.
- "im" est un objet image (obtenu par "Image.new")
- "geom" est un quadruplet (x,y,largeur,hauteur), où "x" et "y" sont
   les coordonnées du point en haut à gauche du rectangle.

"""

   x, y, largeur, hauteur = geom
   for j in range(hauteur):
       for i in range(largeur):
           im.putpixel((x+i,y+j),couleur)

</source>

On peut l'utiliser de la manière suivante : <source lang="python"> def baton(t):

   """Dessine le diagramme en batons pour les données du tableau "t"."""
   ...
   ...
   im = Image.new("RGB", (largeur,hauteur), fond)
   ...
       rectangle(im, y,hauteur-h, largeur, h),coul)
   ...
   im.save(fichier_image + '.png')

</source>

• correction possible du TP1

---

---

Exercices de type examen

• examen blanc

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...)

Notions de complexité

La notion de complexité d'un programme est fondamentale pour pouvoir évaluer l'intérêt pratique d'un programme. La complexité observée lors de test ou de benchmark est parfois suffisante mais ne prend en compte que certaines exécutions (celles qui sons testées par les tests). Il est souvent nécessaire de se faire une idée de la complexité théorique d'un programme pour pouvoir prédire son temps d'exécution (ou ses besoins en ressources) pour les exécutions futures.

Première approche de la complexité

Tout d'abord, nous ne nous intéresserons qu'à la complexité en temps, et (presque) jamais à la complexité en espace. Il ne faut pas en déduire que seule la complexité en temps est importante !

L'idée de base est de compter en combien de temps va s'exécuter un programme donné, mais la question elle même est mal posée :

• comment compte-t'on ?
• et surtout, que compte-t'on ?

Chronométrer le temps d'exécution ne permet pas de faire d'analyse fine, et ne permet pas facilement de prédire le comportement général de votre programme. Comme le temps dépend beaucoup du processeur utilisé, l'idéal serait de pouvoir compter le nombre de cycle nécessaires au programme. Cela est généralement impossible car cela dépend du type de processeur utilisé ainsi que des optimisations faites par le compilateur.

La complexité en temps d'un algorithme, c'est une estimation du nombre d'opérations atomiques effectuées par cette algorithme avant qu'il ne termine. Cette estimation doit être donnée comme une fonction dépendant de la taille de l'entrée sur laquelle est lancé l'algorithme.

La notion d'opération atomique est assez intuitive : c'est une opération algorithmique qui n'est pas divisible en sous-opérations. En première approximation, une opération est atomique si elle ne porte que sur des objets de type entier, caractère ou booléen. (Les types codés sur un ou deux mots). Un test (si (n==42) alors ...) ou une affectation (x:=3,1415926536) sont des opérations atomiques ; mais l'initialisation d'un tableau n'est pas atomique. (Il y a autant d'opérations qu'il y a d'éléments dans le tableau...)

Exemple : la recherche du maximum dans un tableau d'entiers positifs peut se faire comme suit

max := Tab[0]
pour i:=1 à taille
faire
  si (max < Tab[i])
  alors max:=Tab[i]
finfaire
affiche("Le maximum est %i.\n",max)

Le nombre d'opérations est le suivant :

• une opération pour l'initialisation de max
• une opération pour l'initialisation de i à 1
• un test pour voir si i==taille
• une opération pour le test max < Tab[1]
• "peut-être" une opération pour l'affectation max:=Tab[1]
• puis, pour chaque élément suivant du tableau :
  • un incrément du compteur
  • une affectation du compteur
  • un test pour voir si on a atteint la fin du tableau
  • un test
  • peut-être une affectation

Au total, si $n$ est la taille du tableau, on obtient entre $4n$ et $5n$ opérations. De manière générale, on s'intéresse surtout au pire cas ; on dira donc que cet algorithme s'exécute en "au plus $5n$ opérations".

Relier ce nombre d'operations algorithmiques au nombre d'operations effectivement executées par le processeur est cependant tres difficile. Ca devient meme quasiment impossible pour les langages de haut niveau tels que Python : de nombreuses operations sont en fait plus complexes qu'elles n'ont l'air.

Approximations asymptotiques

On ne peut habituellement pas compter de manière aussi précise le nombre d'opérations ; et ça n'a pas toujours du sens de vouloir être trop précis. (Est-ce que i:=i+1 correspond à une ou deux opérations atomiques ?) Nous allons donc utiliser les approximations asymptotique pour compter la complexité... Le but sera alors de distinguer les algorithmes "rapides", "lents", ou "infaisables". La notion de "grand O" permet de faire ça de manière systématique.

définition

si $f$ et $g$ sont des fonctions de $\mathbb {N}$ dans $\mathbb {N}$, on dit que $f$ est un "grand O" de $g$, et on écrit $f=O(g)$ si le quotient $|f(n)| \over |g(n)|$ est borné. Plus précisément, ça veut dire que $\exists B,\forall n,{|f(n)| \over |g(n)|}<B$

Le but de cette définition est multiple :

• elle cache une borne "au pire"
• elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("$4n$ et $5n$, c'est presque la même chose")
• elle permet d'ignorer les cas initiaux et autres phénomènes négligeables
• elle permet de simplifier les calculs de complexité

Propriétés

• si $f=O(h)$ et $g=O(h)$ alors $\alpha f+\beta g=O(h)$
• si $f=O(g)$ et $g=O(h)$ alors $f=O(h)$
• si $f=O(g)$ et $f'=O(g')$ alors $f\times f'=O(g\times g')$
• si $f=O(g)$ et $f'=O(g')$ alors $f+f'=O(|g|+|g'|)$

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : $\log$, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
Si on note $f<g$ pour $f=O(g)$ et « non-$g=O(f)$ » :

$1<\log(\log(n))<n^{\epsilon }<n<n^{c}<n^{\log(n)}<c^{n}<n^{n}<c^{(c^{n})}$

Avec $0<\epsilon <1$ et $c>1$.

---À compléter ? Par exemple, vous pouvez rajouter les fonctions $\log(n)$ et $n\log(n)$...---

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)