Révision : Bac tri

Qu'est-ce qu'un algorithme ?

Un algorithme est une suite d'instructions permettant de résoudre un problème ou d'accomplir une tâche.

Qu'est-ce que la complexité d'un algorithme ?

La complexité d'un algorithme mesure les ressources nécessaires (temps et espace) pour l'exécuter.

Comment évaluer la complexité temporelle ?

On évalue la complexité temporelle en utilisant la notation Big O, qui décrit le comportement asymptotique.

Vrai ou faux : Un tri par sélection est efficace pour de grandes listes.

Faux. Le tri par sélection est inefficace pour de grandes listes, sa complexité est O(n²).

Qu'est-ce qu'un tableau ?

Un tableau est une structure de données qui stocke un ensemble d'éléments de même type en mémoire contiguë.

Qu'est-ce qu'une liste chaînée ?

Une liste chaînée est une collection d'éléments où chaque élément pointe vers le suivant, permettant une insertion efficace.

Complétez : La complexité d'un tri rapide est généralement _____

O(n log n) dans le meilleur des cas, mais O(n²) dans le pire cas.

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure de données où chaque nœud a au maximum deux enfants, souvent utilisés pour le tri et la recherche.

Qu'est-ce que le tri fusion ?

Le tri fusion est un algorithme de tri qui divise le tableau en sous-tableaux, les trie puis les fusionne.

Vrai ou faux : Le tri à bulles est un algorithme optimal.

Faux. Le tri à bulles est peu performant avec une complexité O(n²).

Comment fonctionne l'algorithme Dijkstra ?

L'algorithme de Dijkstra trouve le chemin le plus court d'un nœud à tous les autres dans un graphe pondéré.

Qu'est-ce qu'un graphe ?

Un graphe est une collection de nœuds (sommets) et de liens (arêtes) entre eux, représentant des relations.

Complétez : La récursivité est une méthode où la fonction s'appelle _____

elle-même pour résoudre un sous-problème.

Quels sont les types de tri ?

Les types de tri incluent le tri par insertion, selection, fusion, rapide, et à bulles.

Vrai ou faux : Le tri par insertion fonctionne mieux sur des listes presque triées.

Vrai. Sa complexité est proche de O(n) dans ce cas.

Que signifie O(n log n) ?

C'est une notation qui décrit une complexité algébrique, indiquant qu'un algorithme croît en proportion de n multiplié par log(n).

Qu'est-ce qu'une fonction itérative ?

Une fonction itérative utilise des boucles pour répéter des instructions jusqu'à ce qu'une condition soit remplie.

Qu'est-ce que la programmation dynamique ?

C'est une méthode pour résoudre des problèmes complexes en les décomposant en sous-problèmes simples et en mémorisant les résultats.

Qu'est-ce qu'un tableau associatif ?

Un tableau associatif est une collection de paires clé-valeur, permettant un accès rapide aux valeurs par leur clé.

Vrai ou faux : Les algorithmes gloutons garantissent toujours la meilleure solution.

Faux. Les algorithmes gloutons ne garantissent pas toujours la solution optimale.

Qu'est-ce qu'un tri stable ?

Un tri stable conserve l'ordre des éléments égaux dans la liste après le tri.

Qu'est-ce qu'une pile ?

Une pile est une structure de données qui suit le principe LIFO (last in, first out).