Computer Science Distilled

1. Informatique : Indispensable pour résoudre efficacement les problèmes

L’informatique est partout, mais elle est encore enseignée comme une théorie ennuyeuse.

Application pratique. L’informatique ne se limite pas à une théorie abstraite ; elle constitue une base essentielle pour programmer efficacement et résoudre des problèmes concrets. Beaucoup de programmeurs manquent d’une formation formelle en informatique, ce qui conduit à des solutions peu optimales. Ce livre vise à combler ce fossé en présentant les concepts informatiques de manière claire et accessible.

Pensée computationnelle. Le cœur de l’informatique réside dans la pensée computationnelle, qui consiste à décomposer les problèmes en systèmes calculables. Cette approche ne se limite pas au codage, elle s’applique aussi à des situations quotidiennes, comme optimiser le rangement d’une valise ou accélérer la cuisson grâce au parallélisme.

Puissance abondante, compétences rares. La puissance informatique est largement disponible, mais la capacité à l’utiliser efficacement reste rare. En maîtrisant les principes de l’informatique, chacun peut libérer tout le potentiel des machines et concevoir des solutions innovantes et performantes face à des problèmes complexes.

2. Logique : La pierre angulaire de la pensée computationnelle

Les programmeurs manipulent tellement la logique que cela embrouille leur esprit.

Logique formelle. La logique est fondamentale en informatique, car elle permet aux programmeurs de résoudre les problèmes de manière délibérée. La logique formelle offre un cadre pour raisonner sur la validité des énoncés et des relations, en utilisant des opérateurs comme ET, OU, NON, et les conditionnels.

Algèbre de Boole. L’algèbre de Boole simplifie les expressions logiques, à l’image de l’algèbre élémentaire qui simplifie les expressions numériques. Par exemple, les lois de De Morgan permettent de transformer des ET en OU et vice versa, facilitant ainsi la simplification de modèles logiques complexes.

Tables de vérité. Les tables de vérité proposent une méthode systématique pour analyser les modèles logiques en examinant toutes les configurations possibles des variables. En construisant ces tables, on peut déterminer les conditions dans lesquelles un système fonctionne correctement, comme illustré dans l’exemple du « Système Fragile ».

3. Comptage : Maîtriser l’art de l’énumération

Il est essentiel de compter correctement — vous devrez le faire souvent en travaillant sur des problèmes computationnels.

Analyse combinatoire. Les techniques de comptage, telles que les multiplications, permutations, combinaisons et sommes, sont indispensables pour résoudre des problèmes informatiques. Ces outils permettent de déterminer le nombre de résultats ou configurations possibles, ce qui est crucial pour évaluer la faisabilité des algorithmes.

Factoriels et permutations. La fonction factorielle (n!) calcule le nombre de façons d’ordonner n éléments. Les permutations, qui tiennent compte de l’ordre, servent à compter les manières d’agencer m éléments parmi n.

Combinaisons et sommes. Les combinaisons, notées « n parmi m », calculent le nombre de façons de choisir m éléments parmi n, sans tenir compte de l’ordre. Les sommes, exprimées avec la notation sigma (Σ), servent à calculer le total des possibilités dans des événements successifs, comme démontré dans l’exemple « Vol pas cher ».

4. Probabilités : Naviguer dans le domaine du hasard

Les principes du hasard vous aideront à comprendre les jeux, prévoir la météo ou concevoir un système de secours peu risqué.

Calcul des probabilités. Les principes de probabilité quantifient la chance qu’un événement se produise, permettant de prendre des décisions éclairées dans divers contextes. La probabilité d’un événement se calcule en divisant le nombre de façons dont il peut se produire par le nombre total de résultats possibles.

Événements indépendants et mutuellement exclusifs. Les événements indépendants ont des issues qui ne s’influencent pas, et leurs probabilités se multiplient pour obtenir celle de leur occurrence conjointe. Les événements mutuellement exclusifs ne peuvent pas se produire simultanément, et leurs probabilités se somment pour obtenir celle de l’un ou l’autre.

Événements complémentaires et erreur du joueur. Les événements complémentaires couvrent tous les résultats possibles, et la somme de leurs probabilités est de 100 %. Il est essentiel d’éviter l’erreur du joueur, qui consiste à croire à tort que des événements passés influencent des événements indépendants.

5. Analyse de complexité : Évaluer l’efficacité algorithmique

Dans presque chaque calcul, plusieurs arrangements des processus sont possibles.

Complexité temporelle. La complexité temporelle, notée T(n), mesure le nombre d’opérations qu’un algorithme effectue pour une entrée de taille n. Analyser cette complexité permet de prévoir comment le temps d’exécution évoluera avec la taille des données.

Notation Big-O. La notation Big-O exprime le terme dominant de la fonction de coût d’un algorithme dans le pire des cas, offrant une manière standardisée de représenter la complexité temporelle. Les algorithmes avec des complexités Big-O plus faibles, comme O(n log n), sont généralement plus performants que ceux avec des complexités plus élevées, comme O(n²), pour de grandes entrées.

Algorithmes exponentiels. Les algorithmes à temps exponentiel, avec des complexités telles que O(2^n), sont considérés comme « non exécutables » en raison de leur croissance explosive. Ils sont impraticables pour de grandes tailles de problème et doivent être évités sauf pour des cas très petits.

6. Stratégies de conception d’algorithmes : Une boîte à outils pour résoudre les problèmes

Si vous trouvez un bon coup, cherchez-en un meilleur.

