Programme de formation

• Objectifs

  Les objectifs sont en prolongement de ceux du cours ''Algorithmique et structures de données 1'', en s'appliquant à un domaine de connaissances plus vaste.

  A la fin du cours, l'étudiant a acquis les compétences suivantes :

  • Ecrire et utiliser des structures de données complexes, et des algorithmes avancés impliquant des arbres
  • Analyser un problème et concevoir une solution algorithmique efficace
  • Exploiter les principes de hachage, algorithme probabiliste, et programmation dynamique
  • Pratiquer la programmation Java, en professionnel (Java collections, stream programming...)
  • S'initier aux divers outils du programmeur (tests, aide au diagnostic, debugging, analyse statique, code coverage...)
• Contenu

  • Complexité amortie, complexité espérée.
  • Structures d'arbre : nodes, implicit chaining, left-child-right-sibling ...
  • Heap, Skew-Heap
  • Binary Search Tree, SplayTree, Treap, B-Tree
  • Simulation discrète
  • Pseudo-pointeurs
  • Ensembles disjoints (union-find)
  • String searching, edit distance, compression (Huffman, Lempel-Ziv)
  • Quelques casse-tête (coding interview)
  • Pratique de la programmation Java : code coverage, Java streams, ...

Forme d'enseignement et volume de travail

Spécification du cours

Modalités d'évaluation

• Contrôle continu: travaux écrits, TP/évaluation de rapports

Mode de calcul de la note de cours

La note du contrôle continu est la moyenne pondérée des évaluations du semestre (+/- un possible ajustement lié aux TPs). En cas d'examen de révision, la note finale du cours est la moyenne arithmétique de la note du contrôle continu et de celle de l'examen de révision.

Enseignant(s) et/ou coordinateur(s)

Frédéric Bapst