Flashcards d'informatique : mémoriser algorithmes, automates et structures

Le défi de l'informatique théorique en prépa

Le programme d'informatique de deuxième année de prépa scientifique (MP/MPI) est dense et abstrait. Il couvre la théorie des graphes, les automates et langages formels, la calculabilité, la logique (déduction naturelle), la concurrence, la théorie des jeux, l'apprentissage automatique et des techniques algorithmiques avancées (algorithmes probabilistes, exploration exhaustive, union-find).

Contrairement à la programmation pratique de Sup (ou l'on code et on teste), l'informatique de Spé est largement théorique. Elle repose sur des définitions formelles, des théorèmes de complexité, des propriétés de clôture des langages et des résultats d'indécidabilité. Chaque notion s'appuie sur les précédentes : impossible de comprendre le lemme de pompage sans maîtriser la définition d'un automate fini, ou d'aborder la calculabilité sans connaître les grammaires formelles.

Le problème est le même qu'en maths ou en physique : la courbe de l'oubli (Ebbinghaus, 1885) s'applique aussi aux définitions théoriques. Un théorème d'indécidabilité compris en octobre peut s'effacer en décembre si vous ne le révisez pas activement. La solution repose sur le rappel actif et la répétition espacée, deux techniques validées par la recherche cognitive (Dunlosky et al., 2013).

Pourquoi les flashcards fonctionnent en informatique

L'informatique théorique est une matière ou la précision des définitions est cruciale. Un automate "non déterministe" n'est pas simplement un automate "avec des choix" : c'est un objet formel avec un alphabet, des états, une fonction de transition, un état initial et des états acceptants. Ce niveau de précision est exactement ce que les flashcards entraînent : vous devez reconstruire la définition complète avant de vérifier.

Le rappel actif (active recall) est particulièrement adapté à l'informatique pour trois raisons :

• Les définitions formelles : automate, graphe, langage régulier, grammaire, machine de Turing. Se tester force à formuler chaque composante au lieu de vaguement "se souvenir".
• Les théorèmes et propriétés : clôture des langages réguliers, indécidabilité du problème de l'arrêt, correction d'un algorithme. L'effort de récupération renforce la trace mnésique (Karpicke & Blunt, 2011).
• Les algorithmes et complexités : complexité de Dijkstra, coût amorti d'union-find, tri topologique. Les flashcards ancrent les complexités que l'on confond facilement.

Les decks d'informatique de PSD : 373 cartes, 12 chapitres

Les decks d'informatique de Personal Study Dashboard contiennent 373 flashcards couvrant le programme d'informatique de deuxième année (MP/MPI). Les cartes sont organisées par chapitre :

Automates, langages et grammaires : 108 cartes, 3 chapitres

Le bloc le plus fourni, couvrant la théorie des langages formels :

• Automates : 57 cartes (automates finis déterministes et non déterministes, minimisation, équivalence, produit d'automates, complémentation)
• Langages réguliers : 33 cartes (expressions régulières, lemme de pompage, propriétés de clôture, théorème de Kleene)
• Grammaires non-contextuelles : 18 cartes (dérivations, arbres de dérivation, ambiguïté, forme normale de Chomsky)

Graphes et structures de données : 76 cartes, 2 chapitres

• Graphes : 46 cartes (parcours BFS/DFS, plus courts chemins, composantes connexes et fortement connexes, arbres couvrants, tri topologique)
• Union-Find : 30 cartes (structure union-find, compression de chemin, union par rang, complexité amortie)

Calculabilité et logique : 74 cartes, 2 chapitres

• Calculabilité : 59 cartes (machines de Turing, thèse de Church-Turing, problème de l'arrêt, réductions, théorème de Rice, indécidabilité)
• Déduction naturelle : 15 cartes (règles d'introduction et d'élimination, preuves formelles, connecteurs logiques)

Algorithmique avancée : 43 cartes, 2 chapitres

• Algorithmes probabilistes : 26 cartes (algorithmes de Las Vegas et Monte Carlo, analyse probabiliste, amplification)
• Exploration exhaustive : 17 cartes (backtracking, branch and bound, heuristiques)

Concurrence, jeux et apprentissage : 72 cartes, 3 chapitres

• Concurrence et synchronisation : 31 cartes (processus, exclusion mutuelle, sémaphores, interblocage, sections critiques)
• Apprentissage automatique : 22 cartes (classification, régression, k plus proches voisins, arbres de décision, validation croisée)
• Théorie des jeux : 19 cartes (jeux combinatoires, positions gagnantes et perdantes, Sprague-Grundy, nimbers)

FSRS et l'informatique : planification intelligente

FSRS (Free Spaced Repetition Scheduler) est l'algorithme de répétition espacée intégré dans PSD. Il modélise votre mémoire avec trois paramètres par carte : stabilité, difficulté et probabilité de rappel.

Chaque notion a son propre rythme

En informatique théorique, les notions n'ont pas toutes la même difficulté. La définition d'un graphe orienté est intuitive et se retient facilement : FSRS ne vous la reproposera que rarement. En revanche, la preuve d'indécidabilité par réduction ou les propriétés de clôture des langages algébriques sont plus abstraites : l'algorithme les reproposera plus souvent jusqu'à stabilisation.

Cette adaptation est automatique. Vous n'avez pas besoin de trier vos cartes par difficulté. L'algorithme observe vos réponses et ajuste les intervalles en temps réel.

Méthode de révision pour l'informatique

Voici une approche concrète pour intégrer les flashcards d'informatique dans votre routine :

1. Activez les chapitres en suivant votre cours : graphes d'abord si c'est votre premier chapitre de l'année, puis automates, calculabilité, etc.
2. Révisez 5 à 10 minutes par jour : en régime de croisière, 10 à 20 cartes d'informatique suffisent
3. Reconstruisez la définition complète avant de vérifier : c'est l'effort de rappel qui crée l'apprentissage
4. Pensez aux conditions et aux hypothèses : un automate déterministe n'est pas un automate non déterministe, la différence est dans la fonction de transition
5. Articulez flashcards et pratique : les flashcards ancrent la théorie (définitions, théorèmes, complexités), les exercices et le code développent le savoir-faire (implémentation, preuves, raisonnement)