XTI102 - Structures de Données Avancées

Ceci est le site contenant les ressources pour le cours XTI102 - Structures de Données Avancées dispensé aux étudiants de première année B1/L1 du Programme Experts de l’Efrei.

1 Notes de mise à jour

🥳 Mise à jour pour la partie 6 (31/12/2025)

La partie 6 du projet Fork Knight a été ajoutée, portant sur la simulation complète du système de matchmaking. Vous pouvez désormais fusionner la pull request correspondante dans votre dépôt GitHub pour récupérer les fichiers nécessaires.

Fichiers modifiés:

  • .gitattributes : Ajout des règles de fusion pour les nouveaux fichiers de simulation
  • test-local.sh : Ajout de la délégation aux tests de simulation pour la partie 6
  • CmakeLists.txt et Makefile : Inclusion des nouveaux fichiers de simulation dans le processus de compilation

Nouveaux fichiers ajoutés (à ne pas modifier) :

  • headers/simulation.h : Déclaration de l’API de simulation
  • src/simulation.c : Implémentation de l’API de simulation
  • src/test-simulation.c : Scénarios de test pour valider la simulation
  • test-simulation.sh : Script de test dédié pour la simulation complète

Que fait test-simulation.sh ?

  • ✅ Compile automatiquement le binaire de simulation
  • ✅ Exécute deux fois la simulation avec les mêmes paramètres
  • ✅ Compare les sorties pour vérifier que vous avez deux exécutions identiques
  • ✅ Affiche des messages d’erreur détaillés si besoin

Voici les scénarios testés :

Scénario Description Joueurs Rounds Fichier de sortie
1 Test basique 50 10 output/scenario1_result.txt
2 Test intermédiaire 100 15 output/scenario2_result.txt
3 Stress test 100 20 output/scenario3_result.txt
4 Convergence rapide 50 5 output/scenario4_result.txt
5 Stabilisation 100 30 output/scenario5_result.txt

✅ Critères de validation

  1. Compilation sans erreurs ni warnings
  2. Exécution sans crash des 5 scénarios
  3. Fichiers de sortie générés dans output/
  4. Déterminisme : Les deux exécutions doivent produire des sorties identiques

❌ Erreurs courantes :

  • Fichiers de sortie manquants
  • Segfaults lors de l’exécution
  • Sorties différentes entre les deux exécutions (Vérifiez que srand()n’est pas appelé dans simulateMatch())

À faire :

  1. Fusionner la pull request dans votre dépôt GitHub.
  2. Exécuter ./sync.sh pour récupérer les modifications localement.
  3. Lancer les tests de simulation avec ./test-simulation.sh et vérifier que tout passe correctement.
⚠️ Soumissions Github temporairement indisponibles (17/12/2025)

En raison d’une indisponibilité temporaire du service de validation des soumissions GitHub, les soumissions pour le projet Fork Knight via le script submit.sh vont nécessairement échouer. Ce n’est pas lié à votre code.

Ce que vous devez faire :

  1. Récupérer la dernière version du template en fusionnant la pull request correspondante dans votre dépôt GitHub. Dans le cas où vous avez des conflits de fusion, contactez le coordinateur du module.
  2. Synchroniser votre dépôt local avec ./sync.sh.
  3. Continuer à travailler sur votre code localement, et effectuer des tests locaux avec ./test-local.sh <partie>.
  4. Pour le moment, ne tentez pas de soumettre vos travaux avec ./submit.sh car cela échouera.

Nous vous informerons dès que le service sera rétabli. Merci de votre compréhension.

🔧 Correctifs Tests - Parties 4 & 5 (16/12/2025)

Problèmes corrigés :

  • Fuites mémoire dans les tests : Les tests des parties 4 et 5 ne libéraient pas correctement les joueurs créés
  • Rapports Valgrind : Les rapports de validation GitHub Actions n’affichaient pas les logs Valgrind complets

Action requise :

Si vous avez déjà soumis les parties 4 et/ou 5, acceptez puis fusionnez la pull request dans votre dépôt GitHub. Ensuite effectuez faîtes un ./sync.sh pour récupérer les correctifs localement.

./sync.sh
./test-local.sh 4
./submit.sh 4

Les nouveaux rapports afficheront maintenant les détails Valgrind si des fuites persistent dans votre code.

Les pénalités de retard ne seront pas appliquées pour les soumissions de la Partie 4

2 Syllabus

2.1 Objectifs du cours

