Introduction to Computation and Programming Using Python

1. L’informatique repose avant tout sur le calcul et la mémoire.

Un ordinateur fait deux choses, et rien d’autre : il effectue des calculs et il mémorise les résultats de ces calculs.

Capacités fondamentales. Au cœur de son fonctionnement, un ordinateur est une machine conçue pour deux tâches : réaliser des opérations arithmétiques et logiques à une vitesse incroyable, et stocker les résultats. Cette base simple, exécutée des milliards de fois par seconde avec une capacité mémoire immense, permet d’accomplir les tâches complexes que nous connaissons aujourd’hui. Comprendre ces limites et ces forces fondamentales est la première étape de la pensée informatique.

Au-delà de l’échelle humaine. Alors que l’homme est limité par la vitesse de sa pensée et de ses gestes, l’ordinateur surmonte ces barrières. Des problèmes auparavant insolubles en raison du volume colossal de calculs ou de données deviennent accessibles grâce à la puissance informatique. Ce changement nous permet d’aborder des défis tels que la modélisation climatique ou l’analyse de vastes ensembles de données.

Connaissance impérative. L’informatique s’appuie sur la connaissance impérative – les « recettes » ou algorithmes. Contrairement à la connaissance déclarative (énoncés de faits), la connaissance impérative fournit les instructions pas à pas nécessaires pour atteindre un résultat, comme la méthode d’Héron pour calculer une racine carrée.

2. Les algorithmes fournissent des recettes impératives pour résoudre des problèmes.

Un algorithme est une liste finie d’instructions décrivant un ensemble de calculs qui, exécutés sur un ensemble d’entrées, passent par une séquence d’états bien définis et produisent finalement une sortie.

Instructions structurées. Les algorithmes sont des procédures précises, étape par étape, pour résoudre un problème ou effectuer un calcul. Ils ressemblent à des recettes, détaillant la séquence des opérations et le contrôle du flux, incluant des tests pour décider quand exécuter ou répéter certaines étapes. Cette approche structurée garantit un processus prévisible de l’entrée à la sortie.

Fondement de la programmation. Les langages de programmation sont les outils que nous utilisons pour décrire les algorithmes afin que les ordinateurs puissent les exécuter. Les premiers ordinateurs étaient des machines à programme fixe, conçues pour une tâche unique, tandis que les ordinateurs modernes sont des machines à programme stocké, capables d’exécuter n’importe quel algorithme décrit dans leur jeu d’instructions. Cette flexibilité, fondée sur le concept de machine de Turing universelle, fait des ordinateurs des solveurs de problèmes polyvalents.

Exécution littérale. La puissance et la frustration de la programmation viennent du fait que l’ordinateur exécute les algorithmes exactement tels qu’ils sont écrits. Cette littéralité signifie que l’ordinateur peut accomplir des tâches complexes sans erreur si l’algorithme est correct, mais exécutera aussi fidèlement les erreurs, conduisant à des résultats inattendus ou incorrects. La conception rigoureuse des algorithmes est donc primordiale.

3. Python offre les outils essentiels pour exprimer le calcul.

Heureusement, il ne nous faut qu’une seule construction supplémentaire en langage de programmation, l’itération, pour écrire des programmes d’une complexité arbitraire.

Blocs de base. Python fournit les constructions fondamentales nécessaires à la programmation impérative : types scalaires (int, float, bool, None), variables et affectation, opérateurs, ainsi que les entrées/sorties. Ces éléments permettent de représenter des données, stocker des valeurs, effectuer des calculs et interagir avec l’utilisateur. Comprendre ces bases est le point de départ pour écrire n’importe quel programme.

Contrôler le flux. Les programmes gagnent en puissance grâce aux mécanismes de contrôle de flux qui dictent l’ordre d’exécution. Les instructions conditionnelles (if, elif, else) permettent de bifurquer selon des tests, offrant la possibilité de répondre différemment selon les entrées. L’itération (while, boucles for) permet de répéter des blocs de code, indispensable pour traiter des séquences ou effectuer plusieurs fois une action.

La lisibilité compte. Au-delà de fonctionner, un programme doit être facile à lire et à comprendre pour les humains. Python met l’accent sur la lisibilité grâce à une syntaxe claire, des noms de variables explicites, des commentaires et une indentation cohérente. Cela est crucial, car les programmeurs passent beaucoup de temps à lire du code, notamment lors du débogage.

