Algorithmique et Structure de données

Algorithmique et Structure de donnéeswww.polytech.unice.fr/~vg

Granet Vincent – vg@unice.fr

Polytech – Peip2 – S4/2021

1/50

2/50

Algorithmique et Structure de donnéesSommaire

Sommaire

1 Sommaire

2 Bibliographie

3 Récursivté

4 Type Abstrait Algébrique

3 Tri

4 Arbres

2/50

3/50

Algorithmique et Structure de donnéesBibliographie

Bibliographie

Vincent Granet.Algorithmique et programmation en Java.Dunod, 4e édition, 2014.

Vincent Granet et Jean-Pierre Regourd.Aide-Mémoire de Java.Dunod, 4e édition, 2015.

D. E. Knuth.Sorting and Searching.The Art of Computer Programming, vol. 3. Addison Wesley, 1973.

http://users.polytech.unice.fr/~vg/index-peip2.html.

3/50

4/50

Algorithmique et Structure de donnéesRécursivté

Récursivité

4/50

5/50

Algorithmique et Structure de donnéesRécursivté

Définition

La définition d’un terme est dite récursive lorsque le terme estdécrit à partir de lui-même.En programmation :

récursivité des actionsrécursivité des objets

5/50

6/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des actions

Récursivité des actions

procédure ou fonction récursive => appel récursif

P = C(Ei ,P)

Finitude : l’appel récursif d’une fonction ou d’une procéduredevra toujours apparaître dans un énoncé conditionnel ets’appliquer à un sous-ensemble du problème à résoudre.

Px = si B alors C(Ei ,Px ′) finsi

ou bienPx = C(Ei , si B alors Px ′ finsi)

où x ′ est une partie de x

6/50

7/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des actions

Exemple : Fibonacci

fib(1) = 1fib(2) = 1fib(n) = fib(n−1) + fib(n−2),∀n > 2

{Antécédent : n>0}{Rôle : calcule fib(n)= fib(n−1) + fib(n−2), pour n > 2

et avec fib(1) = 1 et fib(2) = 1}fonction fibonacci(donnée n : naturel) : naturel

si n62 alors rendre 1sinon rendre fibonacci(n−1) + fibonacci(n−2)

finsifinfonc {fibonacci}

7/50

8/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des actions

Récursivité directe et croisée

procédure P... P ...

finproc {P}

Mais une routine P peut faire appel à une ou plusieurs autres routinesqui, en dernier lieu, font appel à la routine P initiale. On parle alorsde récursivité indirecte. Lorsque seulement deux routines sont misesen jeu, on parle de récursivité croisée :procédure P1

... P2 ...finproc {P1}

procédure P2... P1 ...

finproc {P2}

8/50

9/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des actions

Récursivité terminale

La récursivité est terminale, c’est-à-dire lorsque la dernière instructionde la routine est l’appel récursif.

P = si B alors E ;P finsi

P = E ; si B alors P finsi

sont équivalents à :

P = initialisation tantque B faire E fintantque

9/50

10/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des actions

Récursivité vs Itérativité

il existe toujours une écriture itérativepb d’efficacité - coût des appels récursifs - profondeur de larécursivitéfibonacci(50) = 25 milliards d’appels recursifs, bien plus efficacede façon itérativemais l’écriture récursive est plus concise et élégante

10/50

11/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des objets

Récursivité des objets

À l’instar de la récursivité des actions, un objet récursif est unobjet qui contient un ou plusieurs composants du même type quelui.La récursivité des objets peut être également indirecte.

11/50

12/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des objets

Exemple

classe Arbre Généalogiqueprénom type chaîne de caractèresmère, père type Arbre Généalogique

finclasse {Arbre Généalogique}

Conceptuellement, une telle déclaration décrit une structure infinie,mais en général les langages de programmation ne permettent pascette forme d’auto-inclusion des objets. Contrairement à la récursivitédes actions, celle des objets ne crée pas « automatiquement » uneinfinité d’incarnations d’objets. C’est au programmeur de créerexplicitement chacune de ces incarnations et de les relier entre elles.

12/50

13/50

Algorithmique et Structure de donnéesRécursivté

Récursivité des objets

en Java

class ArbreGénéalogique {String prénom;// définition de l’ascendanceArbreGénéalogique mère, père;// le constructeurArbreGénéalogique(String s) {

prénom=s;}

} // ArbreGénéalogique

