...
Algorithmes et complexité 6JUCSN03 | ECTS | 3 | SEMESTRE | 6 | |||||||||||||||||||||||||||||||
| CM | TD | TP | EI | Travail personnel | |||||||||||||||||||||||||||||||
| 10h | 20h | 0h | 0h | 20h | |||||||||||||||||||||||||||||||
| Langues d'enseignement | Français | ||||||||||||||||||||||||||||||||||
| Responsable(s) | |||||||||||||||||||||||||||||||||||
| Mots clefs | Modèle de calcul, algorithmique, récursion, complexité des algorithmes et des problèmes, bornes inférieures, NP-difficulté | ||||||||||||||||||||||||||||||||||
| Prérequis | - | ||||||||||||||||||||||||||||||||||
| Objectif pédagogique | |||||||||||||||||||||||||||||||||||
Ce cours vise à donner les bases de la conception et de l'analyse de méthodes de calcul, c'est à dire de traitement d'information par des systèmes physiques. Il aborde notamment l'organisation efficace du calcul (l'algorithmique) et les limites à cette efficacité (la théorie de la complexité). | |||||||||||||||||||||||||||||||||||
| Organisation et contenus | |||||||||||||||||||||||||||||||||||
Ce module comporte six séances méthodologiques et trois séances consacrées à des cas d’étude. Les TD se font sur papier. Séance 1. Cas d'étude : problèmes d'affectation et algorithme de Gale-Shapley Problématique d'affectation de ressources, notion de problème algorithmique, problème des mariages stables, algorithme de Gale-Shapley, analyse et adaptations de cet algorithme, déploiement dans parcoursup. Séance 2. Modèles de calcul classiques Notions d'architecture des ordinateurs, modèles RAM, complexité asymptotique pire-cas. Séance 3. Méthode de conception d'algorithmes récursifs Simplifier et déléguer, recherche dichotomique, diviser pour régner, exploration par retour arrière. Séance 4. Complexité asymptotique pire cas d'algorithmes récursifs Analyse d'arbres d'exécution, théorème maître, théorème d'Akra-Bazzi. Séance 5. Cas d'étude : systèmes de votes Problématique de choix social, Théorème de Gibbard–Satterthwaite, Méthodes de comptage : Copeland, Minimax, Kemeny-Young, paires ordonnées, Schulze. Séance 6. Bornes inférieures de complexité Notion de complexité d'un problème, arguments d'adversaires, arbres de décision. Séance 7. Réduction entre problèmes Problème de colorabilité, mécanisme de réduction et propagation des bornes inférieures. Séance 8. NP-difficulté Problèmes de satisfiabilité, classes de complexité P et NP, théorème de Cook-Levin, NP-difficulté et NP-complétude. Séance 9. Modèle de calcul quantique Qbit et mesure, portes quantiques, impossibilité du clonage quantique, circuits simples, algorithme de Deutsch–Jozsa ou Grover. Le polycopié est disponible sur la page : https://members.loria.fr/Xavier.Goaoc/ | |||||||||||||||||||||||||||||||||||
Compétences | |||||||||||||||||||||||||||||||||||
| Niveaux | Description et verbes opérationnels | ||||||||||||||||||||||||||||||||||
| Connaître | Des algorithmes de référence, des exemples variés de modèles de calcul. | ||||||||||||||||||||||||||||||||||
| Comprendre | Ce que signifie calculer, ce qu'il est possible/impossible de calculer efficacement. | ||||||||||||||||||||||||||||||||||
| Appliquer | Des méthodes de conception d'algorithmes et d'analyse de complexité d'algorithmes/de problèmes algorithmiques. | ||||||||||||||||||||||||||||||||||
| Analyser | L'efficacité d'une méthode algorithmique et la difficulté d'un problème algorithmique. | ||||||||||||||||||||||||||||||||||
| Synthétiser | |||||||||||||||||||||||||||||||||||
| Évaluer | |||||||||||||||||||||||||||||||||||
| Contributions aux Objectifs de Développement Durable des Nations Unies | |||||||||||||||||||||||||||||||||||
| Modalités de contrôle des connaissances et compétences | |||||||||||||||||||||||||||||||||||
| Contrôle Continu | Examen écrit | Oral / Soutenance | Rapport / Projet | ||||||||||||||||||||||||||||||||
...