STRUCTURES DE DONNÉES ET ALGORITHMES FONDAMENTAUX

3 de 87 Algorithmesetstructuresdedonnées Laplupartdesbonsalgorithmesfonctionnentgrâceàuneméthode astucieusepourorganiserlesdonnées Nousallonsétudierquatre

Algorithmique et Structures de Données

Dans le premier chapitre, des notions de base sur la structure globale d’un algorithme sont données, ainsi que les différentes parties qui le composent suivie par les instructions de base les plus élémentaires Le deuxième chapitre décrit en détails les différentes structures de contrôles ( boucles ) qui

Structures de données et algorithmes fondamentaux

données algorithme résultat Pour illustrer ces notions de “problème” et d’“instance”, prenons l’exemple d’un système de navigation GPS : —le problème typique à résoudre serait, étant données deux villes et un réseau routier, de trouver un chemin le plus court possible entre ces deux villes dans le réseau donné;

STRUCTURES DE DONNEES ET ALGORITHMES

3 6 la structure de tableau 46 3 7 la structure de record 48 3 8 la structure de suite 51 chapitre 4 : structures de donnÉes dynamiques 53 4 1 types de donnees recursifs 53 4 2 pointeurs 55 4 3 listes lineaires 57 chapitre 5 : structures de donnees elaborees 62 5 1 type abstrait et structure de donnee 62 5 2 structures lineaires 63

Algorithmique et Structures de Données

1 Structure de données Chapitre 1 Structure de données Les ordinateurs sont là pour nous affranchir des tâches fastidieuses ou répétitives Mais les répétitions se retrouvent même dans nos programmes Ainsi, nous sommes souvent amenés à rassembler une collection de données dans un tableau Nous savons déjà utiliser les tableaux

STRUCTURES DE DONNÉES ET ALGORITHMES FONDAMENTAUX

Nouvelle structure de données : Liste Chaînée Introduction aux Types de Données Abstraits (TAD) TAD=Algorithme Structure = Implantation Plusieurs exemples de TAD (Ensemble, Liste Itérative, Liste Récursive, Pile, File) Pour aller plus loin : livre « Types de Données et Algorithmes », par C Froidevaux, M-C Gaudel et M Soria

STRUCTURES DE DONNÉES - IGM

Structures de données Algorithme Structures de données et algorithmes, InterÉditions, 1987 struct_1 PDF Author: mac

Algorithmique et structure de données 2

Faculté des Mathématiques et de l’informatique Département d’informatique Algorithmique et structure de données 2 Chapitre 1 : Les sous-programmes : Fonctions et Procédures Cours Conçu par Dr Omar TALBI Version 1 0 2019-2020 Public concerné: -Etudiants 1ère LMD –MI Année universitaire 2019-2020

Algorithmique et Programmation 2 Structures de données en python

Notion d'algorithme Exemple : Pour le problème de recherche un élément dans un tableau non trié Si le nombre d'éléments du tableau est n, la complexité de la recherche dans le pire des cas est O(n) car il faut parcourir le tableau et tester tous ses éléments Exemple graphique de fonction f et de fonction

ALGORITHMES FONDAMENTAUX

Algorithmique - Programmation - Langages 2

(APL2)

APL2 - Erwan Kerrien2PLAN DU MODULE

CM#1 (rappels +)

Complexité (principe de mesure, ordre polynomial) ; Tableaux (rappels, impact sur la mémoire) CM#2 Type abstrait de données (ADT, exemple de l'ensemble) ; Listes chaînées (pile, file, liste circulaire, liste doublement chaînée ; algorithmes de base)CM#3

Arbres binaires

; Tableaux associatifs ; Algorithmes de baseTD x7

Exercices sur ces notions

TP x9

Implantation en C

; Initiation au C

APL2 - Erwan Kerrien3PRENONS UN PEU DE RECUL

Pourquoi une structure de données ?Stockage et manipulation de nombreuses données

Notion générique d'ensemble

