Algorithmique Avancée
Plan du cours
- Revisiter la technique Diviser pour Régner
- Compter le nombre d'inversions en \(O(n \log n)\)
- Multiplication matricielle: l'algorithme de Strassen
- Calculer le plus proche pair des points
- Algorithmes glutons
- Ordonnancement minimisant le temps de complétude
- Code de Huffman
- Pagination
- Programmation dynamique
- Ensembles indépendants des graphes-lignes.
- Sac à dos
- Alignement des séquences
- Arbres binaires de recherche optimaux
- Flots et Coupes
- Théorème Min Coupe - Max Flot.
- Algorithmes de Ford-Fulkerson, d'Edmonds-Karps et de Dinic
- Applications
- Algorithmes d'approximation
- Minimisation de makespan, couvertures de sommets, couvertures d'ensembles
- Maximisation de coverage, applications en influence
- Algorithmes randomisés
- Tri rapide (avec pivot aléatoire), Max-3-Sat
- Min-Coupes, Collecteurs des coupons
Les exercices d'implémentation
- Le nombre d'inversions:
- Vérification simple: D'abord, vérifier si algorithm retourne 0 pour une liste trié et retourne \(n(n-1)/2\) pour une liste trié à l'envers
- Test simple: Ce fichier
contient une liste de 10 entiers. Votre programme doit compter 28 inversions.
- Test: Ce fichier
contient des entiers entre 1 et 100000. La ligne \(i\) indique le \(i\)-ème élément de la liste. Combien d'inversions dans cette liste?
- Codes de Huffman:
Le format de fichier est:
[nombre des symbols]
[poids de sympbol #1]
[poids de sympbol #2]
...
- Test simple: Pour les instances de 10 et 15 sympbols dans ces fichiers
test #1 et test #2, quelles sont les longueurs min et max dans un code prefix-free optimal? (Réponse: 2 et 5 pour test #1, 3 et 6 pour test #2).
- Test: Même question pour ce fichier
de 1000 sympbols.
- Arbres binaires de recherche optimaux:
Ce fichier décrit une instance du problème. Le format de fichier est:
1ère ligne: le nombre \(n\) des clés (mots)
2e ligne: \(n\) poids (entiers) séparés par les virgules
Quelle est la valeur de la solution optimale?
Références
Liens utils et intéressants.