Algorithmique avancée : structures de données et complexité
Fiche de révision · Numérique et sciences informatiques · 1ère
L'essentiel du cours
Chapitre 1 : Les structures de données : organiser l'information
L'accès à un élément d'un tableau par son indice est direct et rapide.
Chapitre 2 : Piles et files : ranger pour mieux traiter
La pile mémorise l'ordre inverse des actions ; la file conserve l'ordre d'arrivée.
Chapitre 3 : Dictionnaires et ensembles : accès par clé
Avec une clé, l'accès à une valeur est direct, comme chercher un mot dans un dictionnaire papier grâce à l'ordre alphabétique.
Chapitre 4 : Complexité : mesurer l'efficacité d'un algorithme
La complexité permet de comparer des algorithmes indépendamment de la machine utilisée.
Teste-toi · 8 questions
1.Quelle structure de données fonctionne selon le principe LIFO ?
Voir la réponseMasquer la réponse
Réponse : Une pile
LIFO = Last In, First Out : le dernier élément ajouté est le premier retiré, c'est la pile.
2.Dans un tableau Python de n éléments, quel est l'indice du dernier élément ?
Voir la réponseMasquer la réponse
Réponse : n-1
Les indices commencent à 0, donc le dernier élément est à l'indice n-1.
3.Quelle est la complexité d'une recherche séquentielle dans un tableau de taille n ?
Voir la réponseMasquer la réponse
Réponse : O(n)
On peut devoir parcourir tous les éléments du tableau, donc le nombre d'opérations est proportionnel à n.
4.Un dictionnaire associe :
- A.des clés uniques à des valeurs
- B.des éléments ordonnés sans doublon
- C.des valeurs uniquement entières
- D.des indices numériques à des valeurs
Voir la réponseMasquer la réponse
Réponse A : des clés uniques à des valeurs
Un dictionnaire est une collection de couples clé-valeur où chaque clé est unique.
5.Laquelle de ces opérations est typique d'une file ?
- A.Dépiler
- B.Empiler
- C.Insérer au milieu
- D.Défiler
Voir la réponseMasquer la réponse
Réponse D : Défiler
Une file utilise les opérations enfiler et défiler ; empiler/dépiler sont pour une pile.
6.Un algorithme de tri par insertion a une complexité en :
- A.O(n)
- B.O(n log n)
- C.O(n²)
- D.O(log n)
Voir la réponseMasquer la réponse
Réponse C : O(n²)
Le tri par insertion compare chaque élément à presque tous les précédents, ce qui donne un ordre quadratique O(n²).
7.Pourquoi la recherche dichotomique est-elle plus efficace que la recherche séquentielle sur un tableau trié ?
Voir la réponseMasquer la réponse
Réponse : Elle divise l'espace de recherche par deux à chaque étape
La dichotomie réduit de moitié la zone à explorer à chaque comparaison, d'où une complexité O(log n).
8.Quel type de structure est un ensemble (set) en Python ?
Voir la réponseMasquer la réponse
Réponse : Une collection non ordonnée d'éléments uniques
Un ensemble stocke des éléments uniques, sans ordre garanti et sans doublon.