Descriptif
Ce cours commence par quelques révisions sur quelques structures mathématiques discrètes (relations, ordres, treillis, matroïdes) utiles en optimisation combinatoire. Dans une seconde partie, il s'intéresse à l'approximation de problème NP-difficile avec garantie de performance. Enfin, dans une dernière partie, il s'intéresse à l'apport de l'aléa en algorithmique.
Objectifs pédagogiques
Acquis d'apprentissageÀ l'issue de l'UE, l'élève sera capable de:
- Rattacher des problèmes d'optimisation combinatoire à des algorithmes de sélection dans des matroïdes.
- Analyser des algorithmes naïfs en démontrant des garanties d'approximation
- Proposer des algorithmes polynomiaux approchés pour résoudre des problèmes NP-difficile
- Analyser l'apport de la randomisation de certains algorithmes
Compétences de rattachement (et justification)
- BC1.3 – Elaborer une ou plusieurs solutions technologiques, en s’appuyant sur la modélisation théorique et la méthode scientifique de manière à faire ressortir la pertinence desdites solutions permettant une prise de décision; Justification : De nombreux exercices partent de petites situations concrètes et montrent comment s'emparer des outils de modélisation mathématique pour les résoudre par l'approche vue en cours.
- BC10.1 – Modéliser des phénomènes, des situations, des signaux, des données dans un objectif, par exemple de conception de nouveaux produits dans le domaine du numérique; Justification : De nombreux exercices partent de petites situations concrètes et montrent comment s'emparer des outils de modélisation mathématique pour les résoudre par l'approche vue en cours.
- BC10.2 – Analyser et résoudre des problèmes mathématiques et algorithmiques nécessaires dans des étapes de réalisation d’un projet en s’appuyant, si besoin est, sur des simulations et dans l’objectif d’implémenter des solutions compétitives; Justification :
- BC10.3 – Analyser une résolution par des approches formelles ou mathématiques; Justification :
24 heures en présentiel
20 heures de travail personnel estimé pour l’étudiant.
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'ingénieur
Vos modalités d'acquisition :
Examen final.
L'UE est acquise si Note finale >= 10- Crédits ECTS acquis : 2.5 ECTS
- Crédit d'UE électives acquis : 2.5
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Echange international non diplomant
Vos modalités d'acquisition :
Examen final.
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
