S TRUCTURES D E D ONNÉES Introduction à l’algorithmique et aux structures de données 1

1

STRUCTURES DE DONNÉES Introduction à l’algorithmique et aux structures de données

2

A propos du sujetL’organisation du cours

I. Introduction

3

Plan de séance

De quoi est-il question ? Algorithme & SDD : dualité Culture G : histoire et anecdotes Enjeux et principes de l’algorithmique

Session SDD 2011 Programme Méthode pédagogique Quelques repères : cours, TD, TP, … Evaluation, coefficients Ce qui change par rapport à 2010

Equipe pédagogique Pour approfondir : bibliographie

4

Algorithme

But : effectuer une opération complexe Données en entrée Production d’un résultat : données en sortie

Moyen : succession d’opérations élémentaires Méthode systématique, déterministe Implique une façon de structurer les données à

manipuler Equifinalité

Plusieurs méthodes possibles Elles ne se valent pas toutes ENJEU : la

performance !

Intro Sujet Algo & SDD

5

Structure de donnée

Organisation des données à manipuler Deux grandes familles élémentaires

Structures séquentielles Structures arborescentes Plus généralement… les graphes

La structure appelle la méthode de traitement SDD séquentielles : traitement naturellement

itératif SDD arborescentes : traitement naturellement

récursif

Intro Sujet Algo & SDD

6

Etude de cas

Deux exemples issus de l’algorithmique numérique

Arithmétique But : addition et multiplication SDD : Numération de position vs. TFA A vous de jouer avec 23.32 = 72 et 22.33 = 108

Polynômes But : Evaluer un polynôme SDD : Polynôme développé vs. factorisé Problème : factoriser est difficile Solution : Algorithme de Horner

Intro Sujet Algo & SDD

7

A retenir

Algorithme et SDD sont indissociables Se conçoivent ensemble Répondent à un même but

Réaliser une opération complexe De la manière la plus performante possible

Pour approfondir (niveau ontologique) http://www.scriptol.fr/programmation/algorit

hme-definition.php

Intro Sujet Algo & SDD

8

Algorithme : origine étymologique

Intro Sujet Culture G

Al Khawarizmi, 783-850 Le Diophante perse Chiffres indiens

Œuvre : ..Al-jabr.. (825) Résolution d’équations Méthode

systématique Condition d’arrêt Structure algébrique

9

Algorithme : l’archétype antique

Intro Sujet Culture G

Euclide, 325-265 av. JC

Les Eléments (livre 7) Algorithme d’Euclide

Calcul du PGCD Intuition géométrique Simplicité : 1 ligne Efficacité : O(n) Généricité : entiers,

polynômes, etc.

10

Algorithme : l’archétype antique

En langage algorithmiqueExemple de traduction en C

Intro Sujet Méthode

unsigned gcd(unsigned a, unsigned b)

{

if (b == 0) return a;

else return gcd(b, a % b);

// ou // return b ? gcd(b, a % b) : a;

}

Elaborer(schématiser, tâtonner,

intuiter)

Spécifier(langage algorithmique)

Implémenter(langage de

programmation)

11

Et bien avant Euclide

Intro Sujet Culture G

Babyloniens 2000 à 500 av. JC Algorithmes pratiques

Astronomie Economie

Mathématiques Numération sexagésimale Triplets pythagoriciens

1000 ans avant Pythagore Résolution d’équations Elévation à la puissance

12

Et bien avant Euclide

Intro Sujet Culture G

Os d’Ishango ~20000 av. JC De nature

arithmétique Associé à un procédé Lequel ?

13

L’art d’opérer avec efficacité

Rappel de la motivation historique Le calcul : astronomie, économie, mathématique Ishango, les babyloniens, Euclide et les autres

Enjeu : la performance (minimiser la complexité) Temporelle, spatiale Equifinalité, optimalité difficile à prouver Nombreux problèmes ouverts L’algorithmique est un domaine de recherche très actif

Plutôt un art qu’une science Mais un art scientifique A rapprocher des arts tactiques en général Astuce et sagacité : une anecdote : Karatsuba

Intro Sujet Enjeu

14

Une anecdote contemporaine

Intro Sujet Culture G

Kolmogorov, 1903-1987 Monstre sacré Conjecture de 1952 Multiplication ≥ O(n2) Conférence de 1960

Karatsuba, 1937-2008 Simple étudiant Réfutation : O(n1,58) Nouveau paradigme

« diviser pour régner »

15

Multiplication de deux nombres en numération de position Nombres de 2n chiffres Décomposition en deux moitiés

Représentation algébrique de la multiplication naïve

Les multiplications sont plus coûteuses que les additions Version naïve : 4 multiplications intermédiaires

Forme équivalente de Karatsuba Complexification

Mémorisation et réutilisation de résultats intermédiaires Ajout de 3 opérations additives supplémentaires

On tombe à 3 multiplications ! Application récursive du procédé : O(n2) O(n1,58)

Une anecdote contemporaine

Intro Sujet Culture G

nM m

nM m

A A b A

B B b B

2n n n nM m M m M M M m m M m mAB A b A B b B A B b A B A B b A B

2n nM M M m M m M M m m m mAB A B b A A B B A B A B b A B