Arbres binaires de recherche
Définition Un arbre binaire de recherche (ABR) (binary search tree – BST) est un arbre binaire tel que : les clefs des nœuds doivent être ordonnables (il doit exister entre elles une relation d’ordre) pour chacun...
Catégorie : Algorithmique
Alignements
L’objectif de l’exercice est de trouver tous les alignements de éléments dans un tableau de dimension lignes par colonnes. Résoudre un tel problème est notamment très utile pour évaluer l’état d’une grille dans des jeux tels...
Parcours d’arbres binaires
Les arbres binaires sont des structures de données hiérarchiques (ses nœuds sont liés par des relations père-fils) et récursives. On peut implémenter un arbre binaire et ses nœuds en Python par les classes Arbre et...
Algorithmes pour le Bac
Programme de Première Compétences préalables Lire et modifier les éléments d’un tableau grâce à leurs index, Utiliser des tableaux de tableaux pour représenter des matrices : notation a[i][j], Itérer sur les éléments d’un tableau, Itérer sur...
Images : exercices
Conversion image→ascii Écrire un programme qui converti une image en caractères ascii. Indications : télécharger l’image ci-contre, utiliser la bibliothèque PIL pour la convertir en niveaux de gris, puis en obtenir une liste de valeurs de...
Récursivité
Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème. L’approche récursive est un des concepts de base en informatique. Algorithme itératif vs récursif On...
Exercices récursivité
Analyse d’une fonction récursive Soit le programme Python suivant : def f(a, b) : « » » a et b sont deux entiers naturels non nuls « » » if b == 1 : return a return a + f(a,...
Algorithmes gloutons
Optimisation Un problème d’optimisation est un problème algorithmique dans lequel l’objectif est de trouver la « meilleure » solution (selon un critère donné) parmi un ensemble de solutions également valides mais potentiellement moins bonnes. Le contexte d’un problème...
Recherche dichotomique
Lorsque l’on souhaite rechercher une occurrence dans un tableau non trié, il faut, dans le pire des cas, le parcourir jusqu’au bout. La complexité est d’ordre ( étant la taille du tableau). Si le tableau est...
Programmation dynamique
La programmation dynamique est une méthode algorithmique destinée à résoudre des problèmes d’optimisation. Elle consiste à faire en sorte de ne pas calculer plusieurs fois la même chose. Pour cela, les résultats intermédiaires sont momentanément stockés...