Méthodes de conception de programmes

Langue
d'enseignement

Français

Préalables

Ce cours suppose acquises les compétences en programmation, algorithmique et structures de données visées par le cours LEPL1402 et les concepts de logiques visés par le cours LINFO1114.

Thèmes abordés

• Spécification de programmes simples, avec procédures et avec structures de données
• Logique et récurrence
• Preuve de programmes simples, avec procédures et avec structures de données
• Techniques de conception d'algorithmes
• Patrons de programmation

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :
1	Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : S1.I5 S2.2-3 Les étudiants ayant suivi avec fruit ce cours seront capables de imaginer un algorithme correct et efficace pour résoudre un problème donné créer et spécifier la conception d'un produit logiciel à l'aide d'une méthodologie de conception des programmes et de notations appropriées démontrer l'exactitude d'algorithmes simples utiliser une approche rigoureuse pour assurer l'exactitude du résultat, en utilisant des outils mathématiques

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».

Contenu

·         Spécification de programmes : pré/post-conditions, assertions, invariants et variants, correction partielle et terminaison

·         Logique des prédicats :  syntaxe, preuve formelle, tableau de preuve

·         Récurrence : preuves par induction, ensembles bien-fondés
·         Preuve de programmes : triplets de Hoare, calcul wp, méthode des assertions inductives,
·         Procédures : abstraction procédurale, récursion, effets de bord
·         Structures de données : fonction d'abstraction, invariant de représentation, induction structurale
·         Preuve automatisée de programmes : principes, outils
·         Conception d'algorithmes : division en sous-problèmes, diviser-pour-régner, programmation dynamique.
·         Patrons de programmation

Faculté ou entité
en charge

INFO