Bases & algorithmique · 6 mondes · 18 étapes

Algorithmique

Apprendre à penser un problème, en Python, dans le navigateur.

Progression

0 %

0/18 étapes terminées

Mode 7

Réviser vite, retenir longtemps

Des fiches express pour relire l'essentiel en deux minutes, des cartes mémoire qui reviennent au bon moment, et un jeu chronométré pour ancrer le vocabulaire.

« Résume les concepts les plus importants dans un guide clair et concis qui m'aide à réviser rapidement et à mémoriser les idées clés sans complexité inutile. »

Fiches express

L'essentiel, semaine par semaine

Semaine 1

5 points

Penser en étapes

Un algorithme : entrée → étapes exécutables → sortie, et il s'arrête.
Écrire la méthode en français avant la première ligne de code.
Accumulateur et compteur se préparent avant la boucle.
Une recherche de maximum part du premier élément, jamais de 0.
Dérouler à la main : une colonne par variable, une ligne par tour.

total = 0for p in poids:    total = total + pprint(total)

À retenir : La difficulté est dans la méthode, pas dans la syntaxe.

Semaine 2

5 points

Chercher

Recherche linéaire : fonctionne toujours, coûte n dans le pire cas.
Convention : on renvoie la position, ou -1 si la valeur est absente.
Recherche dichotomique : debut, fin, milieu = (debut + fin) // 2.
Elle exige une liste triée, sinon les réponses sont fausses.
while debut <= fin et les ± 1 : les trois détails qui la rendent correcte.

while debut <= fin:    milieu = (debut + fin) // 2    if annuaire[milieu] == cherche:        position = milieu        break    elif annuaire[milieu] < cherche:        debut = milieu + 1    else:        fin = milieu - 1

À retenir : Trier coûte cher : la dichotomie se rentabilise sur des recherches répétées.

Semaine 3

5 points

Compter les opérations

On compte les opérations en fonction de n, on ne chronomètre pas.
Une boucle : O(n). Une boucle dans une boucle : O(n²).
Couper en deux à chaque tour : O(log n).
On garde le terme dominant et on jette les constantes.
On raisonne sur le pire cas, celui qui fait tomber les serveurs.

comparaisons = 0for i in range(len(v)):    for j in range(i + 1, len(v)):        comparaisons += 1# n(n-1)/2 comparaisons

À retenir : La forme de la croissance domine toujours le coefficient.

Semaine 4

5 points

Trier

Tri par sélection : chercher le minimum du reste, échanger, recommencer.
Tri par insertion : décaler les plus grands, glisser la valeur à sa place.
Les deux sont en O(n²) ; l'insertion devient O(n) sur une liste presque triée.
a[i], a[j] = a[j], a[i] échange deux cases en une ligne.
sorted() renvoie une nouvelle liste, .sort() modifie et renvoie None.

for i in range(len(colis)):    mini = i    for j in range(i + 1, len(colis)):        if colis[j] < colis[mini]:            mini = j    colis[i], colis[mini] = colis[mini], colis[i]

À retenir : Écrire un tri une fois pour comprendre ; utiliser sorted() ensuite.

Semaine 5

5 points

La récursivité

Toujours deux parties : cas de base, puis cas récursif qui réduit le problème.
Le cas de base s'écrit en premier : c'est lui qui garantit l'arrêt.
Faire confiance à l'appel : supposer le cas plus petit résolu.
Fibonacci naïf est exponentiel ; mémoïsé, il est linéaire.
La mémoïsation échange de la mémoire contre du temps.

def somme(liste):    if not liste:        return 0    return liste[0] + somme(liste[1:])

À retenir : Pas de cas de base, ou pas de réduction : RecursionError.

Semaine 6

5 points

La boîte à outils

Dictionnaire et ensemble : appartenance en O(1) grâce au hachage.
Comptage : compte[cle] = compte.get(cle, 0) + 1.
Glouton : meilleur choix local, correct seulement si le problème s'y prête.
Deux pointeurs : sur liste triée, remplace une double boucle par un parcours.
Méthode : clarifier, chercher le motif, version naïve, mesurer, optimiser.

vus = set()for x in valeurs:    if cible - x in vus:        trouve = True    vus.add(x)

À retenir : Une recherche répétée dans une liste est le symptôme du quadratique.