If you're seeing this message, it means we're having trouble loading external resources on our website.

Si vous avez un filtre web, veuillez vous assurer que les domaines *. kastatic.org et *. kasandbox.org sont autorisés.

Contenu principal

Qu'est-ce qu'un algorithme et pourquoi est-ce important ?

Vous souhaitez rejoindre la discussion ?

Vous comprenez l'anglais ? Cliquez ici pour participer à d'autres discussions sur Khan Academy en anglais.

Transcription de la vidéo

Qu'est-ce qu'un algorithme ? Une définition pourrait être une suite d'instructions pour accomplir une tâche. Vous utilisez un algorithme pour aller de chez vous à l'école, (1: pédalez jusqu'à la gare 2 : prendre le train 3 : marcher jusqu'au bureau ) pour préparer un grilled cheese, (1 : prendre du pain 2 : mettre du fromage 3 : faire griller) ou pour trouver ce dont vous avez besoin dans une épicerie. (1 : trouver la bonne allée, 2 : parcourir le rayon, 3 : s'arrêter quand l'article est trouvé). En informatique, un algorithme est une suite d'instructions à exécuter par un programme pour accomplir une tâche. Les algorithmes sont la base scientifique de l'informatique. Et trouver de bons algorithmes, et savoir quand les utiliser, vous permettra d'écrire d'intéressants et d'importants programmes. Nous allons évoquer quelques algorithmes célèbres. Comment Google Hangouts parvient-il à transmettre de la vidéo en direct sur internet aussi rapidement ? Il utilise des algorithmes de compression audio et vidéo. Comment Google Maps parvient à déterminer comment aller de Dallas, au Texas, à Orlando, en Floride, pour que vous puissiez vous rendre à Disney World ? Il utilise un algorithme de recherche d'itinéraire. Comment Pixar colorie la modélisation 3D d'un personnage en se basant sur l'éclairage d'une pièce virtuelle ? En utilisant un algorithme de rendu. Comment la Nasa décide-t-elle d'orienter les panneaux solaires sur la Station Spatiale Internationale et quand les réorienter ? Elle utilise un algorithme d'optimisation et d'ordonnancement. Ces algorithmes sont plus complexes que nos algorithmes de tous les jours, comme la préparation d'un grilled cheese. Mais ils se résument à la même chose, une suite d'instructions pour accomplir une tâche. Si vous avez la connaissance d'algorithmes existants, vous pouvez vous épargner des efforts et rendre vos programmes plus rapides en appliquant celui qui convient. Par exemple, imaginons que vous écrivez un programme de jeu et que vous voulez que l'utilisateur puisse jouer contre l'ordinateur. Vous pourriez chercher de l'inspiration du côté des jeux de dames. Les informaticiens ont trouvé comment écrire des programmes de jeux de dames qui ne perdent jamais en utilisant l'algorithme minimax qui recherche les mouvements possibles dans un gigantesque arbre. Si votre jeu ressemble aux jeux de dames alors vous pourriez utiliser des algorithmes qui reposent sur ces techniques. Sinon, la connaissance des limites de ces algorithmes pourrait vous amener à repenser votre jeu si il requiert un ordinateur compétitif. Il est aussi important de savoir comment concevoir de nouveaux algorithmes que de savoir analyser leur justesse et leur efficacité. En biologie, de nouveaux algorithmes sont créés sans arrêt dans l'objectif de concevoir des structures moléculaires qui sont au cœur de traitements médicaux. En physique, des algorithmes simulent des modèles de climat et de météorologie. D'autres algorithmes recherchent et analysent les meilleures données sur les étoiles dans l'univers, collectées par des télescopes spatiaux automatisés. Dans toutes les sciences, et même sur des sites web comme celui de la Kahn Academy, on a besoin d'algorithmes efficaces pour analyser d'énormes jeux de données ou pour opérer une sélection intelligente parmi une vaste quantité de décisions possibles. Dans presque tous les domaines qui peuvent vous intéresser, de nouveaux algorithmes vont permettre qu'une énorme puissance de calcul informatique soit exploitée afin d'effectuer ce dont les gens ont vraiment besoin et ce qui est important pour eux. Maintenant, tous les algorithmes ne sont pas égaux. Qu'est-ce qui fait un bon algorithme ? Les deux critères les plus importants sont : 1. qu'il résolve un problème, et 2. qu'il le fasse de manière efficace. La plupart du temps, nous voulons que l'algorithme nous donne une réponse qui soit toujours correcte. Parfois, nous pouvons nous contenter d'un algorithme qui ne donne pas toujours la réponse correcte, ou pas la meilleure, car les seuls algorithmes parfaits que nous connaissons pour ces problèmes nécessitent vraiment, vraiment beaucoup de temps. Par exemple, imaginons que nous voulions un programme qui déterminerait l'itinéraire le plus efficace pour un camion qui livre des paquets, qui commence et finit sa journée au dépôt. Ça prendrait des semaines à le faire tourner pour calculer toutes les possibilités. Mais si nous sommes satisfaits avec un programme qui trouverait un itinéraire qui est bon, même s'il n'est peut-être pas le meilleur, alors il pourrait tourner en quelques secondes. Dans certains cas, ce qui est bien est suffisant. Comment mesure-t-on l'efficacité d'un algorithme ? On pourrait mesurer le temps que prend le code pour s'exécuter, mais ça ne nous informerait que sur cette implémentation particulière, avec un langage de programmation précis, sur un ordinateur précis, et seulement pour les données qui ont été fournies. À la place, les informaticiens utilisent une technique appelée analyse asymptotique, qui permet de comparer des algorithmes indépendamment du langage de programmation ou du matériel. C'est pourquoi on peut l'affirmer, oui, certains algorithmes sont plus efficaces que d'autres. Maintenant vous pouvez découvrir les algorithmes et l'analyse asymptotique, à la Khan Academy, grâce à la participation de deux professeurs de l'Université de Dartmouth. Tom Cormen est le premier auteur de l'un des manuels d'université sur les algorithmes les plus utilisés dans le monde, en plus d'être aussi l'auteur de "Algorithms Unlocked". Devin Balcom a conçu le cours d'introduction à l'informatique de Dartmouth et poursuit des recherche en robotique. Il a construit le premier robot au monde capable de plier des origamis. Tom et Devin vont vous enseigner la plupart des algorithmes qu'on peut découvrir en cours d'informatique à l'université, comme par exemple des algorithmes de recherche, de tri, récursifs, et ceux que je préfère, à titre personnel, les algorithmes de la théorie des graphes. Il y aura des tonnes de visualisations interactives, des quiz et des défis de programmation pour vous aidez à mieux comprendre tout au long de votre parcours d'apprentissage.