Chapitre 1 Listes, piles et files d'attente
1.1 Introduction
1.2 Structures de données contiguës et liées
1.2.1 Structures de données contiguës
1.2.2 Structures de données liées
__1.2.3 comparaison
__1.2.4 Contraintes sur les tableaux de style C
1.3 std::array
__1.3.1 Exercice 1 : Implémentation d’un tableau de taille dynamique
__1.3.2 Exercice 2 : Création d’un conteneur de stockage de données rapide et polyvalent
1.4 std::vector
__1.4.1 std::vector - Tableau de taille variable
__1.4.2 allocateur std::vector
1.5 std::forward_list
__1.5.1 Insertion et suppression d'éléments dans std::forward_list
__1.5.2 Autres fonctions membres de std::forward_list
__1.5.3 Exercice 3 : Suppression conditionnelle d’éléments à l’aide de la fonction remove_if() dans une liste chaînée
1.6 Itérateurs
__1.6.1 Exercice 4 : Parcours de différents itérateurs
__1.6.2 Exercice 5 : Création d’un conteneur personnalisé de base
__1.6.3 Exercice pratique 1 : Mise en œuvre d’une liste de lecture musicale
1.7 std::list
__1.7.1 Fonctions membres de std::list
__1.7.2 Exercice 6 : Utilisation des fonctions d’insertion ou de suppression de std::list
__1.7.3 Itérateur bidirectionnel
__1.7.4 Invalidation de l'itérateur
__1.7.5 Exercice pratique 2 : Simulation de jeu de cartes
1.8 std::deque
1.8.1 Structure du ponton
Adaptateur de conteneur 1.9
__1.9.1 std::stack
__1.9.2 std::queue
__1.9.3 std::priority_queue
__1.9.4 Itérateur d'adaptateur
1.10 Analyse comparative
__1.10.1 Exercice pratique 3 : Simulation de la file d’attente d’impression pour une imprimante partagée
1.11 Sortir

Chapitre 2 Arbres, tas et graphes
2.1 Introduction
2.2 Problèmes non linéaires
__2.2.1 Problèmes hiérarchiques
__2.2.2 Dépendances circulaires
2.3 Arbre : Forme inversée
__2.3.1 Exercice 7 : Création d’un organigramme
__2.3.2 Parcours d'arbre
__2.3.3 Exercice 8 : Implémentation du parcours par niveau
2.4 Différentes structures arborescentes
__2.4.1 Arbre binaire de recherche
__2.4.2 Complexité temporelle des opérations sur les arbres
__2.4.3 Exercice 9 : Implémentation d’un arbre binaire de recherche
__2.4.4 Arbre équilibré
__2.4.5 Arbre N-aire
__2.4.6 Exercice pratique 4 : Création de structures de données de système de fichiers
2,5 hanches
__2.5.1 Opérations sur le tas
__2.5.2 Exercice 10 : Trouver la médiane
__2.5.3 Exercice pratique 5 : Fusion de listes de données à l’aide de tas
2.6 Graphique
2.6.1 Représentation d'un graphe à l'aide d'une matrice d'adjacence
__2.6.2 Exercice 11 : Construction d’un graphe et représentation sous forme de matrice d’adjacence
__2.6.3 Représenter un graphe sous forme de liste d'adjacence
__2.6.4 Exercice 12 : Construction d’un graphe et représentation sous forme de liste d’adjacence
2.7 Sortir

Chapitre 3 Tables de hachage et filtres de Bloom
3.1 Introduction
3.2 Table de hachage
3.2.1 Hachage
__3.2.2 Exercice 13 : Un dictionnaire simple pour stocker des valeurs entières
3.3 Collisions dans la table de hachage
__3.3.1 Chaînage
__3.3.2 Exercice 14 : Tables de hachage utilisant le chaînage
__3.3.3 Adressage ouvert
__3.3.4 Hachage Cuckoo
__3.3.5 Exercice 15 : Hachage du coucou
3.4 Tables de hachage C++
__3.4.1 Exercice 16 : Tables de hachage fournies par STL
__3.4.2 Exercice pratique 6 : Associer les URL longues à des URL courtes
Filtre Bloom 3.5
__3.5.1 Exercice 17 : Création d’un filtre de Bloom
__3.5.2 Exercice pratique 7 : Vérification des adresses électroniques en double
3.6 Sortir

