Qu'est-ce qu'un graphe biparti ?

Un graphe biparti est un graphe dont les sommets peuvent être divisés en deux ensembles disjoints, sans arêtes entre les sommets du même ensemble.

Qu'est-ce qu'un algorithme de backtracking ?

Un algorithme de backtracking explore toutes les solutions possibles et revient en arrière lorsqu'une solution ne peut pas être atteinte.

Qu'est-ce que l'algorithme de Dijkstra ?

L'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court entre deux nœuds dans un graphe pondéré.

Qu'est-ce qu'un algorithme de tri par tas ?

Le tri par tas utilise une structure de données appelée tas pour trier les éléments en les extrayant dans l'ordre.

Qu'est-ce que la recherche en profondeur (DFS) ?

La recherche en profondeur explore un graphe en suivant un chemin jusqu'à ce qu'il atteigne un nœud sans enfants, puis revient en arrière.

Qu'est-ce qu'une pile ?

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré.

Donnez un exemple d'algorithme glouton.

L'algorithme de Kruskal pour trouver l'arbre couvrant minimal est un exemple d'algorithme glouton.

Citez deux algorithmes de tri courants.

Le tri à bulles et le tri rapide (quicksort) sont deux algorithmes de tri courants.

Quels sont les avantages de la récursivité ?

La récursivité simplifie le code et permet de résoudre des problèmes complexes de manière élégante.

Qu'est-ce qu'un algorithme de recherche ?

Un algorithme de recherche est une méthode pour trouver un élément spécifique dans une structure de données.

Qu'est-ce qu'un tri par sélection ?

Le tri par sélection consiste à trouver l'élément le plus petit et à le placer au début de la liste, puis à répéter ce processus.

Qu'est-ce qu'un algorithme de compression ?

Un algorithme de compression réduit la taille des données pour économiser de l'espace de stockage ou améliorer la vitesse de transmission.

Qu'est-ce qu'un graphe en algorithmique ?

Un graphe est une structure de données composée de nœuds (sommets) et d'arêtes qui les relient.

Qu'est-ce qu'une fonction récursive ?

Une fonction récursive est une fonction qui s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes.

Qu'est-ce qu'un tri par insertion ?

Le tri par insertion construit progressivement une liste triée en insérant chaque nouvel élément à sa position correcte.

Qu'est-ce qu'un graphe orienté acyclique (DAG) ?

Un DAG est un graphe orienté qui ne contient pas de cycles, permettant une représentation hiérarchique des relations.

Quels sont les éléments fondamentaux d'un algorithme ?

Les éléments fondamentaux d'un algorithme incluent l'entrée, le traitement, et la sortie.

Quelle est la méthode de programmation dynamique la plus connue ?

La méthode de la programmation dynamique la plus connue est l'algorithme de Fibonacci.

Qu'est-ce qu'un algorithme de validation ?

Un algorithme de validation vérifie si une solution proposée satisfait toutes les contraintes d'un problème.

Qu'est-ce que la recherche en largeur (BFS) ?

La recherche en largeur explore un graphe niveau par niveau, visitant tous les nœuds d'un niveau avant de passer au suivant.

Qu'est-ce qu'un algorithme de partitionnement ?

Un algorithme de partitionnement divise un ensemble de données en sous-ensembles selon des critères spécifiques.

Qu'est-ce qu'une file ?

Une file est une structure de données qui suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré.

Qu'est-ce qu'un algorithme de recherche de minimum ?

Un algorithme de recherche de minimum trouve la valeur minimale dans un ensemble de données.

Quelle est la différence entre complexité temporelle et complexité spatiale ?

La complexité temporelle évalue le temps d'exécution d'un algorithme, tandis que la complexité spatiale évalue la mémoire utilisée.

Qu'est-ce qu'un algorithme de Monte Carlo ?

Un algorithme de Monte Carlo utilise des méthodes aléatoires pour résoudre des problèmes mathématiques ou d'optimisation.

Qu'est-ce qu'un algorithme ?

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

Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?

Un arbre binaire a au maximum deux enfants par nœud, tandis qu'un arbre binaire de recherche respecte l'ordre des valeurs pour faciliter la recherche.

Qu'est-ce qu'un arbre AVL ?

