Ensimag Rubrique Formation 2022

Algorithmique et programmation - 3MM1AP

  • Volumes horaires

    • CM 36.0
    • Projet -
    • TD 36.0
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 6.0

Objectif(s)

Ce cours prolonge et approfondit les compétences des apprentis en algorithmique et programmation. Il couvre la programmation impérative structurée et la programmation orientée objets, l'algorithmique et les structures de données élémentaires jusqu'à des techniques algorithmiques plus avancées, tout en insistant sur les raisonnements (assertions, analyse de coût) utiles à l'élaboration des algorithmes.

Responsable(s)

Xavier NICOLLIN

Contenu(s)

  • Programmation impérative : implémentation des structures de données élémentaires en langage C (période 1)
  • Programmation orientée objets : bases (concept d'objet, écriture de classes et utilisation d'objets), polymorphisme, héritage, type abstrait d'ensembles d'objets (conteneurs et itérateurs), utilisation de bibliothèques de composants; avec implémentation en Java (période 2)
  • Algorithmique et structures de données : parcours séquentiels ; structures de données simples (tableaux, piles, files, chaînages) et plus complexes (tables de hachage et dictionnaires, graphes, arbres, files de priorité); récursivité; introduction à la programmation dynamique
  • Analyse d'algorithmes : complexité, preuve de terminaison (convergent), preuve de correction (invariant de boucle); plus généralement initiation aux raisonnements par assertions sur les programmes

Prérequis

  • Les programmes en algorithmique et programmation des DUT informatiques;
  • Une pratique du langage C (incluant tableaux, pointeurs, fonctions et récursivité)
  • Une bonne maitrise des programmes de mathématique du lycée, notamment en ce qui concerne l'arithmétique et les probabilités

Contrôle des connaissances

Evaluation : 50% de Devoir à la maison + TP notés et 50% de Examen Ecrit (N.C.)

Rattrapage : 40% de Devoir à la maison + TP notés (note reportée) et 60% de Examen Ecrit (2h)

Session 1 :

  • Période 1 :
    - TP1 sur temps libre
    - note de contrôle continu CC1
    - examen écrit (E1) 2h, tous documents papier autorisés
    - NP1 = (2*E1 + 2*TP1 + CC1)/5
  • Période 2 :
    - TP2 sur temps libre
    - examen écrit (E2) 3h, tous documents papier autorisés
    - NP2 = (3*E2 + 2*TP2)/5
  • N1 = (NP1 + NP2)/2

Session 2 :

  • examen écrit (ET2) 2h tous documents papier autorisés, portant sur l'ensemble du cours.
  • N2 = (3*ET2 + TP1 + TP2)/5

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2025/2026

Informations complémentaires

Code de l'enseignement : 3MM1AP
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

  • Equipe Programmation-logiciel
  • Equipe Algorithmique-Mathématiques discrètes

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

H. ABELSON, G.SUSSMAN, J.SUSSMAN : "Structure and interpretation of
computer programs", McGraw-Hill, 1985 ; "Structure et interprétation
des programmes informatiques", InterEditions, 1989

C. FROIDEVAUX, M.C.GAUDEL, M.SORIA : "Types de données et
algorithmes", McGraw-Hill, 1990

A. V. Aho, J. E. Hopcroft, J. D. Ullman : Data Structures and
Algorithms, Addison-Wesley, 1985.