Les cours-conférences du Collège Belgique à Liège

Pierre Wolper, membre de l'Académie royale de Belgique, Doyen de la Faculté de Sciences appliquées de l'ULg

Mardi 19 avril

La pensée algorithmique

En partenariat avec :

Liege Creative, une initiative de :

Le Collège Belgique est soutenu par :

Avec le soutien de la Présidence du Gouvernement wallon

La  pensée  algorithmique

Pierre Wolper Université de Liège

1

La  pensée  algorithmique  Computational  (algorithmic)  

thinking •  Raisonner et aborder les

problèmes en termes de traitement de l’information •  Le traitement de l’information

peut être réalisé o par un système physique simple o par un système biologique o par un système informatique (ordinateur)

2

Traitement  de  l’information

Capteurs Information Traiter    Mémoriser

Information  Prédiction  Action

3

Pour être traitée, l’information doit être représentée physiquement : •  de l’encre sur du papier, •  l’état d’un système mécanique, •  l’état d’un système neuronal, •  l’état d’un système électronique.

Un  système  simple  de  traitement  de  l’information

4

Un  système  de  traitement  de  l’information  bien  connu

•  Capture de l’information : sens

•  Traitement : système

nerveux •  Actions : muscles

5

Pensée  algorithmique  et  informatique

•  La pensée algorithmique est l’ensemble des approches et méthodes qui permettent de formuler et résoudre un problème sous une forme exploitable par un système de traitement de l’information.

•  L’informatique (ordinateurs, programmation)

permet la concrétisation de méthodes issues de la pensée algorithmique.

6

Recontre  entre  deux  systèmes  de  traitement  de  

l’information

7

Représenter  l’information •  Les systèmes informatiques

représentent l’information sous la forme d’une séquence de symboles (binaires).

110000111010111100101011011111000

•  Cette représentation est universelle : o Nombres, textes, images, son, vidéo, … o  Il n’y a pas de limite à la précision possible !

Exemple: L’âge le l’univers en secondes 11000001010110110011111111000111111001101001000000000000000 8

La  représentation  d’une  image

9

Chaque  pixel  est  représenté  par  l’intensité  des  3  couleurs  fondamentales

Traiter  l’information •  Si l’information est représentée par une

séquence de symboles (binaires), •  La traiter revient à comparer, mémoriser,

modifier des symboles. •  Mais, comment décrire les opérations à

effectuer? •  Cela peut se faire à l’aide d’un formalisme

très simple: la machine de Turing. •  La thèse de Turing affirme que ce

formalisme est suffisant. 10

Une  machine  de  Turing

11

De  la  théorie  à  la  pratique •  Même si tout traitement de l’information peut être

décrit par une machine de Turing, ce formalisme n’est pas adapté à décrire des traitements complexes.

•  Il faut des méthodes pour organiser et structurer l’information représentée.

•  Il faut des méthodes pour exprimer simplement le traitement à appliquer.

•  Il faut des méthodes pour concevoir les traitements de l’information et veiller à leur efficacité.

•  Il faut apprendre à penser algorithmiquement.

12

Organiser  et  structurer  l’information

Un exemple: le dictionnaire •  Une entrée dans un dictionnaire est un mot

suivi de sa définition et autres informations. •  Il faut pourvoir trouver rapidement

l’information concernant un mot. •  Pour cela les mots sont triés par ordre

alphabétique. •  Pour faciliter la recherche les premier et

dernier mots de chaque page sont repris en haut de la page.

13

Comment  chercher  ? •  Feuilleter le dictionnaire page par page depuis le

début: trop lent ! •  Estimer où ouvrir le dictionnaire avant de

commencer à chercher (A au début, Z à la fin, I au milieu): mieux.

•  Une aide: un onglet pour chaque lettre. •  Une aide plus efficace: un index. •  L’index reprendra le premier mot de chaque page

et le numéro de page correspondant: Pour une dictionnaire de 2000 pages, l’index ne fait que 20 pages.

14

