Objectif du Plan d'études romand (PER)
GYM INF 3 — Option complémentaire : informatique.
Aperçu des questions
1Si un algorithme donne toujours le bon résultat, c'est qu'il est forcément efficace (rapide).
VraiFaux
2En recherche dichotomique, chaque étape divise par deux le nombre de candidats restants. Pour trouver un nom dans une liste triée de 1024 noms, combien d'étapes faut-il au maximum ?
3Que faut-il ABSOLUMENT pour pouvoir utiliser la recherche dichotomique sur une liste ?
Que tous les éléments de la liste soient obligatoirement des nombres, et jamais du texteQue la liste entière tienne d'un seul bloc dans la mémoire vive de l'ordinateurQue la liste soit déjà triéeQue la liste contienne strictement moins de mille éléments au grand maximum
4Un algorithme compare chaque élément d'une liste à tous les autres. Pour 10 éléments cela fait environ 10 × 10 = 100 comparaisons. Pour 100 éléments, combien environ ?
5Chaque complexité reste-t-elle PRATICABLE sur de grandes données, ou devient-elle vite IMPRATICABLE ?
6Trouver le plus court trajet passant par 20 villes en testant tous les ordres possibles est infaisable, même pour un superordinateur. Pourquoi ?
Parce que les superordinateurs ne savent malheureusement pas du tout calculer des distances entre des villesParce que le nombre de trajets possibles est astronomique : des milliards de milliardsParce qu'il n'existe aucune formule mathématique connue pour mesurer une distance sur une carteParce que la mémoire de l'ordinateur ne peut pas retenir les noms de plus de dix villes à la fois
7Classe ces complexités de la plus RAPIDE à la plus LENTE (sur de grandes données).
À remettre dans le bon ordre :
Linéaire (n) : le temps suit la taille des donnéesLogarithmique (log n) : le temps monte très lentementQuadratique (n²) : le temps grimpe en flècheTemps constant : une seule opération, quoi qu'il arrive
8Certains problèmes sont impossibles à résoudre par un ordinateur, quelle que soit sa puissance, même en un temps infini.
VraiFaux
9Que signifie dire qu'un algorithme s'exécute en « temps linéaire » (complexité n) ?
Que son temps d'exécution ne dépend absolument pas de la quantité de données à traiterSi on double la taille des données, le temps de calcul double lui aussiQue l'algorithme se termine toujours en exactement une seconde, quelle que soit la situationSi on double la taille des données, le temps de calcul est aussitôt multiplié par quatre
10Face à un problème dont la solution exacte prendrait un temps déraisonnable, que peut faire un informaticien ? (plusieurs réponses)
11Un algorithme en force brute demande 2ⁿ essais. En passant de n = 10 à n = 20, par combien le nombre d'essais est-il multiplié ?
Les bonnes réponses se découvrent en jouant le Kwiiz.
