Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Notes de cours Algorithmique avancée Ecole Centrale Pierre Fraigniaud CNRS et U

Notes de cours Algorithmique avancée Ecole Centrale Pierre Fraigniaud CNRS et Université Paris Diderot pierre.fraigniaud@irif.fr Version 17 octobre 2017 Résumé Ce cours a pour objectif de donner aux élèves un aperçu de quelques unes des techniques modernes de conception et d’analyse d’algorithmes. Ainsi, tous les grands thèmes de l’algo- rithme seront abordés dans le cours : calculabilité, complexité, récursivité, programmation dynamique, programmation linéaire, algorithmes d’approximation, algorithmes paramétrés, algorithmes probabilistes, etc. A l’issue de ce cours, les élèves devraient être capables d’iden- tiﬁer la ou les méthodes les plus appropriées pour la résolution des problèmes algorithmiques qu’ils pourront rencontrer dans leurs carrières. Il ne sera bien sur pas possible de rentrer dans les détails de toutes les thématiques abordées dans le cours, qui mériteraient chacune un cours à part entière. Toutefois, les ouvrages de référence qui seront indiqués durant le cours devraient permettre de satisfaire tous les élèves désirant en savoir plus sur tels ou tels thèmes du cours. Ouvrages de référence — Complexité algorithmique [11] — Techniques de conception et d’analyse d’algorithmes [3] — Algorithmes d’approximation [14] — Algorithmes paramétrés [5] — Algorithmes probabilistes [9] — Méthodes heuristiques [8] — Algorithmes parallèles [6] — Algorithmes distribués [1, 7, 12] — Algorithmes online [2] 1 Table des matières 1 Préambule : les graphes et PageRank de Google 5 1.1 Des objets au cœur de l’algorithmique : les graphes . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Codage et notations asymptotiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Matrices et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Composantes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Calculabilité et complexité algorithmique 10 2.1 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Machines RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Les modèles de machines RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Le modèle du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Les classes p et np . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.1 Les problèmes de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 La classe p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.3 La classe np . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.4 Réduction polynomiale et problème np-diﬃciles . . . . . . . . . . . . . . . . . . . . 21 2.4 Exemples de preuves de NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.1 Réduction à partir de 3-sat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.2 Réduction à partir de couverture ensemble . . . . . . . . . . . . . . . . . . . . 26 2.5 Complexité spatiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.1 Espace polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.2 Espace logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5.3 Complexité spatiale non déterministe . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5.4 Les preuves interactives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Techniques de conception d’algorithmes 29 3.1 Analyse et preuves d’algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.1 Parcours DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.1.2 Parcours BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.3 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Algorithmes glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 Arbre couvrant de poids minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2.2 Matroïdes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 Algorithmes récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4 Programmation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . uploads/Philosophie/ notes-algo-avance.pdf