Algorithmes et Programmation 2, année 2022

TD 1

L’objectif de ce TP est de se (re)familiariser avec les fonctions en Python et avec Python globalement.

Rendre le TP

Le TD doit être rendu sur Moodle avant le début du TD suivant. En cas de TD non rendu, vous aurez automatiquement 0, sauf cas exceptionnel.

Le rendu doit être un dossier compressé au format zip contenant:

Un fichier contenant les réponses
Un fichier par exercice du TD

Chaque fonction présente dans le TD doit contenir une documentation et un nom clair.

Les TP peuvent être rendus à plusieurs et le nom des personnes doit apparaître clairement dans le fichier réponses. Il est indispensable de faire un rendu par personne pour ne pas avoir 0. Si une réponse est faite à plus que deux, vous devez l’indiquer dans le fichier réponse. Si ce n’est pas indiqué, cela sera considéré comme du plagiat.

Si vous utilisez du code sur internet, vous devez indiquer la source dans le code source et dans le fichier réponse. Si ce n’est pas indiqué, cela sera considéré comme du plagiat.

Des scripts automatiques sont exécutés pour vérifier cela pour chaque rendu, ne tentez pas la chance …

Rappels: définir une fonction

Une fonction est définie de la manière suivante:

def ma_fonction(un_argument, un_autre, une_clef="valeur par défaut"):
    """ Courte description de la fonction

    Longue longue description de la fonction, doit contenir
    plein d'information intéressante, incluant la complexité,
    le type d'algorithmes, des pointeurs vers des pages (wikipédia
    par exemple).

    Variables
    ---------
    un_argument : int
        On indique ici le type de variable attendu et une courte description
    un_autre : str
        on le fait pour chaque variable

    Retourne
    --------
    Une chaîne de caractères (str)

    Exemples
    --------
    On ajoute des exemples d'execution qui illustre comment la fonction
    marche.

    >>> ma_fonction(5, "m", une_clef=" une chouquette!")
    mmmmm une chouquete à la crème
    """
    return un_autre * un_argument + une_clef

On peut vérifier les exemples présents dans fichiers Python à l’aide du module Python doctest.

Exercice 1

Télécharger le fichier qui contient la fonction ci-dessus. Exécuter la commande python3 -m doctest ex0.py. Corrigez les erreurs.

Vous pouvez essayer la fonction depuis le terminal directement en utilisant la console interactive. Pour ce faire, il suffit de taper ipython3 dans le terminal et d’importer la fonction à l’aide de la commande from ex0 import ma_fonction.

Exercice 2

Un étudiant de L2 MIASHS un rendu un TD en oubliant de respecter les consignes! Il a très mal nommé ses fonctions et ne leur à pas mis de documentations.

Afin qu’il n’ait pas 0, renommez les fonctions et écrivez pour lui la documentation.

Exercice 3

Écrire une fonction qui retourne le nombre d’occurrence d’un caractère dans une chaîne.
Combien d’opérations nécessite cette fonction pour être exécuté par rapport la taille de la chaîne passée en argument (que l’on notera \(n\))?

Pour calculer le nombre d’opération, il faut compter le nombre de tour de boucles réalisé et le nombre d’opération que nécessite un tour de boucle. On s’intéresse principalement à la croissance de ce nombre par rapport à \(n\). Il n’est pas nécessaire d’être trop précis. Par exemple, les fonctions de l’exercice 2, ont comme nombre d’opérations:

Première et deuxième fonctions s’exécutent avec un nombre constant d’opérations
Troisième, quatrième s’exécutent avec un nombre d’opération de la forme \(an\) pour \(a\) une constante qui importe pas et \(n\) l’argument en entrée.
La cinquième fonction s’exécutent un nombre d’opération de la forme \(an\), avec \(a\) une constante qui importe pas et \(n\) la taille de la liste.

Écrire une fonction qui affiche le nombre d’occurrence de chaque voyelle (en minuscule et majuscule, accentuées ou non) dans une chaîne de caractères (indice: réutilisez la fonction précédente).
Combien d’opération nécessite cette fonction pour être exécutée par rapport la taille de la chaîne passée en argument (que l’on notera \(n\))?

Vous pouvez compter le nombre d’appel à la première fonction et multiplier par la réponse à la question 2.

(Question bonus). Proposez une autre manière d’écrire cette fonction qui nécessite au plus \(n+c\) opérations, avec \(c>0\) une constante.

On pourra utiliser une liste qui contient autant d’entier que de voyelles dans l’alphabet.

Exercice 4

Écrire un programme qui gbrouille le mot dans un texte de façon ce que le texte demeure lisible.

Par exemple le texte suivant: gDbeout ! les dmanés de la trere ! Dobeut ! les fotçars de la fiam ! La raosin tonne en son crtaère , C’ est l’éruptoin de la fin . C’est lisible, non?

Vous gbrouillerez les mots en échangéant la position de 2 lettres choisies au hasard parmi les lettres du centre du mot (c’est-à-dire ni la première ni la dernière).

Pensez à utiliser la fonction randint du module random à l’aide de l’instruction from random import randint.

Exercice 5

Écrire une fonction qui génère un mot de passe de \(n\) caractères contenant:

un caractère non-alphanumérique
un chiffre
une majuscule

Exercice 6 (Facultatif, difficile)

Une liste peut contenir des objets Python arbitraires. En particulier, une liste Python peut contenir elle même des listes. Une liste de liste récursive d’entiers et une liste dont les éléments sont soit des listes soit des entiers.

Par exemple

L = [0, [1, [2,3],[[40],[5]], [[[600]]], 7], 888]

Le problème algorithmique aplatir est définit ainsi:

aplatir
- Entrée: une liste de liste récursive d’entiers \(L\)
- Retourne: une liste d’entier contenant tous les entiers qui apparaissent \(L\) dans leur ordre d’apparition.

Par exemple, aplatir(L) retourne la liste [0, 1, 2, 3, 40, 5, 600, 7, 888]

Écrire une fonction non récursive de aplatir.
Écrire une fonction récursive de aplatir.
Donnez la complexité de chacune implémentation

Compiled the: mer. 04 sept. 2024 12:49:49 CEST