Consolidation Python : algorithmes et structures de données

Consolidation Python : structures de données (listes, dictionnaires), boucles (for, while), conditions (if/elif/else), fonctions (def), récursivité. Complexité : évaluer le nombre d'opérations. Algorithmes classiques : recherche (séquentielle, dichotomique), tri (séquentiel, fusion). Récursivité : une fonction qui s'appelle elle-même, avec un cas de base. Bonnes pratiques : modularité, lisibilité, noms explicites, documentation. Le débogage s'effectue par tests et affichages. La consolidation Python prépare à des applications dans tous les domaines (suites, intégrales, probabilités).

📝 Examen de trimestre (barème : 20 pts, grille : 16-20 = TB, 12-15 = B, 8-11 = passable, <8 = insuffisant)

1. Liste de 0 à 9 en compréhension. (1 pt)
2. Recherche dichotomique : écrire. (3 pts)
3. Tri par sélection : écrire. (2 pts)
4. Factorielle récursive. (2 pts)
5. Fibonacci récursif. (2 pts)
6. Recherche séquentielle. (1 pt)
7. Démontre que la dichotomie est en O(log n). (2 pts)
8. Tri fusion : principe. (2 pts)
9. Liste des carrés pairs de 0 à 20. (2 pts)
10. Dictionnaire : comptage d'occurrences. (2 pts)
11. Complexité du tri par sélection. (1 pt)
12. Fonction récursive : cas de base. (1 pt)
13. Vérifier qu'une liste est triée. (1 pt)

Corrigé et barème :

1. [x for x in range(10)] (1 pt).
2. while g≤d, m=(g+d)//2, comparaison, division (3 pts).
3. Pour chaque i, échanger avec le min (2 pts).
4. def f(n): return 1 if n≤1 else n·f(n−1) (2 pts).
5. def fib(n): return n if n<2 else fib(n−1)+fib(n−2) (2 pts).
6. for x in L: if x==val: return True (1 pt).
7. Division par 2 à chaque étape (2 pts).
8. Diviser, trier récursivement, fusionner (2 pts).
9. [x² for x in range(21) if x²%2==0] (2 pts).
10. D={}; for x in L: D[x]=D.get(x, 0)+1 (2 pts).
11. O(n²) (1 pt).
12. Condition d'arrêt (1 pt).
13. all(L[i]≤L[i+1] for i in range(len(L)−1)) (1 pt).

📝 Corrigés détaillés des exercices

Corrigé de l'exercice 1

Question : Liste de 0 à 9 en compréhension ?

Méthode : Compréhension.

Étapes détaillées :

1. Compréhension.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : [x for x in range(10)]

Corrigé de l'exercice 2

Question : Factorielle récursive ?

Méthode : Récursivité.

Étapes détaillées :

1. Récursivité.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : def f(n): return 1 if n≤1 else n·f(n−1)

Corrigé de l'exercice 3

Question : Fibonacci récursif ?

Méthode : Récursivité.

Étapes détaillées :

1. Récursivité.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : def fib(n): return n if n<2 else fib(n−1)+fib(n−2)

Corrigé de l'exercice 4

Question : Recherche séquentielle ?

Méthode : Boucle.

Étapes détaillées :

1. Boucle.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : for x in L: if x==val: return True

Corrigé de l'exercice 5

Question : Complexité de la dichotomie ?

Méthode : Division par 2.

Étapes détaillées :

1. Division par 2.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : O(log n)

Corrigé de l'exercice 6

Question : Complexité du tri par sélection ?

Méthode : Double boucle.

Étapes détaillées :

1. Double boucle.
2. Choisis la méthode, la formule ou le théorème approprié.
3. Effectue les calculs en détaillant chaque étape.
4. Vérifie et conclus.

Réponse finale : O(n²)

Corrigé de l'exercice 7

Question : Cas de base d'une fonction récursive ?

Méthode : Récursivité.

Étapes détaillées :

1. Identifie l'algorithme demandé et les structures à utiliser (boucle, condition, fonction…).
2. Écris le code Python en respectant la syntaxe (indentation, types, opérateurs).
3. Teste mentalement avec un exemple simple.
4. Vérifie la complexité et les cas limites.

Réponse finale : Condition d'arrêt

Corrigé de l'exercice 8

Question : Vérifier qu'une liste est triée ?

Méthode : Comparaisons.

Étapes détaillées :

1. Identifie l'algorithme demandé et les structures à utiliser (boucle, condition, fonction…).
2. Écris le code Python en respectant la syntaxe (indentation, types, opérateurs).
3. Teste mentalement avec un exemple simple.
4. Vérifie la complexité et les cas limites.

Réponse finale : all(L[i]≤L[i+1] for i in range(len(L)−1))