Structures de données et complexité
Notions de Complexité
Notion d'algorithme Algorithme : ensemble d'actions de
traitement l'information échanger, recevoir, ranger, compter…
Agit sur des données initiales ("entrées") Produit des résultats ("sorties")
Programmation d'un algorithme: Expression dans un langage de
programmation Styles de programmation (itérative,
récursive…)
Complexité d’un algorithme
Mesurer l’efficacité d’un algorithme
Coût en nombre d’opérations: Fonction du nombre n de données (mots mémoire ou
bits) à traiter
Algorithme polynomial : O(n 2) , O(n 3), … opérations
Parcours d’une matrice carrée n x n, produit de 2 matrices, ...
Algorithme exponentiel : O(e n) Très lent en pratique
Coût moyen : pas facile à calculer hypothèses probabilistes sur la répartition des données
Complexité : coût maximal, pire des cas
Structures de données
A quoi ça sert ?!?
Savoir ranger les données Tableaux limités Agencer les données d’une
certaine manière Ex: Processus physiques de type flux…
Les PILES - Stack (LIFO)
Last In – First Out Principe de la pile d’assiette
Opérations sur les piles
Empiler(e): ajouter e en haut de la pile
Dépiler(): extraire l’élément au sommet
Vide(): vider la pile EstVide(): teste si la pile est vide EstPleine(): teste si la pile est pleine
Exemple d’utilisation
Notation postfixée des expressions arithmétiques 2+5*6 256*-
Détermination de palindrome, etc…
Implémentation par tableau
Empile
Empile
Dépile
Les FILES (FIFO)
First In – First Out Principe de la File d’attente
Opérations sur les files
Enfiler(e): ajouter e en haut de la file
Défiler(): extraire l’élément en bas Vide(): vider la file EstVide(): teste si la file est vide EstPleine(): teste si la file est
pleine
Exemple d’utilisation
File d’attente utilisateur ou processus
Base de données Etc…
Implémentation par tableau
Enfile
Empile
Défile
Vision circulaire de la file
Test pour plein: Fin = Début
Test pour vide: Fin = Début
Comment faire ? Variable
booléenne
Les Listes chaînées
Inconvénients des précédents: nombres limités d’éléments
Principe: le jeu de piste; pointeur vers l’élément suivant
Opérations sur les Listes
Ajoute(e): ajouter e au bout de la liste
Récupère(n): extraire l’élément à la nième position
Vide(): vider la liste EstVide(): teste si la liste est vide…etc…
Exemple d’utilisation
On peut implémenter des piles, files, tableaux et bien d’autres choses avec des listes.
Les Listes doublement chaînées
Inconvénients des listes simplement chaînées: un seul sens de parcours
Principe: on rajoute un sens; pointeur vers l’élément suivant et l’élément précédent
Arbres Binaires
Structures arborescentes
Utilisations: Langage naturel Algorithme de recherche Jeu, echecs
Possibilités pour le prochain cours Théorie des graphes Sécurité informatique (Net & Réseaux) Base de donnée et + si temps libre Théorie de la complexité avancée Programmation objet Intelligence artificielle distribuée Intelligence artificielle « Logique » Vie Artificielle et Programmation génétique