• Accéder à un élément • Ajouter un élément • Supprimer un élément • Tester l'appartenance d'un élément • Définir l'ensemble vide • Compter le nombre d'éléments ... (on peut ajouter les opérations d'union, intersection, sous-ensemble...) → Analyse centrée sur les opérations : Type Abstrait de Données

APL2 - Erwan Kerrien4TYPE ABSTRAIT DE DONNÉES

Changement de focalisation

Implantation (représentation) → opérations

Deux éléments de définition

Signature : nom (sorte), sortes utilisées, ensemble de valeurs valides, opérations

Préconditions/axiomes

APL2 - Erwan Kerrien5BOOLÉEN COMMME TAD (PROPOSITION)

Signature

Sorte : Booléen

Utilise

: (nil)

Opérations

Vrai : → Booléen

Faux: → Booléen

¬ (not)

: Booléen → Booléen ˄ (and): Booléen x Booléen → Booléen ˅ (or): Booléen x Booléen → BooléenPréconditions/axiomes

¬ Vrai = Faux

¬¬b = b

(b=Vrai ˅ b=Faux) = Vrai (b ˄ Faux) = Faux (b ˅ Vrai) = Vrai

¬ (a ˄ b) = ¬a ˅ ¬b

Commutativité

a ˄ b = b ˄ a a ˅ b = b ˅ a

Distributivité

a ˄ (b ˅ c) = (a˄b) ˅ (a˄c)

Représentation

? Peut être quelconque (0/1, 'V'/'F', " VRAI »/" FAUX », 3/-18...)

APL2 - Erwan Kerrien6UTILISATION DU TAD

Rappel des opérations/valeurs

Vrai, Faux, ¬ (not), ˄ (and), ˅ (or)

Définition de nouvelles fonctions (algorithmes)

Fonction xor

Entrées : a, b : Booléen Sortie

: Booléen Début

Renvoyer (a ˅ b) ˄ ¬(a ˄ b)

Fin (a ˅ b) ˄ ¬(a ˄ b)= et(ou(a,b),not(et(a,b))Fonction nand

Entrées

: a, b : Booléen Sortie : Booléen Début

Renvoyer ¬(a ˄ b)

Fin

¬(a ˄ b) = not(and(a,b))

APL2 - Erwan Kerrien7INTÉRÊT D'UN TAD

Séparer algorithme et programmation

Algorithme décrit en utilisant les opérations définies pour le TAD Programmation implante ces opérations, puis l'algorithme

Conception modulaire de programmes

Écrire plein de petites fonctions est bien

Écrire plein de petites fonctions est bien (répétition voulue)

Bon pour

→ conception et réalisation de tests unitaires → maintenance du code → réutilisation du code → identification et correction de bugs → structuration de la documentation APL2 - Erwan Kerrien8EXEMPLE IMPLANTATION BOOLÉEN

Fonction Vrai

Sortie : Booléen Début

Renvoyer -18

Fin

Fonction Faux

Sortie

: Booléen Début

Renvoyer 3

Fin

Fonction not

Entrée

: b : Booléen Sortie : Booléen Début

Si b = Faux() alors

Renvoyer Vrai()

Sinon

Renvoyer Faux()

FinSi

FinFonction and

Entrée

: a,b : Booléen Sortie : Booléen Début

Si a=Faux() alors

Renvoyer Faux()

Sinon

Si b=Faux() alors

Renvoyer Faux()

Sinon

Renvoyer Vrai()

Finsi Finsi Fin

Fonction or

Entrée

: a,b : Booléen Sortie : Booléen Début

Si a=Vrai() alors

Renvoyer Vrai()

Sinon

Si b=Vrai() alors

Renvoyer Vrai()

Sinon

Renvoyer Faux()

Finsi FinSi Fin

APL2 - Erwan Kerrien9TAD ENSEMBLE

Signature

Sorte : Ensemble

Utilise

: Élément, Booléen, Entier

Opérations

ensemble_vide: → Ensemble

EstVide

: Ensemble → Booléen

Ajouter

: Ensemble x Élément → Ensemble

Supprimer

: Ensemble x Élément → Ensemble

EstDans

: Ensemble x Élément → Booléen Taille: Ensemble → EntierAxiomes (E:Élément, S:Ensemble)

EstVide(ensemble_vide) = Vrai

Si Taille(S) > 0 alors

EstVide(S) = Faux

Sinon S=ensemble_vide

EstDans(ensemble_vide, E)=Faux

EstDans(Ajouter(S,E),E) = Vrai

Si EstDans(S,E)=Faux alors

Taille(Ajouter(S,E)) = Taille(S)+1

Si EstDans(S,E)=Vrai alors

Taille(Supprimer(S,E)) = Taille(S)-1

Si EstDans(S,E)=Faux alors

Taille(Supprimer(S,E)) = Taille(S)

Cas sans répétition (cas avec répétition = multi-ensemble)

EstDans(Supprimer(S,E),E) = Faux

Si EstDans(S,E)=Vrai alors

Taille(Ajouter(S,E)) = Taille(S)

APL2 - Erwan Kerrien10TAD ENSEMBLE

Signature

Sorte : Ensemble

Utilise

: Élément, Booléen, Entier

Opérations

ensemble_vide : → EnsembleEstVide : Ensemble → Booléen

Ajouter

: Ensemble x Élément → Ensemble

Supprimer

: Ensemble x Élément → Ensemble

EstDans

: Ensemble x Élément → Booléen

Taille: Ensemble → Entier

Problème

Cette définition de permet pas d'accéder à un élément !Par exemple : comment lister les éléments pour les afficher ? (fonction Afficher(Ensemble))

APL2 - Erwan Kerrien11TAD LISTE ITÉRATIVE

Liste

Ensemble d'éléments rangés

Rangé ≠ trié → Rangé = chaque élément a un rang

Liste itérative : rang=entierSignature

Sorte : ListeIter

Utilise

: Élément, Booléen, Entier

Opérations

liste_vide: → ListeIter

EstVide: ListeIter → Booléen

Contenu

: ListeIter x Entier → Élément

Ajouter

: ListerIter x Entier x Élément → Ensemble

Supprimer: ListeIter x Entier → ListeIter

EstDans

: ListeIter x Élément → Booléen Taille: ListeIter → EntierProcédure Afficher

Entrée

: L : ListeIter Variables : i,T : entier Début

T ← Taille(L)

Pour i allant de 0 à T-1 faire

Afficher(Contenu(L,i))

FinPour

Fin APL2 - Erwan Kerrien12COMMENT FAIRE AUTREMENT ?Brique de base : cellule

Information

(ex : entier)

Adresse (pointeur)

de la cellule suivante

Problème

: données contiguësUtiliser des cases dispersées en mémoire

APL2 - Erwan Kerrien13

CRÉATION

Ensemble d'entiers : [3,2,0,7,8]

3 2

078ø

Nouvelle structure de données : liste chaînéeItérer sur :Allocation celluleRemplissage celluleMise à jour adresse cellule

[PDF] STRUCTURES DE DONNÉES ET ALGORITHMES FONDAMENTAUX

ALGORITHMES FONDAMENTAUX

Algorithmique - Programmation - Langages 2

APL2 - Erwan Kerrien2PLAN DU MODULE

CM#1 (rappels +)

Arbres binaires

Exercices sur ces notions

Implantation en C

APL2 - Erwan Kerrien3PRENONS UN PEU DE RECUL

Notion générique d'ensemble

APL2 - Erwan Kerrien4TYPE ABSTRAIT DE DONNÉES

Changement de focalisation

Deux éléments de définition

Préconditions/axiomes

Signature

Sorte : Booléen

Utilise

Opérations

Vrai : → Booléen

Faux: → Booléen

¬ (not)

¬ Vrai = Faux

¬¬b = b

¬ (a ˄ b) = ¬a ˅ ¬b

Commutativité

Distributivité

Représentation

APL2 - Erwan Kerrien6UTILISATION DU TAD

Rappel des opérations/valeurs

Vrai, Faux, ¬ (not), ˄ (and), ˅ (or)

Fonction xor

Entrées : a, b : Booléen Sortie

Renvoyer (a ˅ b) ˄ ¬(a ˄ b)

Entrées

Renvoyer ¬(a ˄ b)

¬(a ˄ b) = not(and(a,b))

APL2 - Erwan Kerrien7INTÉRÊT D'UN TAD

Séparer algorithme et programmation

Conception modulaire de programmes

Écrire plein de petites fonctions est bien

Bon pour

Fonction Vrai

Sortie : Booléen Début

Renvoyer -18

Fonction Faux

Sortie

Renvoyer 3

Fonction not

Entrée

Si b = Faux() alors

Renvoyer Vrai()

Renvoyer Faux()

FinFonction and

Entrée

Si a=Faux() alors

Renvoyer Faux()

Si b=Faux() alors

Renvoyer Faux()

Renvoyer Vrai()

Fonction or

Entrée

Si a=Vrai() alors

Renvoyer Vrai()

Si b=Vrai() alors

Renvoyer Vrai()

Renvoyer Faux()

APL2 - Erwan Kerrien9TAD ENSEMBLE

Signature

Sorte : Ensemble

Utilise

Opérations

EstVide

Ajouter

Supprimer

EstDans

EstVide(ensemble_vide) = Vrai

Si Taille(S) > 0 alors

EstVide(S) = Faux

Sinon S=ensemble_vide

EstDans(ensemble_vide, E)=Faux