Informatique - CNC Maroc
L'épreuve d'informatique évalue l'algorithmique et la programmation, généralement en Python, ainsi que les structures de données, la complexité et des notions de bases de données relationnelles. Les questions demandent de compléter un code, d'écrire une fonction, de justifier une complexité ou d'écrire une requête SQL.
À maîtriser
- Structures : listes, piles, files, dictionnaires, arbres binaires, graphes.
- Algorithmes classiques : recherche dichotomique, tris, parcours d'arbres, plus court chemin.
- Complexité : O(1), O(log n), O(n), O(n log n), O(n²), en distinguant pire cas et cas moyen.
- SQL : SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY ; clés primaires et étrangères.
Exemple
Recherche dichotomique dans un tableau trié de n = 1024 éléments. Chaque itération divise l'intervalle de recherche par 2 : après k itérations, la taille restante est n/2^k. On s'arrête lorsque n/2^k ≤ 1, soit k ≥ log₂(1024) = 10. Le nombre maximal de comparaisons est donc 10 et la complexité est O(log n), à comparer au O(n) de la recherche linéaire - c'est cette comparaison qui justifie l'algorithme.
Pièges qui coûtent des points
- Erreurs de bornes (while debut <= fin) et confusion entre indices 0 et 1 en Python.
- Oublier les cas limites : tableau vide, tableau à un seul élément, élément absent.
- Annoncer une complexité sans préciser qu'il s'agit du pire cas.
- En SQL, confondre WHERE (filtre sur les lignes) et HAVING (filtre sur les groupes), ou omettre le GROUP BY.