Crowdly
Додати до Chrome
Algo et complexité, L2 informatique, site de Metz
Шукаєте відповіді та рішення тестів для Algo et complexité, L2 informatique, site de Metz? Перегляньте нашу велику колекцію перевірених відповідей для Algo et complexité, L2 informatique, site de Metz в arche.univ-lorraine.fr.
Отримайте миттєвий доступ до точних відповідей та детальних пояснень для питань вашого курсу. Наша платформа, створена спільнотою, допомагає студентам досягати успіху!
Donner le nombre d'instructions exécutées par le code ci-dessous. On attend un nombre, pas une formule en N !
Donnez votre réponse sous la forme d'un nombre, sans aucun espace ou aucune ponctuation.
Exemples de réponses correctement rédigées - mais fausses 😉 - :
488017
Exemples de réponses mal rédigées :
il y a 488 instructions exécutéesentre 0 et 10>7> 7
Le code à analyser :
i ← 2j ← 3+iPour i de 3 à 5 faire
j ← 2*j
FPour
Voici un extrait d'algorithme qui porte sur l'intervalle d'entiers [a, b] :
UnSurDeux ← vrai
Tant que (a ≤ b) faire
m ← (a+b) DIV 2
Si UnSurDeux Alors
a ← m+1
Sinon
b ← m-1
FSi
UnSurDeux ← non UnSurDeux
FTQ
Sous l'hypothèse que N représente le nombre d'entiers de a à b (N = b-a+1), choisissez la formule de sa complexité en temps (pour information, il n'y a pas de cas pire que les autres).
Voici une fonction récursive qui calcule le plus grand élément d'un tableau entre les indices deb et fin (deb ≤ fin) :
fonction MaxTab (↓ T : TTableau, ↓ deb : entier, ↓ fin : entier) : entier// ...
Variable
milieu, M1, M2 : entier
Début
Si deb = fin alors
Afficher ("Coucou")retourner T [deb]
Sinon
milieu ← (deb+fin) DIV 2M1 ← MaxTab (T, deb, m)M2 ← MaxTab (T, 1+m, fin)si (M1 < M2) alors
retourner M2
Sinon
retourner M1
FSi
FSi
Fin
Si le tableau Tab = [7, 4, 5] est indicé à partir de 1
et si on appelle la fonction comme suit :
M ← MaxTab (Tab, 1, 3)
combien de fois le message "Coucou" s'affichera-t-il ?
0,9.N² - 4.N + 3 = O (N²)
Voici une procédure récursive. Ne cherchez pas à savoir ce qu'elle fait : elle ne fait rien de cohérent. Considérez qu'elle résout un problème qui porte sur un intervalle non vide [D, F] (D ≤ F) d'un tableau :
procedure P (↓ T : TTableau, ↓ D : entier, ↓ F : entier)// ...
Début
Si ... // Une ou plusieurs exceptions
...
...
Sinon // Cas général
Si T [D] > T [D+1]
P (T, D+1, F-1)
Sinon
P (T, D, F-2)
FSi
FSi
Fin
Compte tenu du cas général, sélectionnez les exceptions les plus probables.
Donner le nombre d'instructions exécutées par le code ci-dessous. On attend un nombre, pas une formule en N !
Donnez votre réponse sous la forme d'un nombre, sans aucun espace ou aucune ponctuation.
Exemples de réponses correctement rédigées - mais fausses 😉 - :
488017
Exemples de réponses refusées :
il y a 488 instructions exécutéesentre 0 et 10>7> 7
Le code à analyser :
i ← 16tant que i > 1 faire
S ← S + ii ← i DIV 2
FTQ
La taille du problème résolu par la portion de code ci-dessous est N. En appliquant les conventions du cours, choisissez la meilleure formule pour le nombre d'instructions exécutées dans le pire des cas.
Nota : les tableaux sont indicés à partir de 1.
i ← 1
S ← 0
Tant que i≤ N Faire
Si T [i] < 0 alors
S ← S + T [i]
T [i] ←T [i] * 2
FSi
i ← i + 2
FTQ
En appliquant les conventions du cours, donnez le nombre d'instructions exécutées par la portion de code ci-dessous dans le pire des cas. La taille du problème est N.
S ← 0
Pour i décroissant de N à 2 Faire
Si T [i] > 0 alors
S ← S + T [i]
Si T [i] > T [i - 1] Alors
S ← S - 1
FSi
FSi
FPour
100.N² + 4.N+3
et
1/100.N² - 4.N-3
ont le même ordre de grandeur.