Comment  chercher  (suite)  ? •  Si l’index est trop gros: on crée un index de l’index:

1 page ! •  Comment retrouver la page à partir de son

numéro : calculer où ouvrir le dictionnaire. •  Exemple: si le dictionnaire a une épaisseur de 10 cm

et comporte 2000 pages, la page 764 se trouve à 3,82 cm du haut du livre

15

L’index  un  outil  puissant •  Le principe présenté est exactement celui utilisé en

algorithmique pour permettre la recherche rapide d’informations.

•  Un dictionnaire courant comporte 60.000 mots, mais que faire si on a 60.000.000, 60.000.000.000 ou même 60.000.000.000.000 d’informations à indexer?

•  On crée un index, un index de l’index, un index de l’index de l’index, …

•  Chaque niveau réduit la taille de l’index d’un facteur 100 è 7 niveau suffisent pour 60.000 milliards d’éléments !

•  Ainsi fut indexée toute l’information du monde (60.000 milliards de pages web) !

16

Exprimer  simplement  le  traitement  à  appliquer

•  C’est le domaine des langages et environnements de programmation.

•  Mais, il faut surtout travailler en utilisant des niveaux d’abstractions : o Travailler à différents niveaux de détail

suivant les besoins, o Pouvoir travailler à un niveau sans connaître

les niveaux inférieurs, o Se doter d’opérations de plus en plus

puissantes permettant de simplifier le travail.

17

L’abstraction:  un  exemple Créer une animation vidéo

18

Niveaux  d’abstrations •  30 secondes de vidéo = 30 × 25 images = 30 × 25 ×

1.000.000 = 750.000.000 de pixels. •  Préciser la couleur et l’intensité de 750.000.000 de

pixels: ??? •  Abstraction : dessiner des lignes des courbes,

colorier des surfaces, leur donner une texture, un dégradé ; le calcul des pixels est automatisé.

•  Abstraction : dessiner une image composée d’objets représentés par leur forme 3D, la couleur et les caractéristiques de leur surface ; le calcul de l’image de chaque objet est automatisé.

•  Abstraction : voir certains objets comme mobiles et permettre de décrire leurs mouvements : le calcul des images successives montrant le mouvement est automatisé.

19

Concevoir  des  solutions  algorithmiques

Un mécanisme puissant la récursion •  Le principe est simple: concevoir la

solution pour un cas de grande taille, en supposant o que l’on peut résoudre les cas de

taille inférieure, o que l’on dispose de la solution pour

les cas de taille minimale.

20

La  récursion  :  un  exemple Les tours de Hanoï

21

                                                                                 A                                                                              B                                                                        C

Les  tours  de  Hanoï  :    Une  solution  récursive

•  Si la tour comporte 1 disque, la solution est immédiate.

•  Si la tour comporte n disques et que je peux résoudre le problème pour une tour de n-1 disques o Je déplace les n-1 disques supérieurs de A

vers B, o Je déplace le dernier disque de A vers C, o Je déplace les n-1 disques de B vers C :

récursion!

22

Les  tours  de  Hanoï  :    la  solution

•  Des méthodes ont été mise au point pour directement mettre en œuvre les algorithmes récursifs.

•  Le résultat paraît presque magique.

23

Une  autre  technique  magique:  l’apprentissage

24

Homme ou arbre ?

Apprentissage  

25

Homme ou arbre

L’  apprentissage  (Supervisé)

Classification d’images •  Une image est un tableau de pixels. •  On définit une fonction paramétrée des

pixels, par exemple

•  En utilisant des images pour lesquelles la

classification est connue, on ajuste les paramètres de façon à séparer les classes.

26

αij p(i, j)ij∑

27

Classification  d’images •  Pour les images cette approche simple ne

fonctionne pas. •  Il est nécessaire d’extraire des

« caractéristiques » de l’image pour réduire la dimension des données et se focaliser sur ce qui est important.

•  Définir et extraire des « caractéristiques » est difficile.

28

Avancée de rupture: l’apprentissage profond

L’apprentissage  profond  (deep  learning)

