Aller au contenu

Corrigé Informatique ITC CCINP 2025

sujet

Remarques - Mettre une variable non définie plus haut à droite d'un signe = renvoie une erreur. - Les algorithmes de base sur les listes : trouver le maximum, somme de valeur, calcul de moyenne, tri doivent être connus. - Les algorithmes de tri suivants sont au programme: - à compléxité quadratique : insertion, sélection, à bulles - à complecité \(\mathcal{O}(n.log(n))\) : fusion, rapide.

Partie I - Gestion des randonnées dans une base de données⚓︎

Remarques - JOIN s'utilise avec des relations (tables), pas des attributs. - NATURAL JOIN effectue une jointure entre deux tables sur l'ensemble des attributs ayant un même nom. Dans cet exercice, cela effectuerait une jointure sur les attributs Id. Cela n'a pas de sens, ils ne représentent pas la même chose. - GROUP BY sert à utiliser les fonction d'agrégat (SUM, AVG, MAX, MIN, COUNT) sur des regroupement de n-uplets plutôt que sur toute la relation.

Q1) Titre n'est pas une option pour être une clé primaire. En effet, plusieurs randonnées peuvent avoir le même titre et une clé primaire doit être unique pour garantir un dépendance fonctionnelle. Id est le choix priviligié de clé primaire.

Q2) IdAuteur est une clé étrangère de Randonnee qui référence Auteur.Id, clé primaire de Auteur.

Q3)

SQL
1
2
3
SELECT Titre, Lieu, Distance
FROM Randonnee
WHERE Type = "Pied"

Q4)

SQL
1
2
3
4
5
SELECT IdAuteur, COUNT(*) AS nb_activités
FROM Randonnee
WHERE Type = "Pied" AND Niveau = 3
GROUP BY IdAuteur
ORDER BY nb_activités DESC

Q5)

SQL
1
2
3
4
SELECT Pseudo, Titre
FROM Auteur
JOIN Randonnee
ON IdAuteur = Auteur.Id

Q6)

SQL
1
2
3
4
5
6
7
8
SELECT Prenom, Nom
FROM Auteur
JOIN Randonnee
ON IdAuteur = Auteur.Id
WHERE Type = "Cheval"
GROUP BY Auteur.Id
ORDER BY COUNT(*) DESC
LIMIT 1

Partie II - Quelques calculs de dénivelés⚓︎

Dans cette partie, les fonctions sont données avec leur signature pour plus de compréhension. Pour les copies il était demandé de ne pas recopier les signature.

Q7) import gpxpy as g ou simplement import gpxpy.

Q8) La fonction mystère calcule la somme des altitudes des points de iti puis divisent par le nombre de points. C'est donc l'altitude moyenne : 105

Q9)

Les résultats de compléxités doivent être justifiés. Dire qu'il y'a \(n\) tours de boucle ne suffit pas à avoir une compléxité en \(\mathcal{O}(n)\), il faut en plus que chaque tour est une compléxité en \(\mathcal{O}(1)\), c'est à dire qu'il ne soit composé de une ou pluieurs instructions élémentaires.

La ligne 2 a une complexité en \(\mathcal{O}(1)\)

  • Chaque tour de boucle a une complexité en \(\mathcal{O}(1)\), il y a n tours de boucles, donc la complexité totale de la boucle est en \(\mathcal{O}(n)\).
  • le calcul ru return est aussi en complexité constante : \(\mathcal{O}(1)\)

Ainsi la complexité de la fonction est linéaire \(\mathcal{O}(n)\) en la taille de la liste donnée en entrée.

Q10)

Python
1
2
3
4
5
6
def altitude_maximale(iti:itineraire) -> float:
    lat,long,alt_max = iti[0]
    for (lat,long,alt) in iti:
        if alt > alt_max:
            alt_max = alt
    return alt_max

Le résultat ci-dessous, écrit par compréhension est bien sûr le même. Cependant, il faut en maîtriser la syntaxe. Je ne la conseille pas pour un concours.

Python
1
2
def altitude_maximale(iti:itineraire) -> float:
    return max([alt for _,_,alt in iti])

Q11)

Python
1
2
3
def denivele_global(iti:itineraire) -> float:
    lat, long, depart = iti[0]
    return altitude_maximale(iti) - depart

II.1 - Premier calcul de dénivelé positif⚓︎

Q12)

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def denivele_positif_cumule(iti:itineraire) -> float:
    lat1, long1, alt1 = iti[0]
    denivele_positif = 0
    for point in iti[1:]: # [1:] pour prendre la liste à partir du second élément
        lat2, long2, alt2 = point
        diff_deniv = alt2 - alt1
        if diff_deniv > 0:
            denivele_positif += diff_deniv
        alt1 = alt2 # pour passer au prochain point

    return denivele_positif

II.2 - Lissage des altitudes⚓︎

Q13)

Python
1
2
3
4
5
6
def alt_glissante(liste_alt:list, p:int) -> list:
    lissee = []
    for i in range(len(liste_alt)):
        fenetre = liste_alt[i:i+p] # la tranche gère automatiquement la borne droite en fin de liste
        lissee.append(sum(fenetre)/len(fenetre))
    return lissee

Q14) Dans la boucle for les deux instructions sont en \(\mathcal{O}(p)\) (une affectation d'une tranche de taille p et le calcul d'une somme de p éléments suivie d'une division \(\mathcal{O}(1)\). A noter que p est un majorant car les fenetres deviennent plus petites en fin de liste.

Il y a n tours de boucles.

La complexité est alors en \(\mathcal{O}(n.p)\) où n est la taille de liste_alt.

II.3 - Utilisation d’altitudes de référence⚓︎

Q15) lat_ref et long_ref sont des listes (initialisées avec []). Elles contiennent respectivement les latitudes et longitudes (type float) du dictionnaire de référence dem (Digital Elevation Model).

Q16) auxiliaire a pour signature:

auxilaire(x: list, y: list) -> list

En effet, les tests x == [ ] et y == [ ] indiquent que x et y sont de type list. L'utilisation de la méthode pop sur x et y est donc cohérente, bien que non caractéristique des listes.

Les return x et return y indiquent alors que le type de retour est aussi list. Et la méthode append est aussi cohérente avec les listes.

et principal(x: list) -> list

En effet, le slicing des lignes 17 et 18 indiquent que x est une liste (ou un tuple) cependant l'utilisation de x1 et y1 (les tranches) dans auxiliaire indique que x est une liste. Le type de retour est celui de auxiliaire donc une liste.

Q17) La fonction principal s'appelle elle-même. Il s'agit donc de de code récursif. Elle s'appelle sur deux sous-listes de taille a peu près égale à la moitiée de la taille initiale. Elle utilise la méthode diviser pour régner. Cette méthode permet d'obtenir une complexité en \(\mathcal{O}(n.log(n))\).

Q18) La fonction principal s'arrête quand elle s'appelle sur une liste de taille inférieure ou égale a 1. Comme les appels récursifs se font sur des tailles (entières) inférieures à la moitié le cas de base finira par être atteint. La ligne 19 avec l'appel à auxiliaire doit aussi se terminer. C'est le cas car les appels récursifs se font en décrementant la taille de la somme des listes x et y de 1, la condition x == [] ou y == [] est donc garantie après un nombre fini d'appels récursif.

Q19) La fonction auxiliare est une fonction de fusion de deux listes triées. principal est donc une fonction qui utilise le tri fusion pour trier une liste.

Q20)

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def ref(valeur: float, liste_ref: list) -> float:
    # on détermine ind_deb et ind_fin tels que
    # liste_ref[ind_deb] < valeur <= liste_ref[ind_fin]
    # avec une méthode par dichotomie
    ind_deb = 0
    ind_fin = len(liste_ref) - 1

    while ind_deb < ind_fin - 1:
        k = (ind_deb + ind_fin) // 2
        if valeur <= liste_ref[k]:
            ind_fin = k
        else:
            ind_deb = k

    # on détermine le plus proche
    if liste_ref[ind_fin] - valeur < valeur - liste_ref[ind_deb]:
        return liste_ref[ind_fin]
    else:
        return liste_ref[ind_deb]

Q21)

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def standardise(liste_parcours:itineraire) -> itineraire:
    standard = [] # itinéraire vide
    for lat, long, alt_gps in liste_parcours:
        lat_proche = ref(lat, lat_ref)
        long_proche = ref(long, long_ref)

        alt_standard = dem[(lat_proche, long_proche)]

        # ajout du point standardisé dans le nouvel itinéraire
        standard.append((lat, long, alt_standard))

    return standard

Remarque Ce code ne fonctionna qu'avec la condition que le dictionnaire dem possède bien toutes les clés d'un quadrillage complet. Cette condition est supposée réalisée en II.3. Sinon il faudrait rechercher le point de coordonnées le plus proche parmis les clés de dem et non séparément la latitude et la longitude.