[TP06] Palindromes - Itératif - [LINFO1103] Introduction à l'algorithmique

[TP06] Palindromes - Itératif

Un palindrome est une séquence qui est indépendante du sens de lecture, c'est-à-dire une séquence qui est identique qu'elle soit lue de gauche à droite ou de droite à gauche. Par exemple, les mots radar et kayak sont des palindromes, le mot bonbon n'en est pas un.

Vous êtes chargés d'implémenter les fonctions is_palindrome_rec et is_palindrome étant donné les propriétés suivantes :

Une séquence contenant aucun caractère peut être considérée comme un palindrome.
Une séquence contenant exactement un caractère est un palindrome.
Une séquence est un palindrome si le premier et dernier caractère sont identiques, que le deuxième et avant-dernier caractère sont identiques, ...

Vous noterez que les chaînes de caractères Python (str) peuvent être vues comme des tableaux immuables. Cela signifie :

que vous pouvez utiliser les str comme des tableaux (list) mais que, comme les tuples en Python, vous ne pouvez pas modifier leur contenu
supposons que s = "hello" alors s[:2] renvoie "he", s[1] renvoie "e" et s[2:] renvoie "llo"
lorsque, comme ci-dessus, on extrait une sous-chaîne d'une chaîne s de longueur $n$ , cette extraction se réalise en réalité en recopiant les caractères concernés dans une nouvelle chaîne.
Par conséquent,
- accéder à s[:2] s'exécute en temps constant $\Theta(1)$ car on n'a qu'un nombre constant de caractères (ici les 2 premiers) à recopier, quelle que soit la longueur totale $n$ de la chaîne s.
- accéder à s[2:] s'exécute en $O(n)$ car on doit recopier $n - 2$ caractères de la chaîne s, donc tous sauf les 2 premiers.

Copia este comando en tu terminal:

La contraseña correcta es

Pregunta 1: Identification de palindromes (itératif)

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier palindrome.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def is_palindrome(s):
    """
    pre: `s` est un str
    post: détermine itérativement si `s` est un palindrome ou non
    """

return False

 
return False

Pregunta 2: Complexité temporelle

Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.

Comme d'habitude, $n$ désigne la taille du problème, c'est-à-dire dans ce cas-ci le nombre de caractères de la chaîne s.

$\Theta(n^2)$

$\Omega(\sqrt{n})$

$O(\log(n))$

$\Theta(n)$

$O(n)$

$O(n^2)$

Autor(es)	Vincent Branders, Pierre Dupont
Fecha de entrega	26/03/2025 14:00:00
Tiempo límite de envío	Sin límite de envío

Información

Inicia sesión