UCL - Etudes

Formations
Premier cycle
Deuxième cycle
Troisième cycle
Certificats (programmes non académiques)
Passerelles
Formation continue
Facultés et entités
Cadre académique
Réforme de Bologne
Accès aux études
Organisation des études
Lexique
Calendrier académique
Règlement des études et examens
Charte pédagogique
Renseignements généraux

Algorithmique et structures de données [LINF2121]
[30h+30h exercices] 5 crédits

English version

Version imprimable

Cette activité se déroule pendant le 1er semestre

Enseignant(s):

Pierre Dupont (coord.), Baudouin Le Charlier, Kim Mens

Langue d'enseignement :

français

Niveau :

cours de 2ème cycle

>> Objectifs (en terme de compétences)
>> Objet de l'activité (principaux thèmes à aborder)
>> Résumé : Contenu et Méthodes
>> Autres informations (Pré-requis, Evaluation, Support, ...)
>> Autres crédits de l'activité dans les programmes

Objectifs (en terme de compétences)

- Concevoir et réaliser un algorithme correct et efficace pour un problème donné.

- Faire un choix argumenté sur l'utilisation de telle ou telle structure de données ainsi que sur l'algorithme qui la manipule.

- Mettre en oeuvre des structures de données et les algorithmes associés dans des programmes Java de qualité professionnelle.

- Appliquer à bon escient les principes de la programmation orientée-objet tels que généricité, abstraction, composition et réutilisation.

- Travailler efficacement en équipe pour l'analyse du problème posé, la conception, l'implémentation et la documentation des programmes résolvant les problèmes posés.

Objet de l'activité (principaux thèmes à aborder)

- Mesures de complexité d'un algorithme et méthodes d'analyse de complexité.
- Méthodes de conception de programmes : spécifications et conception orientée-objet.
- Structures de données de base (listes, arbres, arbres binaires de recherche) : étude de leurs propriétés abstraites, de leurs représentations concrètes, de leur application et des principaux algorithmes qui les manipulent.
- Introduction aux Design Patterns liés à la manipulation de structures de données.
- Structures de données avancées (tables de hachage, tas, arbres binaires équilibrés, représentation et manipulation de graphes, traitement de données textuelles, dictionnaires).

Résumé : Contenu et Méthodes

- Complexité calculatoire.
- Arbres, arbres binaires de recherche, arbres AVL, 2-4 Trees.
- Dictionnaires et tables de hachage.
- Files de priorité et tas.
- Graphes (représentations, algorithmes de parcours, plus court chemin).
- Manipulation de données textuelles (arbres de suffixes, pattern matching, compression).
- Design patterns en Java.

Autres informations (Pré-requis, Evaluation, Support, ...)

- Pré-requis:
(1) Maîtrise de la programmation dans un langage orienté-objet tel que Java et connaissance de structures de données élémentaires (piles, files, listes, etc.)

OU

(1) LINF1150 Introduction à l'algorithmique et la programmation: 1ère partie B. LeCharlier
(2) LINF1251 Introduction à l'algorithmique et à la programmation : 2ème partie P. VanRoy

OU

(1) FSAC1650 Informatique T6

- Références
Ouvrage(s) obligatoire(s)
(1) Goodrich et Tamassia, "Data Structures and Algorithms in Java, Third Edition" , John Wiley & Sons, 2004.

Ouvrage(s) recommandé(s)
(2) Cormen T.H. et al. , "Introduction to Algorithms, Second Edition" , MIT Press, 2001. Brassard G. & Bratley P., "Fundamentals of Algorithms" , Prentice Hall, 1996.

- Modalités d'organisation
(1) La méthode pédagogique suivie dans ce cours est celle de l'Approche par Problèmes (APP) décrite à l'adresse http://www.fsa.ucl.ac.be/candis. Les étudiants travaillent alternativement en groupe (analyse du problème, point sur les connaissances théoriques à acquérir, définition des tâches de chacun, mise en commun de solutions partielles, analyse critique des résultats, etc.) et individuellement (étude et acquisition personnelle du contenu théorique, prise en charge d'une partie de la programmation et de la documentation des programmes, réflexion personnelle sur les questions posées, etc.). La majorité des séances de travail en groupe sont encadrées par un tuteur (le titulaire ou un assistant).

(2) Evaluation continue des travaux de groupes (réponses aux questions relatives à chaque problème donné, programme résultat et sa documentation).

(3) Examen écrit individuel

- Remarques:
Site WEB du cours: http://www.info.ucl.ac.be/notes_de_cours/LINF2121/

Autres crédits de l'activité dans les programmes

ECGE3DS/IG

Diplôme d'études spécialisées en économie et gestion (informatique de gestion - Master in Information Systems)

(5 crédits)

Obligatoire

ECGE3DS/SC

Diplôme d'études spécialisées en économie et gestion (Master in business administration) (Supply Chain Management)

(5 crédits)

INFO21

Première année du programme conduisant au grade d'ingénieur civil informaticien

(5 crédits)

Obligatoire

INFO22

Deuxième année du programme conduisant au grade d'ingénieur civil informaticien

(5 crédits)

LINF21

Première licence en informatique

(5 crédits)

LINF21/GN

Première licence en informatique (informatique générale)

(5 crédits)

Obligatoire

LINF21/GS

Première licence en informatique (informatique de gestion)

(5 crédits)

Obligatoire

LING2MS

Master en linguistique, à finalité spécialisée en ingénierie linguistique

(5 crédits)

MAP22

Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(5 crédits)

MAP23

Troisième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(5 crédits)

MATH21/G

Première licence en sciences mathématiques (Général)

(5 crédits)



Ce site a été conçu en collaboration avec ADCP, ADEF, CIO et SGSI
Responsable : Jean-Louis Marchand - Contact : secretaire@fsa.ucl.ac.be
Dernière mise à jour : 25/05/2005