Chaque clé unique dans une carte est associée à une valeur (éventuellement non unique). Parfois, nous voulons associer plus d'une valeur à une clé donnée. Décrivez comment nous pouvons utiliser un type de données abstrait de liste ou d'ensemble pour associer plus d'une valeur à une clé unique.

Chaque sommet dans un graphe peut être étiqueté avec un identifiant unique, tel qu'un nombre unique. Décrivez la relation entre les sommets adjacents. Comment pourrions-nous utiliser des types de données abstraits tels que les listes, les ensembles et les cartes pour représenter ces relations ?

Décrivez comment nous pourrions implémenter le type de données abstrait graphe en utilisant d'autres types de données abstraits tels que les listes, les ensembles et/ou les cartes. Expliquez pour les graphes dont les arêtes ont des poids associés ainsi que pour les graphes dont les arêtes n'ont pas de poids associés.

Décrivez deux ou trois modèles de problèmes différents pour un système médical conçu pour aider les médecins à recommander des soins préventifs aux patients.

Comparez et opposez les modèles de problèmes du système médical. Quels sont les compromis de chaque modèle de problème ?

Comment le choix du modèle de problème affecte-t-il les algorithmes potentiels ? Décrivez un algorithme pour chaque modèle de problème.

Considérez une implémentation de saisie semi-automatique qui repose sur une recherche séquentielle pour trouver tous les termes correspondants. Quel est l'ordre de grandeur en notation grand O dans le pire des cas pour le calcul d'une seule requête de saisie semi-automatique par rapport à N, le nombre de termes potentiels ?

Considérez une implémentation de saisie semi-automatique qui trie la liste des termes potentiels et effectue ensuite une recherche binaire pour trouver les termes correspondants. Si l'ordre de grandeur de l'algorithme de tri est en O(N log N), quel est l'ordre de grandeur en notation grand O dans le pire des cas pour le calcul d'une seule requête de saisie semi-automatique par rapport à N, le nombre de termes potentiels ?

Pourquoi les concepteurs d'algorithmes pourraient-ils préférer utiliser la recherche binaire plutôt que la recherche séquentielle pour la saisie semi-automatique ?

Dans un espace 1D où chaque point est défini par des coordonnées x, un problème courant est de trouver la paire de points la plus proche dans l'espace : la paire de points qui a la plus petite distance parmi toutes les paires de points potentielles. Quel est un algorithme par force brute pour résoudre ce problème de la paire de points la plus proche en 1D ? Quel est l'ordre de grandeur en notation grand O de cet algorithme ?

Dans un espace 2D, chaque point est défini par des coordonnées (x, y). Quel est un algorithme par force brute pour résoudre le problème de la paire de points la plus proche en 2D ?

Quels sont les sous-problèmes récursifs dans un algorithme diviser pour régner pour résoudre le problème de la paire la plus proche ?

Les images numériques sont représentées dans les ordinateurs comme une grille 2D de pixels colorés. En édition d'image, le problème du remplissage par inondation prend un pixel de départ donné et remplace tous les pixels d'une région contiguë qui partagent la même couleur par une couleur différente. Comment pouvons-nous représenter les pixels colorés d'une image numérique comme un graphe avec des sommets et des arêtes pour le problème du remplissage par inondation ?

Comment devrions-nous modifier un algorithme de parcours de graphe pour résoudre le problème du remplissage par inondation en utilisant votre représentation de graphe ?

Qu'est-ce qu'un algorithme de réduction pour passer du problème du remplissage par inondation au problème du parcours de graphe ? Dans ce cas, l'algorithme de parcours de graphe ne peut pas être modifié. Au lieu de cela, définissez une étape de prétraitement pour créer une représentation de graphe qui encode la règle de même couleur du remplissage par inondation.