Les algorithmes : entre quotidien et créativité par le Prof. Samuel NICOLAY et son équipe, ULg - Département de Mathématique | LIEGE CREATIVE, 25.06.15

Jeudi 25 juin

Les algorithmes : entre quotidien et créativité

Prof. Samuel NICOLAY et son équipe, ULg – Mathématique

Gregory REICHLING, Citius Engineering

Vincent FAVART, Musimap

Avec le soutien de :

S. Nicolay

Les algorithmes : entre quotidien et créativité

Gérard Berry (1948, informaticien, membre de l'Académie des Sciences françaises)

« Un algorithme, c’est tout simplement une façon de décriredans ses moindres détails comment procéder pour faire quelque chose. »



Un algorithme sert à décomposer une tâche (a priori complexe)en une suites d'actions ne faisant pas intervenir la réflexion.



Un algorithme sert à décomposer une tâche (a priori complexe)en une suites d'actions ne faisant pas intervenir la réflexion.

Les ordinateurs peuvent dès lors efficacement relayer l'hommedans l'exécution d'un algorithme, puisqu'ils ne connaissent pasla fatigue et qu'ils effectuent bon nombred'opérations élémentaires de manière extrêmement rapide.

Résoudre un casse-tête, comme le Rubik's cube (solution systématique)

Exemples d'algorithmes dans la vie quotidienne


Tissage (automatisé par le métier Jacquard)



Tissage (automatisé par le métier Jacquard)


Tout n'est pas algorithme !

Algorithme de l'amitié (Big Bang Theory)

téléphoner

la personneest là ?

laisser unmessage

attendre quela personne

rappelle

es-tu librepour dîner ?

aller dîner

veux-tuboire une

boisson chaude ?

cas possibles :caféthé

chocolat

prendre un caféprendre un thé

prendre un chocolat

commencerune amitié

intérêtcommun ?

partager l'activité

réponse ?

réponse ?

qu'aimes-tudans la vie ?

faisons celaensemble !

non

oui

oui

non

oui

non

oui

non

Trois exemples plus en détails

Compression d'images


Observations atypiques



Observations atypiques


Détection de bugs

Les algorithmes et le traitement de l’image

Thomas Kleyntssens

[email protected]

Université de Liège

LIEGE CREATIVE - 25 juin 2015

Le traitement de l’image Premier algorithme naïf Les ondelettes

Le traitement de l’image est une discipline à mi-chemin entre

l’informatique et les mathématiques. Elle étudie les images

numériques dans le but d’en extraire de l’information ou de modifier

leur qualité.

Qu’est-ce qu’une image ?

La compression d’image : un subtil compromis entre nombre de

pixels (qualité visuelle) et espace sur le disque dur.

Il existe beaucoup de normes de compression : JPEG, TIFF, GIF,

JPEG 2000, ...

1 / 5

Thomas Kleyntssens - Les algorithmes et le traitement de l’image


Le traitement de l’image est une discipline à mi-chemin entre

l’informatique et les mathématiques. Elle étudie les images

numériques dans le but d’en extraire de l’information ou de modifier

leur qualité.

Qu’est-ce qu’une image ?

La compression d’image : un subtil compromis entre nombre de

pixels (qualité visuelle) et espace sur le disque dur.

Il existe beaucoup de normes de compression : JPEG, TIFF, GIF,

JPEG 2000, ...

1 / 5



Image de taille 526x526



2 / 5




Image de taille 263x263 Image de taille 131x131

2 / 5



Les ondelettes

Elles s’adaptent aux propriétés locales de l’image.

Elles donnent des informations sur les contours, les textures, ...

Il existe plusieurs ondelettes.

La norme JPEG 2000, utilisée dans le Digital Cinema Package

utilise la transformée en ondelettes. Les ondelettes les plus

couramment utilisées sont les ondelettes de Daubechies.

Ingrid Daubechies, née le 7 août 1954, est une physicienne et mathématicienne belge ayant reçu de

nombreux prix : Golden Jubilee Award for Technological Innovation from the IEEE Information Theory

Society, German Eduard Rhein Foundation, NAS Award in Mathematics, Emmy Noether Lecturer, IEEE

Jack S. Kilby Signal Processing Medal, Benjamin Franklin Medal in Electrical Engineering from the

Franklin Institute, Fellow of the American Mathematical Society, ...

3 / 5




4 / 5



Images de taille 263x263

4 / 5



Image originale Ondelette (taille 263x263)

Ondelette (taille 131x131) Suppression (taille 131x131)

5 / 5


Merci pour votre attention

x1

−4−2

02

4 x2−4−2

02 4

−5

0

5

10

15

Robustifier nos analyses de donnees :

un must !

Stephanie Aerts

HEC Ecole de Gestion& Departement de Mathematiques

Universite de Liege

[email protected]

Stephanie Aerts Robustifier nos analyses de donnees : un must !

Robustesse : Quesako ?

But : Detecter de facon automatisee les observations atypiques.




Idee :1. Calculer la moyenne2. Calculer l’ecart-type3. Observation atypique = a plus de 3 ecarts-types de la moyenne.

Ecart type : 6.76

140 160 180 200 220

moy. 165.5



140 160 180 200 220



140 160 180 200 220

140 160 180 200 220

moy. 165.5

moy. 166.8

Ecart type : 6.76 ; Ecart type : 9.70

MAIS la moyenne et l’ecart type ne sont pas robustes.! E!et masquant.


Avec deux variables


Idee : Observation atypique = observation loin de la moyenne

Poid

s

140 160 180 200


Avec deux variables

MAIS il faut une autre notion de distance.

Poid

s

140 160 180 200


Avec deux variables

MAIS il faut une autre notion de distance.

Poid

s

140 160 180 200


Avec deux variables


1. Calculer la moyenne2. Calculer l’ellipsoıde de tolerance3. Observation atypique = en dehors de l’ellipsoıde de tolerance


Avec deux variables


1. Calculer la moyenne2. Calculer l’ellipsoıde de tolerance3. Observation atypique = en dehors de l’ellipsoıde de tolerance

Poid

s

140 160 180 200

MAISLa moyenne et l’ellipsoıde ne sontpas robustes.

! Renversement de direction! E!et masquant.


Detection d’observations atypiques - Algorithme

But : Detecter de maniere objective les observations atypiques.

ALGORITHME1. Calculer la moyenne robuste2. Calculer l’ellipsoıde de tolerance robuste3. Observation atypique = en dehors de l’ellipsoıde robuste.


Detection d’observations atypiques - Algorithme

Etapes 1 & 2 : Comment calculer la moyenne et l’ellipsoıde robustes

de facon objective et automatisee (recette)

de facon generale : pour n’importe quel nombre de variables

de facon e!cace

! ALGORITHME MCD


Algorithme MCD - Idee naıve

Supposons qu’il y ait 5% de contamination.

Idee :Calculer la moyenne et l’ellipsoıde sur unsous-ensemble (95%) de points.Lesquels ?

L’ensemble des points qui minimise levolume de l’ellipsoıde.


Algorithme MCD - Idee naıve

Supposons qu’il y ait 5% de contamination.

Idee :Calculer la moyenne et l’ellipsoıde sur unsous-ensemble (95%) de points.Lesquels ?

L’ensemble des points qui minimise levolume de l’ellipsoıde.

MAISPour n = 100 et 95% : 75 287 520 sous-ensembles a tester !Pour n = 200 et 95% : 6.75 "1020 sous-ensembles a tester !


Algorithme MCD - Alternatives

Re-echantillonnageNe considerer que quelques sous-ensembles au hasardChoisir parmi ceux-la le meilleur en terme de volume! Tres approximatif


Algorithme MCD - Alternatives

Re-echantillonnageNe considerer que quelques sous-ensembles au hasardChoisir parmi ceux-la le meilleur en terme de volume! Tres approximatif

Re-echantillonnage amelioreIl existe des theoremes mathematiquespermettant de ne pas selectionner ces sous-ensembles ”arbitrairement”.


Conclusion

Toute analyse statistique peut etre totalement faussee par lapresence de points atypiques.

Ceux-ci devraient etre detectes de facon objective et automatisee.

Il est necessaire de robustifier les methodes employees.

Comment ?Par des algorithmes alliant

la puissance de nos ordinateurs

des resultats mathematiques


Merci pour votre attention

[email protected]


Pourquoi faut-il détecter les bugs ?




Pour des raisons économiques !!




Pour des raisons de sécurité !!




Pour quels programmes ?!




Méthodologie!

Méthodologie!

•  Approche naïve: tester abondamment

Méthodologie!


•  Meilleure solution: exploration exhaustive

Méthodologie!



•  Recours à des modèles

Méthodologie!



•  Recours à des modèles

•  Regrouper les comportements récurrents

Détection automatique de bugs!


•  Vérification = recherche automatisée de bugs



•  État de l’art:



•  État de l’art: •  Outils existants




•  Coûteux




•  Coûteux

•  Besoin d’experts




•  Coûteux


•  Particularité de nos techniques:




•  Coûteux


•  Particularité de nos techniques: •  Couverture totale




•  Coûteux


•  Particularité de nos techniques: •  Couverture totale

•  Traitent l’infini

Software

Les algorithmes : entre quotidien et créativité par le Prof. Samuel NICOLAY et son équipe, ULg - Département de Mathématique | LIEGE CREATIVE, 25.06.15