Λίστα με τα μαθήματα Συνδεθείτε

Information

Author(s) Pierre Dupont
Deadline 19/08/2025 13:15:00
Submission limit No limitation

Συνδεθείτε

Συνδεθείτε

Tâche 2

On s'intéresse à la complexité temporelle de la fonction is_palindrome qui a pour objectif de déterminer si
la séquence d'éléments d'un tableau (implémenté par le type de base list en python) est un palindrome.

Pour rappel, une séquence forme un palindrome si la séquence est la même qu'on la lise de gauche à droite ou de droite à gauche.
Donc, les tableaux (par exemple, contenant des entiers) \([5, 6, 6, 5]\) et \([8, 9, 10, 9, 8]\) sont des palindromes, alors que le tableau \([1, 1, 3]\) n'en est pas un.

Le code python de cette fonction est présenté ci-dessous:

def is_palindrome(tab):
    """
    pre: 'tab' est une list (type de base de python)
    post: renvoie True si la séquence d'éléments du tableau 'tab' forment un palindrome, False sinon
    """
    if len(tab) <= 1:
        return True
    if tab[0] == tab[len(tab)-1]:
        return is_palindrome(tab[1:len(tab)-1])
    return False

Note importante : l'appel récursif dans cette implémentation prend comme argument un sous-tableau qui correspond au tableau tab, passé en paramètre, mais sans son premier et son dernier élément. Ce sous-tableau tab[1:len(tab)-1] est obtenu par l'opération de slicing en python qui produit une nouvelle list à partir d'un indice de départ et un indice de fin de la list originale.
Si \(n\) désigne la taille du tableau tab (en réalité, une list python, avec \(n=\)len(tab)) passé en paramètre, l'obtention de ce sous-tableau par cette opération de slicing a une complexité temporelle en \(\Theta(n)\). Cette propriété doit vous servir dans l'écriture correcte des équations de récurrence pour analyser la complexité temporelle globale de cet algorithme récursif.

Note 2 : bien que l'algorithme ci-dessus est correct quelque soit la taille du tableau, nous faisons l'hypothèse simplificatrice, pour toutes les sous-questions qui suivent, que \(n=\)len(tab) est pair.

Question 1: Définition du cas de base de la récurrence
Sélectionnez, parmi les réponses proposées, celle qui définit le cas de base de la récurrence de la fonction is_palindrome.

Question 2: Définition de la récurrence dans le cas général
Sélectionnez, parmi les réponses proposées, celle qui définit le cas général de la récurrence de la fonction is_palindrome.

Question 3: Profondeur maximale
Pour un problème de taille n (supposé pair), quelle sera la profondeur de récursion maximale, désignée généralement par \(i_{max}\), atteinte par la fonction is_palindrome décrite ci-dessus.

Note : cette sous-question ne peut rapporter des points que si vous avez correctement répondu aux 2 sous-questions précédentes.
Question 4: Complexité temporelle de l'algorithme
Quelle est la complexité temporelle de la fonction is_palindrome obtenue en résolvant les équations de récurrence de cette méthode ?

Note : une propriété mathématique utile pour résoudre ce système d'équations de récurrence est la suivante.
Pour tout entier \(a \ge 1\), la somme \(\sum_{j=0}^{\frac{n}{a}} a \times j\) désigne la somme des entiers de \(0\) à \(n\) par pas de \(a\). Cette somme vaut simplement \(\frac{n (n + a)}{2a}\).

Par exemple,
pour \(a = 1\), on retrouve la somme classique des entiers de \(0\) à \(n\), c'est-à-dire \(0 + 1 + \dots + (n-1) + n\) qui vaut \(\frac{n (n + 1)}{2}\).

Pour \(a = 2\), on a la somme des entiers de \(0\) à \(n\) par pas de 2, c'est-à-dire \(0 + 2 + \dots + (n-2) + n\) qui vaut \(\frac{n (n + 2)}{4}\).

Pour \(a = 3\), on a la somme des entiers de \(0\) à \(n\) par pas de 3, c'est-à-dire \(0 + 3 + \dots + (n-3) + n\) qui vaut \(\frac{n (n + 3)}{6}\).

Et ainsi de suite.

Identifiez la complexité temporelle et la notation la plus appropriée pour décrire cette complexité.

Indiquez d'abord la notation (Omega, Theta ou O) suivi de la complexité indiquée entre parenthèse, sans blanc ni espace.
  • par exemple, indiquez Omega(log(n)) pour une complexité qui serait \(\Omega(\log(n))\)
  • par exemple, indiquez O(n*log(n)) pour une complexité qui serait \(O(n\log(n))\)
  • par exemple, indiquez Theta(2^n) pour une complexité qui serait \(\Theta(2^n)\)
Note : cette sous-question ne peut rapporter des points que si vous avez correctement répondu aux 3 sous-questions précédentes.