Chapitre 4 Diviser pour mieux régner
4.1 Introduction
4.2 Recherche binaire
4.2.1 Exercice 18 : Implémentation de la recherche binaire et évaluation de ses performances
__4.2.2 Exercice pratique 8 : Vaccination
4.3 Comprendre la stratégie « diviser pour régner »
4.4 Algorithme de tri par la méthode diviser pour régner
4.4.1 Tri fusion
4.4.2 Exercice 19 : Tri fusion
4.4.3 Tri rapide
__4.4.4 Exercice 20 : Tri rapide
__4.4.5 Exercice 9 : Tri partiel
__4.4.6 Sélection du temps linéaire
__4.4.7 Exercice 21 : Sélection en temps linéaire
4.5 Techniques de division pour régner et fonctions de la bibliothèque standard C++
4.6 MapReduce : une technique de division et de conquête à un niveau d’abstraction supérieur
__4.6.1 Abstractions Map et Reduce
__4.6.2 Exercice 22 : Implémentation de Map et Reduce à l’aide de la bibliothèque standard C++
4.6.3 Intégration partielle à l'aide du framework MapReduce
__4.6.4 Exercice 23 : Vérification de la primalité des nombres à l’aide de MapReduce
__4.6.5 Exercice pratique 10 : Implémentation du comptage de mots à l’aide de MapReduce
4.7 Sortir

Chapitre 5 Algorithmes gloutons
5.1 Introduction
5.2 Algorithme glouton de base
__5.2.1 Ordonnancement selon la méthode du travail le plus court
__5.2.2 Exercice 24 : Ordonnancement selon la méthode du travail le plus court
5.3 Problème du sac à dos
__5.3.1 0-1 Problème du sac à dos
5.3.2 Problème du sac à dos divisible
__5.3.3 Exercice 25 : Problème du sac à dos divisible
__5.3.4 Exercice pratique 11 : Problème d’ordonnancement des tâches
__5.3.5 Exigences relatives aux algorithmes gloutons
__5.3.6 Problème de l'arbre couvrant minimal
5.3.7 Structure de données d'ensembles disjoints
__5.3.8 Exercice 26 : Algorithme de Kruskal pour l’arbre couvrant minimal
5.4 Coloration des graphiques
__5.4.1 Exercice 27 : Coloration de graphes gloutonne
__5.4.2 Exercice 12 : Algorithme de Welsh-Powell
5.5 Sorties

Chapitre 6 Algorithmes de graphes I
6.1 Introduction
6.2 Problème de parcours de graphe
6.2.1 Recherche en largeur
6.2.2 Exercice 28 : Implémentation du parcours en largeur (BFS)
6.2.3 Recherche en profondeur
__6.2.4 Exercice 29 : Implémentation d’un parcours en profondeur (DFS)
__6.2.5 Exercice 13 : Identification des graphes bipartis
6.3 Algorithme de l'arbre couvrant minimal de Prim
__6.3.1 Exercice 30 : Implémentation de l’algorithme de Prim
6.4 Algorithme de Dijkstra pour le plus court chemin
__6.4.1 Exercice 31 : Implémentation de l’algorithme de Dijkstra
6.4.2 Exercice 14 : Trouver le chemin le plus court à New York
6.5 Sorties

Chapitre 7 Algorithmes de graphes II
7.1 Introduction
7.2 Réexamen du problème du plus court chemin
7.3 Algorithme de Bellman-Ford
__7.3.1 Exercice 32 : Implémentation de l’algorithme de Bellman-Ford
7.4 Algorithme de Bellman-Ford et cycles à poids négatifs
__7.4.1 Exercice 33 : Trouver des cycles à poids négatif
__7.4.2 Exercice 15 : Le robot gourmand
7.5 Algorithme de Johnson
__7.5.1 Exercice 34 : Implémentation de l’algorithme de Johnson
7.5.2 Exercice 16 : Statistiques des graphes aléatoires
7.6 Éléments de connexion robustes
7.6.1 Connectivité dans les graphes orientés et non orientés
7.7 Algorithme de Kosaraju
__7.7.1 Exercice 35 : Implémentation de l’algorithme de Kosaraju
__7.7.2 Exercice 17 : Jeu de téléportation dans un labyrinthe
7.8 Choisir la bonne méthode
7.9 Sorties

