Objectifs (en terme de compétences)

A l'issue de cet enseignement, les étudiants seront en mesure de :
de faire un choix justifié entre plusieurs représentations des informations et plusieurs algorithmes pour les traiter,
de raisonner sur des (fragments de) programmes : complexité des algorithmes et efficacité des programmes les mettant en œuvre, raisonnement récursif,
d'appliquer des principes de modélisation orientée-objet,
de concevoir et d'appliquer des méthodes de test d'un programme.

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

Les principaux thèmes abordés lors de cet enseignement sont :
Techniques d'analyse de la complexité calculatoire d'un algorithme
Techniques de raisonnement sur des programmes
Modélisation orientée-objet
Structures de données linéaires et arborescentes
Algorithmes récursifs
Mise en œuvre en Java de programmes de complexité moyenne
Méthodes de tests et de validation de programmes

Résumé : Contenu et Méthodes

Types abstraits de données
Types abstraits linéaires (piles, files, listes, …) et leurs applications
Techniques de représentation des types abstraits linéaires
Modélisation orientée-objet (héritage, composition et réutilisation)
Préconditions, postconditions, invariants
Techniques de raisonnement (règles de déduction, preuves de terminaison, …)
Notions de complexité calculatoire
Analyse de la complexité temporelle d'un algorithme
Analyse de la complexité spatiale d'une structure de données
Formulation récursive d'une solution et algorithmes récursifs
Types abstraits arborescents (arbres binaires) et leurs applications
Techniques de représentation des arbres binaires
Mesures de l'efficacité d'un programme
Conception et mise en œuvre de méthodes de test et de validation
Les méthodes utilisées privilégieront l'apprentissage actif des étudiants. Les modalités précises de mise en oeuvre d'une participation active de l'étudiant dans son apprentissage sont laissées aux titulaires, dans le respect des orientations pédagogiques de la Faculté.

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

FSAB 1401 Informatique 1