Itération et récursion. L’itération utilise des boucles pour répéter un processus jusqu’à ce qu’une condition soit remplie, tandis que la récursion implique qu’une fonction délègue du travail à des copies d’elle-même. Les algorithmes récursifs sont souvent plus simples, mais peuvent engendrer une surcharge computationnelle.

Force brute et retour en arrière. La force brute résout les problèmes en inspectant toutes les solutions possibles, tandis que le retour en arrière optimise la recherche en testant les mauvaises options puis en revenant en arrière. Le retour en arrière est efficace lorsque les choix limitent les choix suivants.

Heuristiques et diviser pour régner. Les heuristiques offrent une solution raisonnable en sacrifiant l’optimalité pour la rapidité, tandis que la méthode diviser pour régner décompose les problèmes en sous-problèmes plus petits et similaires. La programmation dynamique évite les calculs redondants en identifiant et mémorisant les sous-problèmes répétés.

7. Structures de données : Organiser l’information pour un accès optimal

Les bons programmeurs s’inquiètent des structures de données et de leurs relations.

Types abstraits de données (TAD). Les TAD définissent un ensemble d’opérations pour un type de données donné, masquant les détails d’implémentation et favorisant la réutilisation du code. Les TAD courants incluent les piles, files, listes, dictionnaires et ensembles.

Tableaux et listes chaînées. Les tableaux stockent les éléments dans des emplacements mémoire contigus, offrant un accès instantané mais une flexibilité limitée. Les listes chaînées utilisent une chaîne de cellules avec des pointeurs, permettant une insertion et suppression faciles, mais un accès plus lent.

Arbres et tables de hachage. Les arbres organisent les données hiérarchiquement, avec les arbres binaires de recherche permettant une recherche efficace. Les tables de hachage utilisent des fonctions de hachage pour associer les données à des emplacements mémoire, offrant un accès en temps constant O(1), mais nécessitant une gestion attentive des collisions.

8. Algorithmes : Tirer parti des solutions existantes

[Le codage est] attrayant non seulement parce qu’il peut être économiquement et scientifiquement gratifiant, mais aussi parce qu’il peut être une expérience esthétique comparable à la composition poétique ou musicale.

Algorithmes de tri. Les algorithmes de tri ordonnent les données selon un ordre précis, avec des algorithmes simples comme le tri par sélection et le tri par insertion en O(n²), et des algorithmes plus efficaces comme le tri fusion et le tri rapide en O(n log n). Le tri par insertion est très efficace pour des ensembles presque triés.

Algorithmes de recherche. Les algorithmes de recherche localisent une information spécifique en mémoire, avec la recherche séquentielle en O(n) et la recherche binaire en O(log n) pour des données triées. Les tables de hachage offrent un temps de recherche en O(1).

Algorithmes sur graphes. Les algorithmes sur graphes opèrent sur des données représentées par des nœuds et des arêtes, avec la recherche en profondeur (DFS) et la recherche en largeur (BFS) explorant les graphes différemment. L’algorithme de Dijkstra trouve le chemin le plus court entre des nœuds.

9. Bases de données : Gérer d’immenses collections de données

Bien que je sois surtout connu pour mon travail sur les bases de données, mes compétences fondamentales sont celles d’un architecte : analyser les besoins et construire des solutions simples mais élégantes.

Bases de données relationnelles. Les bases relationnelles organisent les données en tables avec lignes et colonnes, utilisant des clés primaires et étrangères pour établir des relations. SQL est le langage standard pour interroger ces bases.

Bases de données non relationnelles (NoSQL). Les bases NoSQL offrent plus de flexibilité en abandonnant les relations tabulaires et les schémas fixes. Les magasins de documents, les magasins clé-valeur et les bases de graphes en sont des exemples.

Bases de données distribuées. Les bases distribuées coordonnent plusieurs ordinateurs pour gérer de grands ensembles de données, des charges de requêtes élevées ou des applications critiques. Les techniques incluent la réplication maître unique, la réplication multi-maîtres et le partitionnement (sharding).

10. Architecture informatique : Dévoiler les mécanismes internes

Toute technologie suffisamment avancée est indiscernable de la magie.

Processeur et mémoire. Un ordinateur se compose d’un processeur (CPU) et d’une mémoire (RAM). La mémoire stocke les instructions et les données, tandis que le processeur récupère les instructions et effectue les calculs.

Fonctions du CPU. Le CPU réalise des opérations mathématiques simples et déplace les données entre la RAM et ses registres internes. Le jeu d’instructions définit les opérations qu’un CPU peut exécuter.

Hiérarchie de la mémoire. La hiérarchie mémoire comprend les registres CPU, les caches L1/L2/L3, la RAM et le stockage secondaire (disque dur). Les caches exploitent la localité temporelle et spatiale pour réduire le temps d’accès à la RAM.

11. Langages de programmation : Faire le pont entre humain et machine

Quand quelqu’un dit : « Je veux un langage de programmation où je n’ai qu’à dire ce que je veux faire », donnez-lui une sucette.

Valeurs, expressions et instructions. Les langages de programmation manipulent l’information à travers des valeurs, expressions et instructions. Les valeurs représentent l’information, les expressions produisent des valeurs, et les instructions ordonnent à l’ordinateur d’agir.

Variables et typage. Les variables associent des noms à des valeurs, et le typage attribue un type de données aux variables. Le typage statique exige des déclarations explicites, tandis que le typage dynamique vérifie les types à l’exécution.

Paradigmes de programmation. Les paradigmes de programmation proposent différentes approches pour résoudre les problèmes, incluant la programmation impérative, orientée objet et fonctionnelle. Chaque paradigme a ses forces et faiblesses, influençant la structure et l’organisation du code.