Algorithmique avancée en C SEOC - 4PMIGL11

Informations générales

  • Volumes horaires

    • CM 2.0
    • Projet 0
    • TD 28.0
    • Stage 0
    • TP 0
    • DS 0

    Crédits ECTS

    Crédits ECTS 0.0

Objectif(s)

Ce cours vise à amener les étudiants en provenance de Phelma à un haut niveau en algorithmique et programmation, en préparation de toute la suite de la filière et des futurs débouchés.

Contact François CAYRE

Contenu(s)

Ce module vise la réalisation par les étudiant(e)s, en petit groupe, d'une bibliothèque de structures de données usuelles en langage C, l'occasion d'introduire des techniques et des conceptions de haut niveau de réutilisabilité et de performance, testées et validées dans un environnement (fourni) de qualité semi-professionnelle. Toutes les structures de données seront génériques, dans les limites permises par le langage.

L'évaluation sera réalisée sur le fondement (1) d'un code C qui doit prouver lui-même ses caractéristiques et propriétés et (2) d'un rapport devant rendre compte de l'explication des performances atteintes par différentes stratégies d'implantation.

Le niveau visé en sortie est exigeant et n'est plus tant seulement scolaire que résolument (semi-)professionnel.

L'utilisation des IA sera réservée à l'obtention de précisions théoriques ou techniques hors des séances encadrées.

  1. Programmation
  • Pointeurs génériques et méta-données cachées
  • Structures intrusives et pseudo-héritage
  • Préprocesseur et méta-programmation, possibilités et limites
  • Validation : tests unitaires, fuzz testing, jumeau numérique, benchmarking et relation avec le matériel
  1. Algorithmique
  • Types abstraits et généricité
  • Structures linéaires (deques, etc.)
  • Structures arborescentes, stratégies d'équilibrage (aucune, rouge-noir, treaps, splay)
  • Structures associatives (adressages fermé vs. ouvert, pierres tombales ou pas, tables Robin-Hood)
  • Application aux ensembles génériques
  1. Bonus
  • Tables vectorisées (conception de type Abseil + SIMD)


Prérequis

Premiers éléments de programmation en langage C.

Structures de données de base (linéaires, arborescentes, associatives).

Contrôle des connaissances



Informations complémentaires

Cursus ingénieur->Filière SEOC->Semestre 7

Bibliographie

Voir bibliographie dans le sujet.