Chapitre 8 Programmation dynamique I
8.1 Introduction
8.2 Qu'est-ce que la programmation dynamique ?
8.3 Mémorisation : une approche descendante
8.4 Tabulation : une approche ascendante
8.5 Problème de la somme des sous-ensembles
8.5.1 Étape 1 : Analyse des conditions de nécessité de la programmation dynamique
8.5.2 Étape 2 : Définition des conditions et états de base
8.5.3 Étape 2-(a) : Enquête complète
8.5.4 Exercice 36 : Résolution du problème de la somme des sous-ensembles par la méthode de recherche exhaustive
8.5.5 Étape 2-(b) : Application de l’optimisation – Retour arrière
__8.5.6 Exercice 37 : Résolution du problème de la somme des sous-ensembles par la méthode du retour arrière
__8.5.7 Étape 3 : Mémorisation
__8.5.8 Exercice 38 : Résolution du problème de la somme des sous-ensembles par mémoïsation
__8.5.9 Étape 4 : Tabulation
__8.5.10 Exercice 39 : Résolution du problème de la somme des sous-ensembles à l’aide d’un tableau
__8.5.11 Exercice 18 : Itinéraire
8.6 Programmation dynamique pour les chaînes de caractères et les séquences
8.6.1 Problème de la plus longue sous-séquence commune
8.6.2 Exercice 40 : Résolution du problème de la plus longue sous-séquence commune à l’aide de la méthode de recherche exhaustive
8.6.3 Première étape de l'optimisation : trouver la sous-structure optimale
8.6.4 Exercice 19 : Trouver la plus longue sous-séquence commune à l’aide de la mémoïsation
8.6.5 ? Du haut vers le bas : remplacer la mémoïsation par la tabulation
__8.6.6 Exercice 20 : Trouver la plus longue sous-séquence commune à l’aide d’un tableau
8.7 Exercice 21 : Permutations de mélodies
8.8 Sorties

Chapitre 9 Programmation dynamique II
9.1 Introduction
9.2 P et NP
9.3 Retour sur le problème de la somme des sous-ensembles
9.4 Problème de sac à dos
__9.4.1 Problème du sac à dos 0-1 - Extension du problème de la somme des sous-ensembles
__9.4.2 Exercice 41 : Problème du sac à dos 0-1
__9.4.3 Problème du sac à dos infini
__9.4.4 Réduction de l'espace d'état
__9.4.5 Exercice 42 : Problème du sac à dos infini
__9.4.6 Exercice pratique 22 : Profit maximal
9.5 Graphes et programmation dynamique
__9.5.1 Réexamen de l'algorithme de Bellman-Ford
9.5.2 Résolution du problème du plus court chemin par la programmation dynamique
__9.5.3 Exercice 43 : Chemin le plus court à départ unique (mémoïsation)
__9.5.4 Chemin le plus court entre toutes les paires de sommets
__9.5.5 Algorithme de Floyd-Warshall
__9.5.6 Exercice 44 : Implémentation de l’algorithme de Floyd-Warshall
__9.5.7 Exercice pratique 23 : Construction de routes
9.6 Sortie

Annexe Solutions des exercices pratiques

Théorie et résolution de problèmes, tout en un !
Des structures de données C++ aux algorithmes de graphes et à la programmation dynamique !

Apprenons différentes théories algorithmiques et implémentons-les en C++ dernier format.
Explique divers algorithmes tels que les structures de données C++, les algorithmes gloutons, les algorithmes de type diviser pour régner, les algorithmes de graphes et la programmation dynamique.
Explique la relation entre les structures de données traditionnelles et les implémentations de classes STL en C++, vous aidant ainsi à choisir la structure de données la plus appropriée pour un problème donné.
Tout le code du livre est implémenté en C++14.

Apprenez grâce à 44 problèmes d'entraînement et 23 exercices pratiques.
Pour expliquer les différents algorithmes, nous proposons une résolution de problèmes étape par étape afin que vous puissiez les apprendre concrètement en les codant vous-même.
Cet exercice démontre que, même si différentes structures de données devraient théoriquement avoir des performances similaires, elles peuvent différer considérablement lorsqu'elles sont exécutées sur de véritables ordinateurs.
De plus, les connaissances acquises peuvent être résumées une dernière fois grâce à des exercices pratiques.
Recommandé aux demandeurs d'emploi qui se préparent aux tests de codage et à ceux qui souhaitent apprendre les algorithmes en utilisant la syntaxe C++ la plus récente.

Découvrons les principaux algorithmes fréquemment testés.
Les tests de codage nécessitent également une stratégie.
Il existe différents algorithmes, mais celui-ci est composé des principaux algorithmes qui sont fréquemment testés lors des tests de programmation.
Concentrons-nous sur les algorithmes fréquemment testés tels que diviser pour régner, la recherche dans les graphes, le plus court chemin et la programmation dynamique.