Ausbildungsprogramm

• Angestrebte Kompetenzen und Lernziele

  Les objectifs sont en prolongement de ceux des cours Algo1+2, en s'appliquant à un domaine de connaissances plus vaste.

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

  • Faire de l'optimisation de code, et mesurer le gain
  • Maîtriser la technique de backtracking, et son application aux jeux de stratégie
  • Connaître les principaux concepts de la théorie des graphes, et quelques algorithmes essentiels
  • Ecrire et utiliser des structures de données complexes, et des algorithmes non triviaux, dans le domaine de la géométrie calculatoire
  • Manipuler directement du bytecode Java
  • Comprendre quelques aspects du concept de Blockchain
  • Comprendre les bases du calcul quantique
• Kursinhalte

  • Optimisation de code
  • Bactracking, application aux jeux, alpha/beta pruning
  • Théorie des graphes : parcours, DAG, clique, matching, coloration, bipartite, condensation, vertex/edge cover, tournoi, chemin eulérien/hamiltonien, flux et réseaux, min-cut...
  • Algorithmes sur les graphes : plus courts chemins, minimum spanning tree, maximum flow, topological sorting, strongly connected components, fermeture transitive
  • Géométrie calculatoire : primitives, sens de rotation, coordonnées composites, dualité point-droite
  • Algorithmes géométriques : technique de balayage, point dans un polygone, clustering
  • Structures de données géométriques : carte polygonale DCEL, RangeTree, IntervalTree, PrioritySearchTree
  • Bytecode Java (concepts et outils)
  • Initiation au concept de Blockchain
  • Initiation au Quantum Computing

  Certains TPs d'Algo3 sont réalisés dans le cadre du cours C++, pour renforcer les synergies à l'intérieur du module.

Unterrichtsform

Kursbeschreibung

Lernkontrolle

• Schlussprüfung Lernkontrolle Berichte, Berichte
• Prüfung: schriftlich (120 Min.)

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