Informatique 2 [ LFSAB1402 ]

FSAB1401: Informatique 1 ou équivalent

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 oeuvre en Java de programmes de complexité moyenne
• Méthodes de tests et de validation de programmes

A l'issue de cet enseignement, les étudiants seront en mesure de :

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

L'évaluation comprend 2 composantes: une interrogation intermédiaire en milieu de quadrimestre et un examen final (examen écrit)au terme du quadrimestre. La note globale résulte de la combinaison des 2 notes.

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é.

• Types abstraits de données
• Types abstraits linéaires (piles, files, listes, etc. ') 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, etc.')
• 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 oeuvre de méthodes de test et de validation

Support: Dossiers de travail sur les différentes parties du cours (version disponible sur le site, et version papier)

Peter Van Roy et Seif Haridi, PROGRAMMATION: Concepts, techniques et modèles, Dunod, 2007

Peter Van Roy et Seif Haridi, Concepts, Techniques, and Models of Computer Programming, MIT press, 2004