sujet Test 2 : preuve et complexité

Auteur :

François Brucker

Ce test vous demande de créer des fonctions de recherche de caractères dans une chaine de caractères.

Rendu

Type de rendu

Rendu sur feuille

Éléments de notation

Écriture sous la forme d'un pseudo-code correcte
Preuves :
- de finitude
- d'exactitude
Calcul de complexité

1. Présence

On considère la fonction suivante, de signature : def est_présent(chaine: str, caractère:str) -> bool.

Son code est le suivant :

def est_présent(chaine, caractère):
    return est_présent_rec(chaine, caractère, 0)


def est_présent_rec(chaine, caractère, indice):
    if indice > len(chaine) - 1:
        return False
    elif chaine[indice] == caractère:
        return True
    else:
        return est_présent_rec(chaine, caractère, indice + 1)

Est-ce un algorithme ?
Quel problème résout cette fonction ? Et pourquoi (donnez une démonstration par récurrence) ?
Quelle est sa complexité, et surtout pourquoi ?

2. Lettre dupliquée

Créer la fonction possède_caractère_dupliqué(chaine: str) -> bool qui rend :

True si la chaîne en paramètre, de longueur $n$, contient deux indices $0\leq i < j < n$ tels que $\text{chaine}[i] = \text{chaine}[j]$,
False sinon.

On vous demande également de :

Justifier l'exactitude de votre fonction
Donner (en justifiant) la complexité min et max de votre fonction

3. Bit dupliqué

On suppose que l'on applique la fonction de la question précédente à des chaines uniquement composées des caractères "0" et "1".

Quel est la complexité min et max de la fonction dans ce cas là ?