Une bonne connaissance des algorithmes et des structures de données est indispensable pour un développeur. C’est aussi présent dans 97 Things Every Programmer Should Know. J’ai suivi le cours Algorithms: Design and Analysis, de l’université de Stanford, sur Coursera. Ce cours est passionnant et exigeant. Il m’a permis de réviser des algos appris à l’école, d’en découvrir de nouveau et d’implémenter tout cela en Scala. Il est constitué de deux parties de 6 semaines. Voici un petit mémo qui me servira de pense-bête pour me remémorer tous les choses apprises durant ce cours. J’ai laissé la plupart des termes en anglais car il est plus aisé de trouver de l’information en anglais sur ces sujets. Voici le programme :

Première partie

Introduction

Karatsuba multiplication : pour montrer qu’il peut toujours y avoir un meilleur algorithme, même pour quelque chose d’aussi trivial qu’une multiplication.

merge sort : introduction à diviser pour régner

Diviser pour régner

  • Diviser en sous-problème plus petit
  • Résoudre récursivement chaque sous-problème
  • Combiner le résultat des sous-problèmes

Voici deux autres algorithmes pour illustrer ce principe.

counting inversion : étant donné un tableau A contenant les nombres 1,2,…,n, il faut déterminer le nombre d’inversions, c’est-à-dire le nombre de couples d’indices (i,j) tels que A[i] > A[j]. Cela permet de mesurer la similarité entre 2 listes rankés, pour du collaborative filtering par ex.

Algorithme de Strassen pour la multiplication de matrices.

Master method

C’est une boite noire pour résoudre les récurrences.

Quick sort

Un algorithme star, tri en O(nlog n), travail in-place (économe en mémoire). L’idée principale est de partitionner autour d’un pivot.

Graphes et algorithme de contraction

Le découpage d’un graphe est une partition des nœuds en deux ensembles non vides.

Le problème du minimum cut : étant donné un graphe non orienté, déterminer un découpage qui minimise le nombre d’arcs traversants. C’est utile pour identifier les goulots d’étranglement, pour détecter les communautés dans un réseau social, pour segmenter une image.

Pour représenter un graphe, il existe 2 choix : la liste d’adjacence O(m+n) et la matrice d’adjacence O(n2), chacun ayant des avantages et des inconvénients en fonction de la densité du graphe et des opérations nécessaires.

L’algorithme de Karger utilise une contraction aléatoire et demande donc à être exécuté plusieurs fois.

Recherche dans les graphes

BFS : parcours en largeur. O(m+n) avec une queue (FIFO). Utile pour les plus court chemin

DFS : parcours en profondeur. O(m+n) avec une stack (LIFO). Utile pour calculer un ordre topologique DAG

SCC : Kosaraju. O(m+n). basé sur DFS

Algorithme de Dijkstra

Single-Source Shortest Path. Implémentation naïve : O(mn). Implémentation avec une heap : O(mlog n). Permet de souligner l’importance de l’utilisation d’une structure de données adaptée. Ne fonctionne pas avec des longueurs négatives.

Heap

insert et extract-min en O(log n). Permet de souligner l’importance de l’utilisation d’une structure de données adaptée. PriorityQueue in Scala. Application : maintenir la médiane en utilisant 2 heaps.

BST

Comme des tableaux triés mais supporte aussi l’insertion et la suppression en O(log n) au lieu de O(n). La plupart des opérations dans un arbre sont en O(height), c’est-à-dire entre O(n) dans le cas d’une chaine et O(log n) dans le cas d’un arbre parfaitement balancé. C’est pour cela que les arbres balancés sont intéressants, comme les Red-black trees.

Les BST peuvent être stocké dans un tableau.

Il y a les Red-black tree mais aussi : AVL tree, …, B-tree.

Hashing

Hash table : insert, delete, lookup in O(1). Application : de-duplication, 2-SUM problem

Bloom filter

fast insert and lookup, plus économe en mémoire qu’une HashMap. Inconvénients : faux positif.

Utilisation : correcteur d’orthographe, liste de mots de passe interdits, routeurs réseau

Deuxième partie

Les algorithmes greedy (glouton)

  • Facile de proposer de multiples algorithmes greedy pour plusieurs problèmes
  • Facile d’analyser le temps d’exécution
  • Difficile de prouver la justesse

Attention : la plupart des algos greedy ne sont pas corrects (ex: Dijkstra avec des longueurs négatives).

Ordonnancement de tâches

Problème d’ordonnancement de tâches : dans quel ordre doit-on exécuter des tâches pour minimiser la somme pondérée des temps d’achèvement. Trier par ordre décroissant de wj/lj. O(nlogn) : pour le tri.

