INFO704 : Analyse d'algorithmes

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 :

1. == Quelques ressources bibliographiques ==
3. Ouvrage de référence :
   1. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introduction à l'algorithmique" pour les deux premières #éditions )
5. Autres références bibliographiques :
   1. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
   2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
6. 1. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
8. == TP ==
10. Dates provisoires :
11. - 22/25 septembre
12. - 9 octobre
13. - 16 octobre
16. TP1 les 22/25 septembre : Analyser la complexité d'algorithmes
17. - Sujet du TP 1
18. - Fichiers pour le TP
19. - Nécessité d'importer la librairie matplotlib
22. TP2 le 9 octobre : Problème NP-complet
23. - Sujet du TP 2 (Partie I)
24. - Exemples d'entrée
25. - Générateur aléatoire d'entrées
28. TP3 le 16 octobre : Réductions
29. - Sujet du TP 2 (Partie II)
30. - Esquisse de résolveur pour Clique
31. - Nécessité d'importer la librairie pycosat
35. == Déroulement (2020) ==
37. Cours 1 (7 septembre) : Introduction
38. - Introduction
39. - Exemple de différents tris
40. - Notions d'instance et de problème
41. - Notion de complexité asymptotique
42. - Grand-O de la notation de Landau
45. TD 1 (10 septembre) : Analyses d'algorithmes
46. - Sujet du TD
47. - Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes
50. Cours 2 (17 septembre) : Algorithmes récursifs (Diviser pour régner)
51. - Présentation des algorithmes Diviser-pour-régner.
52. - Théorème général.
53. - distance minimale
56. TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
57. - Exercices, complexité des fonctions #récursives.
58. - Solutions des questions 6 et 7.
59. - Solution de la question 5.
62. Cours 3 (2 octobre) : Programmation dynamique
63. - Algorithme récursif pour les nombres de Fibonacci
64. - Programme python pour le problème #de découpe de barres
65. - Algorithme de Levenshtein
66. - Présentation 'tablette' vue en #cours
69. TD 3 (5 octobre) : Exercices sur la programmation dynamique
71. - Sujet du TD
72. - Si besoin, problème du sous-tableau de somme maximale.
73. - Notes lors de la correction
76. Cours 4 (13 octobre) : Premières réductions algorithmiques
77. - Un liste de réductions algorithmiques entre différents problèmes
78. - Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR
81. TD 4 (14 octobre) : Clique et consorts
82. - Réductions autour de Clique et NP-complétude de #Clique
83. - Notes sur le problème SAT
86. Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude
87. - Petite introduction en survol de la NP-#complétude
88. - Notes de cours sur les classes #de complexité
89. - Petit Vrai/Faux sur la NP-complétude
90. - 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
92. TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude
93. - Énoncé du TD
94. - Problème du sac à dos
95. - Corrigé de l'exercice 3 du TD
98. == Annales Examen ==
100. Examen 2017
102. == Historique ==
103. Ce cours était donné précédemment par Xavier Provençal.
104. Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.