Un arbre AVL est un arbre binaire de recherche auto-équilibré, garantissant que la hauteur des sous-arbres diffère d'au plus un.

Qu'est-ce qu'un algorithme de classification ?

Un algorithme de classification attribue des étiquettes à des données en fonction de leurs caractéristiques, souvent utilisé en apprentissage automatique.

Qu'est-ce que le tri par fusion ?

Le tri par fusion est un algorithme de tri qui divise la liste en sous-listes, les trie, puis les fusionne en une seule liste triée.

Qu'est-ce qu'un algorithme de hachage ?

Un algorithme de hachage transforme des données d'entrée en une valeur fixe, facilitant la recherche et la vérification d'intégrité.

Qu'est-ce qu'un problème NP-complet ?

Un problème NP-complet est un problème pour lequel aucune solution efficace n'est connue, mais dont la solution peut être vérifiée rapidement.

Qu'est-ce que la programmation par contrainte ?

La programmation par contrainte est une méthode de résolution de problèmes qui impose des restrictions sur les variables pour trouver des solutions.

Qu'est-ce qu'un arbre rouge-noir ?

Un arbre rouge-noir est un arbre binaire de recherche qui maintient un équilibre en imposant des règles de coloration sur les nœuds.

Qu'est-ce qu'un algorithme de simulation ?

Un algorithme de simulation modélise le comportement d'un système pour analyser ses performances ou ses résultats.

Qu'est-ce que l'optimisation combinatoire ?

L'optimisation combinatoire est la recherche de la meilleure solution parmi un ensemble fini de solutions possibles.

Qu'est-ce qu'un algorithme dynamique ?

Un algorithme dynamique résout des problèmes en les décomposant en sous-problèmes et en mémorisant les résultats pour éviter les calculs redondants.

Quels sont les types de graphes ?

Les types de graphes incluent les graphes orientés, non orientés, pondérés et non pondérés.

Qu'est-ce qu'un algorithme glouton ?

Un algorithme glouton fait des choix optimaux locaux dans l'espoir d'atteindre une solution globale optimale.

Qu'est-ce que la recherche de chemin dans un graphe ?

La recherche de chemin dans un graphe consiste à trouver un chemin entre deux nœuds, souvent en utilisant des algorithmes comme Dijkstra ou A*.

Qu'est-ce qu'un algorithme de recherche de maximum ?

Un algorithme de recherche de maximum trouve la valeur maximale dans un ensemble de données.

Qu'est-ce qu'un algorithme de tri ?

Un algorithme de tri est une méthode pour réorganiser les éléments d'une liste dans un ordre spécifique, comme croissant ou décroissant.

Qu'est-ce qu'un algorithme de séparation et conquête ?

Un algorithme de séparation et conquête divise un problème en sous-problèmes, résout chaque sous-problème, puis combine les résultats.

Quelle est la différence entre recherche linéaire et recherche binaire ?

La recherche linéaire parcourt chaque élément un par un, tandis que la recherche binaire divise la liste en deux à chaque étape, nécessitant une liste triée.

Qu'est-ce qu'une complexité algorithmique ?

La complexité algorithmique mesure le temps et l'espace nécessaires à un algorithme pour s'exécuter en fonction de la taille de l'entrée.

Qu'est-ce qu'un arbre de décision ?

Un arbre de décision est un modèle prédictif qui utilise une structure arborescente pour représenter des décisions et leurs conséquences.

Qu'est-ce qu'un tableau associatif ?

Un tableau associatif est une structure de données qui associe des clés à des valeurs, permettant un accès rapide aux données.

Qu'est-ce qu'un arbre en algorithmique ?

Un arbre est une structure de données hiérarchique composée de nœuds, où chaque nœud a un parent et zéro ou plusieurs enfants.

Qu'est-ce que la recherche heuristique ?

La recherche heuristique utilise des règles empiriques pour trouver des solutions approximatives à des problèmes complexes.

Algorithmes Fondamentaux

Introduction aux concepts de base des algorithmes et à leur application dans la résolution de problèmes quotidiens

Level: basic
Languages: fr → fr
Cards: 49
Markdown: Algorithmes Fondamentaux (.md)

Flashcards (49)