Algorithme de Prim

Minimum spanning tree, Arbres couvrants minimaux. Le but est de connecter un ensemble de points au moindre cout. Il existe 2 algos très rapides, en O(m log n) : Prim et Kruskal. Le graphe en entrée est un graphe connexe et non orienté. L’algo de Prim passe de O(mn) en O(m log n) en utilisant une structure de donnée adaptée, à savoir une heap (tas).

Algorithme de Kruskal

L’algo de Kruskal utilise lui une structure de données Union-Find pour détecter les cycles. Cette structure permet de maintenir des partitions d’un ensemble d’objets.

Clustering

Il est aussi connu sous le nom de unsupervised learning. Le but est de classer n points en groupe cohérents. Soit k le nombre de clusters voulus, l’espace maximum d’un k-clustering est minseparated\ p,q d(p,q). Le problème du Max-spacing k-Clustering : Soit une distance d et un nombre k, déterminer le k-Clustering avec l’espace maximum.

Huffman code

Un code binaire est une association entre chaque caractère d’un alphabet et une chaine binaire. Un code binaire peut-être vu comme un arbre binaire. Le but est de déterminer le meilleur encodage binaire. Définition : étant la probabilité pour chaque caractère, déterminer un arbre qui minimise la longueur d’encodage moyenne. L’idée de l’algo est de construire l’arbre du bas vers le haut (bottom-up) en effectuant des fusions successives.

Introduction à la programmation dynamique

Le problème du Weighted Independant Set (WIS) permet d’introduire la programmation dynamique. Soit un chemin avec des poids sur les nœuds, il faut choisir un ensemble de nœuds non adjacents maximisant la somme des poids. Voici les ingrédients clés de la programmation dynamique : 1. identifier un petit nombre de sous-problèmes 2. peut rapidement et correctement résoudre de plus grand sous-problème à partir des solutions de plus petits sous-problèmes. 3. après avoir résolu tous les sous-problèmes, pouvoir construire la solution finale

The Knapsack problem

(problème du sac à dos) : Définition : soit un ensemble d’objets avec une valeur et un poids, le but est de choisir un sous-ensemble d’objets dont la valeur totale est maximale sans dépasser un poids donné. Algo dynamique en O(nW).

sequence alignment

Aligner 2 chaines en minimisant la pénalité totale. Utilisation du score de Needleman-Wunsch pour mesurer la similarité entre 2 chaines.

Algorithme de Bellman-Ford

Il permet de résoudre le Single Source Shortest Path (SSSP), plus courts chemins à origine unique. Étant donné un graphe orienté et un nœud source, le but est de calculer la longueur du plus court chemin pour chaque destination. L’avantage de cet algorithme est qu’il fonctionne avec des arcs de longueur négative. Temps d’exécution : O(mn)

All-Pairs Shortest Path (APSP)

calcule la longueur du plus court chemin pour chaque couple de nœud. L’algorithme de Floyd-Warshall : O(n3) L’algorithme de Johnson : une invocation de Bellman-Ford puis n invocation de Dijkstra. O(mnlog n)

Problèmes NP-complet

Commençons par 2 exemples de problèmes : plus courts chemins sans cycle dans un graphe avec des cycles négatifs et Knapsack. Il est largement conjecturé que P ≠ NP mais ça n’a jamais été prouvé, il existe même une récompense de 1 million de dollars à celui qui trouvera la démonstration. Il existe 3 stratégies quand on est confronté à de tels problèmes :

  • se concentrer sur des cas spéciaux
  • heuristique : algorithme rapide mais pas toujours correct
  • solution en temps exponentiel meilleure que brute force

NP complet : un problème pour lequel il n’existe pas de solution en temps polynomial

Algorithmes exacts

Vertex cover, problème de couverture minimum de sommets. Étant donné un graphe non orienté, le but est de déterminer un sous-ensemble de sommets qui contient au moins une extrémité de chaque arc. Il existe un algo de programmation dynamique en O(n22n).

Traveling Salesman Problem (TSP), le problème du voyageur de commerce : Étant donné un graphe complet et non orienté, le but est de déterminer le plus court trajet qui passe une fois par chaque nœud. En brute force, le cout est O(n!) mais il existe une solution en programmation dynamique en O(n22n).

Algorithmes approximatifs

Idéalement, ils fournissent une garantie de performance.

Algorithmes de recherche locale

Maximum cut problem

Bonus

Le paradoxe des anniversaires est le nombre de personnes que l’on doit réunir pour avoir une chance sur deux que deux personnes de ce groupe aient leur anniversaire le même jour de l’année. Il se trouve que ce nombre est 23. Le message est qu’en algorithmie, il faut se méfier de ses intuitions.