Les cartes peuvent être définies en termes d'ensembles : chaque carte est un ensemble dont les éléments représentent des paires clé-valeur, où la clé doit être unique, mais la valeur peut ne pas l'être. Considérez d'autres relations entre les types de données abstraits. Les ensembles et les cartes peuvent-ils être définis en termes de graphes ? Les listes peuvent-elles être définies en termes de cartes ? Les files de priorité peuvent-elles être définies en termes de cartes ? Pourquoi pourrait-il être utile de définir des types de données abstraits en termes d'autres types de données ?

La théorie des graphes fait référence à l'étude mathématique des graphes. Comment un théoricien des graphes pourrait-il décrire les listes chaînées et les structures de données arborescentes ? En quoi cela diffère-t-il de notre utilisation des types de données abstraits ?

Le tri et la recherche sont deux exemples de problèmes de structure de données liés au stockage et à la récupération d'éléments. Où le tri et la recherche apparaissent-ils dans les structures de données linéaires, les structures de données arborescentes et/ou les structures de données de graphes ?

Quels sont les avantages et les inconvénients des modèles de problèmes plus simples, par rapport aux modèles de problèmes plus complexes ?

La définition formelle de la notation grand O ne correspond pas exactement à notre définition de travail des ordres de grandeur. Faites des recherches supplémentaires pour expliquer pourquoi la recherche binaire est également en O(N).

Puisque la recherche binaire est en O(N), il est également vrai que la recherche binaire est en O(N²). Expliquez pourquoi les informaticiens pourraient trouver que O(N²) est une description moins utile de l'exécution de la recherche binaire par rapport à O(log N).

Nous pouvons montrer que l'ordre de grandeur dans le pire des cas pour tout algorithme de tri par comparaison doit être au moins linéarithmique en utilisant un argument d'explosion combinatoire dans le nombre de permutations uniques d'éléments dans une liste. Quel est le nombre de permutations uniques d'une liste de N éléments ? Combien de questions de comparaison doivent être posées pour identifier une permutation particulière parmi toutes les permutations ? Comment ces questions sont-elles liées au tri par comparaison ?

Le parcours en largeur est un patron de conception d'algorithme fondamental pour les problèmes de graphe. Comment le parcours en largeur est-il appliqué comme base pour la conception d'algorithmes gloutons tels que l'algorithme de Prim et l'algorithme de Dijkstra ? Comment l'algorithme de Kruskal s'intègre-t-il dans ces patrons et paradigmes de conception d'algorithmes ? Si l'algorithme de Prim est analogue au tri dans l'algorithme de Kruskal, pourquoi n'y a-t-il pas d'analogue à l'algorithme de Dijkstra dans le tri également ?

Supposons que nous voulions trouver le plus long chemin d'un sommet de départ à un sommet d'arrivée dans un graphe. Comment un algorithme non déterministe pourrait-il résoudre ce problème en temps polynomial ?

Supposons que nous voulions trouver le plus long chemin d'un sommet de départ à un sommet d'arrivée dans un graphe (résolvant le problème de fonction) sans utiliser d'algorithme non déterministe. Supposons que P = NP et que nous ayons un algorithme déterministe en temps polynomial qui retourne s'il existe un chemin de coût exactement k (résolvant le problème de décision). Nous connaissons également le coût du plus long chemin réel. Comment pouvons-nous appliquer de manière répétée cet algorithme de décision pour concevoir un algorithme de fonction de plus longs chemins en temps polynomial ?