Révisions d'Informatique, Passage TSI 1 vers TSI 2

Révisions d'Informatique en prépa TSI : 30 exercices corrigés avec rappels de cours, de la sup à la spé. Gratuit sur MonProf+.

Les 6 chapitres de la fiche

À maîtriser :

Une variable stocke une valeur typée (entier `int`, flottant `float`, chaîne `str`, booléen `bool`) ; la fonction `type(x)` donne le type de `x`.
Une fonction se définit avec `def nom(parametres):`, ne s'exécute que lorsqu'elle est appelée, et renvoie une valeur grâce à `return` (sans `return`, elle renvoie `None`).
Boucle `for` : nombre d'itérations connu à l'avance, par exemple `for i in range(n):`. Boucle `while` : répétition tant qu'une condition reste vraie, à utiliser quand le nombre de passages dépend d'une mesure.
Test conditionnel `if / elif / else` : les conditions s'évaluent dans l'ordre, la première vraie est exécutée, toutes les suivantes sont ignorées.
Opérateurs de comparaison (`==`, `!=`, `<`, `<=`, `>`, `>=`) et logiques (`and`, `or`, `not`) pour construire des conditions composées sur des mesures physiques.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Une liste Python se parcourt avec `for element in liste:` (accès direct aux valeurs) ou `for i in range(len(liste)):` (accès à l'indice, utile pour comparer des positions).
Calculer min, max ou somme "à la main" : initialiser avec le premier élément de la liste, puis comparer ou accumuler sur le reste ; le cas d'une liste vide doit toujours être traité à part.
Compter les éléments vérifiant une condition : un compteur initialisé à 0, incrémenté à chaque tour où le `if` du parcours est vérifié.
Recherche linéaire : parcourir la liste du début à la fin, renvoyer l'indice dès que la valeur est trouvée, renvoyer -1 si le parcours se termine sans succès.
Recherche dichotomique : ne s'applique qu'à une liste déjà triée. À chaque étape, on compare la valeur cherchée à l'élément du milieu de la zone restante pour éliminer une moitié de la liste.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Une fonction récursive s'appelle elle-même sur une version "plus petite" du problème, jusqu'à atteindre un cas de base qui ne s'appelle plus lui-même.
Deux ingrédients obligatoires : un cas de base (arrêt explicite, sans appel récursif) et une réduction du problème à chaque appel qui se rapproche strictement du cas de base (garantit la terminaison).
La pile d'appels : chaque appel récursif reste "en attente" jusqu'à ce que l'appel suivant renvoie son résultat ; les calculs en attente se déroulent ensuite dans l'ordre inverse des appels.
Toute fonction récursive peut se réécrire avec une boucle, et réciproquement : la version itérative est en général plus économe en mémoire, la version récursive est parfois plus lisible sur un problème naturellement décomposable.
Sur des données de grande taille, une récursivité trop profonde peut dépasser la limite de récursion de Python et lever une `RecursionError` : la version itérative est alors préférable.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Tri par sélection : à chaque étape, rechercher le plus petit élément de la zone non triée et l'échanger avec l'élément situé en tête de cette zone.
Tri par insertion : à chaque étape, insérer l'élément courant à sa juste place parmi les éléments déjà triés, en décalant vers la droite ceux qui sont plus grands que lui.
Pourquoi trier une liste : une liste triée permet une recherche dichotomique rapide et facilite le calcul de statistiques (médiane, détection de valeurs extrêmes, comparaison à un relevé de référence).
Coût en nombre de comparaisons : le tri par sélection effectue toujours $n(n-1)/2$ comparaisons pour $n$ éléments, quel que soit l'ordre initial ; le tri par insertion en effectue beaucoup moins si la liste est presque déjà triée.
Ordre de grandeur $O(n^2)$ : le nombre d'opérations des deux tris croît comme le carré du nombre d'éléments, ce qui les rend lents sur de très grands relevés (au-delà de quelques milliers de valeurs).

5 exercices corrigés dans ce chapitre.

À maîtriser :

Un entier naturel $n$ s'écrit en base 2 comme une somme de puissances de 2 : $n = \sum_{i=0}^{k-1} b_i \cdot 2^i$ avec $b_i \in \{0,1\}$. En Python, `bin(n)` renvoie la chaîne `'0b...'` et `int(s, 2)` reconvertit une chaîne binaire en entier.
L'hexadécimal (base 16, chiffres 0-9 puis A-F) regroupe les bits par paquets de 4 : un octet (8 bits) se note toujours sur exactement 2 chiffres hexadécimaux, par exemple `0xFF` pour $255$. En Python : `hex(n)` et `int(s, 16)`.
Le complément à deux sur $n$ bits code un entier signé de l'intervalle $[-2^{n-1}, 2^{n-1}-1]$ : un nombre positif garde son écriture binaire usuelle, un nombre négatif $x$ est codé par l'entier positif $x + 2^n$.
Un flottant est stocké en base 2 avec un nombre fini de bits de mantisse : la plupart des décimaux (comme $0.1$) n'ont pas d'écriture binaire finie, d'où des erreurs d'arrondi ; ainsi `0.1 + 0.2 != 0.3` en Python. On compare deux flottants avec une tolérance $\varepsilon$, par exemple `math.isclose(a, b, rel_tol=1e-9)`, jamais avec `==`.
Un capteur relié à un convertisseur analogique-numérique (CAN) sur $n$ bits code une tension continue par un entier parmi $2^n$ valeurs possibles : la résolution du capteur vaut $\dfrac{V_{max} - V_{min}}{2^n - 1}$.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Une pile (structure LIFO, « dernier entré, premier sorti ») se manipule en Python avec une simple liste : `pile.append(x)` empile, `pile.pop()` dépile le dernier élément ajouté. Elle sert par exemple à vérifier un parenthésage.
Une file (structure FIFO, « premier entré, premier sorti ») se manipule avec `collections.deque` : `file.append(x)` ajoute une commande en fin de file, `file.popleft()` retire la plus ancienne, en temps constant contrairement à `list.pop(0)`.
La recherche par dichotomie sur une liste triée de longueur $n$ compare la cible à l'élément médian et réduit l'intervalle de recherche de moitié à chaque tour : elle termine en au plus $\lceil \log_2(n) \rceil$ comparaisons, contre $n$ pour une recherche linéaire.
Un dictionnaire associe des clés à des valeurs (par exemple une référence de pièce à son stock disponible) et permet la lecture, l'écriture et la mise à jour en temps moyen constant, quel que soit le nombre de références stockées.
Un algorithme glouton construit une solution en effectuant à chaque étape le choix localement optimal, sans revenir en arrière ; il est optimal pour certains problèmes (rendu de monnaie avec un système de pièces adapté, choix d'activités par date de fin), mais pas pour tous.

5 exercices corrigés dans ce chapitre.

30 exercices corrigés avec indice et rappel de cours, en accès libre.