•  Étager l’apprentissage:

29

•  Il est aussi possible d’apprendre les « caractéristiques » !

Applications  de  l’apprentissage

•  Reconnaître la parole, la musique, du texte.

•  Classer des images, reconnaître des visages.

•  Jeu de GO. •  Vision, robotique, véhicules

autonomes, drones.

30

Une  victoire  de  la  machine

31

Penser  algorithmiquement

Penser algorithmiquement, c’est •  Penser en termes de données organisées et

structurées, •  Penser en termes d’abstractions, •  Penser en termes de méthodes systématiques

exprimées clairement, •  Penser en termes des mécanismes puissants de

création de solutions algorithmiques, e.g. récursion, apprentissage.

C’est aussi tenir compte de l’efficacité et de la taille des solutions.

32

Les  limites  –  en  théorie Tout problème n’a pas de solution algorithmique! •  Problème : classer en deux catégories des

séquences de symboles (binaires). o Exemple: nombres divisibles par 3 ou non.

•  La limite existe uniquement si on ne met pas de borne à la longueur des séquences considérées.

•  Elle vient simplement du fait qu’il y a plus de catégories que de descriptions finies (algorithmiques).

33

Les  limites  en  pratique •  Pour une taille bornée des données, tout

problème a une solution algorithmique. •  Mais,

o La solution peut être absurdement grande: une table de classification pour des séquences de 200 bits comporterait plus d’entrées que la terre ne comprend d’atomes.

o La solution peut être inefficace au point d’être inexploitable.

34

Des  solutions  algorithmiques  inefficaces •  Comment trouver le parcours minimum pour

visiter n endroits? Essayer toutes les possibilités! o  Il y en a un nombre fini, o  Mais ce nombre croît trop vite!

•  Au départ j’ai n choix •  A l’étape suivante (n − 1), •  Ensuite (n-2)…. •  Les choix se multiplient: au total

n ✕ (n − 1) ✕(n − 2) ✕ … ✕ 2 ✕ 1 •  Pour n = 20 déjà des milliards de milliards de

possibilités. Il faut un algorithme plus efficace ! 35

Pensée  algorithmique  et  science

•  La science tente de comprendre le monde qui nous entoure pour l’expliquer et le prédire.

•  Pour cela elle utilise des modèles, souvent mathématiques.

•  L’algorithmique et l’informatique permettent de mieux exploiter les modèles mathématiques.

•  Mais un modèle peut aussi directement s’exprimer en termes de données et d’algorithmes.

•  Un excellent exemple est la génétique moderne.

36

Pensée  algorithmique  et  technologie

•  L’impact le plus visible sont tous les dispositifs de conservation, traitement et transmission de l’information.

•  La combinaison de senseurs, de traitement avancé de l’information, de communication et d’actuateurs permet toutes sortes d’innovations : o  contrôle électronique d’un moteur, o  réseaux électrique intelligent, o  internet des objets.

•  Comme en science, l’exploitation des données et des algorithmes permet de modéliser ce qui ne l’était pas : o  publicité ciblée, o  évaluation du risque d’un crédit. 37

Pensée  algorithmique  et  société

•  La pensée algorithmique ouvre des nouvelles voies de solution (choix des écoles).

•  Elle doit faire partie de notre culture et est indispensable pour comprendre le monde dans lequel nous vivons.

•  Elle doit être enseignée dans nos écoles. •  Les technologies qu’elle permet ouvre

d’innombrables opportunités, mais suscitent aussi des craintes.

38

Les  robots  vont-­‐‑ils  nous  remplacer  ?   Quel est leur avis?

39

Des  possibilités  plus  intéressantes

40

En  conclusion •  La pensée algorithmique et les systèmes

informatiques sont une révolution pour nos sociétés.

•  Nous devons la connaître et la maîtriser. •  Les adaptations en matière d’organisation

de la société et du type des emplois seront considérables.

•  Nous devons nous y préparer. •  Les possibilités d’amélioration de notre vie

sont gigantesques. 41