Ce cours a pour objectif de renforcer la capacité des étudiants à concevoir, analyser et implémenter des solutions algorithmiques efficaces en langage C, tout en s’appuyant sur des structures de données dynamiques avancées et des algorithmes fondamentaux.

Il s’inscrit dans la continuité du cours XTI101, et vise à doter les étudiants des bases solides nécessaires pour structurer et manipuler des données de manière pertinente et performante.

Le cours sera fortement axé sur la pratique avec des travaux dirigés et un projet de groupe incrémental, permettant aux étudiants d’appliquer les concepts théoriques à des problèmes concrets.

Compétences visées
  • Identifier et décrire les structures de données dynamiques classiques
  • Énoncer les principes de la récursivité et les cas d’usage courants
  • Expliquer le fonctionnement des structures de données dynamiques, leurs avantages, inconvénients et cas d’utilisation
  • Implémenter en langage C les structures de données vues en cours dans le cadre d’un programme fonctionnel
  • Intégrer et adapter les algorithmes étudiés dans la résolution de problèmes concrets.
  • Concevoir un programme modulaire intégrant plusieurs structures et algorithmes pour répondre à un besoin donné (via le projet de groupe).

2.2 Contenu

  1. Principes de la récursivité
  2. Listes chaînées : principes de base et implémentation
  3. Listes avancées : listes head-tail, listes circulaires, listes doublement chaînées
  4. Projet de groupe incrémental

2.3 Séquences pédagogiques

Organisation du module

Ce module est organisé en 6 séances de 5 heures chacune, réparties entre mi-novembre et début janvier. Les activités comprennent une partie théorique (cours), des travaux dirigés et des travaux pratiques essentiellement consacrés au projet de groupe.

Séances Dates Partie théorique Travaux Dirigés Partie Projet Évaluation
Séance 1 Semaine du 17/11 Récursion TD1 Partie 1 -
Séance 2 Semaine du 24/11  Listes chaînées - Bases TD2 Partie 2 -
Séance 3 Semaine du 01/12 Listes chaînées - Avancées TD3 Partie 3 -
Séance 4 Semaine du 08/12 File de priorité - Partie 4 -
Séance 5 Semaine du 15/12 - - Partie 5 et 6 Évaluation écrite
Séance 6 Semaine du 05/01 - - - Oral de projet

2.4 Outils et ressources

  • Langage de programmation : C
  • Environnement de développement : IDE au choix mais CLion recommandé
  • Système de gestion de version : Git et GitHub
  • Système de suivi de projet : GitHub Classroom

2.5 Modalités d’évaluation

Évaluation

La note finale du module sera calculée comme suit :

  • 50% : Évaluation écrite de type DE (semaine du 15/12) sur les concepts théoriques et pratiques abordés dans le module.
  • 50% : Évaluation pratique sur l’ensemble du projet de groupe, incluant une présentation orale (semaine du 08/01) dont la notation détaillée est fournie dans les fiches correspondants à chaque partie du projet.

2.6 Équipe enseignante et personnes ressources

Responsable de formation (à contacter pour toute question administrative/sur la formation)
  • DEV/IN : Léa Delacroix
  • ICS/CS : Zorica Kljajevic
  • B1-BDX : Marion Nazarre
Responsables pédagogique (à contacter pour toute question en lien avec le module)
  • Responsable de niveau B1/L1 : Asma Gabis
  • Coordinateur du module : Rado Rakotonarivo
Prise de contact
  • Pour toute question relative au module, privilégiez l’email avec un objet clair (ex : “XTI102 - Question sur le projet”) et en précisant votre section et groupe.
  • Contacter en priorité vos enseignants référents en mettant en copie le coordinateur du module.
Demande de permanence

Vous pouvez contacter les enseignants suivants pour demander/organiser des séances de permanence individuelles ou en petits groupes :

Équipe enseignante

Section Groupe Enseignant.e.s
B1 Cyber 1 (CS1) Safwan Chandeb, Ikhlas Mastour
B1 Cyber 2 (CS2) Mourad Kmimech, Imen Rjab
B1 DEV 1 (DEV) Rado Rakotonarivo, Lotfi Gaaloul
L1 Cyber 1 (ICS) Rado Rakotonarivo, Imène Ben Kermi
L1 DEV 1 (IN) Mourad Kmimech, Kamel Chabchoub
B1-BDX Cyber (CS) Alexandre Blanché, John Dreyfus
B1-BDX DEV (DEV) Kais Baccour, Olivier Villain