Qu'est-ce qu'un algorithme ?
Une suite finie, ordonnée et non ambiguë d’instructions transformant des entrées en sorties.
Qu'est-ce qui différencie une affectation d'une égalité mathématique ?
L'affectation modifie la valeur d'une variable, contrairement à une égalité mathématique.
Qu'est-ce qu'un invariant dans une boucle ?
Une propriété qui reste vraie à chaque itération de la boucle.
Que combine la correction totale d'un algorithme ?
La correction partielle et la terminaison.
Qu'assure la correction partielle dans la correction totale ?
Elle est garantie par les préconditions, postconditions et invariants.
Quelle différence d'exécution existe entre une boucle tant qu'et une boucle répéter...jusqu'à ?
La boucle tant que peut ne jamais s’exécuter, la boucle répéter...jusqu’à s’exécute au moins une fois.
Quel est l'ordre croissant usuel des complexités en notation O ?
O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), puis O(n!).
Qu'impose O(g) en termes de bornes pour une fonction ?
Une borne supérieure.
Qu'impose Ω(g) en termes de bornes pour une fonction ?
Une borne inférieure.
Que représente Θ(g) pour la croissance d'une fonction ?
Une croissance précise à constante près.
Quelle complexité donne la récurrence T(n)=T(n−1)+O(1) ?
O(n).
Quelle complexité donne la récurrence T(n)=T(n/2)+O(1) ?
O(log n).
Que garantit la complexité amortie ?
Un coût moyen sur une séquence d’opérations.
Quelle différence existe entre un TAD et une structure de données ?
Le TAD décrit les opérations, la structure est une implémentation concrète.
Quelles sont les caractéristiques d'un tableau en termes d'indexation et d'accès ?
Un tableau est contigu, indexé de 0 à n−1, avec accès A[i] en O(1).
Quel est le coût amorti de l’ajout en fin dans un tableau dynamique ?
L’ajout en fin coûte O(1) amorti.
Pourquoi l’insertion ou suppression au milieu d’un tableau dynamique coûte O(n) ?
À cause des décalages nécessaires.
Comment calcule-t-on la somme A[l..r] avec les préfixes cumulés ?
La somme vaut P[r+1]−P[l] avec P[0]=0 et P[i+1]=P[i]+A[i].
Quel est le temps et la mémoire nécessaires pour calculer une somme avec prétraitement de préfixes cumulés ?
Le prétraitement prend O(n) et la somme se calcule en O(1).
Quelle est la complexité d’insertion après un nœud connu dans une liste chaînée ?
L’insertion après un nœud connu coûte O(1).
Quelle est la complexité d’accès au iᵉ nœud et de recherche dans une liste chaînée ?
L’accès et la recherche coûtent O(n).
Comment fonctionne la détection de cycle de Floyd en termes de pointeurs et complexité ?
Elle utilise un pointeur lent et un rapide en O(n) temps et O(1) mémoire.
Qu'est-ce qu'une collision en hachage ?
Plusieurs clés produisent le même indice de hachage.
Comment gère-t-on une collision en hachage ?
Par chaînage ou adressage ouvert.
Que signifie que deux clés égales produisent le même hash ?
Elles ont le même indice de hachage.
Que signifie que deux hashes égaux n'impliquent pas des clés égales ?
Des clés différentes peuvent avoir le même hash.
Quelle est la formule du facteur de charge d'une table de hachage ?
α = n/m, avec n le nombre de clés et m la capacité.
Quelle condition est nécessaire pour la recherche binaire ?
Un tableau trié avec accès direct.
Qu'est-ce qu'un tri stable ?
Il conserve l'ordre relatif des éléments aux clés égales.
Quel est le coût du tri par comptage et quand est-il adapté ?
O(n+k), adapté si l'univers k est petit par rapport à n.
Qu'est-ce qu'une fonction récursive doit posséder pour résoudre un problème ?
Un cas de base et une progression vers ce cas.
Que conserve chaque appel récursif en mémoire ?
Ses paramètres, ses variables locales et son adresse de retour.
Quelle est la complexité mémoire liée à la profondeur des appels récursifs ?
Elle est en O(profondeur).
Qu'est-ce que la mémoïsation en programmation ?
Une approche top-down qui mémorise les résultats des sous-problèmes déjà calculés.
Quels concepts la programmation dynamique exploite-t-elle ?
Des sous-problèmes chevauchants et une sous-structure optimale.
Quels éléments définit la programmation dynamique ?
Des états, des transitions et des cas de base.
Quels sont les étapes clés d'une recette de programmation dynamique ?
Définir l’état minimal, la transition, les cas de base, le mode et l’ordre de calcul, et éventuellement la reconstruction.
Qu'est-ce qu'un arbre en théorie des graphes ?
Un graphe connexe sans cycle.
Combien d'arêtes possède un arbre avec n nœuds ?
n−1 arêtes.
Quelle est la différence entre profondeur et hauteur dans un arbre ?
La profondeur est la distance racine-nœud, la hauteur est le plus long chemin nœud-feuille.
Quels sont les parcours préordre, infixe, postordre et largeur de A(B(D,E),C(F,G)) ?
ABDECFG, DBEACFG, DEBFGCA et ABCDEFG respectivement.
Quelle propriété caractérise un arbre binaire de recherche ?
Les clés du sous-arbre gauche sont inférieures à la clé du nœud, celles du droit sont supérieures.
Quel est le coût des opérations dans un ABR équilibré et dégénéré ?
O(log n) si équilibré, O(n) si dégénéré.
Combien coûte la recherche, insertion et suppression dans un ABR en fonction de la hauteur ?
Ces opérations coûtent O(h).
Quelle structure favorise les requêtes par intervalle sur disque ?
Le B+ arbre.
Que contient un graphe G=(V,E) ?
Des sommets et des arêtes ou arcs.
Quelles sont les caractéristiques possibles d'un graphe ?
Il peut être orienté ou non orienté, pondéré ou non pondéré.
Quelle mémoire utilise une matrice d’adjacence ?
Elle utilise O(V²) mémoire.
Quelle est la complexité pour tester une arête avec une matrice d’adjacence ?
Le test s'effectue en O(1).
Quelle mémoire utilise une liste d’adjacence et pour quel type de graphes est-elle adaptée ?
Elle utilise O(V+E) mémoire et convient aux graphes clairsemés.
Quelle est la somme des degrés dans un graphe non orienté ?
Elle vaut 2E.
Quelle est la somme des degrés entrants et sortants dans un graphe orienté ?
Chacune vaut E.
Quelle structure de données utilise BFS et comment explore-t-il ?
BFS utilise une file et explore par niveaux.
Qu'est-ce que relâcher (u,v,w) dans un algorithme de plus court chemin ?
Mettre à jour d[v] et le prédécesseur si d[u]+w<d[v].
Quelle méthode d'algorithme convient aux arêtes de même coût ?
L'algorithme BFS.
Quel algorithme gère les poids négatifs et détecte les cycles négatifs ?
L'algorithme de Bellman-Ford.
Quelle est la complexité en temps de Dijkstra avec un tas ?
O((V+E)log V).
Quelle est la complexité en mémoire de Floyd-Warshall ?
O(V²).
Qu'est-ce qu'un arbre couvrant minimal ?
Un arbre reliant tous les sommets avec V−1 arêtes et poids total minimal.
Comment Prim choisit-il l'arête à ajouter à l'arbre ?
Il ajoute l’arête sortante la moins chère.
Quel est le coût amorti de Union-Find avec compression de chemin et rang ?
O(α(n)).
Quelles étapes caractérisent la méthode diviser-régner ?
Elle divise le problème puis combine les solutions.
Quelle caractéristique distingue la méthode gloutonne ?
Elle choisit localement de manière irréversible avec une preuve nécessaire.
Quelle particularité a la programmation dynamique ?
Elle réutilise des sous-solutions.
Qu'est-ce que le backtracking ?
Une méthode qui construit un choix, explore récursivement puis annule en cas d'impasse.
À quels types de problèmes s'appliquent les techniques deux pointeurs et fenêtre glissante ?
Aux tableaux et intervalles.
Quelle complexité a l'algorithme KMP ?
O(n+m).
Quelle complexité a l'algorithme Kadane ?
O(n).
Quelle complexité a Quickselect dans le pire cas ?
O(n²).
Teste tes connaissances avec un QCM de 33 questions sur Algorithmique et structures de données.
1. Quel énoncé décrit correctement un algorithme ?
2. Lors de la conception d’une preuve par invariants, que doit être un invariant de boucle ?
Révisez le cours complet dans la fiche de révision de Algorithmique et structures de données.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards