Compétence 2
Optimiser des applications informatiques
| Élément | Contenu détaillé |
|---|---|
| SAÉ concernées |
S1.01 – Comparaison d’approches algorithmiques Problématique : résoudre le problème du voyageur de commerce (8 villes) en minimisant distance et énergie via différentes heuristiques en C. S2.02 – Exploration algorithmique d’un problème Problématique : étudier, comparer et optimiser plusieurs variantes d’un algorithme pour un défi de recherche opérationnelle (heuristiques, méta-heuristiques). |
| Sujet étudié |
|
| Livrables remis |
|
| Équipe | Groupe de 2 : Ahmed Errebache & Adam Choujaa. |
| Rôle personnel (Ahmed) |
|
| Regard critique |
Point fort majeur : couverture complète du sujet : de la recherche brute aux
heuristiques avancées, avec comparaisons systématiques. Limite principale : forte complexité algorithmique et combinatoire ; certaines variantes (S2) manquaient d’optimisation sur grands jeux de données. |
2. Apprentissages critiques (AC) mobilisés
(Compétence 2 – Concevoir et modéliser les données)
Mobilisé : Oui Niveau auto-évalué : Maîtrise
Exemple : J’ai défini les nœuds « villes » et les arcs « distances » sous forme de matrice C (int dist[8][8]) à partir du cahier de charges du voyageur de commerce (main.c).
Mobilisé : Oui Niveau auto-évalué : En progrès
Exemple : Schéma conceptuel papier représentant un graphe orienté : les 8 villes en cercles et les routes en flèches pondérées (distance vs énergie).
Mobilisé : Oui Niveau auto-évalué : Maîtrise
Exemple : Pseudo-code du TSP transformé en C :
for each permutation P of {0…7}:
distance = sum(dist[P[i]][P[i+1]])
if distance < best: best = distance
puis implémenté dans main.c.
Mobilisé : Non Niveau auto-évalué : En progrès
Commentaire :
Les tests automatisés manquent : j’ai vérifié manuellement quelques parcours, mais pas de benchmark
systématique.
3. Ressources mobilisées
(Compétence 2 – Concevoir et modéliser les données)
Semestre 1
R1.01 – Initiation au développement
Apports : Logique algorithmique, pseudo-code, structures de contrôle (boucles, conditions).
Mobilisation : Traduction du TSP en C, implémentation du menu interactif et gestion de la matrice de distances.
R1.03 – Intro à l’architecture des ordinateurs
Apports : Gestion de la mémoire, représentation des données en tableaux, appels de fonction.
Mobilisation : Optimisation de la lecture/écriture de la matrice `dist[8][8]` et allocation statique en C.
R1.04 – Systèmes d’exploitation
Apports : Modes d’I/O, buffering, fonctionnement des appels système.
Mobilisation : Utilisation de `fopen()`/`fscanf()` pour charger les distances depuis un fichier texte.
R1.06 – Mathématiques discrètes
Apports : Théorie des graphes, permutations, complexité combinatoire.
Mobilisation : Sélection des permutations et estimation de la complexité O(n!); choix d’heuristiques gloutonnes.
R1.07 – Outils mathématiques fondamentaux
Apports : Algèbre des ensembles, matrices et transformations.
Mobilisation : Manipulation de la matrice de distances, calcul de sommes partielles pour parcours.
Semestre 2
R2.01A – Programmation objet (Java)
Apports : Classes, encapsulation, collections (List, Map).
Mobilisation : Prototype Java pour comparer structure C vs objets Java (liste de villes, poids).
R2.04 – Communication & bas niveau
Apports : Terminologie technique, protocoles de débogage.
Mobilisation : Rapport oral détaillant le fonctionnement interne du code C, pointeurs et pile d’appels.
R2.07 – Graphes
Apports : Représentation listée vs matricielle, trajets minimaux.
Mobilisation : Choix de la matrice d’adjacence pour TSP, évaluation des parcours heuristiques.
R2.09 – Méthodes numériques
Apports : Recuit simulé, algorithme génétique, optimisation continue.
Mobilisation : Implémentation d’un recuit simulé pour améliorer la solution gloutonne du TSP; comparaison des coûts.
4. Implication & déroulement
(Compétence 2 – Concevoir et modéliser les données)
SAÉ S1.01 – Voyageur de commerce (TSP)
Pour ce projet, Adam et moi avons utilisé Google Docs pour co-rédiger le cahier des charges et Discord pour synchroniser nos avancements. L’organisation globale manquait parfois de cohérence : Adam s’est moins impliqué en phase d’implémentation, tandis que j’ai reçu des retours positifs de M. Bourjij et M. Kerrien.
- Matrice de distances : écriture et initialisation de
int dist[8][8]. - Algorithmes : brute-force exhaustive puis heuristique gloutonne, toutes deux commentées.
- Menu interactif : gestion des options « charger », « exécuter », « comparer ».
Livrables :
• main.c (programme complet commenté)
• Présentation orale (slides + démonstration)
- Point fort : code C rigoureux, modularisé, respectant la séparation des responsabilités.
- Limite : manque de tests automatisés et couverture de cas limite (8 villes seulement).
5. Analyse des apprentissages
(Compétence 2 – Concevoir et modéliser les données)
Retour réflexif sur mes apprentissages
Lors du projet TSP en S1, j’ai vraiment consolidé mes bases en initiation au développement
et
en mathématiques discrètes. Passer du pseudo-code à l’implémentation C m’a appris à
formuler
clairement les structures de données (matrice dist[8][8]) et à gérer les permutations de
manière
systématique. J’ai compris l’importance de séparer l’analyse des données et la logique métier du code
d’interface.
L’écriture du menu interactif et des fonctions de chargement (file I/O en C) m’a renforcé dans la maîtrise des appels système et du buffering appris en systèmes d’exploitation. J’ai vu combien un I/O mal géré peut ralentir l’ensemble d’un algorithme, ce qui m’incite désormais à toujours profiler ces étapes.
Globalement, j’ai retenu que :
- Force : conception rigoureuse des structures et modularité du code – je peux désormais passer d’un modèle conceptuel (graphe TSP) à son implémentation sans pertes majeures.
- À approfondir : automatisation des tests et benchmarks (AC21.04). J’ai encore du mal à intégrer des suites de tests unitaires en C et à orchestrer mes scripts Python pour qu’ils couvrent automatiquement tous les cas.
Leçon tirée :
L’outil le plus puissant n’est rien sans une structuration claire des données. Avant même d’écrire une
ligne de code, il faut valider son modèle conceptuel et prévoir la suite de tests pour s’assurer de
sa robustesse et de sa performance.
6. Axes d’amélioration
(Compétence 2 – Voyageur de commerce & exploration algorithmique)
Observation : la structure de la matrice dist[8][8] était claire, mais
j’ai manqué
d’un schéma conceptuel formel (graphe, nœuds/arcs) avant de coder.
→ À améliorer : dessiner systématiquement un petit MCD/graphe papier ou UML pour valider la topologie avant l’implémentation, afin de détecter plus tôt les incohérences.
Observation : brute-force et heuristique gloutonne fonctionnent, mais sont très lentes dès 10+ villes.
→ À améliorer : explorer et comparer systématiquement d’autres heuristiques (recuit simulé, recherche tabou) dès le prototypage, et mesurer leurs complexités avant intégration.
Observation : les mesures CPU ont été réalisées manuellement, sans suite de tests.
→ À améliorer : mettre en place un script shell ou Makefile pour lancer automatiquement les benchs sur plusieurs jeux de données, et produire des rapports CSV/JSON.
Observation : README et commentaires C existent, mais absence de guide de démarrage et de conventions Git claires.
→ À améliorer : adopter Conventional Commits, ajouter un guide « make test » et « make run », et maintenir un CHANGELOG.md pour chaque version majeure.
Observation : les boxplots et ECDF sont utiles mais parfois confus (axes et légendes).
→ À améliorer : normaliser le style des graphiques, ajouter titres, labels, et une section « Comment lire ce graphique » dans le notebook.
Observation : l’implication d’Adam sur le projet TSP a été irrégulière, ce qui a généré des restructurations de dernière minute.
→ À améliorer : définir dès le début un rétroplanning partagé, répartir explicitement les tâches « implémentation » vs « tests/validation », et tenir deux stand-ups hebdomadaires pour synchroniser.
7. Traces choisies
(Compétence 2 – Optimiser des applications informatiques)
Trace 1 : Rendu complet SAE 1.02 (PDF)
Commentaire : Ce document illustre la présentation orale de la SAE 1.02, l’approche algorithmique et le sujet du voyageur de commerce.
Trace 2 : Extrait c (SAE 1.02 – Info)
// Définition d'une structure pour un point (coordonnées x, y)
typedef struct {
int x;
int y;
} Point;
// Définition d'une structure pour la carte contenant les points et la grille
typedef struct {
Point points[N]; // Liste des points
char grille[GRID_Y][GRID_X]; // Grille de caractères
int compteur; // Compteur pour le nombre de points
} Carte;
--------------------------------------------------------------------------------------
void genererChemins(int chemin[], int debut, int fin) {
static int compteur = 0;
if (debut == fin) {
for (int i = 0; i <= fin; i++) {
printf("%d", chemin[i] + 1);
}
printf(" ");
compteur++;
if (compteur % 10 == 0) {
printf("\n");
}
}
for (int i = debut; i <= fin; i++) {
int temp = chemin[debut];
chemin[debut] = chemin[i];
chemin[i] = temp;
genererChemins(chemin, debut + 1, fin);
chemin[i] = chemin[debut];
chemin[debut] = temp;
}
}
Commentaire : Extrait du code C utilisé pour générer toutes les permutations (chemins possibles) dans le problème du voyageur de commerce (TSP). Cette fonction affiche chaque chemin et compte le nombre total de solutions générées.
Trace 3 : Extraits de captures d’écran de l’application Voyageur de commerce
8. Originalité & qualité
(Compétence 2 – Comparaison d’approches algorithmiques)
Synthèse de l’originalité et de la qualité
-
Approche originale :
- Menu CLI dynamique proposant 10 choix interactifs ( génération aléatoire, affichage grille, plus proche voisin, heuristiques ) pour guider l’utilisateur pas à pas dans l’exploration du TSP.
- Combinaison de trois algorithmes (exhaustif, récursif, plus proche voisin) dans un même exécutable, permettant une comparaison immédiate des performances en un seul lancement.
- Option « Recharger » intégrée pour simuler contrainte de batterie dans le même programme, même si non finalisée entièrement.
-
Qualité du code :
- Structure modulaire : séparation claire en
main.c,tsp.hetheuristics.c, facilitant la maintenance. - Commentaires explicites en tête de chaque fonction et précondition/ postcondition pour garantir la lisibilité.
- Affichage ASCII soigné de la grille des distances et des solutions, avec numérotation alignée.
- Gestion des erreurs d’entrée et des choix utilisateur robuste (boucles while, vérifications scanf).
- Structure modulaire : séparation claire en
Points forts
- Expérience utilisateur CLI très guidée, avec menu clair et indications pas-à-pas.
- Capacité à basculer entre plusieurs stratégies algorithmiques au même instant, pour un gain de productivité d’analyse.
- Code organisé et commenté, prêt à être étendu par de nouveaux algorithmes ou contraintes métier.
Axes d’amélioration
- Finaliser la contrainte « Recharger batterie » pour générer automatiquement les points d’arrêt et recalculer la tournée.
- Optimiser la récursion exhaustive en introduisant un « branch and bound » pour réduire l’espace de recherche.
- Ajouter une visualisation graphique simple (ex. export SVG ou Python) pour illustrer le parcours choisi.
- Mettre en place des tests unitaires (Criterion ou CMocka) pour valider toutes les fonctions essentielles.