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 :
- 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
- !---
- TP les 10 octobre et 6 novembre.
- - Énoncé du TP, première partie : tp-part-1.pdf. Plus de détails pour chacuns des #trois sujets :
- * tp-part-1-CHO.pdf
- * tp-part-1-CHNO.pdf
- * tp-part-1-3C.pdf
- Voici aussi un exemple d'entrée pour chaque sujet :
- * Graphe-vrai-CHO.pdf
- * Graphe-vrai-CHNO.pdf
- * Graphe-vrai-3C.pdf
- -----
- TP3 le 18 octobre : Réductions polynomiales
- - Énoncé du TP, deuxième partie.
- - Documents pour les réductions :
- * Avro #Chapitre 10
- * Cormen-Leiserson-Rivest-Stein #Coloration
- * Cormen-Leiserson-Rivest-Stein HNO
- (Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la Version anglaise)
- * Hon HO Version francaise
- * Garey-Johnson HNO
- * wiki proof
- - Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
- * 3SAT-vrai
- * CS-vrai
- * 3SAT-faux
- * CS-faux
- --
- == 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
- !-- Réductions de NP-complétude
- !-- - Problèmes NP-difficiles et NP-complets.
- - Théorème de Cook-Levin. Cook-Levin
- - Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --
- --
- !-- Complexité des problèmes
- - Introduction aux classes de complexité.
- !-- - Complexité d'un problème.
- - Classe P.
- !-- - Types de problèmes ( décision, optimisation, existence ). --
- - Réduction polynomiale.
- - Algorithme de vérification.
- - Classe NP.
- --
- TD 4 (14 octobre) : Clique et consorts
- - Réductions autour de Clique et NP-complétude de #Clique
- - Notes sur le problème SAT
- !-- Programmation dynamique
- - Énoncé de TD.
- - Correction sur la distance de Levenshtein.
- --
- 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.
-->