Cours 2018-2019

Algorithmique 1 [IHDCB232]

  • 10 crédits
  • 30h+30h
  • 1er quadrimestre
Langue d'enseignement: Français
Enseignant: Vanhoof Wim

Acquis d'apprentissage

A l'issue de ce cours l'étudiant sera capable de raisonner formellement sur la correction d'un programme de petite taille et de calculer sa complexité. Et il aura une maîtrise de la logique de Hoare comme technique de preuve de correction. Il maîtrisera les techniques de bases de l'algorithmique.

Objectifs

L'objectif de ce cours est de familiariser l'étudiant à un raisonnement formel sur les programmes (en termes de correction et de complexité) et de lui enseigner une démarche rigoureuse de construction de programmes de petite taille.

Contenu

Ce cours introduit l'étudiant au raisonnement formel par rapport aux programmes. Nous étudions les concepts principaux sous-jacents à la spécification d'un programme. Nous apprenons des techniques qui permettent de prouver la correction d'un programme par rapport à sa spécification. Ensuite, et à partir de ces techniques, nous arrivons à une méthodologie de construction qui permet la réalisation d'un programme à priori correct. Nous introduisons également les notions de base derrière le calcul de complexité (en temps et en espace) d'un programme et on étudie quelques d'algorithmes de recherche et de tri. 


Pré-requis

Programmation 2 [IHDCB132] et Programmation 1 [IHDCB131]

Co-requis

Mathématiques pour l'informatique (2e partie) [IHDCB222]

Méthodes d'enseignement

Cours magistraux ex-cathédra avec des sessions de travaux dirigés sur papier.

Mode d'évaluation

Examen écrit comportant principalement des exercices (spécification, preuve de correction, construction de programmes selon les méthodologies vues au cours) ainsi que des questions de compréhension.

Sources, références et supports éventuels

  • W. Vanhoof, Méthodes de programmation, notes de cours.
  • K. Rosen, Discrete Mathematics and its applications (Chapter 1, Section 1.1, pp. 1 - 37), 4th edition, McGraw-Hill, 1999.
  • W.A. Wulf, M. Shaw, L.~Flon, and P. Hilfinger, Fundamental Structures of Computer Science. Addison-Wesley, 1981. Chapter 5, pp. 101 -143.
  • D. Gries, The Science of Programming, Springer-Verlag, 1981, Chapters 13 - 16, pp. 163 -215.
  • A. Aho and J. Ullman. Foundations of Computer Science, W.H. Freeman & Company, 1992.
  • K.R. Apt and E.R. Olderog. Verification of Sequential and Concurrent Programs. Springer-Verlag 1997.
  • R.C. BackHouse. Program Construction and Verification. Prentice-Hall, International series in computer science, 1986.
  • E.W. Dijkstra. A discipline of programming. Prentice-Hall, 1976.
  • The Science of Programming
  • Concepts fondamentaux de l'Informatique
  • Méthodes de programmation
  • Verification of Sequential and Concurrent Programs

Langue d'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
T. 081725252
F. 081724967
secretariat.info@unamur.be

Cycle

Etudes de 1er cycle