Référence : Introduction à l'algorithmique

Introduction à l'algorithmique

Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Utilisée dans les 17 développements suivants :

Transformée de Fourier rapide
Algorithme de Floyd-Warshall
Médiane en temps linéaire
Problème du voyageur de commerce euclidien
Tri par tas
Hachage parfait
Arbres binaires de recherche optimaux
Tri fusion
Complexité amortie des tableaux dynamiques
Algorithme de Bellman-Ford
Exemples de réduction polynomiale
Master Theorem
Complexité moyenne du tri rapide
Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet
Correction des algorithmes de Prim et Kruskal
Algorithme d'Edmonds-Karp
Insertion dans un arbre B

Utilisée dans les 10 leçons suivantes :

931 (2021) Schémas algorithmiques. Exemples et applications.
9 (2022) Algorithmique du texte. Exemples et applications.
925 (2021) Graphes : représentations et algorithmes.
926 (2021) Analyse des algorithmes : complexité. Exemples.
26 (2022) Classes P et NP. Problèmes NP-complets. Exemples.
4 (2022) Exemples de structures de données. Applications.
919 (2017) Unification : algorithmes et applications.
921 (2021) Algorithmes de recherche et structures de données associées.
927 (2021) Exemples de preuve d’algorithme : correction, terminaison.
8 (2022) Algorithmes de tri. Exemples, complexité et applications.

Utilisée dans les 23 versions de développements suivants :

Tri fusion

Développement :
Tri fusion
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Complexité amortie des tableaux dynamiques

Développement :
Complexité amortie des tableaux dynamiques
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Exemples de réduction polynomiale

Développement :
Exemples de réduction polynomiale
Remarque :
3-SAT $\leq_P$ CLIQUE et 3-SAT $\leq_P$ SUBSET-SUM
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Problème du voyageur de commerce euclidien

Développement :
Problème du voyageur de commerce euclidien
Remarque :
Avec la 2-approx polynomiale dans le cas euclidien.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Algorithme de Bellman-Ford

Développement :
Algorithme de Bellman-Ford
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Tri par tas

Développement :
Tri par tas
Remarque :
En faisant la correction de manière complètement formelle, on atteint relativement les 15 min.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet

Développement :
Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet
Remarque :
Papadimitriou pour 2-SAT, Cormen pour CLIQUE.
Références :
- Computational complexity , Papadimitriou
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- di16.pdf

Correction des algorithmes de Prim et Kruskal

Développement :
Correction des algorithmes de Prim et Kruskal
Remarque :
On utilise la preuve du Cormen qui traite le cas général de ce type d'algorithmes.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Algorithme d'Edmonds-Karp

Développement :
Algorithme d'Edmonds-Karp
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- di15.pdf

Arbres binaires de recherche optimaux

Développement :
Arbres binaires de recherche optimaux
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- abro.pdf

Médiane en temps linéaire

Développement :
Médiane en temps linéaire
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- selection.pdf

Problème du voyageur de commerce euclidien

Développement :
Problème du voyageur de commerce euclidien
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- voyageur.pdf

Transformée de Fourier rapide

Développement :
Transformée de Fourier rapide
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- fft.pdf

Tri par tas

Développement :
Tri par tas
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- heapsort.pdf

Complexité moyenne du tri rapide

Développement :
Complexité moyenne du tri rapide
Remarque :
L'algorithme présenté dans le Beauquier n'est pas le tri rapide de base, c'est pour ça qu'on se base sur celui présenté dans le Cormen et qu'on adapte la preuve du Beauquier pour calculer la complexité en moyenne du tri rapide.
Références :
- Eléments d'algorithmique, Beauquier, Berstel et Chrétienne
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- TriRapide.pdf

Tri par tas

Développement :
Tri par tas
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- TriParTasv2.pdf

Hachage parfait

Développement :
Hachage parfait
Remarque :
On peut admettre la démonstration du théorème 2 si trop long.
Se recase (mal) dans la 932.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- HachageParfait.pdf

Arbres binaires de recherche optimaux

Développement :
Arbres binaires de recherche optimaux
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- ABROpti.pdf

Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet

Développement :
Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- Computational complexity , Papadimitriou
Fichier :
- SAT et CLIQUE.pdf

Problème du voyageur de commerce euclidien

Développement :
Problème du voyageur de commerce euclidien
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- TSP.pdf