Cette définition est possible en Java car les attributs mère et pèresont des références à des objets de type ArbreGénéalogique et nonpas l’objet lui-même.Chacun des ascendants, lorsqu’il est connu, est créé grâce àl’opérateur new et est relié à sa propre ascendance par l’intermédiairedes références.

13/50

14/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Type Abstrait Algébrique

14/50

15/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Introduction

structure de données est désigne une composition de donnéesunies par une même sémantique.cette sémantique ne se réduit pas à celle des types (élémentairesou structurés) des langages de programmation utilisésune structure de données peut être modélisée en termes dedonnées abstraites munies d’opérations abstraites.et décrite de façon formelle par un type abstrait algébrique defaçon indépendante de tout langage de programmation

15/50

16/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

Type abstrait algébrique

Un type abstrait est décrit par sa signature qui comprend :une déclaration des ensembles définis et utilisés ;une description fonctionnelle des opérations ;une description axiomatique de la sémantique des opérations.

16/50

17/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

Exemple : Ensemble

On souhaite décrire la notion d’ensemble dont les éléments sont detype quelconque.

Déclaration des ensembles :Ensemble utilise E, booléen.

Constante :ensemble vide : ∅ ∈ Ensemble

17/50

18/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

Description fonctionnelle

La définition fonctionnelle présente les signatures des opérations dutype abstrait.

est-vide? : Ensemble → booléen∈ : Ensemble×E → booléenajouter : Ensemble×E → Ensembleenlever : Ensemble×E → Ensembleunion : Ensemble×Ensemble → Ensemble

18/50

19/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

Description axiomatique

La définition axiomatique décrit la sémantique des opérations du typeabstrait.

1 est-vide?(∅) = vrai2 ∀x ∈ E ,∀e ∈ Ensemble,est-vide?(ajouter(e,x)) = faux3 ∀x ∈ E ,x ∈ ∅= faux4 ∀x ,y ∈ E ,∀e ∈ Ensemble,

x = y ⇒ y ∈ ajouter(e,x) = vraix 6= y ⇒ y ∈ ajouter(e,x) = y ∈ e

5 ∀x ,y ∈ E ,∀e ∈ Ensemble,x = y ⇒ y ∈ enlever(e,x) = fauxx 6= y ⇒ y ∈ enlever(e,x) = y ∈ e

6 ∀x ∈ E ,∀e ∈ Ensemble,x 6∈ e⇒ @e′ ∈ Ensemble, e′ = enlever(e,x)

7 x ∈ union(e,e′)⇒ x ∈ e ou x ∈ e′

19/50

20/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

implémentation d’un type abstrait

façon dont le type abstrait est programmé dans un langageparticulier.doit respecter la définition formelle du type abstrait pour êtrevalide.consiste donc à choisir les structures de données concrètes

et de rédiger le corps des différentes fonctions qui manipuleront cestypes.

20/50

21/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Définition

implémentation Java

En Java, la notion d’interface représente la définition fonctionnelled’une type abstrait :

public interface Ensemble<E> {public boolean estVide();public boolean dans(E x);public void ajouter(E x);public void enlever(E x) throws ExceptionÉlémentAbsent;public Ensemble<E> union(Ensemble<E> x);

}

21/50

22/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Implémentation

implémentation JavaLa mise en œuvre des opérations dépendra des types de donnéeschoisis pour implémenter le type abstrait (arbre, une liste, etc.)

public class EnsembleListe<E> implements Ensemble<E> {

Liste<E> l;

public EnsembleListe() {// Le constructeur...

}public boolean estVide() { ... }public boolean dans(E x) { ... }public void ajouter(E x) { ... }public void enlever(E x) throws ExceptionÉlémentAbsent {

...}...

} // fin classe EnsembleListe

22/50

23/50

Algorithmique et Structure de donnéesType Abstrait Algébrique

Utilisation

Utilisation

l’utilisation du type abstrait devra se faire exclusivement parl’intermédiaire des opérations qui lui sont associées indépendament deson implémentation.

Ensemble<Integer> e1 = new EnsembleListe<Integer>();Ensemble<Rectangle> e2 = new EnsembleListe<Rectangle>();Ensemble<Ensemble<String>> e3 =

new EnsembleListe<Ensemble<String>>();Ensemble e4 = new EnsembleListe();

e1.ajouter(123);e2.ajouter(new Rectangle(2,5));e3.ajouter(new EnsembleListe<String>());e4.ajouter(123.45);

23/50