Flashcard: Algorithmique et structures de données — 69 carte

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²).