University Côte d'azur
/ Formation / Syllabus SMUFN317
Français English

UE Advanced Algorithms

ECUE's code : SMUFN317

This course give 3.0 ECTS.
EUR DS4H
Informatique
Campus SophiaTech Les Lucioles
Master 1
Semestre impair
Anglais , Français

PRESENTATION

Dans ce cours, nous mettrons en oeuvre des méthodes pour résoudre des problèmes difficiles pour la complexité des calculs (NP-difficiles) lorsqu'on a absolument besoin d'une réponse en un temps raisonnable. Pour cela, il faut nécessairement abandonner certaines exigences sur la réponse fournie par l'algorithme. Il existe cependant des techniques pour obtenir des réponses exploitables à ces problèmes difficiles, telles que les algorithmes probabilistes, les algorithmes d'approximation, le branching. Nous illustrerons ces techniques sur plusieurs grands problèmes d'optimisation combinatoires qui se rencontrent fréquemment en pratique dans des contextes variés: la coupe minimum, l'équilibrage de charges, le problème du sac a dos, le stable maximum dans les graphes, la sélection de k centres et d'autres encore. Dans votre vie professionnelle, vous aurez probablement à résoudre certains de ces problèmes dans la conception d'applications. Ce cours vous donnera à la fois une familiarité avec les problèmes les plus courants mais aussi des techniques que vous pourrez mettre en oeuvre pour résoudre d'autres problèmes d'optimisation que vous rencontrerez.

Course's manager(s)

Christophe Crespelle

In class

  • 12h of lectures
  • 12h of directed studies

PREREQUISITES

Before the start of the course, I must ...
  • Faire le test de positionnement disponible sur l'espace Moodle.
  • Savoir calculer la complexité temporelle d'un algorithme.
  • Savoir utiliser les structures de données de base: tableaux, listes, arbres binaires, tas.
  • Connaître les algorithmes de base sur les graphes : parcours, plus courts chemins, etc.

OBJECTIVES

By the end of this course, I should be able to...
  • Formuler des problèmes d'optimisation combinatoire classiques et décrire des algorithmes pour les résoudre.
  • Modéliser un problème pratique par une question algorithmique.
  • Reconnaître des problèmes difficiles.
  • Utiliser un algorithme probabiliste pour résoudre un problème difficile.
  • Utiliser un algorithme d'approximation pour résoudre un problème difficile.

CONTENT

  • No description
  • No description
  • No description
  • No description
Access to complete Syllabus (Authentification required)
Important
This syllabus has no contractual value. Its content is subject to change throughout this year: be aware to the last updates