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. 1. Hopcroft et Ullman, Introduction to automata theory, languages, and computation, (1979).
3. == TP ==
5. Dates provisoires :
6. - 22/25 septembre
7. - 9 octobre
8. - 16 octobre
11. TP1 les 22/25 septembre : Analyser la complexité d'algorithmes
12. - Sujet du TP 1
13. - Fichiers pour le TP
14. - Nécessité d'importer la librairie matplotlib
17. TP2 le 9 octobre : Problème NP-complet
18. - Sujet du TP 2 (Partie I)
19. - Exemples d'entrée
20. - Générateur aléatoire d'entrées
23. TP3 le 16 octobre : Réductions
24. - Sujet du TP 2 (Partie II)
25. - Esquisse de résolveur pour Clique
26. - Nécessité d'importer la librairie pycosat
28. !---
29. TP les 10 octobre et 6 novembre.
31. - Énoncé du TP, première partie : tp-part-1.pdf. Plus de détails pour chacuns des #trois sujets :
32. * tp-part-1-CHO.pdf
33. * tp-part-1-CHNO.pdf
34. * tp-part-1-3C.pdf
35. Voici aussi un exemple d'entrée pour chaque sujet :
36. * Graphe-vrai-CHO.pdf
37. * Graphe-vrai-CHNO.pdf
38. * Graphe-vrai-3C.pdf
39. -----
40. TP3 le 18 octobre : Réductions polynomiales
41. - Énoncé du TP, deuxième partie.
42. - Documents pour les réductions :
43. * Avro #Chapitre 10
44. * Cormen-Leiserson-Rivest-Stein #Coloration
45. * Cormen-Leiserson-Rivest-Stein HNO
46. (Attention la figure 34.16 est incorrecte. La remplacer par la figure 34.16 de la Version anglaise)
47. * Hon HO Version francaise
48. * Garey-Johnson HNO
49. * wiki proof
50. - Voici des exemples d'entrée pour 3SAT et Couverture par Sommets :
51. * 3SAT-vrai
52. * CS-vrai
53. * 3SAT-faux
54. * CS-faux
56. --
58. == Déroulement (2020) ==
60. Cours 1 (7 septembre) : Introduction
61. - Introduction
62. - Exemple de différents tris
63. - Notions d'instance et de problème
64. - Notion de complexité asymptotique
65. - Grand-O de la notation de Landau
68. TD 1 (10 septembre) : Analyses d'algorithmes
69. - Sujet du TD
70. - Fonctions mathématiques de base : polynômes, #exponentielles et logarithmes
73. Cours 2 (17 septembre) : Algorithmes récursifs (Diviser pour régner)
74. - Présentation des algorithmes Diviser-pour-régner.
75. - Théorème général.
76. - distance minimale
79. TD 2 (29 septembre) : Exercices d'analyse pour des algos récursifs ("Master Theorem")
80. - Exercices, complexité des fonctions #récursives.
81. - Solutions des questions 6 et 7.
82. - Solution de la question 5.
85. Cours 3 (2 octobre) : Programmation dynamique
86. - Algorithme récursif pour les nombres de Fibonacci
87. - Programme python pour le problème #de découpe de barres
88. - Algorithme de Levenshtein
89. - Présentation 'tablette' vue en #cours
92. TD 3 (5 octobre) : Exercices sur la programmation dynamique
94. - Sujet du TD
95. - Si besoin, problème du sous-tableau de somme maximale.
96. - Notes lors de la correction
99. Cours 4 (13 octobre) : Premières réductions algorithmiques
100. - Un liste de réductions algorithmiques entre différents problèmes
101. - Note sur les mathématiques derrière la #réduction de 3SUM vers 3COLLINEAR
102. !-- Réductions de NP-complétude
103. !-- - Problèmes NP-difficiles et NP-complets.
104. - Théorème de Cook-Levin. Cook-Levin
105. - Preuve de NP-Complétude. !-- : Couverture des arêtes et k-coloriage. --
106. --
107. !-- Complexité des problèmes
108. - Introduction aux classes de complexité.
109. !-- - Complexité d'un problème.
110. - Classe P.
111. !-- - Types de problèmes ( décision, optimisation, existence ). --
112. - Réduction polynomiale.
113. - Algorithme de vérification.
114. - Classe NP.
115. --
116. TD 4 (14 octobre) : Clique et consorts
117. - Réductions autour de Clique et NP-complétude de #Clique
118. - Notes sur le problème SAT
119. !-- Programmation dynamique
120. - Énoncé de TD.
121. - Correction sur la distance de Levenshtein.
122. --
124. Cours 5 (23 octobre, matin) : Classes de complexité et NP-complétude
125. - Petite introduction en survol de la NP-#complétude
126. - Notes de cours sur les classes #de complexité
127. - Petit Vrai/Faux sur la NP-complétude
128. - 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
130. TD 5 (23 octobre, après-midi) : Classes de complexité et NP-complétude
131. - Énoncé du TD
132. - Problème du sac à dos
133. - Corrigé de l'exercice 3 du TD
136. == Annales Examen ==
138. Examen 2017
140. == Historique ==
141. Ce cours était donné précédemment par Xavier Provençal.
142. Ce cours est une refonte de INFO724 Algorithmique avancée, graphes et NP-complétude.

-->