Recherche séquentielle dans un tableau 1D

Recherche du maximum / second maximum

Comptage par dictionnaire

Notions de coût : O(1), O(n), O(n²)

Utilisation de modules/bibliothèques (lecture fichier, stats, graphiques)

Tri à bulles

Recherche des deux valeurs les plus proches dans un tableau

Recherche d'un facteur dans un texte (naïve)

Reconnaître ET prouver la complexité quadratique

Validation de la correction par invariant dès le S1

Recherche dichotomique dans un tableau trié

Exponentiation rapide

Savoir que log₂(10⁹) ≈ 30 — accélération linéaire → logarithmique

Structure obligatoire : cas de base + cas récursif qui converge

Version récursive d'algorithmes dichotomiques

Énumération (sous-listes, permutations d'une liste)

Dessins de fractales (turtle)

Dépassement de pile — expliquer et éviter

Rendu de monnaie

Sélection d'activités (intervalles compatibles)

Allocation de salles pour des cours

Glouton ≠ Optimal en général — toujours savoir contre-exemplariser

Accès à img[i][j] : i = ligne, j = colonne

Rotation d'image 90° et 180°

Convolution : flou et détection de contour

Réduction / agrandissement d'image

Tri par insertion — O(n²) pire, O(n) meilleur, stable, en place

Tri par sélection — O(n²) toujours, non stable, en place

Tri à bulles — O(n²) pire, O(n) meilleur avec flag, stable, en place

Tri fusion — O(n log n) toujours, stable, non en place O(n)

Tri rapide — O(n log n) moyen, O(n²) pire cas, non stable, en place

Tri par comptage — O(n+k), non comparatif, stable

Savoir caractériser un tri : stable / en place / comparatif

Spécification : signature + précondition + postcondition (avant le code)

Précondition / Postcondition / Invariant (en commentaires Python)

Assertion : assert condition

Variant de boucle → preuve de terminaison

Invariant de boucle → preuve de correction partielle

Correction partielle vs correction totale

Jeu de tests : cas typiques + limites + extrêmes

Effet de bord d'une instruction vs expression

Complexité en espace (en plus de la complexité temporelle)

Entiers positifs sur mots de taille fixe (binaire)

Complément à deux pour entiers signés

Distinction réels / décimaux / flottants

Flottants : mantisse × 2^exposant — pas d'obligation IEEE-754 en détail

Précision flottante — ne jamais tester l'égalité directe

Entiers multi-précision Python — coût arithmétique croissant avec la taille

Vocabulaire : orienté/non orienté, arc/arête, degré entrant d⁻/sortant d⁺, cycle, connexité

Matrice d'adjacence vs liste d'adjacence — choisir selon densité

BFS (largeur) avec collections.deque + popleft()

DFS (profondeur) — récursif ou itératif avec pile explicite

Tableau visités[] obligatoire pour éviter les boucles infinies

Détection de cycle dans un graphe non orienté (DFS + parent)

Test de connexité (BFS/DFS depuis chaque sommet non encore visité)

Algorithme de Dijkstra (poids positifs uniquement)

Reconstruction du chemin Dijkstra : tableau predecesseur[]

Complexité de Dijkstra : O((n+m) log n) avec tas binaire

A* = Dijkstra + heuristique admissible h(s) ≥ 0

Vocabulaire : table, attribut, enregistrement, domaine, schéma

Clé primaire (peut être composite) — unicité et non-nullité

Clé étrangère — référence à la clé primaire d'une autre table

Associations 1-1, 1-n, n-n (décomposer n-n en deux 1-n)

SELECT cols FROM tables WHERE cond (filtrage, projection, AS)

ORDER BY, DISTINCT, LIMIT, OFFSET

JOIN T1 JOIN T2 ON phi (équi-jointures) + autojointure

UNION, INTERSECT, EXCEPT

Agrégats : MIN, MAX, SUM, AVG, COUNT + GROUP BY

HAVING — filtrer après agrégation (≠ WHERE qui filtre avant)

Requêtes imbriquées (sous-requêtes dans WHERE ou SELECT)

INSERT INTO table (col1, col2) VALUES (v1, v2)

UPDATE table SET col = val WHERE condition

DELETE FROM table WHERE condition

Cardinalités (0,1) (1,1) (0,n) (1,n) dans un schéma entité-association

Passage MCD → MLD : règles de traduction des associations

Lire et compléter un schéma MCD (entités, associations, cardinalités)

Schéma relationnel MLD — notation : Table(#clé, attr1, #attr2→AutreTable)

NULL — concept exclu du programme officiel mais souvent rencontré

INSERT avec SELECT — insérer le résultat d'une requête

Contrainte d'intégrité référentielle — FK orpheline

Hachage : clé → fonction de hachage → indice → O(1) moyen

Clés hashables : int, str, tuple (PAS list ni dict)

Deux conditions prog. dynamique : sous-structure optimale + chevauchement

Mémoïsation top-down : récursion + dictionnaire cache

Bottom-up : remplir le tableau dp[] dans l'ordre croissant

Distance de Levenshtein (édition)

Plus longue sous-suite commune (LCS)

Floyd-Warshall — plus courts chemins toutes paires, O(n³)

Reconstruction de la solution optimale (backtracking sur table dp)

k plus proches voisins (k-NN) — classification supervisée

Matrice de confusion — VP, FP, VN, FN

k-moyennes — clustering non supervisé

Jeux à 2 joueurs sur graphe biparti — 3 types d'états finaux

Positions gagnantes par calcul des attracteurs (propagation arrière)

Algorithme minimax avec heuristique

Jeux à 3 états finaux : J1 gagne / J2 gagne / match nul

Type abstrait Pile (LIFO) : empiler, dépiler, sommet, est_vide

Type abstrait File (FIFO) : enfiler, défiler, tête, est_vide

Application pile : vérification de parenthésage équilibré

Listes chaînées : nœud = valeur + pointeur suivant

Insertion en tête O(1), accès i-ème O(n) dans une liste chaînée

Implémentation d'une pile / file par liste chaînée

Listes doublement chaînées — pointeurs précédent et suivant

Complexité amortie — séquence de n opérations sur une pile

Vocabulaire : racine, feuille, nœud interne, hauteur, taille, sous-arbre

Représentation Python : None = arbre vide, Noeud(val, gauche, droite)

Parcours préfixe NLR, infixe LNR, postfixe LRN — récursion naturelle

Calcul récursif : taille, hauteur, nombre de feuilles

Parcours en largeur (BFS) avec une file

Arbre binaire parfait / complet — relation hauteur et nombre de nœuds

Propriété ABR : gauche < racine ≤ droite à chaque nœud — sur TOUT le sous-arbre

Recherche et insertion dans un ABR — O(h)

Arbre équilibré : h ≈ log₂(n), opérations O(log n)

Arbre dégénéré : données triées en entrée → h = n-1, O(n)

Suppression dans un ABR — cas du nœud avec deux fils

Tas (heap) — arbre binaire complet avec propriété de tas

Encodage de Huffman — arbre de fréquences pour compression

Typage dynamique — type déterminé à l'exécution, pas à la déclaration

Portée lexicale — cherche variable localement puis dans l'espace global

Appel par valeur — évalue l'argument avant d'appeler la fonction

int : +, -, *, //, **, % (opérandes positifs pour //,%)

float : +, -, *, /, **

bool : not, or, and — évaluation paresseuse (court-circuit)

Chaînes/Tuples (immuables) : len, indice, +, *, tranche [a:b:p]

Listes : compréhension, [e]*n, append, pop, tranche, copie superficielle

Dictionnaires : {c1:v1,...}, accès, insertion, k in d, len, copy

if / elif / else

while (sans else), break, return dans boucle

for (sans else) sur range, str, tuple, list, dict.keys(), dict.items()

def f(p1, ..., pn): ... return

import module / as alias / from module import f, g

Fichiers : open, read, readline, readlines, split, write, close

assert condition (sans message d'erreur)

Chapitre 1 : Codage de l'information

Chapitre 2 : Algorithmique de base

Chapitre 3 : La base de Python

Chapitre 4 : Les fonctions

Chapitre 5 : Les séquences

Chapitre 6 : Les matrices

Chapitre 7 : Les fichiers

Chapitre 8 : Les dictionnaires

Chapitre 9 : Les ensembles

Chapitre 10 : Gestion des exceptions

Chapitre 11 : POO

Chapitre 12 : Modules numpy, matplotlib, scipy

TD 1 : Codage de l'information

TD 2 : Codage de l'information

TD 3 : Le module turtle

TD 4 : Algorithmique : Affectation

TD 5 : Algorithmique : I/O

TD 6 : Algorithmique : Tests

TD 7 : Algorithmique : Boucles

TD 8 : Algorithmique : Révision

TD 9 : Python - Initiation

TD 10 : Python - I/O

TD 11 : Python - Tests

TD 12 : Python - Boucles

TD 12 (suite) : Python - Boucles

TD 13 : Les fonctions

TD 14 : Les fonctions récursives

TD 15 : Les chaînes de caractères

TD 16 : Les chaînes de caractères

TD 17 : Les listes et les tuples

TD 18 : Les listes et les tuples

TD 19 : Les matrices

TD 19 : Le module PIL

TD 20 : Fichiers

TD 21 : Dictionnaires - Ensembles - Exceptions

TD 22 : POO

TD 23 : Module numpy

TD 24 : Modules matplotlib, scipy