Insertion dans un arbre B

Développement :
Insertion dans un arbre B
Remarque :
Ça s'appelle B-arbres dans le Cormen (chapitre 18), il explique pourquoi c'est intéressant pages 425-429, puis l'insertion est faite pages 433-437.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- arbre_b.pdf

Algorithme de Floyd-Warshall

Développement :
Algorithme de Floyd-Warshall
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- algo_floyd_warshall.pdf

Master Theorem

Développement :
Master Theorem
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest

Utilisée dans les 26 versions de leçons suivantes :

902 : Diviser pour régner : exemples et applications.

Leçon :
Diviser pour régner : exemples et applications.
Remarque :
Plan brouillon...
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- Eléments d'algorithmique, Beauquier, Berstel et Chrétienne
Fichiers :

906 : Programmation dynamique : exemples et applications.

Leçon :
Programmation dynamique : exemples et applications.
Références :
Fichier :
- 2016_906.pdf

907 : Algorithmique du texte : exemples et applications.

Leçon :
Algorithmique du texte : exemples et applications.
Remarque :
[Admin] N'a même pas utilisé un Crochemore, une hérésie !
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichiers :
- 2016_907.pdf
- 2016_907_remarque.pdf

925 : Graphes : représentations et algorithmes.

Leçon :
Graphes : représentations et algorithmes.
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- Eléments d'algorithmique, Beauquier, Berstel et Chrétienne
Fichiers :

926 : Analyse des algorithmes : complexité. Exemples.

928 : Problème NP-complets : exemples de réductions.

Leçon :
Problème NP-complets : exemples de réductions.
Références :
Fichier :
- 2016_928.pdf

901 : Structure de données : exemples et applications.

Leçon :
Structure de données : exemples et applications.
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- Types de données et algorithmes, Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria
Fichier :
- 2015_901.pdf

902 : Diviser pour régner : exemples et applications.

Leçon :
Diviser pour régner : exemples et applications.
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- Algorithms from P to NP , Moret
Fichier :
- 2015_902.pdf

906 : Programmation dynamique : exemples et applications.

Leçon :
Programmation dynamique : exemples et applications.
Références :
Fichier :
- 2015_906.pdf

907 : Algorithmique du texte : exemples et applications.

919 : Unification : algorithmes et applications.

Leçon :
Unification : algorithmes et applications.
Références :
Fichier :
- 2015_919.pdf

921 : Algorithmes de recherche et structures de données associées.

925 : Graphes : représentations et algorithmes.

Leçon :
Graphes : représentations et algorithmes.
Références :
- Algebraic graph theory , Biggs
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- 2015_925.pdf

926 : Analyse des algorithmes : complexité. Exemples.

927 : Exemples de preuve d'algorithme : correction, terminaison.

Leçon :
Exemples de preuve d'algorithme : correction, terminaison.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- 2015_927.pdf

928 : Problème NP-complets : exemples de réductions.

901 : Structures de données. Exemples et applications.

Leçon :
Structures de données. Exemples et applications.
Références :
Fichier :
- 901.pdf

902 : Diviser pour régner. Exemples et applications.

Leçon :
Diviser pour régner. Exemples et applications.
Références :
- A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis, Anne Benoît, Yves Robert, Frédéric Vivien
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- 902.pdf

903 : Exemples d’algorithmes de tri. Correction et complexité.

Leçon :
Exemples d’algorithmes de tri. Correction et complexité.
Référence :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Fichier :
- 903.pdf

906 : Programmation dynamique. Exemples et applications.

Leçon :
Programmation dynamique. Exemples et applications.
Références :
- Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
- An Introduction to the Analysis of Algorithms, Robert Sedgewick, Phillipe Flajolet
Fichier :
- 906.pdf

907 : Algorithmique du texte. Exemples et applications.

Leçon :
Algorithmique du texte. Exemples et applications.
Références :
Fichier :
- 907.pdf

921 : Algorithmes de recherche et structures de données associées.

925 : Graphes : représentations et algorithmes.

Leçon :
Graphes : représentations et algorithmes.
Références :
Fichier :
- 925.pdf

926 : Analyse des algorithmes : complexité. Exemples.

927 : Exemples de preuve d’algorithme : correction, terminaison.

928 : Problèmes NP-complets : exemples et réductions.