Les Newsletters Interstices
Photo by Emily Morter on Unsplash
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    10 questions sur les algorithmes

    Algorithmes
    Culture & Société
    Pas à pas, explorez l'algorithmique, cette branche des mathématiques qui a permis tant d'avancées en informatique...
    0%

    Qu'est-ce qu'un algorithme ?

    Correct! Wrong!

    Voir l'article Qu'est-ce qu'un algorithme ?

    Un algorithme est une méthode ou un procédé décrit pas à pas. Ce n'est pas un problème de décision, mais une méthode pour résoudre un tel problème. Un algorithme n'est pas non plus un langage de programmation, mais tout algorithme dont les entrées et les résultats peuvent être codés par des entiers peut être traduit (plus ou moins directement, plus ou moins « naturellement ») dans n'importe quel langage de programmation. Enfin, un algorithme n'est pas un codage numérique, mais les données et les résultats de n'importe quel algorithme doivent être codés de façon numérique - et même arithmétique - pour être mis en œuvre sur un ordinateur (voir à ce sujet Compression de maillages).

    Qu'y a-t-il de commun entre une recette de cuisine et un algorithme ?

    Correct! Wrong!

    Une recette de cuisine ressemble à un algorithme jusqu'à un certain point : elle décrit une méthode pas à pas pour réaliser un plat (le résultat) à partir d'ingrédients (les entrées). Mais elle laisse une part à l'interprétation personnelle, ce qui explique aussi que le résultat n'est pas garanti !

    Cette analogie est cependant bien utile pour faire comprendre qu'un algorithme n'est pas forcément du domaine des mathématiques.

    Par ailleurs, il ne faut pas confondre algorithme et théorème. Un théorème est l'énoncé d'une propriété qui a été prouvée (pour celui de Fermat par exemple, après plusieurs siècles depuis son énoncé). La validité d'un algorithme peut se fonder sur des théorèmes (voir Une preuve sur les nombres premiers).

    Comment se définit la complexité en temps d'un algorithme calculant un résultat à partir d'un paramètre fourni ?

    Correct! Wrong!

    La complexité en temps d'un algorithme se mesure en nombre d'opérations élémentaires à effectuer en fonction de la taille des données d'entrée. Ce nombre est corrélé au temps précis de son exécution sur machine, tout en étant indépendant du langage de programmation dans lequel il est codé, ainsi que de la machine sur laquelle il est implanté. Il est plus facile - et tout aussi pertinent pour l'estimation de la complexité d'un algorithme - de ne pas calculer le nombre exact d'opérations de base, mais de la situer par rapport à des fonctions de référence, qui représentent des ordres de grandeurs (log n, n, n (log n), n2, nk, 2n...). La complexité dépend de la taille du paramètre d'entrée. Par exemple, trier par ordre alphabétique un ensemble de fiches de 10 noms est plus rapide que trier (selon la même méthode de tri) un ensemble de fiches de 1000 noms.

    Sur la notion de complexité, voir aussi la conférence de Philippe Flajolet, Entre mathématiques et informatique : l'analyse des algorithmes.

    Comment peut-on trier par ordre alphabétique un fichier de 1000 noms ?

    Correct! Wrong!

    Il existe de nombreux algorithmes de tri différents. Certains algorithmes sont meilleurs en moyenne que d'autres, tout en étant moins performants dans les configurations les plus favorables (fichier déjà trié) ou les plus défavorables (fichier de départ trié à l'envers). Il faut distinguer la complexité dans le cas le pire, le meilleur ou moyen. L'algorithme de tri rapide ou Quicksort est l'algorithme connu jusqu'à présent comme le meilleur en moyenne (en n(log n)), mais sa complexité dans le cas le pire est de l'ordre de n2 (où n est le nombre d'éléments à trier). On peut montrer que sans information sur les noms à trier, on ne peut pas trier un fichier de n éléments en moins de n(log n) opérations de comparaisons.

    Qu'est-ce que l'algorithme de Dijkstra ? (Trouvez l'une des deux bonnes réponses)

    Please select 2 correct answers

    Correct! Wrong!

    Les bonnes réponses sont la 1 et la 2.

    Voir l'article Le plus court chemin.

    À première vue, il semble que déterminer le plus court chemin entre deux sommets donnés soit plus simple que déterminer les plus courts chemins d'origine fixée vers n'importe quelle extrémité. Cependant, et contrairement à l'intuition précédente, la résolution du premier problème nécessite en général de résoudre le second problème, pour lequel l'algorithme de Dijkstra est le meilleur algorithme connu jusqu'à présent.
    Le meilleur algorithme connu jusqu'à présent pour calculer le plus court chemin entre 2 sommets quelconques dans un graphe est le magnifique algorithme général de Roy-Warshall-Floyd.
    La complexité de l'algorithme de Dijkstra est de l'ordre de n2 (où n est le nombre de sommets). Donc, si son exécution prend de l'ordre d'1 ms sur un graphe de 10 sommets, son exécution sur un graphe de 1000 sommets prendra de l'ordre de 10s (et non pas de 1s).

    En informatique, qu'est-ce qu'un arbre ?

    Correct! Wrong!

    Un arbre au sens informatique peut être une structure de données (par exemple un arbre de jeu) ou un modèle de calcul algorithmique (arbre de décision), mais n'a rien à voir avec l'arboriculture.
    Un réseau a une structure de graphe (voir l'article Algorithmes pour les réseaux ad hoc). Mais les arbres sont des graphes très particuliers.
    Enfin, un arbre n'est pas une instruction d'un langage informatique, mais cette structure de données peut être manipulée par de telles instructions.

    Qu'appelle-t-on machine de Turing universelle ?

    Correct! Wrong!

    Voir les articles d'Interstices sur Alan Turing.

    La machine de Turing universelle n'est pas un ordinateur, mais un modèle de calcul simulant l'exécution d'un algorithme quelconque (modélisé par une machine de Turing particulière).
    Turing a par ailleurs participé à la mise en œuvre d'une méthode de décodage des messages secrets de la machine Enigma.
    Réaliser une machine de traduction automatique était un des grands rêves d'Alan Turing, qui n'est toujours pas réalisé aujourd'hui : il n'existe pas encore de méthode universelle pour traduire automatiquement et de manière satisfaisante un texte quelconque d'une langue dans une autre.

    Parmi les affirmations suivantes, laquelle est fausse ?

    Correct! Wrong!

    Ce n'est pas parce qu'un énoncé mathématique est vrai qu'il est décidable. Il existe des problèmes non décidables. Un problème est décidable s'il existe un algorithme qui permet de résoudre toutes les instances possibles de ce problème. Pour décider si une formule est prouvable dans un système formel, on énumère toutes les preuves possibles (des plus courtes aux plus longues) : s'il en existe une, on la trouvera. Une telle méthode énumérative dont la terminaison n'est garantie qu'en cas d'existence d'une solution s'appelle un semi-algorithme.

    Voir l'article Alan Turing : du calculable à l'indécidable.

    Parmi ces définitions d'un problème NP-complet, laquelle est fausse ?

    Correct! Wrong!

    NP ne veut pas dire Non Polynomial, mais Non déterministe Polynomial.

    Voir l'article P = NP, un problème à un million de dollars ?

    À partir de quel moment, et sous quelles conditions, un énoncé difficile à démontrer et jugé très probable doit-il être adopté comme nouvel axiome ? Le problème P = NP est un problème fondamental du calcul mathématique, l'un de sept problèmes sélectionnés par l'Institut Clay en l'an 2000 : comme pour les six autres, une somme d'un million de dollars attend celle, celui ou ceux qui le résoudront...

    Trouver un alignement (optimal) entre deux séquences, qu'est-ce que c'est ? (Trouvez l'une des deux bonnes réponses)

    Please select 2 correct answers

    Correct! Wrong!

    Les bonnes réponses sont la 2 et la 3.

    Voir l'article Alignement optimal et comparaison de séquences génomiques et protéiques.

    La comparaison de séquences est de loin la tâche informatique la plus fréquemment exécutée par les biologistes. Ce problème est décidable : il existe plusieurs algorithmes pour le résoudre. Les algorithmes mis en œuvre servent à comparer des séquences génomiques ou protéiques comme des mots d'un texte. L'un de ces algorithmes permet de trouver un alignement optimal entre deux séquences en le représentant comme un chemin optimal dans un graphe.

    10 questions sur les algorithmes : résultat
    Parfait
    C'est un sans faute, vous êtes un expert du domaine !
    Bravo
    Vous avez réussi une grande partie du quiz
    Encourageant
    Continuez à lire Interstices, pour répondre à toutes les questions
    Trop ardu ?
    Continuez à lire Interstices, vous réussirez mieux la prochaine fois...

    Newsletter

    Le responsable de ce traitement est Inria, en saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles.

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Marie-Christine Rousset

    Professeur à l'Université Joseph Fourier (Grenoble 1), chercheuse en bases de données et représentation de connaissances.

    Voir le profil

    Découvrez le(s) dossier(s) associé(s) à cet article :

    DossierDonnées
    Algorithmes

    Données structurées et leur traitement