Programme de formation

• Objectifs

  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
• Contenu

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

Forme d'enseignement et volume de travail

Spécification du cours

Modalités d'évaluation

• Contrôle continu: travaux écrits, TP/évaluation de rapports
• Examen: écrit (120 min.)

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