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.