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¶
- Tri
tri fusion algo
bucket sort algo
tri à bulles algo
- Complexité
- Calcul matriciel
Winograd Minimum Filtering algo convolution rapide
im2col algo ou comment réarranger une matrice pour transformer une convolution entre un produit matriciel
- Diviser pour reigner
dichotomie algo
branch and bound algo
The Ultimate Planar Convex Hull Algorithm? algo (relectures Kirkpatrick-Seidel’s Prune-and-Search Convex Hull Algorithm, An Algorithm for Finding Convex Hulls of Planar Point Sets), détermine l’enveloppe convexe d’un ensemble de points avec un coût de \(O(n \ln H)\) où H est le nombre de segments de l’enveloppe
- Programmation dynamique
- Permutations
Sattolo’s algorithm algo
- Problème non NP-complet
Problème du voyageur de commerce algo (ou Graphe Hamiltonien), lire Solution of a Large-Scale Traveling-Salesman Problem.
Problème de tournées de véhicules algo, extension du problème du voyageur de commerce
- Structure de données
liste chaînée déf
table de hachage déf
suffix tree déf
trie déf
b-tree déf
x-fast-trie déf
tas ou heap , Fibonacci Heap déf
Judy Arrays, site, en python, en C, cette structure implémente un mapping int/int plus efficace que l’implémentation traditionnelle avec une table de hashage, la structure utilise les propriétés des caches dans les processeurs déf
- Graphes
composantes connexes ou parcours de graphe en profondeur, parcours de graphe en largeur déf/algo
degré déf
FLoyd-Flukerson algo
minimum cut algo
maximum cut algo
graphe bi-parti déf
PageRank algo
Appariement, Edmonds Blossum, Hopcroft–Karp, Blossom 5, déf/algo (ou couplage)
Algorithme de Gale-Shapley, algo, problème des mariages stables
distance de Robinson–Foulds, algo, distance entre deux arbres
robustesse d’un réseau Quantifying the robustness of metro networks
détection de motif fréquents fp-growth,
- Texte
distance de Jaccard algo
n-grammes déf
Algorithme d’Aho-Corasick algo, voir aussi Commentz-Walter
Transformée de Burrows-Wheeler algo, voir Transformée de Burrows Wheeler
algorithme Apriori : apprentissage de règles d’associations algo
- Optimisation
- Autre
codage Huffman (voir aussi LZ77, LZ78) algo
filtre de Bloom algo
Blockwise inversion algo
Toom-Cook algo
Canopy Clustering algo
- Programmation
mémoïzation déf (voir aussi Mémoïzation d’une fonction Python)
récursivité déf
- Algorithmes probabilistes
- Compression
LZFSE algo
LZMA algo
LZ77 and LZ78 algo
- Algorithmes d’inspiration quantique
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¶
Introduction to graphs and networks (échantillon dans un graphe, chaîne de Markov, centralité, …)
Articles sur des algorithmes¶
Blossom5 matching
Expander Flows, Geometric Embeddings and Graph Partitioning graph partitionning
Recursive n-gram hashing is pairwise independent, at best, Hash-Grams: Faster N-Gram Features for Classification and Malware Detection
Computing Higher Order Derivatives of Matrix and Tensor Expressions
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
Des applications possibles :
Pour s’entraîner¶
Archives de Google Jam, voir aussi Solutions to problems of Code Jam 2020, 2019, 2018, 2017 and earlier
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