INFO0902-1 - Structures de données et Algorithmes (ULg)
Titulaire du cours: Sébastien Collette (ULB) Assistant: Gérard Dethier (ULg) Les cotes sont disponibles ici. Les cours auront lieu le jeudi matin (local S74 du bâtiment B4 - Amphithéâtres de l'Europe). Voir planning ci-dessous. Description Ce cours a pour objectif d'acquérir les bases de l'algorithmique. Nous insisterons principalement sur des méthodes de résolution de problèmes algorithmiques (diviser-pour-rêgner, glouton, programmation dynamique, recherche exhaustive) et sur les structures de données les plus fréquement utilisées (arbres binaires de recherche, tables de hachage, tas...). L'approche se voudra scientifique: nous tenterons de déterminer systématiquement des bornes sur le temps d'exécution et d'exprimer les comportements asymptotiques de nos algorithmes. Planning Le plan du cours évoluera en cours d'année, en fonction de la progression des étudiants. Les slides des cours seront disponibles avant chaque séance. Tous les détails ne sont pas sur les slides, imprimez-les avant le cours afin de pouvoir prendre note facilement.  Les groupes pour les labos et les énoncés seront disponibles sur la page de l'assistant. Cours Projet     Laboratoires (sur PC) Date Intitulé   Date Intitulé 10/02/11 9h-11h Introduction Structures de données élémentaires pdf 10/02/11 11h-13h Syntaxe du langage C pdf 17/02/11 11h-13h Arbres binaires de recherche ressources pdf   groupe 1: 16/02/11 16h-18h ou groupe 2: 17/02/11 9h-11h Pointeurs et allocation mémoire pdf 24/02/11 11h-13h Tas et tris avec les arbres ressources pdf Algorithmes sur les arbres (exercices) pdf   23/02/11 16h-18h ou 24/02/11 9h-11h Listes doublement liées pdf 03/03/11 11h-13h Résolution de problèmes (approche gloutonne et programmation dynamique) ressources pdf 10/03/11 11h-13h Résolution de problèmes (suite) pdf Enoncé  P1 pdf code source 17/03/11 11h-13h Tables de hachage ressources pdf Séance de questions/réponses de 10h à 11 h dans le local du cours. 24/03/11 11h-13h Tables de hachage (suite) Notions de complexité pdf Séance de questions/réponses de 10h à 11 h dans le local du cours. 31/03/11 11h-13h Notions de complexité (suite) et splay trees pdf Remise P1 Enoncé P2 pdf 07/04/11 11h-13h Graphes et plus courts chemins ressources pdf Vacances de printemps 28/04/11 11h-13h Graphes et plus courts chemins (suite) Séance de questions/réponses de 10h à 11 h dans le local du cours.     05/05/11 11h-13h Arbres couvrants et tri topologique ressources pdf Remise P2 Enoncé P3 pdf 12/05/11 11h-13h Flots et autres algorithmes de graphes ressources pdf 19/05/11 11h-13h Conclusion sur les arbres,  comparaison des différentes approches, questions d'examen. pdf Séance de questions/réponses de 10h à 11 h dans le local du cours. 26/05/11 11h-13h Remise P3 Projets Projet 1 - Arbres binaires de recherche : énoncé - correction - cotes Projet 2 - Résolution de problèmes : énoncé - correction Projet 3 - Graphes : énoncé Les projets auront une grande importance pour ce cours. Tout d'abord, ils vous permettront de mettre en pratique la matière vue. Ils seront également une opportunité d'apprendre à résoudre des problèmes algorithmiques. Quelle démarche adopter face à un problème inconnu? Quelle structure de données choisir? Enfin, les projets interviendront significativement dans la note de fin d'année (30%), je vous suggère donc d'y apporter un soin tout particulier. Examen Voici une liste de questions type, similaires à celles que vous pourriez avoir à l'examen.