Algorithmique

L3 Informatique parcours Math-Info, U. Grenoble Alpes

Cours

Le plan indiqué est prévisionnel et susceptible de modifications.

  1. Présentation du cours

Partie 1. Structures de données

  1. Types abstraits de données & rappels : tableaux, listes, arbres binaires
  2. Structures de données linéaires : piles, files, files à priorité
  3. Tableaux dynamique et arbres binaires de recherche
  4. Tables de hachage

Partie 2. Techniques algorithmiques

  1. Diviser pour régner : principes, exemples du tri fusion et de l’algorithme de Karatsuba
  2. Recherche exhaustive : principes, exemples de Sat et du voyageur de commerce
  3. Algorithmes probabilistes : Monte Carlo et Las Vegas, exemples de la coupe minimale et du tri rapide
  4. Programmation dynamique : principes, exemples de la plus longue sous-suite croissante et de la distance d’édition
  5. Algorithmes d’approximation : principes, exemples de couverture par sommets, somme partielle, et équilibrage de charges
  6. Deux techniques avancées : recherche exhaustive rapide (3-Sat), diviser-pour-régner en programmation dynamique (distance d’édition)

Quelques lectures intéressantes

Sujets de TD et d’examens

Bibliographie indicative

Les deux ouvrages suivants sont mes ouvrages préférés d’algorithmique. Malheureusement, ils ne couvrent pas la partie 1. Structures de données. Ne pas hésiter à les consulter pour la partie 2. Techniques algorithmiques.

Dernière modification : 15 novembre 2024