CNC 2024 · MP · Informatique
CNC 2024, filière MP, matière info, épreuve 1.
- Durée : 2 h
- 29 questions
- Difficulté : 3/5
Présentation du sujet
Un sujet d'informatique en trois temps : un exercice sur l'exponentiation rapide et l'évaluation de polynômes, une partie de programmation dynamique sur le produit optimal d'une chaîne de matrices (mémoïsation, puis tableaux bottom-up), et un problème de segmentation d'image par l'algorithme K-means, prolongé par la méthode du coude et des requêtes SQL sur les pixels segmentés.
Thèmes abordés
- exponentiation rapide
- complexité algorithmique
- programmation dynamique (mémoïsation et bottom-up)
- produit d'une chaîne de matrices
- numpy
- traitement d'image et histogramme
- algorithme K-means
- méthode du coude (Elbow)
- bases de données relationnelles et SQL
Parties et questions
Exercice
- Q1 Écrire la fonction puiss (x, n) qui reçoit en paramètres un réel x, et un entier positif n. En utilisant l'algorithme de l'exponentiation rapide ci-dessus, la fonction retourne la valeur de x^n.
- Q2 Écrire la liste qui représente le polynôme : – 3x^3 + 7x^2 – x^6 + 10 – 2x^4
- Q3 Écrire la fonction valeur (x, L) qui reçoit en paramètres un réel x, et une liste L qui représente un polynôme. En utilisant la fonction puiss, la fonction retourne l'image de x par le polynôme L.…
- Q4 Déterminer la complexité de la fonction valeur (x, L), avec justification.
- Q5 Écrire la fonction images (X, L) qui reçoit en paramètres une liste de réels X, et une liste L qui représente un polynôme. La fonction retourne la liste Y contenant les images des éléments de X par…
- Q6 On note le polynôme L^2 = L o L (L rond L, 2 fois) et L^n = L o L o L ... o L (n fois). Écrire la fonction compose (x, L, n) qui reçoit en paramètres un réel x, une liste L qui représente un…
Partie 2 · Partie I : Produit d'une chaîne matricielle
- Q7 Écrire la fonction minProduit (T, i, j) qui reçoit en paramètres une liste T représentant une chaîne de matrices, i et j deux indices dans T tels que i<j. La fonction retourne le nombre minimum de…
- Q8 Écrire la fonction minPrd (T, i, j) qui reçoit en paramètres une liste T représentant une chaîne de matrices, i et j deux indices dans T tels que i<j. En utilisant le principe de la mémoïsation, la…
- Q9 Écrire la fonction matriceC (T) qui reçoit en paramètre une liste T représentant une chaîne de matrices. En utilisant l'algorithme (1) décrit précédemment, la fonction retourne la matrice C.
Partie 3 · Partie II : Segmentation d'image · Taille et histogramme d'une image couleur
Partie 4 · Partie II : Segmentation d'image · Algorithme K-means
Partie 5 · Partie II : Segmentation d'image · Méthode Elbow et base de données
Le corrigé détaillé, question par question, est disponible gratuitement sur cette page.