4. L’abstraction est la clé pour gérer la complexité des programmes.

Les fonctions sont un moyen de créer des éléments computationnels que l’on peut considérer comme des primitives.

Cacher les détails. L’abstraction nous permet d’utiliser des morceaux complexes de code comme des « boîtes noires », en nous concentrant sur ce qu’ils font (leur spécification) plutôt que sur la manière dont ils le font (leur implémentation). Les fonctions sont le principal mécanisme pour cela, regroupant du code en unités réutilisables pouvant être appelées avec différents paramètres. Cela simplifie la conception et la maintenance des programmes.

Décomposition et réutilisation. Les fonctions permettent de décomposer un problème complexe en sous-problèmes plus petits et gérables. Une fois définies, elles peuvent être réutilisées plusieurs fois dans un programme ou entre différents programmes, réduisant la redondance et facilitant les mises à jour. Les fonctions d’ordre supérieur, qui prennent des fonctions en argument ou en retournent, augmentent encore la flexibilité et la généralisation.

Règles de portée. Les fonctions introduisent des portées, créant des espaces de noms locaux pour les variables. Cela évite les interactions non désirées entre différentes parties du programme, garantissant que les modifications à l’intérieur d’une fonction n’affectent pas les variables extérieures, sauf intention explicite (comme avec les variables globales, utilisées avec parcimonie). Comprendre la portée est essentiel pour prévoir le comportement du programme.

5. Les types de données structurés organisent efficacement l’information.

Les listes diffèrent des tuples sur un point crucial : les listes sont mutables.

Collections de données. Au-delà des valeurs scalaires simples, les programmes doivent gérer des collections de données. Python offre des types structurés intégrés puissants comme les tuples (séquences ordonnées immuables), les listes (séquences ordonnées mutables), les ensembles (collections non ordonnées mutables d’éléments uniques) et les dictionnaires (mappings mutables de clés vers valeurs). Chaque type est adapté à des usages différents.

Accéder aux éléments. Les types séquentiels (chaînes, tuples, listes) supportent l’indexation et le découpage pour accéder à des éléments individuels ou des sous-séquences. Les dictionnaires utilisent des clés hachables pour une recherche efficace, offrant un moyen flexible d’associer des informations. Comprendre les propriétés de ces types est crucial pour choisir l’outil adapté à la manipulation des données.

Mutabilité et aliasing. Une distinction clé est la mutabilité : un objet peut-il être modifié après sa création ? Les listes, ensembles et dictionnaires sont mutables, tandis que les chaînes, tuples et nombres ne le sont pas. La mutabilité, combinée à l’aliasing (plusieurs noms référant au même objet), peut engendrer des effets secondaires puissants mais parfois délicats à gérer, nécessitant des précautions comme le clonage lors d’itérations ou de modifications indépendantes.

6. L’efficacité compte, surtout pour les problèmes de grande taille.

Comme approximation de « très grand », la notation asymptotique décrit la complexité d’un algorithme lorsque la taille de ses entrées tend vers l’infini.

Au-delà de la justesse. Si la correction est primordiale, la performance d’un algorithme devient critique face à de grandes entrées ou des contraintes temps réel. Mesurer la performance en nombre d’étapes abstraites par rapport à la taille des entrées permet de comparer indépendamment du matériel ou de l’implémentation. L’attention se porte sur la croissance du temps d’exécution.

Focus sur le pire cas. On analyse généralement le temps d’exécution dans le pire cas pour garantir la performance dans les conditions les plus difficiles. La notation asymptotique, comme le Big O (O) et le Big Theta (θ), formalise cette croissance quand la taille des entrées tend vers l’infini, en ignorant les constantes et termes de moindre ordre. Les classes de complexité courantes incluent constant, logarithmique, linéaire, log-linéaire, polynomial et exponentiel.

Choix d’algorithme. L’ordre de croissance impacte fortement la faisabilité pour de grandes entrées. Un algorithme de tri en O(n log n) est bien plus efficace qu’un O(n²) pour de grandes listes. Choisir un algorithme efficace, comme la recherche binaire (O(log n)) plutôt que la recherche linéaire (O(n)) sur des données triées, est souvent plus déterminant que des optimisations de bas niveau. Cependant, les algorithmes simples sont préférés s’ils sont « assez rapides » et plus faciles à comprendre et déboguer.

