2ème année prépas scientifiques (Spé)
Comprendre le principe du parcours en largeur d'un arbre binaire, son implémentation itérative à l'aide d'une file, et savoir le coder en Python et en C.
Un groupe de spéléologues souhaite explorer un réseau de grottes souterraines. Le réseau est modélisé par un graphe où chaque nœud représente une salle et chaque arête un tunnel reliant deux salles.
Une entreprise développe un correcteur orthographique intelligent pour une suite bureautique. Le système doit détecter les fautes de frappe, suggérer des corrections, analyser la similarité entre documents et construire un index de recherche approximative. Le cœur du système repose sur la distance d'édition (distance de Levenshtein), qui mesure le nombre minimal d'opérations élémentaires (insertion, suppression, substitution) pour transformer un mot en un autre.
Une ville souhaite modéliser son réseau de distribution d'eau. Le réseau est représenté par un graphe orienté pondéré où : les sommets représentent des nœuds du réseau (châteaux d'eau, jonctions, quartiers), les arêtes orientées représentent des canalisations avec une capacité maximale (en litres/seconde).
Un arbre d'expression est un arbre binaire qui représente une expression arithmétique : les feuilles contiennent des nombres entiers, les nœuds internes contiennent des opérateurs : '+', '-', '*', '/'.
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).
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 ..
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.
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.
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.
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).
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.