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 algo avance Notes de cours Algorithmique avancée Ecole Centrale Pierre Fraigniaud CNRS et Université Paris Diderot pierre fraigniaud irif fr Version octobre Résumé Ce cours a pour objectif de donner aux élèves un aperçu de quelques unes des techniqu

Notes de cours Algorithmique avancée Ecole Centrale Pierre Fraigniaud CNRS et Université Paris Diderot pierre fraigniaud irif fr Version octobre 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 ? algorithme 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 ? identi ?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 ?? Techniques de conception et d ? analyse d ? algorithmes ?? Algorithmes d ? approximation ?? Algorithmes paramétrés ?? Algorithmes probabilistes ?? Méthodes heuristiques ?? Algorithmes parallèles ?? Algorithmes distribués ?? Algorithmes online CTable des matières Préambule les graphes et PageRank de Google Des objets au c ?ur de l ? algorithmique les graphes Codage et notations asymptotiques Matrices et graphes Composantes connexes Calculabilité et complexité algorithmique Machine de Turing De ?nition Indécidabilité Machines RAM Les modèles de machines RAM Le modèle du cours Les classes p et np Les problèmes de décision La classe p La classe np Réduction polynomiale et problème np-di ?ciles Exemples de preuves de NP-complétude Réduction à partir de -sat Réduction à partir de couverture ensemble Complexité spatiale Espace polynomial Espace logarithmique Complexité spatiale non déterministe Les preuves interactives Techniques de conception d ? algorithmes Analyse et preuves d ? algorithmes Parcours DFS Parcours BFS Algorithme de Dijkstra Algorithmes glouton Arbre couvrant de poids minimum Matro? des Algorithmes récursifs Programmation dynamique Plus longue sous-séquence commune Programmation dynamique dans les arbres C Problème du sac à dos Flots et applications Réseaux de transport Algorithme de Ford-Fulkerson Application au couplage Programmation linéaire Dé ?nition Programmation linéaire en nombres entiers Algorithmes d ? approximation Dé ?nition -approximation de la couverture sommet minimum La classe apx Approximation gloutonne ? Couverture-sensemble Couverture-ensemble pondérée Approximation à partir d ? arbres couvrant minimaux Problème du voyageur de commerce Inapproximabilité Le voyageur de commerce métrique Arbres de Steiner Algorithmes d ? élagage Les schémas d ? approximation Dé ?nition L ? exemple du sac à dos Les classes fptas ptas et apx-complet Méthode de l ? arrondi Algorithmes paramétrés La classe fpt Algorithmes polynomiaux à paramètre ?xé Arbre de recherche pour couverture sommet La classe fpt Les noyaux l ? exemple de maxsat Algorithmes de branchement Algorithme paramétré de branchement pour couverture sommet Analyse des algorithmes de branchement Classes de complexité paramétrée Le problème SAT