7. Les problèmes d’optimisation cherchent la meilleure solution sous contraintes.

La notion de problème d’optimisation offre une manière structurée de penser la résolution de nombreux problèmes informatiques.

Maximiser ou minimiser. Beaucoup de problèmes réels consistent à trouver le meilleur résultat possible, que ce soit maximiser une valeur (comme un profit) ou minimiser un coût (temps, distance), sous certaines limitations ou règles. Ces problèmes sont formalisés par une fonction objectif et des contraintes.

Problèmes du sac à dos. Un exemple classique est le problème du sac à dos, où l’objectif est de sélectionner des objets de valeur maximale sans dépasser une capacité de poids. Le problème du sac à dos 0/1 (prendre ou laisser chaque objet) est difficile à résoudre dans le pire cas, nécessitant un temps exponentiel pour garantir la solution optimale par énumération exhaustive de tous les sous-ensembles.

Approximations gloutonnes. Si la solution optimale est souvent difficile à obtenir, les algorithmes gloutons offrent une alternative pratique. Ils font le choix localement optimal à chaque étape (par exemple, prendre l’objet avec le meilleur rapport valeur/poids). Bien qu’ils ne garantissent pas l’optimum global, ces algorithmes sont souvent beaucoup plus rapides (par exemple O(n log n) pour certaines variantes) et fournissent des solutions raisonnablement bonnes en pratique.

8. La programmation dynamique résout efficacement les problèmes à sous-problèmes chevauchants.

La programmation dynamique est une méthode pour résoudre efficacement des problèmes présentant des sous-problèmes qui se recoupent et une structure optimale.

Éviter le travail redondant. Certains problèmes, comme le calcul naïf récursif des nombres de Fibonacci, résolvent plusieurs fois les mêmes sous-problèmes. La programmation dynamique remédie à cette inefficacité en stockant les résultats des sous-problèmes dans une table ou un « mémo » pour les réutiliser plutôt que de les recalculer. Cela transforme une complexité exponentielle en complexité polynomiale (souvent linéaire) pour ces problèmes.

Deux approches. La programmation dynamique peut être mise en œuvre de haut en bas avec mémoïsation, où les appels récursifs consultent le mémo avant de calculer, ou de bas en haut avec une méthode tabulaire, qui résout itérativement les sous-problèmes du plus petit au plus grand en remplissant la table. La méthode tabulaire est souvent plus simple et efficace si tous les sous-problèmes doivent être résolus.

Sac à dos revisité. Le problème du sac à dos 0/1, bien que fondamentalement exponentiel en nombre d’objets, peut souvent être résolu efficacement par programmation dynamique si la capacité du sac ou les poids des objets restent dans une plage raisonnable. En mémorisant les solutions selon les objets restants et le poids disponible, l’algorithme évite de recalculer les choix optimaux pour des sous-problèmes identiques, conduisant à une complexité pseudo-polynomiale pratique dans de nombreux cas.

9. Le hasard et la simulation modélisent l’incertitude du monde.

De nombreux aspects du monde dans lequel nous vivons ne peuvent être modélisés avec précision que comme des processus stochastiques.

Au-delà du déterminisme. Tous les phénomènes ne sont pas prévisibles avec certitude. Les processus stochastiques, dont les résultats impliquent du hasard, nécessitent des approches informatiques différentes. Les modèles de simulation imitent des systèmes réels en incorporant des éléments aléatoires, permettant d’explorer une gamme de comportements possibles plutôt que de prédire un seul résultat.

Marches aléatoires. Une marche aléatoire, comme la marche de l’ivrogne, est un processus stochastique simple où la direction du mouvement est aléatoire à chaque étape. Simuler de nombreuses marches révèle des propriétés globales, comme la distance moyenne à l’origine, qui ne sont pas intuitives. Différents types de marches aléatoires (par exemple biaisées) peuvent être modélisés en modifiant les probabilités des mouvements.

Modéliser des systèmes complexes. Les simulations sont précieuses lorsque les expériences réelles sont trop coûteuses, dangereuses ou longues, ou lorsque les modèles analytiques sont inaccessibles. Elles permettent d’explorer des scénarios hypothétiques, comme la propagation de maladies infectieuses ou le comportement des marchés financiers. Cependant, les simulations restent des modèles, des approximations de la réalité, et leurs résultats doivent être interprétés avec prudence et esprit critique.

