Scribd
Importer
6 vues1 page

Sujet Examen Complexite Algorithmique

Le document est un examen sur la complexité algorithmique pour l'année académique 2024-2025, comprenant des questions sur la définition de la complexité temporelle, le classement des fonctions par complexité asymptotique, et des analyses de code. Il inclut également des problèmes d'algorithmique, comme l'analyse de l'algorithme de tri par insertion et la détermination de sa complexité dans différents cas. L'examen est divisé en trois parties : questions théoriques, étude de code, et problèmes pratiques.

Transféré par

Jean Bosco
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
6 vues1 page

Sujet Examen Complexite Algorithmique

Le document est un examen sur la complexité algorithmique pour l'année académique 2024-2025, comprenant des questions sur la définition de la complexité temporelle, le classement des fonctions par complexité asymptotique, et des analyses de code. Il inclut également des problèmes d'algorithmique, comme l'analyse de l'algorithme de tri par insertion et la détermination de sa complexité dans différents cas. L'examen est divisé en trois parties : questions théoriques, étude de code, et problèmes pratiques.

Transféré par

Jean Bosco
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ENSIT Année 2024-2025

Calcul de complexité
Durée : 2h 00
Aucun document autorisé – Calculatrice non autorisée

Partie A – Questions de cours (6 points)


1. (1 pt) Donnez la définition de la complexité temporelle d’un algorithme. Expliquez la différence entre les notations
O, Ω, et Θ.
2. (2 pts) Classez les fonctions suivantes de la plus petite à la plus grande complexité asymptotique (justifiez) :
- n log n, log n, n², 2ⁿ, n, n!
3. (1 pt) Quelle est la complexité moyenne de l’algorithme de recherche linéaire dans un tableau non trié contenant n
éléments ? Et dans le pire cas ?
4. (2 pts) Expliquez la différence entre complexité temporelle et complexité spatiale, avec des exemples.

Partie B – Étude de code (4 points)


Analyser la complexité du code suivant :

def mystery(n):
i=1
while i < n:
j=0
while j < i:
print(i, j)
j += 1
i *= 2

- a) Déterminez le nombre total d’itérations de la boucle interne.


- b) Donnez la complexité asymptotique en fonction de n.

Partie C – Problème d’algorithmique (10 points)


Considérez l’algorithme de tri par insertion suivant :

def insertion_sort(tab):
n = len(tab)
for i in range(1, n):
key = tab[i]
j=i-1
while j >= 0 and tab[j] > key:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = key

1. (1 pt) Expliquez brièvement le principe de fonctionnement du tri par insertion.


2. (2 pts) Comptez le nombre d’opérations (comparaisons et affectations) effectuées :
a) dans le meilleur des cas (le tableau est déjà trié)
b) dans le pire des cas (le tableau est trié dans l’ordre décroissant)
3. (2 pts) Donnez la complexité temporelle asymptotique de l’algorithme dans :
- le meilleur cas,
- le pire cas,
- et le cas moyen.
4. (1 pt) Cet algorithme est-il in-place ? Justifiez brièvement

Vous aimerez peut-être aussi