Survol algorithmique

L’algorithmie est une partie des mathématiques. On part toujours d’un état initial pour arriver après une série d’opérations connues à un état final. Cette série dépend de l’état initial. Elle peut inclure de l’aléatoire. On parle d’algorithme lorsqu’on arrive à démontrer que la séquence d’opération qu’il produit mène toujours à l’état final souhaité quel que soit l’état initial. Il existe une grande variété de problèmes déjà résolus qu’il est utile de connaître. C’est autant d’outils disponibles pour créer ses propres algorithmes.

Ordres de grandeur

Qu’est-il raisonnable de faire à supposer qu’on ne dispose que d’une seule machine ? La mémoire n’est plus un problème. Le temps de calcul l’est toujours.

  • n \leqslant 10 : coût \leqslant O(2^n)

  • n \leqslant 15 : coût \leqslant O(n!)

  • n \leqslant 10^2 : coût \leqslant O(n^3)

  • n \leqslant 10^3 : coût \leqslant O(n^2)

  • n \leqslant 10^7 : coût \leqslant O(n \ln (n))

  • n > 10^8 : coût \leqslant O(n)

Comprendre le coût d’un algorithme

Le coût de nombreux algorithmes non NP-complet se décomposer comme suit : O(n^\alpha) O( \ln^\beta n ) O(1). Chaque terme correspond à :

  • O(n^\alpha) avec \alpha \in \mathbb{N} > 1 : un probème combinatoire se résume à un algorithme de coût quadratique, cela est dû à la programmation dynamique. Dans la plupart des cas, on obtient ce coût après avoir transformé le problème dans une forme récurrente : on écrit ce qu’il faut faire pour calculer la solution avec n+1 éléments sachant qu’on connaît la solution avec n éléments.

  • O(n^\beta n) avec \beta \in \mathbb{N} > 0, coût dichotomique, on coupe le problème en deux à chaque itération.

  • O(1) : table de hashage

Dès qu’on sort des puissances entières, il faut s’attendre à un algorithme non trivial tel que l”algorithme de Strassen pour la multiplication de matrice (n^{2.807}), ou celui de Marco Bodrato (A Strassen-like Matrix Multiplication Suited for Squaring and Higher Power Computation).

Le coût minimal d’un algorithme de tri est O(n \ln n) dans le cas générique c’est-à-dire sans hypothèse sur les données. En revanche, dans le cas où les données sont issues d’un ensemble fini de cardinal m, le meilleur tri revient à calculer un histogramme et est de coût inférieur à O( \inf \{ n \ln n, m \} ).

L’article de blog Fast Interesection of Sorted Lists Using SSE Instructions part d’un problème simple qui est l’intersection de deux listes triées et montre comment optimiser son implémentation en introduisant la notion de partitions et un peu de parallélisation.

Mot-clé

L’objectif n’est pas de les comprendre tous mais plus de connaître les problèmes pour lesquels ils ont été conçus.

La distance d’édition sert à calculer la distance entre deux mots. On peut l’utiliser pour trouver les mots les plus proches d’un autre à condition que ces mots ne soient pas nombreux (\sim 10^4). Que faire quand ils sont un milliard ? Ce serait plus facile si les mots étaient représentés par des vecteurs (voir word2vec, Auto Encoders).

On veut comparer deux modèles de ranking. On veut pouvoir comparer visuellement les résultats. Quel ordre est mieux qu’un autre ? Comment afficher les résultats de deux moteurs de recherche de telle sorte que l’oeil humain saisisse rapidement la différence ?

Tout ce qui suit vous donnera des idées.

Catalogue d’algorithmes

Beaucoup de ces algorithmes sont implémentés dans ce projet : TheAlgorithms.

Le module algorithms implémente beaucoup d’algorithmes classiques tels que la recherche binaire, le générateur de nombre aléatoire de Mersenne, le tri heapsort.

Problèmes

Problèmes NP-complets

On distingue trois classes de problèmes P, NP, NP-complet.

coût

P

Un problème appartient à la classe P s’il peut être décidé en temps polynômial.

NP

Un problème de décision est dans NP s’il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l’entrée. Cela implique que pour un problème A, il est possible de vérifier qu’un mot m est solution de A en temps polynomial.

NP-complet

Un problème NP-complet est un problème qui n’admet pas d’algorithmes capables de trouver une solution en un temps polynomial. Plus précisément, pour deux problèmes A et B de cette classe, il existe une transformation (ou réduction) f qui transforme le problème A en B.

Voir 21 problèmes NP-complets de Karp.

BPP

La classe BPP est un objet de la théorie de la complexité, en informatique théorique. C’est une classe de problèmes de décision qui peut être définie avec des machines de Turing probabilistes. L’acronyme BPP vient de Bounded-error Probabilistic Polynomial time.

P=NP ?

C’est un problème encore irrésolu : Problème P = NP.

Problème NP complets

Idée pour démonstrer qu’un problème est NP-complet

Une preuve complète est donnée dans le cours Logique, modèles, calculs (INF 423).

1

L’idée est toujours la même : il faut partir d’un problème NP-complet connu et le réduire de façon polynomial au problème P dont on cherche à démontrer qu’il est NP-complet. La réduction est une transformation d’un problème A en P de telle sorte qu’une solution problème A puisse être transformé en une solution du problème P et réciproquement.

2

Il faut un premier problème NP-complet pour lequel il faut démontrer la NP-complétude. C’est le théorème de Stephen Cook : le problème SAT est NP-complet. On peut montrer que les problème SAT et 3-SAT sont équivalents.

3

Beaucoup de problèmes se présentent sous la forme d’une optimisation. Or SAT est un problème de décision : existe-t-il un point de \acc{0,1}^N qui vérifie une clause logique : \vee_k ( y_{1k} \wedge ... \wedge y_{n_k k} ) avec y_{ik} est soit x_i soit \neg x_i ? Pour passer de l’un à l’autre, on transforme le problème d’optimisation en un problème de décision : existe-t-il une solution dont l’évaluation est inférieure ou supérieur à un certain seuil ?

Liens

Articles sur des algorithmes

Livres

Des applications possibles :

Pour s’entraîner

Google’s recommandations

Coding

You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it’s pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.

Sorting

Know how to sort. Don’t do bubble-sort. You should know the details of at least one n \log(n) sorting algorithm, preferably two (say, quick sort and merge sort). Merge sort can be highly useful in situations where quick sort is impractical, so take a look at it.

Hashtables

Arguably the single most important data structure known to mankind. You absolutely should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees

Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it’s a red/black tree, a splay tree or an AVL tree, and know how it’s implemented. Understand treetraversal

Algorithms

BFS and DFS, and know the difference between inorder, postorder and preorder.

Graphs

Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); familiarize yourself with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. If you get a chance, try to study up on fancier algorithms, such as Dijkstra and A*.

Other Data Structures

You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. Find out whatNP-complete means.

Mathematics

Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because counting problems, probability problems , and other Discrete Math 101 situations surrounds us. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

Operating Systems

Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work. Knowabout deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it’s initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of « modern » concurrency constructs. For information on System

Design

Distributed Systems and Parallel Computing