Programme des cours 2019-2020
BINV1040-1  
Structures de données : bases, SD : bases
Durée :
72h Th
Nombre de crédits :
Bachelier en informatique de gestion6
Nom du professeur :
Annick DUPONT
Coordinateur(s) :
Annick DUPONT
Langue(s) de l'unité d'enseignement :
Langue française
Organisation et évaluation :
Enseignement au deuxième quadrimestre
Unités d'enseignement prérequises et corequises :
Les unités prérequises ou corequises sont présentées au sein de chaque programme
Contenus de l'unité d'enseignement :
  • Découvrir les structures de données classiques employées en informatique (pile, file, liste, arbre, ...) et en comprendre les forces et les faiblesses ;
  • Observer l'utilisation de structures de données pour mener à bien des applications classiques. Il peut s'agir d'applications concrètes comme une gestion de file d'attente ou plus techniques comme l'implémentation d'un algorithme de tri ;
  • Découvrir la notion de chaînage dans une table ou via pointeurs.
- Le vecteur   - La pile Via table Via chaînage   - La file Via table Via chaînage   - La liste Via simple chaînage Via double chaînage   - L'ensemble - Le dictionnaire non trié Via table de booléens Via table de hashing   - L'arbre L'arbre binaire L'arbre binaire de recherche Le B-Arbre
Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement :
  • Ecrire du code répondant aux spécifications données (cf. détails dans la partie "Compléments").
  • Être capable d'implémenter et d'utiliser les structures de données vues au cours (cf. détails dans la partie "Compléments").
  • Utiliser les techniques de programmation vues au cours (cf. détails dans la partie "Compléments").
  • Ecrire du code respectant les concepts orientés objets (cf. détails dans la partie "Compléments").
  • Ecrire du code clair (cf. détails dans la partie "Compléments").
  • Ecrire du code efficace (cf. détails dans la partie "Compléments")
Compétence(s) - Capacité(s): C1 - S'insérer dans son milieu professionnel et s'adapter à son évolution CA1.2 -Collaborer à la résolution de problèmes complexes avec méthode, rigueur, pro activité et créativité C3 - Mobiliser les savoirs et les savoir-faire propres à l'informatique de gestion CA3.1 -Concevoir, implémenter et maintenir des algorithmes répondant aux spécifications et fonctionnalités fournies CA3.4 -Concevoir, implémenter, administrer et utiliser avec maîtrise un ensemble structuré de données     Acquis d'apprentissage(s) terminaux visé(s): - Acquis d'apprentissage terminaux : AAT1. Concevoir des solutions informatiques efficaces qui répondent à des problèmes en maitrisant les structures de données véhiculées. C1-CA1.2 ; C3-CA3.1 et CA3.4 ; C4-CA4.4 * PROGRAMMATION ( AAT1) - Acquis d'apprentissage terminaux : AAT5. Se conformer aux bonnes pratiques du métier tout en restant critique. C1-CA1.4 ; C3-CA3.2 et CA3.5 ; C4-CA4.2 et CA4.3 et CA4.5 ; C5-CA5.3; C5-CA5.4 * QUALITE ( AAT5) - Acquis d'apprentissage terminaux : AAT7. Communiquer (y compris documenter) une solution selon les différents canaux (oraux ou écrits) en procédant avec rigueur et en garantissant la traçabilité. C2-CA2.2; C2-CA2.3 et CA2.4 ; C5-CA5 * COMMUNICATION ( AAT7) - Acquis d'apprentissage terminaux : AAT10. Respecter la déontologie, les règlements et les conventions en usage dans son milieu professionnel. C1-CA1.3 * PROFESSIONNALISME ( AAT10.)
Savoirs et compétences prérequis :
Activités d'apprentissage prévues et méthodes d'enseignement :
Mode d'enseignement (présentiel ; enseignement à distance) :
Trois séances de 2 heures sont prévues chaque semaine durant 12 semaines. Elles sont encadrées par 1 ou 2 professeurs.   Généralement le premier cours de la semaine débute par la diffusion d'un diaporama exposant la théorie nécessaire.   Sur papier, des exercices sont prévus pour comprendre le mécanisme de certaines structures de données ou les techniques utilisées pour les implémenter. Il s'agit souvent de schémas à compléter.   L'étudiant va découvrir les principales structures de données principalement par des exercices de programmation.   Les exercices de programmation se font en Java.
Lectures recommandées ou obligatoires et notes de cours :
Sur la plateforme d'apprentissage en ligne : - Diaporamas présentés au début de certaines séances d'exercices (indispensables) ; - Fiches d'exercices (indispensables)
Modalités d'évaluation et critères :
Responsable de l'évaluation: DUPONT Annick   Langue de l'évaluation: Français   Mode d'évaluation: (100%) Feux rouges/oranges/verts Durant le cours les professeurs présenteront une série d'erreurs graves qu'un étudiant ayant acquis les compétences de l'UE ne peut absolument pas commettre. Ces erreurs constituent des « feux rouges ».   De plus une série d'erreurs moins graves mais montrant tout de même un manque de maîtrise seront également relevées. Ces erreurs constituent des « feux oranges.   Evaluation continue formative Chaque semaine, tous les exercices proposés devront être soumis sur la plateforme d'apprentissage en ligne dans les délais prescrits. Les professeurs corrigeront quelques exercices. Une grille d'évaluation va ainsi se construire tout au long de l'année.   Les correcteurs mettront des points et indiqueront un feu rouge ou orange si au moins l'une des erreurs (moins) graves définies au cours de l'année apparait.   Il s'agit d'une évaluation formative. Les points ne comptent pas pour l'évaluation continue. Cette grille a comme but premier de permettre à l'étudiant d'évaluer ses acquis. Cependant, dans le cas d'un repêchage éventuel (voir conditions de validation de l'UE), cette grille sera consultée.   Examen L'examen est un examen écrit qui se déroule sur PC. Le questionnaire comporte plusieurs questions. Il s'agit principalement de programmation. L'environnement de travail proposé est Eclipse.   Un questionnaire papier demandant des schémas et/ou des ordres de complexité devra être rempli.   Chaque question sera corrigée séparément. Pour chacune de celles-ci, le professeur donnera une cote. En plus de celle-ci, les correcteurs indiqueront un feu rouge ou orange si au moins une des erreurs (moins) graves définies au cours de l'année a été commise.   En cas de feu rouge ou d'accumulation de feux oranges la note de l'examen sera automatiquement ramenée à 9,5.   Si l'étudiant n'a pas réussi au moins la moitié des questions, la note sera aussi ramenée à 9,5. Un 9,5 sera délibéré par l'ensemble des intervenants du cours qui décideront de la validation ou non de l'UE.     La note finale de l'UE est délibérée par les professeurs impliqués dans l'évaluation de celle-ci. En cas de lacune importante dans un ou plusieurs acquis d'apprentissage spécifique à l'UE, le jury de délibération se réserve le droit de ne pas valider l'UE ; càd d'attribuer une note d'UE différente de la cote de l'examen. Cette décision fera l'objet d'une justification de la part des professeurs.    
Stage(s) :
Remarques organisationnelles :
AAS 1 (Ecrire du code répondant aux spécifications données) : L'étudiant est capable de : 1) Utiliser l'environnement de développement utilisé lors des activités d'apprentissage (Eclipse) :
  • Créer un projet
  • Le compiler
  • Gérer les fichiers afin d'assurer leur intégrité (backup)
La solution doit correspondre exactement à la spécification donnée. Lorsque le programme est exécuté, il fournit le résultat attendu et il n'y a pas d'arrêt prématuré.   2) Trouver lui-même les cas particuliers et les traiter. Tester sa solution. Pour ce faire il doit être capable de fournir des jeux de tests complets. AAS 2 (Être capable d'implémenter et d'utiliser les structures de données vues au cours) :   L'étudiant est capable de : - Expliquer les spécificités de chaque structure de données vues. - Simuler « à la main » le fonctionnement de chacune d'elles au moyen de schémas. - Utiliser de façon adéquate chaque structure de données suggérée dans un énoncé pour répondre à un problème concret. - Utiliser efficacement l'API Java et déléguer correctement le travail aux classes existantes.   AAS 3 (Utiliser les techniques de programmation vues au cours) : L'étudiant est capable de : Implémenter de manière fonctionnelle et efficace toutes les techniques de programmation vues :
  • Les tables circulaires ;
  • L'utilisation de pointeurs pour implémenter des listes chaînées ;
  • Le hashing et les techniques d'overflow ;
  • Toute autre technique présentée durant les cours.
