Ausbildungsprogramm

• Angestrebte Kompetenzen und Lernziele

  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...)
• Kursinhalte

  • 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, ...

Unterrichtsform

Kursbeschreibung

Lernkontrolle

• Schlussprüfung Lernkontrolle Berichte, Berichte

Notenberechnung / Validierungsmodalitäten

Die Note des Kurses entspricht dem gewichteten Durchschnitt aller Lernkontrollen während des Semesters (+/- mögliche Anpassung für Praktikum). Im Falle einer Schlussprüfung entspricht die Note des Kurses dem arithmetischen Mittel aus der Note der Lernkontrolle und der Schlussprüfung.

Dozierende

Frédéric Bapst