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)

Antoine FRENOY, Van Dat CUNG

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

Examens :

  • Période 1 : un examen écrit (E1) 2h en fin de période, tous documents papier autorisés
  • Période 2 : un examen écrit (E2) 3h en fin de période, tous documents papier autorisés
  • Session de rattrapage : un examen écrit (ES2) 2h tous documents papier autorisés, portant sur l'ensemble du cours.

Deux travaux pratiques en temps libre (projets): un pendant chaque période académique

  • Période 1 : TP1
  • Période 2 : TP2

Note de contrôle continu en période 1: CC1

A l'issue de la période 1, l'apprenti obtient la note NP1 :
NP1 = (2*E1 + 2*TP1 + CC1)/5

A l'issue de la période 2, l'apprenti obtient la note NP2 :
NP2 = (3*E2 + 2*TP2)/5

La note de la matière est alors calculée par :
NUE = (NP1 + NP2)/2

S'il y a lieu, a l'issue de la session de rattrapage, l'apprenti obtient la note NR :
NR = ( 3*ES2 + TP1 + TP2) /5
Cette note remplace la note de la matière (NUE)

Informations pour les bilans et jurys :

  • Notes envoyées à la scolarité : NP1, NP2, NR
  • Notes apparaissant dans le bulletin de notes :
    pour le bilan 1 : NB1 = NP1
    pour le bilan 2 : NB2 = NP2
    pour le jury de session 1 : NFS1 = NUE
    pour le jury de session 2, s'il y a lieu : NFS2 = NR

Calendrier

Le cours est programmé dans ces filières :

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

Informations complémentaires

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

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

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.