Science is what we understand well enough to explain to a computer. Art is everything else we do. (D. Knuth)
Un programme, stocké sur un disque dur, SSD, ou transféré sur internet lorsqu'on le télécharge, est assimilable à de l'information : ainsi, un programme est une donnée numérique.
Un problème qui peut être résolu algorithmiquement est dit «calculable» (dans le sens : il peut être résolu par une machine de Turing).
Les machines de Turing offrent un cadre théorique qui permet de répondre (négativement) au problème de décision : «pour tout problème donné, existe-t-il un algorithme qui permet de répondre en un nombre fini d'étapes, par «oui» ou «non» à ce problème» ; on verra qu'il n'existe pas de programme qui permet de voir si un programme donné s'arrête ou boucle infiniment.
Une machine de Turing est constituée d' :
a
le plus à gauche (flèche orange). Côté automate,
on part de l'état q1
. a
, et une flèche sort de q1
en mentionnant
la possibilité a
: on va suivre cette flèche à droite de q1
, passer en
q2
, et au passage, remplacer, comme mentionné par la flèche suivie, ce a
sur le ruban par un vide #
, et déplacer la tête de lecture à droite (utiliser votre doigt).
abbabb
est-il accepté ?
aaabbb
est-il accepté ?
1
» côte à côte. Ainsi : 0 sera représenté en unaire par 1
et
4 sera représenté par 11111
. Pour la machine suivante, on part du mot #x̄#
= #1…1#
avec q1
pour état initial, et avec x un entier naturel quelconque,
écrit en unaire sur le ruban (la tête de lecture, comme précisé par la notation, pointe sur le
premier #
à gauche).
#x̄#ȳ#
, où x et y sont des entiers naturels, écrits en unaire sur le ruban avec q1
comme état initial, et
la tête de lecture pointe sur le
premier #
à gauche. #z̄#
; on prouve ainsi que l'addition
des entiers est une opération calculable.
état courant | symbole lu | symbole écrit | déplacement | état suivant |
---|---|---|---|---|
q1 | # | 0 | → | q2 |
q2 | # | 1 | → | q1 |
Remarque : On peut coder une ou plusieurs machines de Turing à l'intérieur d'une machine de Turing : on parle de machine de Turing universelle
Cf la vidéo Science4All - La machine de Turing | Intelligence Artificielle 4
Voir la vidéo CNRS - Le modèle Turing
Langage : Les problèmes peuvent être codés dans un langage formel, écrits
en utilisant un alphabet (fini) de caractères pouvant être manipulés par des machines de
Turing.
Problème de décision : C'est un problème pouvant être traité par une machine
de Turing, pour lequel on peut répondre par oui ou bien par non.
Par exemple :
Décidabilité : On dit qu'un problème est décidable lorsqu'il
est calculable et qu'une machine de Turing permet de répondre "oui" par un état
final ou bien "non" par un arrêt sur un autre état, c'est-à-dire répondre au problème
en un nombre fini d'étapes. Concrètement, il existe un algorithme qui permet de répondre au problème et il s'arrête
en donnant la réponse.
Dans le cas contraire, on dit que le problème est indécidable.
S'il existe un algorithme pouvant répondant "oui" en un nombre fini d'étapes, mais ne pouvant
pas répondre "non" en un nombre fini d´étapes, on dit que le problème est semi-décidable.
Problème de l'arrêt : Ce problème cherche à savoir s'il existe un programme
(appelons-le halt()
), qui prend en entrée n'importe quel programme x (donné
sous forme de chaîne de caractères, ou bien codé sous forme de nombre, par exemple)
et précise si x s'arrête ou non.
Trop beau pour être vrai ! On va voir que ce problème est indécidable, et qu'un tel programme
halt
ne peut exister.
Examinons l'algorithme suivant :
TURING(n) # n est un entier naturel
1. LISTER (sans les exécuter) tous les programmes de taille inférieure ou égale à n caractères,
qui prennent un entier en entrée et renvoient un entier en sortie.
# c'est long, mais possible par reconnaissance de la syntaxe et de la grammaire
# de ces programmes ; aussi, ces programmes sont en nombre fini.
2. SÉLECTIONNER parmi cette liste ceux qui s'arrêtent avec halt() lorsque leur entrée est n.
3. EXÉCUTER chacun des programmes sélectionnés et choisir le plus grand des entiers Smax
apparu en sortie de ces programmes.
4. RETOURNER Smax + 1.
n0
sa taille en caractères.TURING()
s'arrête.TURING(n0)
:
TURING(n0)
se liste lui-même puisque sa taille est inférieure
ou égale à n0
. TURING()
étant n0
, et celui-ci s'arrêtant par construction,
il est sélectionné par halt
.TURING(n0)
renvoie un entier qui est forcément inférieur ou égal à Smax
...
Smax + 1
... CONTRADICTION !halt
ne peut donc pas exister : sinon, on pourrait s'en servir pour
écrire un programme qui renvoie une sortie plus grande que la sortie qu'il renvoie.
Pour exécuter un programme, on peut, encore aujourd'hui, produire un exécutable à partir
d'un script où sont écrites, à l'aide d'une syntaxe minimale, une suite d'
instructions (hardware) du processeur permettant d'agir directement sur les registres.
On appelle ce pseudo-langage l'assembleur ; il est propre à
chaque processeur car leurs
jeux d'instructions peuvent être différents. On le qualifie de langage de bas niveau, dans
le sens où il est très proche du matériel ; le plus proche étant le langage
machine, qui
est essentiellement de l'assembleur écrit en binaire. Voici un exemple d'opération écrite
en assembleur (ces instructions sont assez communes et ce script marcherait sur bon
nombre de processeurs) :
;pour calculer (7+6)%3, on aura le code suivant :
MOV AX, 7 ; Le registre AX reçoit la valeur 7.
ADD AX, 6 ; On ajoute à AX la valeur 6, le résultat est stocké dans la destination, soit AX.
MOV BX, 3 ; On met dans le registre BX la valeur 3 qui servira de source à la division.
DIV BX ; On divise AX par la source, ici BX, qui vaut 3
;le résultat de la division est stocké dans la destination (BX)
;et le modulo (reste de la division qui nous intéresse ici) est mis dans DX
Cf Wikiversity
.jar
(bytecode) qui sera exécuté par la
machine virtuelle Java adaptée au système d'exploitation sur lequel
on exécute le programme. Les .jar sont donc portables sur tous les systèmes disposant
d'une machine virtuelle du même type. Cette grande portabilité est une des raisons
qui a poussé les concepteurs d'Android à baser leur système d'exploitation sur Java. Nous avons déjà étudié la programmation impérative (et ses réalisations itératives et récursives) ainsi que la programmation orientée objet en début d' année.
Nous utilisons aussi parfois, en Python, le paradigme fonctionnel. Le principe est de composer (enchaîner) des fonctions. En ayant des fonctions rigoureusement spécifiées, on limite, voir on élimine les effets de bord, et donc bon nombre d'erreurs possibles, tout en rendant le code source concis et lisible.
Haskell est un bon exemple de langage de programmation fonctionnelle. Liens pour découvrir ce langage : nokomprendo et univ-lille1.fr.
Attention, l'idée du paradigme fonctionnel n'est pas seulement d'utiliser des fonctions mais d'utiliser des fonctions dites pures. Il s'agit de fonctions qui ne modifient pas l'état courant des variables. Autrement dit, le résultat renvoyé par une fonction pure ne doit dépendre que de valeurs passées en paramètres et pas de valeurs externes à la fonction. De plus une fonction pure ne doit pas modifier les valeurs des variables externes, globales.
def est_majeur(age):
return age >= 18
liste = [1, 6, 4]
def ajouter(x):
liste.append(x)
return liste
def ajouter(liste, x): # Cette fonction n'est pas pure
liste.append(x)
return liste
Avec un même langage de programmation, on peut utiliser des paradigmes différents.
Dans un même programme, on peut utiliser des paradigmes différents.
Cette partie est la suite logique du chapitre sur les spécifications et les tests vu en première NSI.
assert condition
assert condition, "message d'erreur"
L'assertion vérifie qu'une condition est respectée, sinon elle stoppe l'exécution du programme et
peut afficher un message d'erreur (celui-ci est facultatif).
Une assertion permet de stopper préventivement une exécution avant qu'une erreur ne se produise. Elles
sont des outils de développement et ne doivent pas apparaître dans un programme final, livrable. En supprimant toutes les
assertions d'un script, le programme doit continuer à fonctionner normalement.
Le mode de programmation qui utilise des assertions est appelée programmation défensive. Elle suppose que les fonctions sont correctement utilisées,
mais prévoit des garde-fous : les assertions, qui permettent de vérifier les préconditions et les postconditions et ainsi de détecter des bugs
au cours du développement.
Ce type de programmation est utilisé pour du code dont on a le contrôle. Par exemple lorsqu'on écrit un module, pour les fonctions qui sont destinées à n'être appelées que dans ce module. Pour les fonctions destinées à être appelées par d'autres modules/scripts/personnes, il est préférable de faire une gestion active des erreurs avec une structure conditionnelle qui retourne des valeurs facilement interprétables et si possible de même type que autres retours.
-1
, à l'aide d'une structure conditionnelle.
def indice(liste, element):
"""Renvoie l'indice de la première occurence de l'élément dans la liste."""
assert element in liste, "L'élément doit être dans la liste."
return liste.index(element)
print(indice(["a", "b", "c", "d"], "e"))
La modularité est le fait de décomposer un programme en plusieurs fonctions/modules/fichiers.
La modularité présente des avantages d'autant plus fort qu'un projet est important :
Cette modularité existe à plusieurs échelles :
Un module constitue une "brique" logicielle d'un projet, pouvant éventuellement être utilisé par d'autres projets. Il est donc important de s'assurer de son indépendance vis-à-vis du reste du projet et de la cohérence des missions qu'il assure. De plus, il est important de le documenter convenablement afin de le rendre compréhensible et facilement réutilisable.
Il existe un grand nombre de modules natifs au moteur Python. La liste exhaustive est disponible dans la Doc Python en ligne. Parmi eux, en voici quelques-uns particulièrement utilisés :
Module | description |
---|---|
tkinter | interface graphique |
math | fonction et constantes mathématiques |
random | génération de nombres aléatoires |
statistics | fonctions de mathématiques statistiques |
time | fonctions liées au temps |
os | interaction avec le système d'exploitation, gestion des fichiers |
smtplib | interaction avec un serveur SMTP |
turtle | affichage graphique |
sqlite3 | interaction avec une BD |
pip | gestion et installation de modules supplémentaires |
PIL | traitement d'image |
NumPy | calcul numérique et matriciel |
Matplotlib | tracé graphique |
Il en existe beaucoup d'autres, développés par la grande communauté des développeurs Python et qui nécessiteront une installation supplémentaire. Ils sont en général accompagnés d'un site internet les documentant
En python, les modules sont importés grâce au mot clé import
proposant plusieurs syntaxes :
from math import *
print(pi)
from math import pi
print(pi)
import math
print(math.pi)
import math as m
print(m.pi)
Attention, la première syntaxe importe directement dans l'espace des noms du programme, tout ce que contient le module (*).
Cela peut entraîner une surcharge de nom, c'est-à-dire l'écrasement d'une variable ou d'une fonction par une autre varible ou une autre fonction portant le même nom.
Ce risque de surcharge est facilement évitable à l'aide des autres syntaxes. En n'important qu'une fonction du module (syntaxe 2)
ou en nommant explicitement le module (syntaxe 3) ou en le renommant (syntaxe 4) lors de l'utilisation d'une de ses fonctions.
Pour créer vos propres modules, il suffit de créer un fichier python mon_module.py
à la racine de votre projet et de
l'importer avec les mêmes syntaxes proposées par l'instruction import
.
from mon_module import *
from mon_module import ma_fonction
import mon_module
import mon_module as mm
Dans le cas d'un site internet, la modularité est déjà prise en compte dans le découpage fonctionnel des fichiers HTML, CSS et JS. Pour rappel, les fichiers HTML hébergeant le contenu du site, les fichiers CSS, sa mise en page et les fichiers JS assurant son interactivité.
Comme pour la plupart des langages de programmation, la modularité est également permise en javascript.
Par exemple sur ce site de cours de NSI, la mise en page des codes est sous-traitée à un module
(fichier javascript) intitulé prism.js
utilisant également un fichier CSS prism.css
. Ces deux
fichiers ont été téléchargés depuis le site prismjs.com et intégrés
aux fichiers du site.
De la même façon qu'en python, les modules sont importés en début de script, nous trouverons dans la balise <head>
d'une page HTML, des liens vers des fichiers Javascript. Ces fichiers peuvent tout aussi bien être locaux (repéré par leur chemin relatif) ou bien hébergé
ailleurs sur internet (repéré par leur URL).
<head>
<meta charset="utf-8" />
<title>C9-Programmation</title>
<link rel="stylesheet" type="text/css" href="styles/style.css" />
<link rel="stylesheet" type="text/css" media="print" href="styles/print.css"/>
<link href="styles/prism.css" rel="stylesheet" />
<script src="scripts/interactif.js" defer></script>
<script src="scripts/prism.js" defer></script>
<script async="true" src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=AM_CHTML" defer></script>
</head>
En programmation, savoir répondre aux causes de bugs et tester ses scripts est essentiel pour obtenir un programme fiable et robuste.
Un bon Environnement de Développement Intégré (EDI) fournit plusieurs outils permettant de limiter l'apparition de bugs. Il doit permettre :
Conçu pour le langage python, la version PyCharm Community
est un EDI libre, gratuit et assez ergonomique qui propose ces fonctionnalités.
Vous pouvez les retrouver également dans Visual Studio Code qui est un
EDI généraliste (plusieurs langages) et qui propose de nombreuses extensions très intéressantes.
while
:
for
, il faudra éviter pendant l'exécution de la boucle de modifier la liste que l'on est en train de parcourir.a = 0.0
while a != 0.3:
a += 0.1
print(a)
print("C'est fini !")
def supprimer_les_nombres_pairs(liste):
for i in range(len(liste)):
if liste[i]%2 == 0:
liste.pop(i)
return liste
liste = [i for i in range(10)]
print(supprimer_les_nombres_pairs(liste))
Quand le moteur Python rencontre une erreur, il lève une exception.
Une exception est un objet en python qui est définie par son type.
Voici une liste non exhaustive de types d'exception :
Type d'erreur | Description |
---|---|
SyntaxError |
Le code ne peut pas être exécuté car l'analyseur a repéré une erreur dans la syntaxe de python. Il peut s'agir
de deux-point ":" manquant, de parenthèses mal couplées ou d'indentation manquante. L'analyseur qui ne reconnaît plus la syntaxe de python, signale une ligne d'erreur mais attention la faute de syntaxe est souvent localisée avant cette ligne. |
ZeroDivisionError |
Erreur de division par zéro. |
NameError |
Une variable, une fonction, une classe, invoquée ... n'est pas précédement définie. |
TypeError |
L'opérateur n'accepte pas le type d'opérande qui lui est donné. |
ValueError |
Ici l'opérateur reçoit le bon type d'opérande mais sa valeur est inappropriée. |
IOError |
Le fichier n'existe pas. |
RecursionError |
La limite de la pile d'appels récursifs a été atteinte. Elle est de 1000 par défaut et peut être modifiée. |
IndexError |
L'indice pour une séquence, ou la clé pour un dictionnaire n'existe pas. |
AssertionError |
Une assertion est fausse. |
KeyboardInterrupt |
L'exécution est stoppée par l'utilisateur (fermeture de fenêtre par exemple). Contrairement aux autres erreurs,
il ne s'agit pas d'un objet Exception , en python. Par exemple,
il ne sera pas capter par l'instruction except Exception : , contrairement à toutes les autres.
Par contre, il sera capter par l'instruction except : .
|
x = int(input("Entrez un nombre : "))
age = input("Entrez votre age : ")
if age >= 18:
print("Vous êtes majeur.")
Python propose une syntaxe afin de gérer les erreurs.
try:
# instructions à exécuter
except """type d'erreur 1""" :
# instructions à exécuter si ce type d'erreur est levée
except """type d'erreur 2""" : # Un deuxième except est facultatif
# instructions à exécuter si ce type d'erreur est levée
else: # Factultatif
# instructions à exécuter s'il n'y a pas eu d'erreur
finally: # Facultatif
# instructions à exécuter dans tous les cas même si un return existe dans un bloc except
Remarque : Il est possible de ne pas préciser le type d'erreur à attraper
après except:
, mais cela est déconseillé
car toutes les erreurs levées ne se valent pas et cela peut être source d'erreurs supplémentaires
en capturant une erreur qui n'aurait pas dû l'être et qui sera alors invisible.
try: except: else:
afin qu'aucune erreur ne soit levée quelque soit l'action de l'utilisateur et qu'il soit informé de son éventuelle erreur.
age = int(input("Entrez votre age : "))
if age >= 18:
print("Vous êtes majeur.")
else:
print("Vous êtes mineur.")
Il est également possible de lever soi-même une erreur à l'aide du mot clé raise
ou
bien encore de récupérer une erreur dans une variable.
raise NameError("Ce nom de variable n'existe pas.")
.
def majeur(age):
if type(age) != type(1):
raise # à compléter
if age < 0:
raise # à compléter
if age >= 18:
return "majeur"
return "mineur"
age = -1
try:
print("Vous êtes {0}.".format(majeur(age)))
except TypeError as er:
print("Erreur :", er)
except ValueError as er:
print("Erreur :", er)
L'utilisation des assertions dans une structure de gestion des erreurs permet de personnaliser encore davantage les messages d'erreur.
age = input("Entrez votre âge :")
try:
age = int(age)
assert age >= 0, "Vous ne pouvez pas avoir un âge négatif."
assert age < 200, "Vous ne pouvez pas avoir plus de 199 ans."
except ValueError:
print("Vous devez entrer uniquement des caractères numériques.")
except AssertionError as msg :
print(msg)
En apparence, python ne se soucie pas des types de variable : lorsqu'on initialise une variable, à aucun moment on ne doit déclarer son type et à tout moment, on peut écraser le contenu d'une variable par une valeur d'un autre type. C'est assez pratique car cela allège le code mais au risque de générer des erreurs.
>>> a = "Hello, World"
>>> print(type(a))
<class str>
>>> a = 3 + 2
>>> print(type(a))
<class int>
Cet exemple montre que Python connaît bien le type de ses variables et qu'il vous autorise à en changer comme bon vous semble. Le risque est d'affecter de mauvaises valeurs à une variable sans s'en rendre compte et ainsi génerer des bugs. Certains langages comme le C obligent à déclarer au préalable les variables et leurs types. Le compilateur va alors détecter les erreurs de typage et avertir le développeur des problèmes avant même qu'ils ne se produisent mais ce n'est pas le cas en python.
Il est possible de réaliser à partir de python 3.10 des annotations de type, qui sont utiles pour le développeur. L'Environnement de Développement Intégré pourra les exploiter pour avertir en cas d'erreurs ou faire des suggestions pertinentes limitant le risque d'erreurs.
Exemple : Ces deux fonctions sont fonctionnellement équivalentes mais la seconde comporte des informations de type utilisé par l'EDI pour aider le développeur.
def triple(x):
return 3 * x
def triple_v2(x: int) -> int:
return 3 * x
Le contrôle de versions permet de suivre les modifications, faites par qui et pourquoi, ce qui devient crucial pour de gros projets et le travail d'équipe.
Voir la Documentation de Git
import this
dans la console python pour re-découvrir les
grands principes de python : The Zen of Python (PEP 20)