#	Front (Term / Question)	Back (Definition / Answer)
1	Qu'est-ce qu'un graphe biparti ?	Un graphe biparti est un graphe dont les sommets peuvent être divisés en deux ensembles disjoints, sans arêtes entre les sommets du même ensemble.
2	Qu'est-ce qu'un algorithme de backtracking ?	Un algorithme de backtracking explore toutes les solutions possibles et revient en arrière lorsqu'une solution ne peut pas être atteinte.
3	Qu'est-ce que l'algorithme de Dijkstra ?	L'algorithme de Dijkstra est utilisé pour trouver le chemin le plus court entre deux nœuds dans un graphe pondéré.
4	Qu'est-ce qu'un algorithme de tri par tas ?	Le tri par tas utilise une structure de données appelée tas pour trier les éléments en les extrayant dans l'ordre.
5	Qu'est-ce que la recherche en profondeur (DFS) ?	La recherche en profondeur explore un graphe en suivant un chemin jusqu'à ce qu'il atteigne un nœud sans enfants, puis revient en arrière.
6	Qu'est-ce qu'une pile ?	Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré.
7	Donnez un exemple d'algorithme glouton.	L'algorithme de Kruskal pour trouver l'arbre couvrant minimal est un exemple d'algorithme glouton.
8	Citez deux algorithmes de tri courants.	Le tri à bulles et le tri rapide (quicksort) sont deux algorithmes de tri courants.
9	Quels sont les avantages de la récursivité ?	La récursivité simplifie le code et permet de résoudre des problèmes complexes de manière élégante.
10	Qu'est-ce qu'un algorithme de recherche ?	Un algorithme de recherche est une méthode pour trouver un élément spécifique dans une structure de données.
11	Qu'est-ce qu'un tri par sélection ?	Le tri par sélection consiste à trouver l'élément le plus petit et à le placer au début de la liste, puis à répéter ce processus.
12	Qu'est-ce qu'un algorithme de compression ?	Un algorithme de compression réduit la taille des données pour économiser de l'espace de stockage ou améliorer la vitesse de transmission.
13	Qu'est-ce qu'un graphe en algorithmique ?	Un graphe est une structure de données composée de nœuds (sommets) et d'arêtes qui les relient.
14	Qu'est-ce qu'une fonction récursive ?	Une fonction récursive est une fonction qui s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes.
15	Qu'est-ce qu'un tri par insertion ?	Le tri par insertion construit progressivement une liste triée en insérant chaque nouvel élément à sa position correcte.
16	Qu'est-ce qu'un graphe orienté acyclique (DAG) ?	Un DAG est un graphe orienté qui ne contient pas de cycles, permettant une représentation hiérarchique des relations.
17	Quels sont les éléments fondamentaux d'un algorithme ?	Les éléments fondamentaux d'un algorithme incluent l'entrée, le traitement, et la sortie.
18	Quelle est la méthode de programmation dynamique la plus connue ?	La méthode de la programmation dynamique la plus connue est l'algorithme de Fibonacci.
19	Qu'est-ce qu'un algorithme de validation ?	Un algorithme de validation vérifie si une solution proposée satisfait toutes les contraintes d'un problème.
20	Qu'est-ce que la recherche en largeur (BFS) ?	La recherche en largeur explore un graphe niveau par niveau, visitant tous les nœuds d'un niveau avant de passer au suivant.
21	Qu'est-ce qu'un algorithme de partitionnement ?	Un algorithme de partitionnement divise un ensemble de données en sous-ensembles selon des critères spécifiques.
22	Qu'est-ce qu'une file ?	Une file est une structure de données qui suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré.
23	Qu'est-ce qu'un algorithme de recherche de minimum ?	Un algorithme de recherche de minimum trouve la valeur minimale dans un ensemble de données.
24	Quelle est la différence entre complexité temporelle et complexité spatiale ?	La complexité temporelle évalue le temps d'exécution d'un algorithme, tandis que la complexité spatiale évalue la mémoire utilisée.
25	Qu'est-ce qu'un algorithme de Monte Carlo ?	Un algorithme de Monte Carlo utilise des méthodes aléatoires pour résoudre des problèmes mathématiques ou d'optimisation.
26	Qu'est-ce qu'un algorithme ?	Un algorithme est une suite d'instructions ou de règles définies pour résoudre un problème ou accomplir une tâche.
27	Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?	Un arbre binaire a au maximum deux enfants par nœud, tandis qu'un arbre binaire de recherche respecte l'ordre des valeurs pour faciliter la recherche.
28	Qu'est-ce qu'un arbre AVL ?	Un arbre AVL est un arbre binaire de recherche auto-équilibré, garantissant que la hauteur des sous-arbres diffère d'au plus un.
29	Qu'est-ce qu'un algorithme de classification ?	Un algorithme de classification attribue des étiquettes à des données en fonction de leurs caractéristiques, souvent utilisé en apprentissage automatique.
30	Qu'est-ce que le tri par fusion ?	Le tri par fusion est un algorithme de tri qui divise la liste en sous-listes, les trie, puis les fusionne en une seule liste triée.
31	Qu'est-ce qu'un algorithme de hachage ?	Un algorithme de hachage transforme des données d'entrée en une valeur fixe, facilitant la recherche et la vérification d'intégrité.
32	Qu'est-ce qu'un problème NP-complet ?	Un problème NP-complet est un problème pour lequel aucune solution efficace n'est connue, mais dont la solution peut être vérifiée rapidement.
33	Qu'est-ce que la programmation par contrainte ?	La programmation par contrainte est une méthode de résolution de problèmes qui impose des restrictions sur les variables pour trouver des solutions.
34	Qu'est-ce qu'un arbre rouge-noir ?	Un arbre rouge-noir est un arbre binaire de recherche qui maintient un équilibre en imposant des règles de coloration sur les nœuds.
35	Qu'est-ce qu'un algorithme de simulation ?	Un algorithme de simulation modélise le comportement d'un système pour analyser ses performances ou ses résultats.
36	Qu'est-ce que l'optimisation combinatoire ?	L'optimisation combinatoire est la recherche de la meilleure solution parmi un ensemble fini de solutions possibles.
37	Qu'est-ce qu'un algorithme dynamique ?	Un algorithme dynamique résout des problèmes en les décomposant en sous-problèmes et en mémorisant les résultats pour éviter les calculs redondants.
38	Quels sont les types de graphes ?	Les types de graphes incluent les graphes orientés, non orientés, pondérés et non pondérés.
39	Qu'est-ce qu'un algorithme glouton ?	Un algorithme glouton fait des choix optimaux locaux dans l'espoir d'atteindre une solution globale optimale.
40	Qu'est-ce que la recherche de chemin dans un graphe ?	La recherche de chemin dans un graphe consiste à trouver un chemin entre deux nœuds, souvent en utilisant des algorithmes comme Dijkstra ou A*.
41	Qu'est-ce qu'un algorithme de recherche de maximum ?	Un algorithme de recherche de maximum trouve la valeur maximale dans un ensemble de données.
42	Qu'est-ce qu'un algorithme de tri ?	Un algorithme de tri est une méthode pour réorganiser les éléments d'une liste dans un ordre spécifique, comme croissant ou décroissant.
43	Qu'est-ce qu'un algorithme de séparation et conquête ?	Un algorithme de séparation et conquête divise un problème en sous-problèmes, résout chaque sous-problème, puis combine les résultats.
44	Quelle est la différence entre recherche linéaire et recherche binaire ?	La recherche linéaire parcourt chaque élément un par un, tandis que la recherche binaire divise la liste en deux à chaque étape, nécessitant une liste triée.
45	Qu'est-ce qu'une complexité algorithmique ?	La complexité algorithmique mesure le temps et l'espace nécessaires à un algorithme pour s'exécuter en fonction de la taille de l'entrée.
46	Qu'est-ce qu'un arbre de décision ?	Un arbre de décision est un modèle prédictif qui utilise une structure arborescente pour représenter des décisions et leurs conséquences.
47	Qu'est-ce qu'un tableau associatif ?	Un tableau associatif est une structure de données qui associe des clés à des valeurs, permettant un accès rapide aux données.
48	Qu'est-ce qu'un arbre en algorithmique ?	Un arbre est une structure de données hiérarchique composée de nœuds, où chaque nœud a un parent et zéro ou plusieurs enfants.
49	Qu'est-ce que la recherche heuristique ?	La recherche heuristique utilise des règles empiriques pour trouver des solutions approximatives à des problèmes complexes.