CNC Informatique — MZA Prépa Excellence.
“`htmlInformatique
CNC
Algorithmique, Python, structures de données, récursivité, complexité, graphes, logique, bases de données et stratégie de résolution : un espace conçu pour raisonner vite et produire des algorithmes corrects.
Les blocs essentiels.
01 • Algorithmique
Variables, conditions, boucles, fonctions et invariants.
02 • Python
Listes, tuples, dictionnaires, fonctions et traitement de données.
03 • Complexité
Temps, mémoire, ordre de grandeur et notation O.
04 • Récursivité
Cas de base, appels récursifs, terminaison et coût.
05 • Structures de données
Piles, files, tableaux, listes et ensembles.
06 • Recherche & tri
Recherche dichotomique, insertion, sélection et fusion.
07 • Graphes
Sommets, arêtes, parcours, connexité et plus courts chemins.
08 • Bases de données
Tables, clés, SQL, sélection, jointures et agrégation.
09 • Stratégie CNC
Compréhension du problème, preuve de correction et tests.
Six réflexes avant d’écrire du code.
Ne pas coder avant de savoir ce que l’algorithme doit garantir.
Spécification
Quelles sont les données d’entrée et la sortie attendue ?
Invariant
Quelle propriété doit rester vraie pendant l’exécution ?
Terminaison
Pourquoi l’algorithme finit-il ?
Complexité
Combien d’opérations et quelle mémoire supplémentaire ?
Problèmes type CNC Informatique.
Mission 1 — Maximum d’une liste
Écrire un algorithme qui détermine le maximum d’une liste non vide.
- compléter l’algorithme ;
- identifier un invariant de boucle ;
- justifier la correction ;
- déterminer la complexité temporelle ;
- déterminer la complexité mémoire.
Mission 2 — Recherche dichotomique
On recherche une valeur x dans une liste triée.
- décrire l’intervalle de recherche ;
- choisir l’indice médian ;
- réduire l’intervalle ;
- justifier la terminaison ;
- déterminer la complexité.
Mission 3 — Parcours d’un graphe
On représente un réseau par un graphe non orienté.
- choisir une représentation adaptée ;
- parcourir les sommets accessibles depuis une source ;
- éviter les visites multiples ;
- tester la connexité ;
- discuter la complexité du parcours.
10 minutes — 6 réflexes informatiques.
01
Une boucle parcourt n éléments une seule fois : complexité typique ?
02
Une recherche dichotomique divise le problème par deux : ordre de complexité ?
03
Une fonction récursive sans cas de base présente quel risque ?
04
Quel parcours utilise naturellement une file : profondeur ou largeur ?
05
Une clé primaire sert principalement à quoi ?
06
Un algorithme passe tous les exemples donnés : est-il forcément correct ?
Reconnaître immédiatement les grands ordres.
O(1)
Temps indépendant de la taille de l’entrée.
O(log n)
Réduction multiplicative du problème, comme la recherche dichotomique.
O(n)
Parcours simple d’une structure de taille n.
O(n²)
Deux boucles imbriquées parcourant n éléments dans le cas typique.
Gestion intelligente d’un réseau de transport.
Partie A — Données
- modéliser les stations et connexions ;
- choisir une structure de données ;
- charger un réseau simple ;
- tester l’existence d’une station ;
- calculer son nombre de voisins.
Partie B — Parcours
- écrire un parcours en largeur ;
- maintenir l’ensemble des sommets visités ;
- calculer les distances en nombre d’arêtes ;
- tester la connexité ;
- analyser la complexité.
Partie C — Optimisation
- identifier les chemins possibles ;
- définir une fonction de coût ;
- proposer un algorithme adapté ;
- justifier son choix ;
- discuter les limites du modèle.
Partie D — Base de données
- définir les tables Station et Liaison ;
- choisir les clés ;
- écrire une requête de sélection ;
- écrire une jointure ;
- produire une agrégation par station.
Les erreurs classiques en concours.
Indice hors limites
Confusion entre longueur n et dernier indice n-1.
Cas vide oublié
Un algorithme échoue sur une entrée particulière non testée.
Récursion infinie
Cas de base absent ou problème qui ne diminue pas.
Mutation involontaire
Une structure passée en argument est modifiée sans que cela soit voulu.
Complexité sous-estimée
Une opération coûteuse est cachée dans une boucle.
Tests insuffisants
Un exemple réussi ne constitue pas une preuve générale.
Avant de valider un algorithme.
Testez vos réflexes algorithmiques.
Le score s’affiche sans correction détaillée.
CNC Informatique — Mode Concours
L’objectif est de transformer un problème en données, algorithme, preuve, complexité et tests, avec une rédaction suffisamment claire pour être évaluée rapidement.