Les Newsletters Interstices

Environnement & Planète
Algorithmes
Architecture & Systèmes
Modélisation & Simulation
Histoire du numérique

Sécurité & Vie privée
Médecine & Sciences du vivant
Interaction Humain/Machine
Intelligence artificielle
Langages, programmation & logiciel

Réseaux & Communication
Traitement d’images & Son
Robotique
Culture & Société
Données

Environnement & Planète
Algorithmes
Architecture & Systèmes
Modélisation & Simulation
Histoire du numérique
Sécurité & Vie privée
Médecine & Sciences du vivant

Interaction Humain/Machine
Intelligence artificielle
Langages, programmation & logiciel
Réseaux & Communication
Traitement d’images & Son
Robotique
Culture & Société
Données

Nos animations
Nos articles
Nos dossiers
Nos podcasts
Nos vidéos
Nos quiz

Qui sommes-nous ?
Nos auteurs
Contactez-nous

Photo by Emily Morter on Unsplash

Publié le : 26/04/2007

Par : Marie-Christine Rousset

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...

1.

Qu'est-ce qu'un algorithme ?

Un problème de décision

Une méthode ou un procédé décrit pas à pas

Un langage de programmation

Un code numérique

None

2.

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

On peut les appliquer comme des théorèmes

Aucun point commun, une recette n'a rien de mathématique

Il s'agit d'une suite d'instructions

Appliquez-les et dans tous les cas, vous obtiendrez un bon résultat

None

3.

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

Elle est en général indépendante de la taille de son paramètre d'entrée

C'est le temps en milli-secondes de son exécution sur un processeur Pentium

C'est l'ordre de grandeur du nombre d'opérations de base effectuées lors de l'exécution de l'algorithme en fonction de la taille de son paramètre d'entrée

C'est le nombre exact d'opérations de base effectuées lors de l'exécution de l'algorithme en fonction de la taille de son paramètre d'entrée

None

4.

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

Il existe un seul algorithme

Il existe plusieurs algorithmes, dont certains sont plus rapides à exécuter dans tous les cas

Il existe plusieurs algorithmes, dont certains sont plus rapides à exécuter en moyenne

Il existe un algorithme qui peut trier 1000 noms en moins de 10 000 opérations de comparaisons

None

5.

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

Le meilleur algorithme connu jusqu'à présent pour calculer le plus court chemin issu d'un sommet donné dans un graphe

Le meilleur algorithme connu jusqu'à présent pour calculer le plus court chemin entre 2 sommets donnés dans un graphe

Le meilleur algorithme connu jusqu'à présent pour calculer le plus court chemin entre 2 sommets quelconques dans un graphe

Un algorithme tel que 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 1s

None

6.

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

Un réseau ad hoc

Une structure de données permettant de représenter de façon compacte les éléments d'un ensemble

Un modèle de calcul de croissance des plantes

Une instruction d'un langage informatique

None

7.

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

Un ordinateur construit par Turing

Un modèle de calcul inventé par Turing

Un algorithme de décodage de messages secrets inventé par Turing pendant la guerre

Une machine de traduction automatique

None

8.

Parmi les affirmations suivantes, laquelle est fausse ?

Un problème est décidable s'il existe un algorithme qui permet de résoudre toutes les instances possibles de ce problème

Tous les énoncés mathématiques vrais sont décidables

Il existe des problèmes non décidables

Le problème de décider si une formule est prouvable dans un système formel est décidable ou semi-décidable

None

9.

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

C'est un problème complètement non polynomial

C'est un problème pour lequel on connaît un algorithme non déterministe de complexité polynomiale

C'est un problème dont la résolution polynomiale vaut un million de dollars

C'est un problème qui peut se réduire par une transformation polynomiale à un autre problème NP-complet

None

10.

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

C'est un problème indécidable

Cela sert à comparer des mots d'un texte ou des séquences génomiques

Cela peut se réduire à trouver un (plus court) chemin entre deux sommets d'un graphe

C'est une tâche informatique rarement exécutée par les biologistes

None

Vous arrivez à la fin de ce quiz. Cliquez sur le bouton ci-dessous pour afficher votre résultat et le récapitulatif des réponses.

Time's up

Niveau de lecture

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

Niveau 1

Totalement accessible (Facile)

Niveau 2

Accessible avec un léger bagage scientifique (Intermédiaire)

Niveau 3

Nécessite un bagage scientifique (Avancé)

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.

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

Données

Algorithmes

Données structurées et leur traitement

Données structurées et leur traitement

Consulter le dossier

Site piloté par

Suivez-nous

Ressources

Nos animations
Nos articles
Nos dossiers
Nos podcasts
Nos vidéos
Nos quiz

À propos

Qui sommes-nous ?
Nos auteurs
Contactez-nous

Mentions légales
Cookies
Données personnelles
Accessibilité
Plan du site

Environnement & Planète
Algorithmes
Architecture & Systèmes
Modélisation & Simulation
Histoire du numérique
Sécurité & Vie privée
Médecine & Sciences du vivant
Interaction Humain/Machine
Intelligence artificielle
Langages, programmation & logiciel
Réseaux & Communication
Traitement d’images & Son
Robotique
Culture & Société
Données

Nos animations
Nos articles
Nos dossiers
Nos podcasts
Nos vidéos
Nos quiz

Qui sommes-nous ?
Nos auteurs
Contactez-nous