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 :
Cours & Tutoriels
CPGE
Classes Préparatoires
152 cours
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 ..
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.
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).
MP, PSI et la TSI
Les graphes
graphe orienté
graphe non orienté
algorithmes sur les graphes
graphe pondéré
théorème de la poignée de main
Les graphes : Introduction et notions fondamentales
De nombreux problèmes rencontrés en mathématiques, en informatique et en ingénierie ont une caractéristique commune : ils mettent en jeu des objets entre lesquels existent des relations. Un graphe ne cherche pas à modéliser la nature des objets, mais la manière dont ils sont reliés.
MP, PSI et la TSI
Les graphes
Algorithmes Gloutons
graphe orienté
graphe non orienté
algorithmes gloutons
coloration graphes
Coloration des graphes
La coloration des graphes consiste à attribuer des couleurs à certains éléments d'un graphe (sommets ou arêtes) en respectant des contraintes d'adjacence.
MP, PSI et la TSI
Les graphes
Algorithmes Gloutons
graphe orienté
graphe non orienté
algorithmes gloutons
Algorithme A*
L'algorithme A* ne se contente pas de regarder le chemin parcouru ; il projette également l'effort restant. C'est un algorithme best-first search (recherche du meilleur d'abord).
MPSI, PCSI et la PTSI
MP, PSI et la TSI
Diviser pour régner
récursivité
Diviser pour régner
Recherche linéaire
recherche séquentielle
algorithmes de recherche
Recherche linéaire (Linear Search)
La recherche linéaire (ou recherche séquentielle) est l'algorithme de recherche le plus simple. Elle consiste à parcourir un tableau élément par élément jusqu'à trouver la valeur recherchée ou atteindre la fin du tableau.
MP, PSI et la TSI
Analyse des algorithmes
Diviser pour régner
Algorithmes de tri
Exercices java
Exercices langage c
Exercices python
algorithmes de tri
tri sélection
tri insertion
tri bulles
tri rapide
Algorithme de tri rapide
Tri rapide Le tri rapide (Quicksort) est un algorithme de tri basé sur le paradigme Diviser pour régner, proposé par C.A.R. Hoare en 1959. C'est l'un des algorithmes de tri les plus utilisés en pratique grâce à ses excellentes performances en moyenne.