Présenter les mécanismes de fonctionnement de ces techniques via des schémas. AAS 4 (Ecrire du code respectant les concepts orientés objets) : L'étudiant est capable de : Appliquer à bon escient les concepts vus dans le cadre de l'UE I1020 « Analyse et   Programmation Orientée Objet » et les nouveaux concepts de l'orienté objet rencontrés (classes internes, principe de délégation, ...). AAS 5 (Ecrire du code clair) : L'étudiant est capable de : - Ecrire du code lisible et compréhensible par une autre personne que les auteurs. - Ecrire du auto-commenté grâce à des noms de variables et méthodes explicites. - Inclure une documentation précise des méthodes lorsqu'elle est demandée. - Commenter de façon brève mais pertinente les passages difficiles à comprendre. - Ecrire du code qui n'est pas inutilement compliqué. - Procéder spontanément à une découpe en sous-méthodes pour des méthodes complexes.   Introduire des méthodes pour éviter de la redondance dans le code. AAS 6 (Ecrire du code efficace) : L'étudiant est capable de : - Estimer l'ordre de complexité des méthodes apparaissant dans les interfaces des différentes structures de données vues, et ceci sans voir le code. - Produire une implémentation dont les ordres de complexités respectent ceux de la structure de données utilisée. Par exemple, l'étudiant sera pénalisé s'il fournit une méthode en O(N) alors qu'une méthode en O(1) existe. Pour des soucis de maintenabilité du code, le facteur multiplicatif peut être ignoré. C'est souvent le cas lorsqu'on découpe une méthode en sous-méthodes. Par exemple, l'étudiant ne sera pas pénalisé si sa méthode est en O(2xN) alors qu'une méthode en O(N) peut être écrite. Il sera néanmoins pénalisé s'il y a des instructions inutiles et/ou sur-consommatrice de travail alors que cela n'apporte rien à la maintenabilité du code.
Contacts :