Programma di studio

• Obiettivi

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

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

Metodo d'insegnamento e volume di lavoro

Titolo del corso

Metodi di valutazione

• prove in itinere prove scritte, lavori pratici / valuatazione delle relazioni di laboratorio
• esame (prova di fine modulo): scritto (120 minuto)

Metodo di calcolo della nota del corso

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.

Docente/i e/o coordinatore/i

Frédéric Bapst