Somme des feuilles, arbre complet, miroir d'un arbre
Dans ce TD, nous allons implémenter des arbres binaires en Python. On choisit de représenter l'arbre vide par la liste vide, et un arbre de racine étiquetée par e et fils fg et fd par la liste [e, fg, fd]
Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.
Un invariant doit satisfaire trois propriétés : initialisation, maintenance et terminaison. Ces trois étapes constituent une preuve par induction que l'algorithme produit le résultat attendu.
Le tri par fusion est l'un des algorithmes de tri les plus populaires et les plus efficaces. Et il est basé sur le paradigme Diviser pour régner.
Un algorithme de tri est utilisé pour réorganiser les éléments d'un tableau ou d'une liste donnée selon un ordre (croissant, décroissant) en utilisant l'un des opérateurs de comparaison ().
Un graphe G=(S,A) est dit connecté, si pour tout couple de sommets (u, v) il existe un chemin reliant u et v
Ecrire une fonction longueur_chaine(ch) qui recoit en argument une chaine de caractères ch, et qui retourne sa taille.
Une société souhaite modéliser son système de gestion des ventes et a donc élaboré le modèle relationnel suivant :
L’idée est simple : pour vérifier l’existence d’un cycle dans un graphe, il suffit de déterminer s’il existe, pour un sommet v, un chemin qui part de v et y revient ; si un tel chemin existe, alors le graphe contient un cycle.
Etant donné deux tableaux triés A et B de taille n chacun, le problème est de trouver la médiane du tableau obtenu après la fusion des deux tableaux (c'est-à-dire un tableau de longueur 2n).
C'est la deuxième série d'exercices corrigés sur les matrices, nous continuons à effectuer des opérations intéressantes de calcul matriciel. Tous les exercices sont résolus en utilisant la programmation Python, Java et C