DS MPSI - Gestion des commandes clients - Système de e-commerce
On modélise des commandes passées par des clients. Les données sont représentées par un dictionnaire :
DS MPSI - Réseau de dépôts - Gestion des liaisons et stocks
On modélise un réseau de dépôts et de liaisons entre eux. Un réseau est représenté par un dictionnaire :
DS MPSI - Championnat de football - Analyse des résultats
On modélise les résultats d'un championnat de football. Les données sont représentées par un dictionnaire :
DS MPSI - Gestion des emprunts de livres
On modélise des emprunts de livres effectués par des élèves. Les données sont représentées par un dictionnaire :
MP, PSI et la TSI
Les arbres
arbres binaires
arbres binaires complets
Les arbres binaires
ArbreAVIL
ArbreEquilibre
DS MP - Arbres binaires de recherche équilibrés (AVL)
On souhaite implémenter une structure de données permettant de gérer un dictionnaire de contacts,où chaque contact est identifié par un entier strictement positif (par exemple un identifiant unique).
MP, PSI et la TSI
Les arbres
arbres
arbres binaires
Les arbres binaires
CompressionDonnees
CodageHuffman
DS MP - Codage de Huffman - Compression de données
Lorsqu'on enregistre des données — qu'il s'agisse d'un texte, d'une image ou de tout autre contenu — on stocke en réalité une suite de symboles (caractères, pixels, etc.). Traditionnellement, chaque symbole est représenté par un nombre fixe de bits : par exemple, en ASCII, un caractère occupe 8 bits ..
Analyse des algorithmes
InvariantDeBoucle
Induction
Terminaison
VarianteDeBoucle
PreuveDAlgorithme
CorrectionPartielle
Preuve d'algorithmes
La preuve d'algorithme est une démonstration mathématique qu'un algorithme produit le résultat attendu pour toutes les entrées valides et qu'il se termine effectivement.
MP, PSI et la TSI
Analyse des algorithmes
analyse des algorithmes
AnalyseAsymptotique
ComplexitéSpatiale
AnalyseDAlgorithmes
Récursion
RelationDeRécurrence
ThéorèmeMaître
DiviserPourRégner
PileDAppels
Analyse des algorithmes : Analyse des fonctions récursives
L'analyse des fonctions récursives repose sur l'établissement et la résolution de relations de récurrence. Cas de base : condition d'arrêt de la récursion. Relation de récurrence : exprime \(T(n)\) en fonction de \(T\) pour des entrées plus petites.
MP, PSI et la TSI
Analyse des algorithmes
ComplexitéTemporelle
AnalyseDAlgorithmes
ComptageDePas
InstructionsÉlémentaires
RègleMaximale
Complexité des algorithmes : Méthode de comptage des pas
La méthode de comptage des pas est une technique systématique pour analyser la complexité temporelle d'un algorithme : On identifie les instructions élémentaires et on compte leur nombre d'exécutions.
MP, PSI et la TSI
Analyse des algorithmes
ComplexitéTemporelle
ComplexitéSpatiale
CompromisTempsMémoire
AnalyseDAlgorithmes
Mémoïsation
Complexité temporelle et spatiale
Lorsqu'on analyse un algorithme, on s'intéresse à deux ressources fondamentales : le temps et l'espace mémoire. Ces deux mesures permettent d'évaluer l'efficacité d'un algorithme et de comparer différentes solutions pour un même problème.
Analyse des algorithmes
PreuveDExactitude
Terminaison
VarianteDeBoucle
DécroissanceStricte
BorneInférieure
Les variantes de boucle
Une variante de boucle (ou fonction de terminaison) est une expression associée à une boucle qui possède les propriétés suivantes : Elle est évaluée à une valeur entière positive ou nulle. Sa valeur décroît strictement à chaque itération de la boucle. Elle fournit une borne inférieure garantissant que la boucle ne peut pas s'exécuter indéfiniment.
MP, PSI et la TSI
Les graphes
arbres
arbres binaires
graphe orienté
graphe non orienté
plus cours chemin dans un graphe
algorithmes sur les graphes
graphe pondéré
Chaîne
Chemin
Circuit
Forte connexité
Composante connexe
Diamètre
Point d'articulation
Graphe biparti
Les graphes : Chemins, cycles et connexité
Chemin Un chemin est une chaîne sans répétition de sommets. Chemin élémentaire : Aucun sommet n'est répété (implique qu'aucune arête n'est répétée).