Bienvenue sur le site de Racem MELLOULI

| Acceuil | Formation & parcours professionnel | Recherche & Publications | Enseignement | Liens | CV |

Algorithmes avancés

DURÉE : 42 heures

SEMESTRE : 2

RESPONSABLE : Racem MELLOULI

OBJECTIF

Ce cours a pour objectif d’approfondir les connaissances de l’étudiant en algorithmique et de développer ses compétence en programmation en abordant des problématiques difficiles et complexes. Par ailleurs, l’étudiant est amené à optimiser la construction algorithmique en termes de temps de calcul et de gestion de la mémoire (optimisation de code). Des notions nouvelles seront abordées à savoir la complexité algorithmique, la combinatoire, le paradigme « diviser pour régner » et les algorithmes par les graphes.

PLAN :

CH1. Algorithmes, combinatoire & complexité

Section1 : Définitions

Section 2 : Complexité algorithmique, notations de Landau, et classes de complexité

Section 3 : Combinatoire et complexité des problèmes

- Problèmes combinatoires et complexité des problèmes

- Algorithmes d’énumération explicite et difficultés d’implémentation et de convergence (TD)

- Exemple de problèmes combinatoires: sac à dos, voyageurs de commerce, plus court chemin, affectation

Exercices / TD: série 1

CH2. Mesure de la complexité et cas des appels récursifs

Section 1 : Mesure et analyse de complexité: cas de l’algorithme de tri par insertion

- Code en C du tri par insertion

- Invariants de boucles et validité du tri par insertion

Section 2 : La récursivité et le paradigme « diviser pour régner »

- Exemple du problème de calcul de x^n

- Exemple de multiplication de matrices carrées de taille n

- Exemple de l’algorithme de tri par fusion

- Dérécursivation

Section3 : Complexité de la récurrence: méthode générale

Exercices / TD: série 2

CH3. Algorithmes stochastiques et algorithmes de résolution heuristique

Section 1 : Définitions

Section 2 : Algorithmes de génération aléatoires des instances d’un problème (implémentation en langage C)

- Cas des problèmes: ordonnancement, sac à dos, voyageurs de commerce, problèmes de couverture commerciale, classification (clustering), problème de plus court chemin

Section 3 : Règles de priorité (FIFO, SPT, etc.)

- Application aux problèmes d’ordonnancement monoprocesseur et processeurs parallèles

- Application au problème de sac à dos

Section 4 : Algorithmes gloutons

- Application aux problèmes du plus court chemin et/ou du voyageur de commerce

Section 5 : Algorithmes d’amélioration

- Application au problème de classification: clustering (mini-projet);

- Utilisation de recherche locale itérative (mini-projets)

Section 6 : Algorithmes de recherche avec retour en arrière: backtracking

- Exemple de la recherche de chemins dans un graphe avec circuits (mini-projet)

- Exemple du problème des 8 reines

Exercices / TD: série 3

CH4. Algorithmes par les graphes

Section 1 : Définitions (éléments de la théorie des graphes)

Section 2 : Rappel sur les listes, piles, arbres (implémentation en C avec des appels récursifs)

Section 3 : Les arbres : cas particulier des tas

Section 5 : Algorithmes de tri par tas HEAPSORT (TD)

Section 6 : Arbre de recherche et table de hachage

Section 7 : Algorithmes de recherche dichotomique (Mini-projets)

Exercices / TD: série 4

Lectures : exemples d’algorithmes de la littérature pour culture générale et pour les mini-projets

Algorithmes pour le problème de plus court chemin:

- Algorithme de Dijkstra (mini-projet)

- Algorithme de Bellman-Ford (mini-projet)

- Algorithme de Floyd-Warshall (mini-projet)

Algorithmes de KNUTH-MORRIS-PRATT (mini-projet)

Algorithmes de BOYER ET MOORE (mini-projet)

Algorithme MOORE HODGSON (mini-projet)

Algorithmes pour Chemins Eulériens (mini-projet : sujet)

Algorithmes (de Prim et de Kruskal) pour problème d’arbre couvrant de poids minimal (mini-projet)

Algorithmes gloutons pour problèmes d’ordonnancement (mini-projet)

Métaheuristiques: cas des algorithmes génétiques

- Principe et étapes de la méthode

- Implémentation sur un problème d’ordonnancement (mini-projet)

Algorithmes Branch-and-Bound

La machine de Turing (histoire de l’informatique)

(...)

Références :

- Philippe Lacomme, Christian Prins, Marc Sevaux, « Algorithmes de graphes », éditions Eyrolles, 2^ème édition 2003 http://www.amazon.fr/Algorithmes-graphes-Philippe-Lacomme/dp/2212113854#reader_2212113854.

- René Lalement, « Objets, algorithmes & patterns », 2000 (polycopier cours 'Ecole des Ponts ParisTech, CERMICS http://cermics.enpc.fr/polys/oap/node46.html.

- Mahdi Khemakhem, « Algorithmique avancée et complexité » (polycopier cours, niveau L3, ISECS - Université de Sfax)

Dernière mise à jour : 29-02-2012.