10. La statistique permet d’inférer à partir d’échantillons et de comprendre les distributions.

Le principe fondamental de la statistique inférentielle est qu’un échantillon aléatoire tend à présenter les mêmes propriétés que la population dont il est issu.

Apprendre des données. La statistique offre des outils pour analyser des données, résumer leurs propriétés et faire des inférences sur des populations plus larges à partir d’échantillons. La statistique descriptive (moyenne, variance, écart-type) quantifie les caractéristiques des données, tandis que la statistique inférentielle utilise la probabilité pour tirer des conclusions sur les populations.

Échantillonnage et confiance. Puisqu’il est souvent impossible d’examiner toute une population, on se base sur des échantillons. La loi des grands nombres suggère que les propriétés d’un échantillon convergent vers celles de la population lorsque la taille de l’échantillon augmente. Le théorème central limite est crucial : il affirme que les moyennes d’échantillons sont distribuées normalement, ce qui permet d’estimer des intervalles et niveaux de confiance (par exemple 95 %) autour des moyennes, même si la population sous-jacente n’est pas normale.

Visualiser les données. Les histogrammes montrent la distribution des valeurs dans un jeu de données, tandis que les graphiques avec barres d’erreur visualisent les intervalles de confiance, indiquant la fiabilité des estimations. Comprendre les distributions de probabilité (normale, uniforme, exponentielle, etc.) aide à interpréter les données et à choisir les tests statistiques appropriés. Cependant, la signification statistique (p-value faible) indique une improbabilité sous une hypothèse nulle, pas nécessairement un effet important ou large.

11. L’apprentissage automatique détecte des motifs et fait des prédictions à partir des données.

Quand les informaticiens parlent d’apprentissage automatique, ils désignent le plus souvent la discipline qui consiste à écrire des programmes qui apprennent automatiquement à faire des inférences utiles à partir de motifs implicites dans les données.

Apprendre à partir d’exemples. Les algorithmes d’apprentissage automatique construisent des modèles à partir de données observées (données d’entraînement) pour faire des prédictions ou découvrir des structures dans de nouvelles données non vues. Cela implique de choisir une représentation du modèle, de définir une fonction objectif pour évaluer la qualité du modèle, et d’utiliser l’optimisation pour trouver le meilleur modèle. Il s’agit de généraliser à partir d’exemples.

Apprentissage supervisé vs non supervisé. L’apprentissage supervisé utilise des exemples étiquetés (vecteurs de caractéristiques associés à des valeurs ou étiquettes) pour apprendre des règles prédictives (régression pour les valeurs, classification pour les étiquettes). L’apprentissage non supervisé utilise des vecteurs de caractéristiques non étiquetés pour découvrir une structure cachée, comme regrouper des exemples similaires en clusters.

Caractéristiques et distance. Un apprentissage efficace repose sur une bonne ingénierie des caractéristiques pour extraire l’information pertinente des données brutes. Les caractéristiques sont converties en vecteurs numériques, et des métriques de distance (comme la distance euclidienne ou de Manhattan, variantes de la distance de Minkowski) sont utilisées pour quantifier la similarité ou la dissemblance entre exemples. Un bon redimensionnement des caractéristiques est important pour éviter que certaines dominent le calcul des distances.

12. Soyez critique : la statistique peut facilement induire en erreur si elle n’est pas comprise.

Il est aussi facile de mentir avec des chiffres qu’avec des mots.

La qualité des données est primordiale. Une analyse statistique n’est aussi bonne que les données qu’elle utilise ; « poubelle entrée, poubelle sortie » est un principe fondamental. Des données biaisées ou erronées conduiront inévitablement à des conclusions trompeuses, quelle que soit la sophistication des méthodes statistiques appliquées. Il faut toujours interroger la source et la méthode de collecte des données.

Corrélation n’est pas causalité. Observer que deux variables évoluent ensemble (corrélation) n’implique pas que l’une cause l’autre. Une variable cachée peut être la cause réelle, ou la corrélation peut être purement fortuite. Assumer une causalité à partir d’une corrélation est une erreur fréquente et dangereuse.

Le contexte et la présentation comptent. Les statistiques et graphiques peuvent être manipulés pour donner une impression souhaitée en choisissant sélectivement les données, en tronquant les axes, en utilisant des échelles trompeuses (comme des axes logarithmiques sans indication

Dernière mise à jour: May 7, 2025