INFO704 : Analyse d'algorithmes
Aller à la navigation
Aller à la recherche
Responsable 2021: Sébastien Tavenas
Adresse couriel : sebastien.tavenas@univ-smb.fr
Problèmes
Problème 1 :
- Il y a N produits à acheter, chacun ayant un certain prix. Vous avez une somme E d'euros à votre disposition. Le but est d'obtenir le nombre maximum d'objets possible.
- Entrée : La première ligne indique le nombre de tests à réaliser. Chaque test commence par une ligne avec les valeurs N et E. La ligne suivante contient N entiers: la liste des prix des N produits. - Sortie : Le nombre de produits que l'on peut obtenir à chaque test. - Taille maximale des paramètres :
- == Quelques ressources bibliographiques ==
- Ouvrage de référence :
- Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à l'algorithmique" pour les deux premières #éditions )
- Autres références bibliographiques :
- Wilf, Algorithms and Complexity, (1994). Disponible en ligne
- Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
-
- Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
- == TP ==
- Dates provisoires :
- - 22/25 septembre
- - 9 octobre
- - 16 octobre
- TP1 les 22/25 septembre : Analyser la complexité d'algorithmes
- - Sujet du TP 1
- - Fichiers pour le TP
- - Nécessité d'importer la librairie matplotlib
- TP2 le 9 octobre : Problème NP-complet
- - Sujet du TP 2 (Partie I)
- - Exemples d'entrée
- - Générateur aléatoire d'entrées
- TP3 le 16 octobre : Réductions
- - Sujet du TP 2 (Partie II)
- - Esquisse de résolveur pour Clique
- - Nécessité d'importer la librairie pycosat
- == Déroulement (2020) ==
- Cours 1 (7 septembre) : Introduction
- - Introduction
- - Exemple de différents tris
- - Notions d'instance et de problème
- - Notion de complexité asymptotique
- - Grand-O de la notation de Landau
- TD 1 (10 septembre) : Analyses d'algorithmes
- - Sujet du TD
- - Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes
- Cours 2 (17 septembre) : Algorithmes récursifs (Diviser pour régner)
- - Présentation des algorithmes Diviser-pour-régner.
- - Théorème général.
- - distance minimale
- TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
- - Exercices, complexité des fonctions #récursives.
- - Solutions des questions 6 et 7.
- - Solution de la question 5.
- Cours 3 (2 octobre) : Programmation dynamique
- - Algorithme récursif pour les nombres de Fibonacci
- - Programme python pour le problème #de découpe de barres
- - Algorithme de Levenshtein
- - Présentation 'tablette' vue en #cours
- TD 3 (5 octobre) : Exercices sur la programmation dynamique
- - Sujet du TD
- - Si besoin, problème du sous-tableau de somme maximale.
- - Notes lors de la correction
- Cours 4 (13 octobre) : Premières réductions algorithmiques
- - Un liste de réductions algorithmiques entre différents problèmes
- - Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR
- TD 4 (14 octobre) : Clique et consorts
- - Réductions autour de Clique et NP-complétude de #Clique
- - Notes sur le problème SAT
- Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude
- - Petite introduction en survol de la NP-#complétude
- - Notes de cours sur les classes #de complexité
- - Petit Vrai/Faux sur la NP-complétude
- - Hors programme : slides sur les classes de #complexité que j'avais utilisé lors d'une année antérieure quand je faisais la preuve du théorème de Levin-Cook
- TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude
- - Énoncé du TD
- - Problème du sac à dos
- - Corrigé de l'exercice 3 du TD
- == Annales Examen ==
- Examen 2017
- == Historique ==
- Ce cours était donné précédemment par Xavier Provençal.
- Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.