De nombreux problèmes algorithmiques du monde réel ne peuvent pas être résolus efficacement à l'aide des outils algorithmiques traditionnels, par exemple, parce que les problèmes sont NP-hard. L'objectif du cours Algorithmes d'approximation est de vous familiariser avec les concepts algorithmiques importants et les techniques nécessaires pour traiter efficacement de tels problèmes. Ces techniques s'appliquent lorsque nous n'avons pas besoin de la solution optimale à certains problèmes, mais d'une approximation proche de la solution optimale. Nous verrons comment trouver efficacement de telles approximations.

Prérequis : Pour suivre ce cours avec succès, vous devez déjà avoir une connaissance de base des algorithmes et des mathématiques. Voici une courte liste de ce que vous êtes supposé savoir : - O-notation, Ω-notation, Θ-notation ; comment analyser les algorithmes - Calcul de base : manipuler des sommations, résoudre des récurrences, travailler avec des logarithmes, etc. - Théorie des probabilités de base : événements, distributions de probabilités, variables aléatoires, valeurs attendues, etc. - Structures de données de base : listes chaînées, piles, files d'attente, tas - Arbres de recherche binaires (équilibrés) - Algorithmes de tri de base, par exemple MergeSort, InsertionSort, QuickSort - Terminologie des graphes, représentations des graphes (listes d'adjacence et matrice d'adjacence), algorithmes de base pour les graphes (BFS, DFS, tri topologique, chemins les plus courts) Le matériel pour ce cours est basé sur les notes de cours qui peuvent être trouvées sous l'onglet "ressources".