Survol algorithmique#

Il est facile de caler un modèle statistiques lorsque les données sont propres et de taille raisonnable. Ce n’est quasiment jamais le cas. On a besoin de nettoyer ou de transformer les données. On a besoin de réduire le temps de calcul d’un algorithme car il est inexploitable en l’état. Pour ces deux raisons, il est utile de connaître quelques algorithmes afin d’avoir d’avoir des idées. On a besoin d’avoir un moyen rapide, visuelle et efficace de comparer deux résultats.

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.

Problèmes NP-complets #

Un peu de morphisme parce que ça m’a toujours fasciné :

Liens #

Problèmes résolus sur ce site
Liste d’algorithme sur Wikipédia (version française)
List of machine learning concepts
Machine Learning, Statistiques et Programmation
Introduction to graphs and networks (échantillon dans un graphe, chaîne de Markov, centralité, …)
Networks and Flows #2
Algorithmes classiques implémentés

Articles sur des algorithmes #

Livres #

Précis de recherche opérationnelle, Robert Faure, Bernard Lemaire, Christophe Picouleau
Programming Pearls, Jon Bentley
Introduction to Algorithms 3rd Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Programmation efficace - 128 algorithmes qu’il faut avoir compris et codés en Python au cours de sa vie, ce livre est accompagné d’un répertoire sur GitHub : tryalgo (documentation) et d’un site web Résolution de problèmes algorithmiques

Pour s’entraîner #

Project Euler
Google Jam, voir aussi Solutions to problems of Code Jam 2020, 2019, 2018, 2017 and earlier
LeetCode
Compétitions de programmation, ce site recensent plusieurs compétitions comme celle-ci Southwestern Europe Regional Contest (SWERC) dont les précédents exercices sont disponibles : ACM-ICPC Live Archive, mais aussi les problèmes du Castor Informatique pour les plus jeunes.

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

Liens

Contenu

Information

Sujet précédent

Sujet suivant