Révisions d'Informatique, Passage PCSI vers PSI ou PC

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

Les 7 chapitres de la fiche

À maîtriser :

Types de base : int, float, str, bool, list ; savoir choisir entre / (division réelle) et // (division entière)
Définir une fonction avec def, des paramètres, et renvoyer un résultat avec return
Structures conditionnelles if / elif / else, opérateurs de comparaison (==, <, >=) et logiques (and, or, not)
Boucles for (parcours d'un itérable ou de range(...)) et while (répétition tant qu'une condition est vraie)
Manipulation de chaînes de caractères : indexation, slicing, méthodes usuelles (split, strip, f-strings)

5 exercices corrigés dans ce chapitre.

À maîtriser :

Parcourir une liste avec for (avec ou sans enumerate) et accumuler un résultat dans une variable au fil du parcours
Calculer à la main des statistiques simples : moyenne, maximum, minimum, écart entre les deux, sans bibliothèque
Distinguer recherche linéaire (parcours complet, coût en $O(n)$) et recherche dichotomique sur liste triée (coût en $O(\log n)$)
Utiliser une compréhension de liste pour construire une liste filtrée ou transformée en une seule ligne
Manipuler un tableau 2D (liste de listes) : indexation tab[i][j], parcours par lignes puis par colonnes

5 exercices corrigés dans ce chapitre.

À maîtriser :

Principe d'une fonction récursive : un cas de base (condition d'arrêt) et un cas récursif, qui appelle la fonction sur une instance plus petite du problème
Vérifier la terminaison : montrer qu'un paramètre (souvent un entier) décroît strictement vers le cas de base à chaque appel
Exemples classiques : factorielle, exponentiation rapide (puissance rapide), recherche dichotomique récursive
Estimer le coût d'un algorithme récursif : nombre d'appels, profondeur de récursion, et limite pratique (RecursionError) en Python
Traduire une relation de récurrence $u_{n+1} = f(u_n)$ en une fonction récursive, en identifiant clairement le cas de base $u_0$

5 exercices corrigés dans ce chapitre.

À maîtriser :

Méthode de dichotomie pour résoudre $f(x) = 0$ sur un intervalle $[a, b]$ où f change de signe, avec une précision epsilon donnée
Méthode d'Euler explicite pour une équation différentielle $y' = f(y, t)$ : discrétisation du temps en pas h, formule $y_{n+1} = y_n + h \cdot f(y_n, t_n)$
Comprendre que l'erreur de la méthode d'Euler explicite diminue quand le pas h diminue, mais que le coût de calcul (nombre d'itérations) augmente en contrepartie
Décrire qualitativement l'allure d'une solution numérique et la comparer à une solution exacte connue, pour juger de la pertinence du pas choisi
Identifier le compromis précision / temps de calcul lors du choix du pas de temps, et le risque d'instabilité si le pas est trop grand

5 exercices corrigés dans ce chapitre.

À maîtriser :

La complexité temporelle d'un algorithme mesure le nombre d'opérations élémentaires effectuées en fonction de la taille $n$ de l'entrée ; la notation $O(f(n))$ donne une borne asymptotique supérieure, indépendante de la machine, et on distingue le meilleur cas, le cas moyen et le pire cas.
La recherche séquentielle parcourt la liste élément par élément en $O(n)$ ; la recherche dichotomique, applicable uniquement sur une liste triée, divise l'intervalle de recherche par deux à chaque étape et coûte $O(\log n)$.
Le tri par insertion maintient l'invariant : après le passage $i$, les $i$ premiers éléments de la liste sont triés entre eux ; sa complexité est $O(n^2)$ en moyenne et au pire, et $O(n)$ dans le meilleur cas (liste déjà triée).
Le tri fusion applique le principe diviser pour régner : il découpe la liste en deux moitiés, les trie récursivement, puis les fusionne en $O(n)$ ; sa complexité totale vérifie $T(n) = 2T(n/2) + O(n)$, soit $T(n) = O(n \log n)$.
Le tri rapide partitionne la liste autour d'un pivot : coût moyen $O(n \log n)$, mais pire cas $O(n^2)$ si le pivot est mal choisi (par exemple liste déjà triée avec pivot pris en premier) ; les fonctions sorted() et list.sort() de Python utilisent Timsort, un tri stable garanti en $O(n \log n)$.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Tout entier naturel $n$ s'écrit de façon unique en base 2 sous la forme $n = \sum_{i=0}^{k} a_i 2^i$ avec $a_i \in \{0, 1\}$ ; la conversion décimal vers binaire s'obtient par divisions euclidiennes successives par 2, et la conversion inverse par la somme $\sum a_i 2^i$.
Le complément à deux sur $n$ bits représente les entiers relatifs de l'intervalle $[-2^{n-1}, 2^{n-1} - 1]$ : le bit de poids fort porte le coefficient $-2^{n-1}$ au lieu de $2^{n-1}$, ce qui permet d'additionner directement les représentations binaires sans traitement particulier du signe.
Un nombre flottant est représenté par un signe, une mantisse et un exposant, sous la forme $\pm m \times 2^e$ ; l'epsilon machine, environ $2,22 \times 10^{-16}$ en double précision, borne l'erreur relative introduite par l'arrondi d'une opération.
Les fractions décimales comme 0,1 n'ont pas toutes une écriture binaire finie : l'expression 0.1 + 0.2 != 0.3 est vraie en Python à cause de l'arrondi, et les erreurs d'arrondi s'accumulent lors de sommations répétées ; on compare donc deux flottants avec une tolérance plutôt qu'avec ==.
Les opérateurs binaires de Python (&, |, ^, ~, <<, >>) agissent directement sur la représentation en bits d'un entier : & et | pour masquer ou combiner des bits, ^ pour un ou exclusif, << et >> pour décaler, ce qui équivaut à multiplier ou diviser par une puissance de 2.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Une pile (LIFO, dernier entré premier sorti) s'implémente en Python avec une list : empiler par append(x) et dépiler par pop(), les deux en $O(1)$ amorti ; une file (FIFO, premier entré premier sorti) s'implémente avec collections.deque, dont popleft() est en $O(1)$, contrairement à list.pop(0) qui coûte $O(n)$.
Pour vérifier l'équilibre d'une expression parenthésée, on empile chaque symbole ouvrant rencontré, et à chaque symbole fermant on dépile et on vérifie qu'il correspond bien à l'ouvrant attendu ; l'expression est équilibrée si et seulement si la pile est vide à la fin du parcours.
La dichotomie sur une liste triée maintient l'invariant : si la valeur cherchée est présente, elle se trouve dans l'intervalle [gauche, droite] ; le variant droite - gauche décroît strictement à chaque itération, ce qui garantit la terminaison en $O(\log n)$ itérations.
Un dictionnaire Python (table de hachage) offre un accès, une insertion et une suppression en $O(1)$ en moyenne par clé, ce qui en fait la structure de choix pour compter des occurrences ou mémoriser des résultats intermédiaires.
Un algorithme glouton construit une solution en effectuant, à chaque étape, le choix localement optimal sans jamais revenir en arrière ; cette stratégie n'est optimale que sous certaines hypothèses, et le rendu de monnaie avec le système {1, 3, 4} pour un montant de 6 est un contre-exemple classique où le glouton échoue.

5 exercices corrigés dans ce chapitre.

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